diff options
| -rw-r--r-- | src/jcgp/JCGP.java | 3 | ||||
| -rw-r--r-- | src/jcgp/backend/modules/es/MuPlusLambda.java | 66 | ||||
| -rw-r--r-- | src/jcgp/backend/modules/problem/DigitalCircuitProblem.java | 8 | ||||
| -rw-r--r-- | src/jcgp/backend/parsers/ChromosomeParser.java | 56 | ||||
| -rw-r--r-- | src/jcgp/backend/parsers/FunctionParser.java | 37 |
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"); } |