Added lots of utility methods for initialisation and mutation; the foundation is laid down and probably works, now it's time to test it and implement the standard CGP modules.

12 files changed, 308 insertions, 67 deletions

diff --git a/src/jcgp/CGP.java b/src/jcgp/CGP.java
index e18e0ea..44c76b2 100644
--- a/src/jcgp/CGP.java
+++ b/src/jcgp/CGP.java
@@ -11,12 +11,33 @@ import jcgp.function.Addition;
 import jcgp.function.Function;
 import jcgp.function.FunctionSet;
 import jcgp.function.Subtraction;
-import jcgp.population.Population;
+import jcgp.population.*;
+
+public final class CGP {
 
-public class CGP {
-	
 	public static class Parameters {
-		private static int rows, columns, inputs, outputs, mutationRate, generations, runs, populationSize;
+		private static int rows, columns, inputs, outputs, mutationRate, generations, runs, populationSize, levelsBack;
+
+		/**
+		 * @return the number of nodes
+		 */
+		public static int getNodeNumber() {
+			return rows * columns;
+		}
+
+		/**
+		 * @return the levelsBack
+		 */
+		public static int getLevelsBack() {
+			return levelsBack;
+		}
+
+		/**
+		 * @param levelsBack the levelsBack to set
+		 */
+		private static void setLevelsBack(int levelsBack) {
+			Parameters.levelsBack = levelsBack;
+		}
 
 		/**
 		 * @return the populationSize
@@ -129,42 +150,181 @@ public class CGP {
 		private static void setRuns(int runs) {
 			Parameters.runs = runs;
 		}
-		
+
 	}
-	
+
 	public static class Utilities {
-		
+
 		public static int getRandomInt(int limit){
 			return numberGenerator.nextInt(limit);
 		}
-		
+
 		public static double getRandomDouble(int limit){
 			return numberGenerator.nextDouble() * limit;
 		}
+
+		/**
+		 * Returns a random allowed connection respecting levels back.
+		 * This method may always pick inputs, as they can be picked
+		 * regardless of the column.
+		 * 
+		 * @param chromosome the chromosome to pick from
+		 * @param column the column to use as reference
+		 * @return a random connection
+		 */
+		public static Connection getRandomConnection(Chromosome chromosome, int column){
+			// work out the allowed range obeying levels back
+			int allowedColumns = ((column >= Parameters.getLevelsBack()) ? Parameters.getLevelsBack() : column);
+			int offset = column - allowedColumns;
+
+			// choose input or node
+			int connectionType = getRandomInt(Parameters.getInputs() + (Parameters.getRows() * allowedColumns));
+			if (connectionType < Parameters.getInputs()) {
+				// input
+				return chromosome.getInput(getRandomInt(Parameters.getInputs()));
+			} else {
+				// node				
+				return chromosome.getNode(getRandomInt(Parameters.getRows()), getRandomInt(allowedColumns) + offset);
+			}
+		}
+
+		/**
+		 * Returns a random allowed connection. 
+		 * 
+		 * This method may always pick inputs, as they can be picked
+		 * regardless of the column.
+		 * 
+		 * @param chromosome the chromosome to pick from
+		 * @param column the column to use as reference
+		 * @param levelsBack whether or not to respect levels back
+		 * @return a random connection
+		 */
+		public static Connection getRandomConnection(Chromosome chromosome, int column, boolean levelsBack){
+			if (levelsBack) {
+				return getRandomConnection(chromosome, column);
+			} else {
+				// choose input or node
+				int connectionType = getRandomInt(Parameters.getInputs() + (Parameters.getRows() * column));
+				if (connectionType < Parameters.getInputs()) {
+					// input
+					return chromosome.getInput(getRandomInt(Parameters.getInputs()));
+				} else {
+					// node				
+					return chromosome.getNode(getRandomInt(Parameters.getRows()), getRandomInt(column));
+				}
+			}
+		}
+
+		/**
+		 * @param chromosome the chromosome to choose from
+		 * @return a random input
+		 */
+		public static Input getRandomInput(Chromosome chromosome){
+			return chromosome.getInput(getRandomInt(Parameters.getInputs()));
+		}
+
+		/**
+		 * Returns a random allowed node respecting levels back.
+		 * 
+		 * This method will NOT pick inputs.
+		 * 
+		 * @param chromosome the chromosome to pick from
+		 * @param column the column to use as reference
+		 * @return a random node
+		 */
+		public static Node getRandomNode(Chromosome chromosome, int column){
+			// work out the allowed range obeying levels back
+			int allowedColumns = ((column >= Parameters.getLevelsBack()) ? Parameters.getLevelsBack() : column);
+			int offset = column - allowedColumns;
+			
+			// pick a random allowed column and row
+			int randomColumn = (getRandomInt(allowedColumns) + offset);
+			int randomRow = (getRandomInt(Parameters.getRows()));
+
+			return chromosome.getNode(randomRow, randomColumn);
+		}
+
+		/**
+		 * Returns a random allowed node.
+		 * 
+		 * This method will NOT pick inputs.
+		 * 
+		 * @param chromosome the chromosome to pick from
+		 * @param column the column to use as reference
+		 * @param levelsBack whether or not to respect levels back
+		 * @return a random node
+		 */
+		public static Node getRandomNode(Chromosome chromosome, int column, boolean levelsBack){
+			if (levelsBack) {
+				return getRandomNode(chromosome, column);
+			} else {
+				// pick any random column before the given column
+				int randomColumn = (getRandomInt(column));
+				// pick a random rowgetColumns
+				int randomRow = (getRandomInt(Parameters.getRows()));
+				return chromosome.getNode(randomRow, randomColumn);
+			}
+		}
+
+		/**
+		 * This method picks a random mutable element from the given chromosome.
+		 * 
+		 * It will pick outputs or nodes fairly.
+		 * 
+		 * @param chromosome the chromosome to pick from
+		 * @return a random mutable element
+		 */
+		public static MutableElement getRandomMutable(Chromosome chromosome){
+			// choose output or node
+			int connectionType = getRandomInt(Parameters.getOutputs() + Parameters.getNodeNumber());
+			
+			if (connectionType < Parameters.getOutputs()) {
+				// outputs
+				return chromosome.getOutput(getRandomInt(Parameters.getOutputs()));
+			} else {
+				// node				
+				return chromosome.getNode(getRandomInt(Parameters.getRows()), getRandomInt(Parameters.getRows()));
+			}
+		}		
 		
+		/**
+		 * pick from any column - use this for setting outputs
+		 * 
+		 * @param chromosome
+		 * @return
+		 */
+		public static Node getRandomNode(Chromosome chromosome) {
+			return chromosome.getNode(getRandomInt(Parameters.getRows()), getRandomInt(Parameters.getColumns()));
+		}
+
 		public static Function getRandomFunction() {
 			return functionSet.getFunction(Utilities.getRandomInt(functionSet.getFunctionCount()));
 		}
-		
+
 		public static Function getFunction(int index) {
 			return functionSet.getFunction(index);
 		}
+
+		public static int getMaxArity() {
+			return maxArity;
+		}
 	}
 
 	// system-wide resources
 	private static FunctionSet functionSet;
 	private static Random numberGenerator;
-	
+	private static int maxArity = 0;
+
 	// 
 	private FitnessFunction fitnessFunction;
 	private EvolutionaryAlgorithm ea;
 	private Population population;
-	
+
 	public CGP() {
 		initialise();
-		
+
 		fitnessFunction.evaluatePopulation(population);
-		
+
 		ea.evolve(population);
 	}
 
@@ -174,7 +334,7 @@ public class CGP {
 	private void initialise() {
 		// initialise random number generator
 		numberGenerator = new Random(1234);
-		
+
 		// initialise parameters
 		Parameters.setInputs(3);
 		Parameters.setColumns(3);
@@ -184,22 +344,22 @@ public class CGP {
 		Parameters.setMutationRate(1);
 		Parameters.setRuns(5);
 		Parameters.setPopulationSize(5);
-		
+		Parameters.setLevelsBack(1);
+
 		// initialise function set
-		functionSet = new FunctionSet();
-		functionSet.setFunctions(new Addition(), new Subtraction());
-		
+		functionSet = new FunctionSet(new Addition(), new Subtraction());
+
+		// compute and set maximum arity
+		maxArity = functionSet.getMaxArity();
+
 		// initialise EA
 		ea = new StandardEA(new StandardMutator());
-		
+
 		// initialise fitness function
 		fitnessFunction = new TestFitFunction();
-		
+
 		// initialise population
-		population = new Population(Parameters.getInputs(),
-									Parameters.getRows(),
-									Parameters.getColumns(),
-									Parameters.getOutputs(),
-									Parameters.getPopulationSize());
+		population = new Population();
+
 	}
 }
diff --git a/src/jcgp/fitness/TestFitFunction.java b/src/jcgp/fitness/TestFitFunction.java
index fea9f2d..00ee833 100644
--- a/src/jcgp/fitness/TestFitFunction.java
+++ b/src/jcgp/fitness/TestFitFunction.java
@@ -9,6 +9,8 @@ public class TestFitFunction implements FitnessFunction {
 	public void evaluatePopulation(Population population) {
 		
 		for (Chromosome c : population) {
+			int i = c.getOutput(0).calculate();
+			System.out.println(i);
 			c.setFitness(1);
 		}
 	}
diff --git a/src/jcgp/function/Addition.java b/src/jcgp/function/Addition.java
index 7dc17e2..8c1e0b5 100644
--- a/src/jcgp/function/Addition.java
+++ b/src/jcgp/function/Addition.java
@@ -6,13 +6,16 @@ public class Addition extends Function {
 
 	@Override
 	public int run(Connection... connections) {
-		int sum = 0;
 		if (connections.length > 0) {
-			for (int i = 0; i < connections.length; i++) {
-				sum += connections[i].evaluate();
-			}
+			return connections[0].evaluate() + connections[1].evaluate();
+		} else {
+			return 0;
 		}
-		return sum;
+	}
+
+	@Override
+	public int getArity() {
+		return 2;
 	}
 
 }
diff --git a/src/jcgp/function/Function.java b/src/jcgp/function/Function.java
index 0f0d8a3..f2d1125 100644
--- a/src/jcgp/function/Function.java
+++ b/src/jcgp/function/Function.java
@@ -3,7 +3,9 @@ package jcgp.function;
 import jcgp.population.Connection;
 
 public abstract class Function {
-
+	
 	public abstract int run(Connection ... connections);
 	
+	public abstract int getArity();
+	
 }
diff --git a/src/jcgp/function/FunctionSet.java b/src/jcgp/function/FunctionSet.java
index e2d04a0..30e1067 100644
--- a/src/jcgp/function/FunctionSet.java
+++ b/src/jcgp/function/FunctionSet.java
@@ -6,7 +6,7 @@ import java.util.ArrayList;
 public class FunctionSet {
 		private ArrayList<Function> functionList;
 		
-		public void setFunctions(Function ... functions) {
+		public FunctionSet(Function ... functions) {
 			functionList = new ArrayList<Function>(functions.length);
 			
 			for (int i = 0; i < functions.length; i++) {
@@ -14,13 +14,6 @@ public class FunctionSet {
 			}
 		}
 		
-		public void addFunction(Function newFunction) {
-			if (functionList == null) {
-				functionList = new ArrayList<Function>();
-			}
-			functionList.add(newFunction);
-		}
-		
 		public int getFunctionCount() {
 			return functionList.size();
 		}
@@ -28,4 +21,17 @@ public class FunctionSet {
 		public Function getFunction(int index) {
 			return functionList.get(index);
 		}
+		
+		public int getMaxArity(){
+			
+			int maxArity = 0;
+			
+			for (Function function : functionList) {
+				if (function.getArity() > maxArity) {
+					maxArity = function.getArity();
+				}
+			}
+			
+			return maxArity;
+		}
 	}
\ No newline at end of file
diff --git a/src/jcgp/function/Subtraction.java b/src/jcgp/function/Subtraction.java
index 70297c3..169f88c 100644
--- a/src/jcgp/function/Subtraction.java
+++ b/src/jcgp/function/Subtraction.java
@@ -6,11 +6,16 @@ public class Subtraction extends Function {
 
 	@Override
 	public int run(Connection... connections) {
-		int subtraction = 0;
 		if (connections.length > 1) {
-			subtraction = connections[0].evaluate() - connections[1].evaluate();
+			return connections[0].evaluate() - connections[1].evaluate();
+		} else {
+			return 0;
 		}
-		return subtraction;
+	}
+
+	@Override
+	public int getArity() {
+		return 2;
 	}
 
 }
diff --git a/src/jcgp/population/Chromosome.java b/src/jcgp/population/Chromosome.java
index 2e22cf9..76667e5 100644
--- a/src/jcgp/population/Chromosome.java
+++ b/src/jcgp/population/Chromosome.java
@@ -2,16 +2,19 @@ package jcgp.population;
 
 import java.util.ArrayList;
 
+import jcgp.CGP.Utilities;
+
 public class Chromosome {
 
-	private ArrayList<Input> inputs;
-	private ArrayList<ArrayList<Node>> nodes;
-	private ArrayList<Output> outputs;
+	private final ArrayList<Input> inputs = new ArrayList<Input>();
+	private final ArrayList<ArrayList<Node>> nodes = new ArrayList<ArrayList<Node>>();;
+	private final ArrayList<Output> outputs = new ArrayList<Output>();
 	
 	private int fitness = 0;
 	
 	/**
 	 * Good citizen.
+	 * 
 	 * @param outputs 
 	 * @param columns 
 	 * @param rows 
@@ -20,13 +23,43 @@ public class Chromosome {
 	 */
 	public Chromosome(int inputCount, int rows, int columns, int outputCount) {
 		
-		inputs = new ArrayList<Input>(inputCount);
+		instantiateElements(inputCount, rows, columns, outputCount);
+		
+		initialiseConnections();
+	
+	}
+
+	private void initialiseConnections() {
+		
+		// initialise nodes
+		for (int r = 0; r < nodes.size(); r++) {
+			for (int c = 0; c < nodes.size(); c++) {
+				Connection[] connections = new Connection[Utilities.getMaxArity()];
+				for (int i = 0; i < connections.length; i++) {
+					connections[i] = Utilities.getRandomConnection(this, c);
+				}
+				nodes.get(r).get(c).initialise(Utilities.getRandomFunction(), connections);
+			}
+		}
+		
+		for (Output output : outputs) {
+			output.setConnection(Utilities.getRandomNode(this));
+		}
+		
+	}
+
+	/**
+	 * @param inputCount
+	 * @param rows
+	 * @param columns
+	 * @param outputCount
+	 */
+	private void instantiateElements(int inputCount, int rows, int columns,	int outputCount) {
 		for (int i = 0; i < inputCount; i++) {
 			inputs.add(new Input());
 		}
 		
 		// rows first
-		nodes = new ArrayList<ArrayList<Node>>(rows);
 		for (int r = 0; r < rows; r++) {
 			nodes.add(new ArrayList<Node>(columns));
 			for (int c = 0; c < columns; c++) {
@@ -34,11 +67,9 @@ public class Chromosome {
 			}
 		}
 		
-		outputs = new ArrayList<Output>(outputCount);
 		for (int o = 0; o < outputCount; o++) {
 			outputs.add(new Output());
 		}
-	
 	}
 	
 	public int getActiveNodeCount() {
@@ -48,33 +79,33 @@ public class Chromosome {
 	/**
 	 * @return the inputs
 	 */
-	public final ArrayList<Input> getInputs() {
+	public ArrayList<Input> getInputs() {
 		return inputs;
 	}
 
 	/**
 	 * @return the nodes
 	 */
-	public final ArrayList<ArrayList<Node>> getNodes() {
+	public ArrayList<ArrayList<Node>> getNodes() {
 		return nodes;
 	}
 
 	/**
 	 * @return the outputs
 	 */
-	public final ArrayList<Output> getOutputs() {
+	public ArrayList<Output> getOutputs() {
 		return outputs;
 	}
 	
-	public final Node getNode(int row, int column) {
+	public Node getNode(int row, int column) {
 		return nodes.get(row).get(column);
 	}
 	
-	public final Output getOutput(int index) {
+	public Output getOutput(int index) {
 		return outputs.get(index);
 	}
 	
-	public final Input getInputs(int index) {
+	public Input getInput(int index) {
 		return inputs.get(index);
 	}
 	
diff --git a/src/jcgp/population/InsufficientConnectionsException.java b/src/jcgp/population/InsufficientConnectionsException.java
new file mode 100644
index 0000000..807ec53
--- /dev/null
+++ b/src/jcgp/population/InsufficientConnectionsException.java
@@ -0,0 +1,10 @@
+package jcgp.population;
+
+public class InsufficientConnectionsException extends RuntimeException {
+
+	/**
+	 * 
+	 */
+	private static final long serialVersionUID = 660740514800883541L;
+
+}
diff --git a/src/jcgp/population/MutableElement.java b/src/jcgp/population/MutableElement.java
index 4397e46..5eae4ef 100644
--- a/src/jcgp/population/MutableElement.java
+++ b/src/jcgp/population/MutableElement.java
@@ -2,4 +2,6 @@ package jcgp.population;
 
 public interface MutableElement {
 	
+	public void setConnection(Connection newConnection);
+	
 }
diff --git a/src/jcgp/population/Node.java b/src/jcgp/population/Node.java
index cce8dfd..8958475 100644
--- a/src/jcgp/population/Node.java
+++ b/src/jcgp/population/Node.java
@@ -1,5 +1,6 @@
 package jcgp.population;
 
+import jcgp.CGP.Utilities;
 import jcgp.function.Function;
 
 
@@ -8,21 +9,28 @@ public class Node implements MutableElement, Connection {
 	private Function function;
 	private Connection[] connections;
 
-	public Node() {
-		
-	}
-	
 	@Override
 	public int evaluate() {
-		return function.run(connections[0], connections[1]);
+		return function.run(connections);
 	}
 	
 	public void setFunction(Function newFunction) {
 		function = newFunction;
 	}
 	
+	@Override
 	public void setConnection(Connection newConnection) {
+		connections[Utilities.getRandomInt(connections.length)] = newConnection;
+	}
+	
+	public void initialise(Function newFunction, Connection ... newConnections) throws InsufficientConnectionsException {
+		
+		function = newFunction;
 		
+		if (newConnections.length >= Utilities.getMaxArity()) {
+			connections = newConnections;
+		} else {
+			throw new InsufficientConnectionsException();
+		}
 	}
-
 }
diff --git a/src/jcgp/population/Output.java b/src/jcgp/population/Output.java
index 2f2df6e..1640deb 100644
--- a/src/jcgp/population/Output.java
+++ b/src/jcgp/population/Output.java
@@ -2,10 +2,17 @@ package jcgp.population;
 
 
 public class Output implements MutableElement {
+	
+	private Connection source;
 
 	public int calculate() {
-		// TODO Auto-generated method stub
-		return 0;
+		return source.evaluate();
+	}
+
+	@Override
+	public void setConnection(Connection newConnection) {
+		source = newConnection;
+		
 	}
 
 }
diff --git a/src/jcgp/population/Population.java b/src/jcgp/population/Population.java
index e1a9a3c..67b6695 100644
--- a/src/jcgp/population/Population.java
+++ b/src/jcgp/population/Population.java
@@ -3,14 +3,19 @@ package jcgp.population;
 import java.util.ArrayList;
 import java.util.Iterator;
 
+import jcgp.CGP.Parameters;
+
 public final class Population implements Iterable<Chromosome> {
 	
 	private ArrayList<Chromosome> population;
 	
-	public Population(int inputs, int rows, int columns, int outputs, int size) {
-		population = new ArrayList<Chromosome>(size);
-		for (int c = 0; c < size; c++) {
-			population.add(new Chromosome(inputs, rows, columns, outputs));
+	public Population() {
+		population = new ArrayList<Chromosome>(Parameters.getPopulationSize());
+		for (int c = 0; c < Parameters.getPopulationSize(); c++) {
+			population.add(new Chromosome(Parameters.getInputs(),
+										  Parameters.getRows(),
+										  Parameters.getColumns(),
+										  Parameters.getOutputs()));
 		}
 	}