Fixed digital problem with more than one test case, improved mu+lambda to be more like CGP

4 files changed, 138 insertions, 29 deletions

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");
 	}