From 2343cc0e456e0306711c0a7218d3027f17cffee7 Mon Sep 17 00:00:00 2001 From: Eduardo Pedroni Date: Fri, 31 Jan 2014 16:45:45 +0000 Subject: 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. --- src/jcgp/CGP.java | 210 ++++++++++++++++++--- src/jcgp/fitness/TestFitFunction.java | 2 + src/jcgp/function/Addition.java | 13 +- src/jcgp/function/Function.java | 4 +- src/jcgp/function/FunctionSet.java | 22 ++- src/jcgp/function/Subtraction.java | 11 +- src/jcgp/population/Chromosome.java | 57 ++++-- .../InsufficientConnectionsException.java | 10 + src/jcgp/population/MutableElement.java | 2 + src/jcgp/population/Node.java | 20 +- src/jcgp/population/Output.java | 11 +- src/jcgp/population/Population.java | 13 +- 12 files changed, 308 insertions(+), 67 deletions(-) create mode 100644 src/jcgp/population/InsufficientConnectionsException.java (limited to 'src') 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 functionList; - public void setFunctions(Function ... functions) { + public FunctionSet(Function ... functions) { functionList = new ArrayList(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(); - } - 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 inputs; - private ArrayList> nodes; - private ArrayList outputs; + private final ArrayList inputs = new ArrayList(); + private final ArrayList> nodes = new ArrayList>();; + private final ArrayList outputs = new ArrayList(); 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(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>(rows); for (int r = 0; r < rows; r++) { nodes.add(new ArrayList(columns)); for (int c = 0; c < columns; c++) { @@ -34,11 +67,9 @@ public class Chromosome { } } - outputs = new ArrayList(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 getInputs() { + public ArrayList getInputs() { return inputs; } /** * @return the nodes */ - public final ArrayList> getNodes() { + public ArrayList> getNodes() { return nodes; } /** * @return the outputs */ - public final ArrayList getOutputs() { + public ArrayList 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 { private ArrayList population; - public Population(int inputs, int rows, int columns, int outputs, int size) { - population = new ArrayList(size); - for (int c = 0; c < size; c++) { - population.add(new Chromosome(inputs, rows, columns, outputs)); + public Population() { + population = new ArrayList(Parameters.getPopulationSize()); + for (int c = 0; c < Parameters.getPopulationSize(); c++) { + population.add(new Chromosome(Parameters.getInputs(), + Parameters.getRows(), + Parameters.getColumns(), + Parameters.getOutputs())); } } -- cgit v1.2.3