aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorEduardo Pedroni <ep625@york.ac.uk>2014-05-10 10:30:20 +0100
committerEduardo Pedroni <ep625@york.ac.uk>2014-05-10 10:30:20 +0100
commit7a54a44b01f1b4ac5b39dc5d7a9d4e62d066982b (patch)
tree6cc39a323ca981bea7b5094acb724db6fd38f1b6 /src
parent1e5e8b97a80e7ea50bcfafa4c2eee9c541f1b35f (diff)
Fixed digital problem with more than one test case, improved mu+lambda to be more like CGP
Diffstat (limited to 'src')
-rw-r--r--src/jcgp/JCGP.java3
-rw-r--r--src/jcgp/backend/modules/es/MuPlusLambda.java66
-rw-r--r--src/jcgp/backend/modules/problem/DigitalCircuitProblem.java8
-rw-r--r--src/jcgp/backend/parsers/ChromosomeParser.java56
-rw-r--r--src/jcgp/backend/parsers/FunctionParser.java37
5 files changed, 141 insertions, 29 deletions
diff --git a/src/jcgp/JCGP.java b/src/jcgp/JCGP.java
index f60fc22..5a86303 100644
--- a/src/jcgp/JCGP.java
+++ b/src/jcgp/JCGP.java
@@ -247,6 +247,9 @@ public class JCGP {
// solution has been found, start next run
resources.println("[CGP] Solution found: generation " + resources.currentGeneration() + ", chromosome " + perfect + "\n");
+ resources.println("[CGP] Printing chromosome...");
+ ChromosomeParser.print(population.get(perfect), resources);
+ resources.println("[CGP] Printing done. ");
if (resources.currentRun() < resources.runs()) {
// there are still runs left
diff --git a/src/jcgp/backend/modules/es/MuPlusLambda.java b/src/jcgp/backend/modules/es/MuPlusLambda.java
index 3743ee6..6a6870f 100644
--- a/src/jcgp/backend/modules/es/MuPlusLambda.java
+++ b/src/jcgp/backend/modules/es/MuPlusLambda.java
@@ -77,21 +77,77 @@ public class MuPlusLambda extends EvolutionaryStrategy {
@Override
public void evolve(Population population, Mutator mutator) {
- // sort the population in order of best fitness
- population.sort();
+ // sort the population neutrally
+ sort(population);
- // population is now sorted in ascending order of fitness, the last chromosomes are the fittest
+ // population is now sorted such that the new parents are in the last mu positions
for (int i = 0; i < getResources().populationSize() - mu.get(); i++) {
- // select a random parent out of the lambda offspring individuals
+ // select a random parent out of the mu population parents
int randomParent = getResources().populationSize() - 1 - getResources().getRandomInt(mu.get());
if (report.get()) getResources().reportln("[ES] Copying Chr " + randomParent + " to population position " + i);
+
+ // copy it into the offspring position
population.copyChromosome(randomParent, i);
- // mutate selected chromosome
+ // mutate the new offspring chromosome
if (report.get()) getResources().reportln("[ES] Mutating copied chromosome");
mutator.mutate(population.get(i));
}
if (report.get()) getResources().reportln("[ES] Generation is complete");
}
+
+ /**
+ * Neutrally sorts the specified population.
+ * <br><br>
+ * Optimised sorting methods tend to be stable, meaning
+ * the order of elements which are already ordered is not
+ * changed. While performing faster, such sorting algorithms
+ * do not promote neutral drift, an important aspect of CGP.
+ * <br><br>
+ * This sort iterates through the population offspring (first lambda
+ * elements) and compares each with each of the parents (last mu
+ * elements), overwriting the parent if the offspring's fitness
+ * is greater than or equal to the parent's.
+ * It is biased towards offspring: parents are replaced with
+ * equally fit offspring as often as possible.
+ *
+ * @param population the population to sort.
+ */
+ private void sort(Population population) {
+ /* Create an array with the index of each of the current parents.
+ * This is done to speed up the sort. No deep chromosome copies are
+ * made until the algorithm is finished; instead, only indices are copied.
+ */
+ int[] parents = new int[mu.get()];
+ for (int i = 0; i < parents.length; i++) {
+ parents[i] = lambda.get() + i;
+ }
+
+ // cycle through the offspring, i.e. the first lambda elements of the population
+ for (int o = 0; o < getResources().populationSize() - mu.get(); o++) {
+ // compare each offspring with each parent, as stored in parents
+ for (int p = 0; p < parents.length; p++) {
+ /* replace parent if the offspring fitness and greater than or equal to its own
+ * if it is equal to, only replace if it is an old parent, if it is greater than,
+ * replace regardless
+ */
+ if ((population.get(o).getFitness() == population.get(parents[p]).getFitness() && parents[p] >= lambda.get())
+ || population.get(o).getFitness() >= population.get(parents[p]).getFitness()) {
+ parents[p] = o;
+ // offspring has been selected, check the next one
+ break;
+ }
+ }
+ }
+
+ /* selection is complete, parents now contains the indices of each selected offspring
+ * time to perform the deep copies
+ */
+ for (int c = 0; c < parents.length; c++) {
+ // copy each selected index in parent to each parent position in the population
+ population.copyChromosome(parents[c], lambda.get() + c);
+ }
+
+ }
}
diff --git a/src/jcgp/backend/modules/problem/DigitalCircuitProblem.java b/src/jcgp/backend/modules/problem/DigitalCircuitProblem.java
index b615675..e2f17c3 100644
--- a/src/jcgp/backend/modules/problem/DigitalCircuitProblem.java
+++ b/src/jcgp/backend/modules/problem/DigitalCircuitProblem.java
@@ -45,13 +45,17 @@ public class DigitalCircuitProblem extends TestCaseProblem<UnsignedInteger> {
Integer output = ((UnsignedInteger) population.get(i).getOutput(o).calculate()).get();
Integer matches = ~(output ^ testCases.get(t).getOutput(o).get());
// check only the relevant bits
- int bits = (int) Math.pow(2.0, (double) resources.inputs());
+ int bits;
+ if (resources.inputs() < 5) {
+ bits = (int) Math.pow(2.0, (double) resources.inputs());
+ } else {
+ bits = 32;
+ }
for (int b = 0; b < bits; b++) {
fitness += (matches >>> b) & 1;
}
}
}
-
// assign the resulting fitness to the respective individual
population.get(i).setFitness(fitness);
}
diff --git a/src/jcgp/backend/parsers/ChromosomeParser.java b/src/jcgp/backend/parsers/ChromosomeParser.java
index 838ec48..6106dbd 100644
--- a/src/jcgp/backend/parsers/ChromosomeParser.java
+++ b/src/jcgp/backend/parsers/ChromosomeParser.java
@@ -29,9 +29,9 @@ public abstract class ChromosomeParser {
* is not viable to implement these defensive measures with the chromosome format used
* by CGP.
*
- * @param file the .chr file to parse from
- * @param chromosome the chromosome to configure
- * @param resources the experiment resources
+ * @param file the .chr file to parse from.
+ * @param chromosome the chromosome to configure.
+ * @param resources the experiment resources.
*/
public static void parse(File file, Chromosome chromosome, Resources resources) {
/*
@@ -134,8 +134,8 @@ public abstract class ChromosomeParser {
* The file is written in the standard .chr format and can
* be read by the original CGP implementation.
*
- * @param file the file to write to
- * @param chromosome the chromosome to save
+ * @param file the file to write to.
+ * @param chromosome the chromosome to save.
* @param resources a reference to the experiment's resources.
*/
public static void save(File file, Chromosome chromosome, Resources resources) {
@@ -187,4 +187,50 @@ public abstract class ChromosomeParser {
resources.println("[Parser] Chromosome saved successfully");
}
+
+ /**
+ * Writes a chromosome to the console in .chr format. Note
+ * that, if using a GUI console, that console must be flushed for the
+ * output to appear.
+ *
+ * @param chromosome the chromosome to save.
+ * @param resources a reference to the experiment's resources.
+ */
+ public static void print(Chromosome chromosome, Resources resources) {
+
+ // for all nodes, columns first
+ for (int c = 0; c < resources.columns(); c++) {
+ for (int r = 0; r < resources.rows(); r++) {
+ for (int i = 0; i < resources.arity(); i++) {
+ // print the connections, separated by spaces
+ Connection conn = chromosome.getNode(r, c).getConnection(i);
+ if (conn instanceof Input) {
+ resources.print(" " + ((Input) conn).getIndex());
+ } else if (conn instanceof Node) {
+ resources.print(" " + (((((Node) conn).getColumn() + 1) * resources.inputs()) + ((Node) conn).getRow()));
+ } else {
+ resources.println("[Parser] Error: could not handle " + conn.getClass() + " as a subclass of Connection");
+ }
+ }
+ // print the function numbers
+ resources.print(" " + resources.getFunctionIndex(chromosome.getNode(r, c).getFunction()));
+ // node is done, print tab
+ resources.print("\t");
+ }
+ }
+ // nodes are done, print two tabs to separate from output
+ resources.print("\t\t");
+ for (int o = 0; o < resources.outputs(); o ++) {
+ Connection source = chromosome.getOutput(o).getSource();
+ if (source instanceof Input) {
+ resources.print(" " + ((Input) source).getIndex());
+ } else if (source instanceof Node) {
+ resources.print(" " + (((((Node) source).getColumn() + 1) * resources.inputs()) + ((Node) source).getRow()));
+ } else {
+ resources.println("[Parser] Error: could not handle " + source.getClass() + " as a subclass of Connection");
+ }
+ }
+
+ resources.println("");
+ }
}
diff --git a/src/jcgp/backend/parsers/FunctionParser.java b/src/jcgp/backend/parsers/FunctionParser.java
index 806099e..081c08a 100644
--- a/src/jcgp/backend/parsers/FunctionParser.java
+++ b/src/jcgp/backend/parsers/FunctionParser.java
@@ -42,11 +42,11 @@ public abstract class FunctionParser {
resources.println("[Parser] Error: could not find " + file.getAbsolutePath());
return;
}
-
+
Scanner in = new Scanner(fr);
boolean excessFunctions = false;
resources.println("[Parser] Parsing file: " + file.getAbsolutePath() + "...");
-
+
/*
* The encoding used in .par files is quite simple, so regex matches are used to extract
* the values.
@@ -71,29 +71,32 @@ public abstract class FunctionParser {
*/
while (in.hasNextLine()) {
String line = in.nextLine();
- if (line.substring(line.length() - 1).matches("[0-9]")) {
- String[] splitString = line.split("[^0-9]+");
- int functionIndex = Integer.parseInt(splitString[splitString.length - 1]);
-
- if (functionIndex < functionSet.getTotalFunctionCount()) {
- if (Integer.parseInt(splitString[0]) != 0) {
- functionSet.enableFunction(functionIndex);
- resources.println("[Parser] Enabled function: " + functionSet.getFunction(functionIndex));
- } else if (Integer.parseInt(splitString[0]) == 0) {
- functionSet.disableFunction(functionIndex);
- resources.println("[Parser] Disabled function: " + functionSet.getFunction(functionIndex));
+ if (!line.isEmpty()) {
+ if (line.substring(line.length() - 1).matches("[0-9]")) {
+ String[] splitString = line.split("[^0-9]+");
+ int functionIndex = Integer.parseInt(splitString[splitString.length - 1]);
+
+ if (functionIndex < functionSet.getTotalFunctionCount()) {
+ if (Integer.parseInt(splitString[0]) != 0) {
+ functionSet.enableFunction(functionIndex);
+ resources.println("[Parser] Enabled function: " + functionSet.getFunction(functionIndex));
+ } else if (Integer.parseInt(splitString[0]) == 0) {
+ functionSet.disableFunction(functionIndex);
+ resources.println("[Parser] Disabled function: " + functionSet.getFunction(functionIndex));
+ }
+ } else {
+ excessFunctions = true;
}
- } else {
- excessFunctions = true;
}
}
+
}
-
+
// warn the user function index went out of bounds
if (excessFunctions) {
resources.println("[Parser] Warning: the parameter file contained more functions than the current function set");
}
-
+
in.close();
resources.println("[Parser] Finished parsing functions");
}