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. --- README | 4 +- 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 +- 13 files changed, 311 insertions(+), 68 deletions(-) create mode 100644 src/jcgp/population/InsufficientConnectionsException.java diff --git a/README b/README index dee17fe..52c2ef9 100644 --- a/README +++ b/README @@ -31,6 +31,8 @@ Added static nested classes for system-wide resources such as a random number ge and the parameter set. These can be accessed from anywhere within the program, but not modified by any class but CGP. +Utilities class has lots of handy methods for getting random elements with fair probability. + Modularized design: Modules for fitness function, mutation operator, evolutionary algorithm and population. @@ -43,6 +45,6 @@ so long as it extends Chromosome. In conjunction with modularized FF, EA and mut flexible and versatile system. The Population class itself is immutable, since the system relies heavily on it. Finally, it is Iterable to for access to the chromosomes within. - +Arity may vary across functions, but all nodes contain enough connections to cope with the largest arity. \ No newline at end of file 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