From 1fd678821cf133c7c431daea687f3467bb0be2dd Mon Sep 17 00:00:00 2001 From: Eduardo Pedroni Date: Tue, 4 Feb 2014 16:20:33 +0000 Subject: Added fitness evaluation mechanism, though it might not be a very good design. Tests will be done to verify that. --- README | 13 +++++ src/jcgp/CGP.java | 73 ++++++++++++++++++------ src/jcgp/ea/EvolutionaryAlgorithm.java | 14 ++--- src/jcgp/ea/StandardEA.java | 11 ++-- src/jcgp/ea/StandardMutator.java | 22 ++++++- src/jcgp/fitness/FitnessEvaluator.java | 17 ------ src/jcgp/fitness/FitnessFunction.java | 4 +- src/jcgp/fitness/ParameterMismatchException.java | 10 ++++ src/jcgp/fitness/TestCase.java | 41 +++++++++++++ src/jcgp/fitness/TestFitFunction.java | 17 ------ src/jcgp/fitness/TruthTableEvaluator.java | 26 +++++++++ src/jcgp/population/Chromosome.java | 4 +- src/jcgp/population/MutableElement.java | 2 + src/jcgp/population/Node.java | 14 ++++- src/jcgp/population/Output.java | 7 +++ src/jcgp/population/Population.java | 2 + 16 files changed, 205 insertions(+), 72 deletions(-) delete mode 100644 src/jcgp/fitness/FitnessEvaluator.java create mode 100644 src/jcgp/fitness/ParameterMismatchException.java create mode 100644 src/jcgp/fitness/TestCase.java delete mode 100644 src/jcgp/fitness/TestFitFunction.java create mode 100644 src/jcgp/fitness/TruthTableEvaluator.java diff --git a/README b/README index 0b886c9..3241aae 100644 --- a/README +++ b/README @@ -66,3 +66,16 @@ sets the chromosome inputs and compares outputs for all TestCase objects given, accordingly. +4/2 + +TestCase has been implemented with a fair degree of defensiveness. A TruthTable class contains the test cases and provides +a way to evaluate fitness. + +TruthTable is a system-wide resource, which may or may not be used by FitnessFunction to assign fitness values to the +population; that is up to the user. + +A standard fitness function which uses TruthTable is defined in TruthTableEvaluator. + +StandardMutator has been implemented, though it looks like it may need refactoring in the future. + + diff --git a/src/jcgp/CGP.java b/src/jcgp/CGP.java index 44c76b2..26d1d2b 100644 --- a/src/jcgp/CGP.java +++ b/src/jcgp/CGP.java @@ -3,20 +3,27 @@ package jcgp; import java.util.Random; import jcgp.ea.EvolutionaryAlgorithm; +import jcgp.ea.Mutator; import jcgp.ea.StandardEA; import jcgp.ea.StandardMutator; import jcgp.fitness.FitnessFunction; -import jcgp.fitness.TestFitFunction; +import jcgp.fitness.TestCase; +import jcgp.fitness.TruthTableEvaluator; import jcgp.function.Addition; import jcgp.function.Function; import jcgp.function.FunctionSet; import jcgp.function.Subtraction; -import jcgp.population.*; +import jcgp.population.Chromosome; +import jcgp.population.Connection; +import jcgp.population.Input; +import jcgp.population.MutableElement; +import jcgp.population.Node; +import jcgp.population.Population; public final class CGP { public static class Parameters { - private static int rows, columns, inputs, outputs, mutationRate, generations, runs, populationSize, levelsBack; + private static int rows, columns, inputs, outputs, mutationRate, generations, runs, populationSize, levelsBack, maxArity; /** * @return the number of nodes @@ -151,9 +158,25 @@ public final class CGP { Parameters.runs = runs; } + /** + * @return the maxArity + */ + public static int getMaxArity() { + return maxArity; + } + + /** + * @param maxArity the maxArity to set + */ + private static void setMaxArity(int maxArity) { + Parameters.maxArity = maxArity; + } + + + } - public static class Utilities { + public abstract static class Utilities { public static int getRandomInt(int limit){ return numberGenerator.nextInt(limit); @@ -304,28 +327,42 @@ public final class CGP { public static Function getFunction(int index) { return functionSet.getFunction(index); } + } - public static int getMaxArity() { - return maxArity; + public static class TruthTable { + + private static TestCase[] testCases; + + private static void setTestCases(TestCase ... testCases) { + TruthTable.testCases = testCases; } + + public static TestCase getTestCase(int index) { + return testCases[index]; + } + + public static int getTestCaseCount() { + return testCases.length; + } + } - + // system-wide resources private static FunctionSet functionSet; private static Random numberGenerator; - private static int maxArity = 0; - // - private FitnessFunction fitnessFunction; + // CGP components private EvolutionaryAlgorithm ea; + private Mutator mutator; private Population population; + private FitnessFunction fitnessFunction; public CGP() { initialise(); - fitnessFunction.evaluatePopulation(population); + fitnessFunction.evaluate(population); - ea.evolve(population); + ea.evolve(population, mutator); } /** @@ -350,14 +387,16 @@ public final class CGP { functionSet = new FunctionSet(new Addition(), new Subtraction()); // compute and set maximum arity - maxArity = functionSet.getMaxArity(); + Parameters.setMaxArity(functionSet.getMaxArity()); // initialise EA - ea = new StandardEA(new StandardMutator()); - - // initialise fitness function - fitnessFunction = new TestFitFunction(); + ea = new StandardEA(); + mutator = new StandardMutator(); + // initialise fitness function and truth table + TruthTable.setTestCases(new TestCase(new int[] {2, 5, 4}, new int[] {1, 10, 15})); + fitnessFunction = new TruthTableEvaluator(); + // initialise population population = new Population(); diff --git a/src/jcgp/ea/EvolutionaryAlgorithm.java b/src/jcgp/ea/EvolutionaryAlgorithm.java index 6e264aa..9e72a1b 100644 --- a/src/jcgp/ea/EvolutionaryAlgorithm.java +++ b/src/jcgp/ea/EvolutionaryAlgorithm.java @@ -2,14 +2,14 @@ package jcgp.ea; import jcgp.population.Population; -public abstract class EvolutionaryAlgorithm { +public interface EvolutionaryAlgorithm { - protected Mutator mutator; +// protected Mutator mutator; +// +// public EvolutionaryAlgorithm(Mutator mutator) { +// this.mutator = mutator; +// } - public EvolutionaryAlgorithm(Mutator mutator) { - this.mutator = mutator; - } - - public abstract void evolve(Population population); + public abstract void evolve(Population population, Mutator mutator); } diff --git a/src/jcgp/ea/StandardEA.java b/src/jcgp/ea/StandardEA.java index fe0b3f9..b98fe9e 100644 --- a/src/jcgp/ea/StandardEA.java +++ b/src/jcgp/ea/StandardEA.java @@ -3,15 +3,12 @@ package jcgp.ea; import jcgp.population.Chromosome; import jcgp.population.Population; -public class StandardEA extends EvolutionaryAlgorithm { - - public StandardEA(Mutator mutator) { - super(mutator); - - } +public class StandardEA implements EvolutionaryAlgorithm { @Override - public void evolve(Population population) { + public void evolve(Population population, Mutator mutator) { + + for (Chromosome chromosome : population) { mutator.mutate(chromosome); } diff --git a/src/jcgp/ea/StandardMutator.java b/src/jcgp/ea/StandardMutator.java index 731215d..cab5c76 100644 --- a/src/jcgp/ea/StandardMutator.java +++ b/src/jcgp/ea/StandardMutator.java @@ -1,13 +1,31 @@ package jcgp.ea; +import jcgp.CGP.Parameters; +import jcgp.CGP.Utilities; import jcgp.population.Chromosome; +import jcgp.population.MutableElement; +import jcgp.population.Node; +import jcgp.population.Output; public class StandardMutator implements Mutator { @Override public void mutate(Chromosome chromosome) { + int mutations = (int) (Parameters.getMutationRate() * ((double) Parameters.getNodeNumber() / 100)); - + for (int i = 0; i < mutations; i++) { + MutableElement m = Utilities.getRandomMutable(chromosome); + + if (m instanceof Output) { + m.setConnection(Utilities.getRandomConnection(chromosome, m.getColumn())); + } else if (m instanceof Node) { + int geneType = Utilities.getRandomInt(1 + Parameters.getMaxArity()); + if (geneType < 1) { + ((Node) m).setFunction(Utilities.getRandomFunction()); + } else { + m.setConnection(Utilities.getRandomConnection(chromosome, m.getColumn())); + } + } + } } - } diff --git a/src/jcgp/fitness/FitnessEvaluator.java b/src/jcgp/fitness/FitnessEvaluator.java deleted file mode 100644 index 5ecf679..0000000 --- a/src/jcgp/fitness/FitnessEvaluator.java +++ /dev/null @@ -1,17 +0,0 @@ -package jcgp.fitness; - -import jcgp.population.Population; - -public class FitnessEvaluator { - - private FitnessFunction fitnessFunction; - - public FitnessEvaluator(FitnessFunction fitnessFunction) { - this.fitnessFunction = fitnessFunction; - } - - public void evaluateFitness(Population population) { - - } - -} diff --git a/src/jcgp/fitness/FitnessFunction.java b/src/jcgp/fitness/FitnessFunction.java index 2155542..6fa63ef 100644 --- a/src/jcgp/fitness/FitnessFunction.java +++ b/src/jcgp/fitness/FitnessFunction.java @@ -3,7 +3,7 @@ package jcgp.fitness; import jcgp.population.Population; public interface FitnessFunction { - - public void evaluatePopulation(Population population); + + public void evaluate(Population population); } diff --git a/src/jcgp/fitness/ParameterMismatchException.java b/src/jcgp/fitness/ParameterMismatchException.java new file mode 100644 index 0000000..0ca69a7 --- /dev/null +++ b/src/jcgp/fitness/ParameterMismatchException.java @@ -0,0 +1,10 @@ +package jcgp.fitness; + +public class ParameterMismatchException extends RuntimeException { + + /** + * + */ + private static final long serialVersionUID = -3161318886125868134L; + +} diff --git a/src/jcgp/fitness/TestCase.java b/src/jcgp/fitness/TestCase.java new file mode 100644 index 0000000..e2bd5ed --- /dev/null +++ b/src/jcgp/fitness/TestCase.java @@ -0,0 +1,41 @@ +package jcgp.fitness; + +import jcgp.CGP.Parameters; + +public class TestCase { + + private int[] inputs; + private int[] outputs; + + public TestCase(int[] inputs, int[] outputs) throws ParameterMismatchException { + if (inputs.length == Parameters.getInputs()) { + this.inputs = inputs; + } else { + throw new ParameterMismatchException(); + } + + if (outputs.length == Parameters.getOutputs()) { + this.outputs = outputs; + } else { + throw new ParameterMismatchException(); + } + + } + + public int getInput(int index) { + return inputs[index]; + } + + public int getOutput(int index) { + return outputs[index]; + } + + public int[] getInputs() { + return inputs; + } + + public int[] getOutputs() { + return outputs; + } + +} diff --git a/src/jcgp/fitness/TestFitFunction.java b/src/jcgp/fitness/TestFitFunction.java deleted file mode 100644 index 00ee833..0000000 --- a/src/jcgp/fitness/TestFitFunction.java +++ /dev/null @@ -1,17 +0,0 @@ -package jcgp.fitness; - -import jcgp.population.Chromosome; -import jcgp.population.Population; - -public class TestFitFunction implements FitnessFunction { - - @Override - 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/fitness/TruthTableEvaluator.java b/src/jcgp/fitness/TruthTableEvaluator.java new file mode 100644 index 0000000..64ca209 --- /dev/null +++ b/src/jcgp/fitness/TruthTableEvaluator.java @@ -0,0 +1,26 @@ +package jcgp.fitness; + +import jcgp.CGP.Parameters; +import jcgp.CGP.TruthTable; +import jcgp.population.Chromosome; +import jcgp.population.Population; + +public class TruthTableEvaluator implements FitnessFunction { + + @Override + public void evaluate(Population population) { + for (Chromosome chromosome : population) { + for (int t = 0; t < TruthTable.getTestCaseCount(); t++) { + chromosome.setInputs(TruthTable.getTestCase(t).getInputs()); + int fitness = 0; + for (int o = 0; o < Parameters.getOutputs(); o++) { + if (chromosome.getOutput(o).calculate() == TruthTable.getTestCase(t).getOutput(o)) { + fitness++; + } + } + chromosome.setFitness(fitness); + } + } + } + +} diff --git a/src/jcgp/population/Chromosome.java b/src/jcgp/population/Chromosome.java index 70e8836..f060e14 100644 --- a/src/jcgp/population/Chromosome.java +++ b/src/jcgp/population/Chromosome.java @@ -45,7 +45,7 @@ public class Chromosome { for (int r = 0; r < rows; r++) { //nodes[r] = new Node[Parameters.getColumns()]; for (int c = 0; c < columns; c++) { - nodes[r][c] = new Node(); + nodes[r][c] = new Node(c); } } outputs = new Output[outputCount]; @@ -59,7 +59,7 @@ public class Chromosome { // initialise nodes - [rows][columns] for (int r = 0; r < nodes.length; r++) { for (int c = 0; c < nodes.length; c++) { - Connection[] connections = new Connection[Utilities.getMaxArity()]; + Connection[] connections = new Connection[Parameters.getMaxArity()]; for (int i = 0; i < connections.length; i++) { connections[i] = Utilities.getRandomConnection(this, c); } diff --git a/src/jcgp/population/MutableElement.java b/src/jcgp/population/MutableElement.java index 5eae4ef..8ac3724 100644 --- a/src/jcgp/population/MutableElement.java +++ b/src/jcgp/population/MutableElement.java @@ -4,4 +4,6 @@ public interface MutableElement { public void setConnection(Connection newConnection); + public int getColumn(); + } diff --git a/src/jcgp/population/Node.java b/src/jcgp/population/Node.java index 8958475..fd0cd47 100644 --- a/src/jcgp/population/Node.java +++ b/src/jcgp/population/Node.java @@ -1,5 +1,6 @@ package jcgp.population; +import jcgp.CGP.Parameters; import jcgp.CGP.Utilities; import jcgp.function.Function; @@ -8,7 +9,12 @@ public class Node implements MutableElement, Connection { private Function function; private Connection[] connections; + private int column; + public Node(int col) { + column = col; + } + @Override public int evaluate() { return function.run(connections); @@ -27,10 +33,16 @@ public class Node implements MutableElement, Connection { function = newFunction; - if (newConnections.length >= Utilities.getMaxArity()) { + if (newConnections.length >= Parameters.getMaxArity()) { connections = newConnections; } else { throw new InsufficientConnectionsException(); } } + + @Override + public int getColumn() { + + return column; + } } diff --git a/src/jcgp/population/Output.java b/src/jcgp/population/Output.java index 1640deb..eeae743 100644 --- a/src/jcgp/population/Output.java +++ b/src/jcgp/population/Output.java @@ -1,5 +1,7 @@ package jcgp.population; +import jcgp.CGP.Parameters; + public class Output implements MutableElement { @@ -15,4 +17,9 @@ public class Output implements MutableElement { } + @Override + public int getColumn() { + return Parameters.getColumns(); + } + } diff --git a/src/jcgp/population/Population.java b/src/jcgp/population/Population.java index 55f756a..e171a2f 100644 --- a/src/jcgp/population/Population.java +++ b/src/jcgp/population/Population.java @@ -43,6 +43,8 @@ public class Population implements Iterable { @Override public void remove() { // not allowed + // since this would shift everything back one position, increment index + index++; } }; -- cgit v1.2.3