diff options
Diffstat (limited to 'src/jcgp/backend/modules/problem')
5 files changed, 93 insertions, 132 deletions
diff --git a/src/jcgp/backend/modules/problem/DigitalCircuitProblem.java b/src/jcgp/backend/modules/problem/DigitalCircuitProblem.java index 6654928..0071ed5 100644 --- a/src/jcgp/backend/modules/problem/DigitalCircuitProblem.java +++ b/src/jcgp/backend/modules/problem/DigitalCircuitProblem.java @@ -2,7 +2,6 @@ package jcgp.backend.modules.problem; import jcgp.backend.function.DigitalCircuitFunctions; import jcgp.backend.function.UnsignedInteger; -import jcgp.backend.population.Chromosome; import jcgp.backend.population.Population; import jcgp.backend.resources.Resources; @@ -18,7 +17,7 @@ import jcgp.backend.resources.Resources; * */ public class DigitalCircuitProblem extends TestCaseProblem<UnsignedInteger> { - + /** * Construct a new instance of DigitalCircuitProblem. * @@ -30,43 +29,38 @@ public class DigitalCircuitProblem extends TestCaseProblem<UnsignedInteger> { setName("Digital circuit"); setFileExtension(".plu"); } - + @Override public void evaluate(Population population, Resources resources) { // for every chromosome in the population for (int i = 0; i < resources.populationSize(); i++) { // assume an initial fitness of 0 int fitness = 0; - + // iterate over every test case for (int t = 0; t < testCases.size(); t++) { - population.getChromosome(i).setInputs((Object[]) testCases.get(t).getInputs()); + population.get(i).setInputs((Object[]) testCases.get(t).getInputs()); // check each output for (int o = 0; o < resources.outputs(); o++) { - Integer output = ((UnsignedInteger) population.getChromosome(i).getOutput(o).calculate()).get(); + 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()); for (int b = 0; b < bits; b++) { - if (((matches >>> b) & 1) == 1) { - fitness++; - } + fitness += (matches >>> b) & 1; } } } - + // assign the resulting fitness to the respective individual - population.getChromosome(i).setFitness(fitness); + population.get(i).setFitness(fitness); } - - // sort population - population.sortAscending(); } - + @Override protected double getMaxFitness() { // calculate the fitness by looking at inputs, not number of test cases - double maxFitness = Math.pow(2.0, (double) resources.inputs()) * resources.outputs(); + double maxFitness = Math.pow(2.0, (double) getResources().inputs()) * getResources().outputs(); return maxFitness; } @@ -81,24 +75,30 @@ public class DigitalCircuitProblem extends TestCaseProblem<UnsignedInteger> { for (int o = 0; o < outputCases.length; o++) { outputCases[o] = new UnsignedInteger(outputs[o]); } - + return new TestCase<UnsignedInteger>(inputCases, outputCases); } - + @Override - public boolean isPerfectSolution(Chromosome fittest) { + public int perfectSolutionFound(Population population) { // higher fitness is better - return fittest.getFitness() >= maxFitness.get(); + for (int i = 0; i < getResources().populationSize(); i++) { + if (population.get(i).getFitness() >= maxFitness.get()) { + return i; + } + } + return -1; } @Override - public boolean isImprovement(Chromosome fittest) { + public int hasImprovement(Population population) { // higher fitness is better - if (fittest.getFitness() > bestFitness.get()) { - bestFitness.set(fittest.getFitness()); - return true; - } else { - return false; + for (int i = 0; i < getResources().populationSize(); i++) { + if (population.get(i).getFitness() > bestFitness.get()) { + bestFitness.set(population.get(i).getFitness()); + return i; + } } + return -1; } } diff --git a/src/jcgp/backend/modules/problem/Problem.java b/src/jcgp/backend/modules/problem/Problem.java index 721b9b3..5f194b5 100644 --- a/src/jcgp/backend/modules/problem/Problem.java +++ b/src/jcgp/backend/modules/problem/Problem.java @@ -6,23 +6,21 @@ import jcgp.backend.function.FunctionSet; import jcgp.backend.modules.Module; import jcgp.backend.parameters.DoubleParameter; import jcgp.backend.parameters.monitors.DoubleMonitor; -import jcgp.backend.population.Chromosome; import jcgp.backend.population.Population; import jcgp.backend.resources.ModifiableResources; import jcgp.backend.resources.Resources; /** - * Defines the general behaviour of a CGP problem. The primary function of Problem + * Defines the general behaviour of a CGP problem. The primary function of {@code Problem} * is to evaluate a population and assign a fitness value to each chromosome. * <br> - * By convention, the population should be sorted into ascending order of fitness. The - * reason for this is because high fitness is not necessarily better - some problem types - * might treat 0 as the best fitness. In order for the evolutionary strategy to be able to - * pick chromosomes by fitness, the safest way is to sort them such that the last chromosome - * is the fittest. + * Problems are free to define whether better fitness means a higher or lower fitness value. + * In some problem types, it is more convenient to treat fitness 0 as the best possible value. + * This can be done by changing the fitness orientation to {@code BestFitness.HIGH} or {@code BestFitness.LOW} as appropriate. + * Fitness orientation is set to high by default. * <br><br> - * When extending this class, the constructor should call a couple methods in order to - * properly construct the problem type: {@code setFunctionSet()} and {@code setFileExtension()}, + * When extending this class, the constructor should call a few methods in order to + * properly construct the problem type: {@code setFunctionSet()}, {@code setFileExtension()} and {@code setFitnessOrientation()}, * with the respective arguments. As with all subclasses of {@code Module}, {@code setName()} and * {@code registerParameters()} should be used where appropriate as well. * <br><br> @@ -41,12 +39,18 @@ public abstract class Problem extends Module { private FunctionSet functionSet; private String fileExtension = ".*"; + private BestFitness fitnessOrientation = BestFitness.HIGH; + protected DoubleParameter maxFitness, bestFitness; /** * Initialises the two problem-wide parameters, maxFitness and bestFitness. + * + * @param resources a reference to the experiment's resources. */ - public Problem() { + public Problem(Resources resources) { + super(resources); + maxFitness = new DoubleMonitor(0, "Max fitness"); bestFitness = new DoubleMonitor(0, "Best fitness"); registerParameters(maxFitness, bestFitness); @@ -73,29 +77,26 @@ public abstract class Problem extends Module { public abstract void evaluate(Population population, Resources resources); /** - * Used to assert whether a given chromosome is a perfect solution + * Used to assert whether a given population contains a perfect solution * to the problem. It is up to the problem to define what qualifies * a perfect solution, as some problems (subject ones such as music and * art evolution, for example) might not have perfect solutions at all. - * <br><br> - * Note that if this method returns true, the experiment will move on - * to the next run, or finish if no more runs are left. * - * @param candidate the potentially perfect chromosome. - * @return true if the argument is a perfect solution. + * @param population the population to search through for a perfect chromosome. + * @return the perfect solution index, if one exits, -1 if no perfect solution was found. */ - public abstract boolean isPerfectSolution(Chromosome candidate); + public abstract int perfectSolutionFound(Population population); /** - * Used to assert whether a given chromosome is an improvement over + * Used to assert whether a given population has a chromosome that is an improvement over * the current best chromosome. A typical implementation of this method * will simply compare chromosome fitness values, though the problem type * is free to implement this in any way. * - * @param candidate the potentially fitter chromosome. - * @return true if the argument is fitter than the currently fittest chromosome. + * @param population the population potentially containing a fitter chromosome. + * @return the index of the first chromosome in the population that is an improvement, -1 if none is found. */ - public abstract boolean isImprovement(Chromosome candidate); + public abstract int hasImprovement(Population population); /** * Parses the specified file and uses the parsed data to @@ -149,6 +150,20 @@ public abstract class Problem extends Module { } /** + * @param newOrientation the new fitness orientation to set. + */ + protected void setFitnessOrientation(BestFitness newOrientation) { + this.fitnessOrientation = newOrientation; + } + + /** + * @return the fitness orientation of this particular problem. + */ + public BestFitness getFitnessOrientation() { + return fitnessOrientation; + } + + /** * @return the current best fitness, in other words, the fitness * value of the fittest chromosome in the current generation. */ diff --git a/src/jcgp/backend/modules/problem/SymbolicRegressionProblem.java b/src/jcgp/backend/modules/problem/SymbolicRegressionProblem.java index 04e9fe8..24c61d6 100644 --- a/src/jcgp/backend/modules/problem/SymbolicRegressionProblem.java +++ b/src/jcgp/backend/modules/problem/SymbolicRegressionProblem.java @@ -4,7 +4,6 @@ import jcgp.backend.function.SymbolicRegressionFunctions; import jcgp.backend.parameters.BooleanParameter; import jcgp.backend.parameters.DoubleParameter; import jcgp.backend.parameters.ParameterStatus; -import jcgp.backend.population.Chromosome; import jcgp.backend.population.Population; import jcgp.backend.resources.Resources; @@ -20,12 +19,12 @@ import jcgp.backend.resources.Resources; * <li>Error threshold: the maximum difference allowed between an * evolved output and the equivalent output from the problem data. * Outputs within the error threshold will be considered correct. - * This is only used if HITS is enabled.</li> + * This is only used if hits is enabled.</li> * <li>Perfection threshold: if the fitness is calculated without - * using the HITS method, it is a decimal value. A solution is + * using the hits method, it is a decimal value. A solution is * considered perfect when the difference between its fitness and * the maximum possible fitness is within the perfection threshold.</li> - * <li>HITS-based fitness: increment the fitness by 1 whenever the + * <li>Hits-based fitness: increment the fitness by 1 whenever the * chromosome output is within the error threshold.</li></ul> * * @@ -79,7 +78,7 @@ public class SymbolicRegressionProblem extends TestCaseProblem<Double> { } }; - hitsBasedFitness = new BooleanParameter(true, "HITS-based fitness"); + hitsBasedFitness = new BooleanParameter(false, "Hits-based fitness"); registerParameters(errorThreshold, perfectionThreshold, hitsBasedFitness); } @@ -87,15 +86,15 @@ public class SymbolicRegressionProblem extends TestCaseProblem<Double> { @Override public void evaluate(Population population, Resources resources) { // for every chromosome in the population - for (int i = 0; i < resources.populationSize(); i++) { + for (int i = 0; i < getResources().populationSize(); i++) { // assume an initial fitness of 0 double fitness = 0; // for each test case for (int t = 0; t < testCases.size(); t++) { - population.getChromosome(i).setInputs((Object[]) testCases.get(t).getInputs()); + population.get(i).setInputs((Object[]) testCases.get(t).getInputs()); // check each output - for (int o = 0; o < resources.outputs(); o++) { - Double cgpValue = (Double) population.getChromosome(i).getOutput(o).calculate(); + for (int o = 0; o < getResources().outputs(); o++) { + Double cgpValue = (Double) population.get(i).getOutput(o).calculate(); Double dataValue = testCases.get(t).getOutput(o); if (hitsBasedFitness.get()) { if (Math.abs(cgpValue - dataValue) <= errorThreshold.get()) { @@ -107,11 +106,8 @@ public class SymbolicRegressionProblem extends TestCaseProblem<Double> { } } // assign the resulting fitness to the respective individual - population.getChromosome(i).setFitness(fitness); + population.get(i).setFitness(fitness); } - - // sort population - population.sortAscending(); } @Override @@ -130,19 +126,27 @@ public class SymbolicRegressionProblem extends TestCaseProblem<Double> { } @Override - public boolean isPerfectSolution(Chromosome fittest) { + public int perfectSolutionFound(Population population) { // higher fitness is better - return fittest.getFitness() >= maxFitness.get() - perfectionThreshold.get(); + for (int i = 0; i < getResources().populationSize(); i++) { + if (population.get(i).getFitness() >= maxFitness.get() - perfectionThreshold.get()) { + return i; + } + } + return -1; } @Override - public boolean isImprovement(Chromosome fittest) { + public int hasImprovement(Population population) { // higher fitness is better - if (fittest.getFitness() > bestFitness.get()) { - bestFitness.set(fittest.getFitness()); - return true; - } else { - return false; + for (int i = 0; i < getResources().populationSize(); i++) { + System.out.println("checking for improvement"); + if (population.get(i).getFitness() > bestFitness.get()) { + System.out.println("found a better chr, " + i); + bestFitness.set(population.get(i).getFitness()); + return i; + } } + return -1; } } diff --git a/src/jcgp/backend/modules/problem/TestCaseProblem.java b/src/jcgp/backend/modules/problem/TestCaseProblem.java index c11fab4..69c078d 100644 --- a/src/jcgp/backend/modules/problem/TestCaseProblem.java +++ b/src/jcgp/backend/modules/problem/TestCaseProblem.java @@ -30,7 +30,7 @@ public abstract class TestCaseProblem<T> extends Problem { * contains arrays of inputs and outputs and associated getters. * * @author Eduardo Pedroni - * @param <U> + * @param <U> the data type of the test case. */ public static class TestCase<U> { private U[] inputs; @@ -80,7 +80,6 @@ public abstract class TestCaseProblem<T> extends Problem { } protected ObservableList<TestCase<T>> testCases; - protected Resources resources; /** * Creates a new TestCaseProblem object. @@ -88,8 +87,7 @@ public abstract class TestCaseProblem<T> extends Problem { * @param resources a reference to the experiment's resources. */ public TestCaseProblem(Resources resources) { - super(); - this.resources = resources; + super(resources); testCases = FXCollections.observableArrayList(); } @@ -139,12 +137,12 @@ public abstract class TestCaseProblem<T> extends Problem { public final void addTestCase(String[] inputs, String[] outputs) { TestCase<T> testCase = parseTestCase(inputs, outputs); - if (testCase.getInputs().length != resources.inputs()) { + if (testCase.getInputs().length != getResources().inputs()) { throw new IllegalArgumentException("Received test case with " + testCase.getInputs().length + - " inputs but need exactly " + resources.inputs()); - } else if (testCase.getOutputs().length != resources.outputs()) { + " inputs but need exactly " + getResources().inputs()); + } else if (testCase.getOutputs().length != getResources().outputs()) { throw new IllegalArgumentException("Received test case with " + testCase.getOutputs().length + - " outputs but need exactly " + resources.outputs()); + " outputs but need exactly " + getResources().outputs()); } else { this.testCases.add(testCase); maxFitness.set(getMaxFitness()); diff --git a/src/jcgp/backend/modules/problem/TravellingSalesmanProblem.java b/src/jcgp/backend/modules/problem/TravellingSalesmanProblem.java deleted file mode 100644 index 94417ae..0000000 --- a/src/jcgp/backend/modules/problem/TravellingSalesmanProblem.java +++ /dev/null @@ -1,56 +0,0 @@ -package jcgp.backend.modules.problem; - -import java.io.File; - -import jcgp.backend.function.TravellingSalesmanFunctions; -import jcgp.backend.population.Chromosome; -import jcgp.backend.population.Population; -import jcgp.backend.resources.ModifiableResources; -import jcgp.backend.resources.Resources; - -/** - * Travelling salesman problem - * <br><br> - * Using this problem type, travelling salesman tours can be evolved. - * {@code parseData()} must be used to load the desired city - * coordinates in the standard .tsp format. - * - * @see TravellingSalesmanFunctions - * @author Eduardo Pedroni - * - */ -public class TravellingSalesmanProblem extends Problem { - - /** - * Construct a new instance of TravellingSalesmanProblem. - * - * @param resources a reference to the experiment's resources. - */ - public TravellingSalesmanProblem(Resources resources) { - setFunctionSet(new TravellingSalesmanFunctions()); - setName("Travelling salesman"); - setFileExtension(".tsp"); - } - - @Override - public void evaluate(Population population, Resources resources) { - // TODO Auto-generated method stub - } - - @Override - public boolean isPerfectSolution(Chromosome fittest) { - // TODO Auto-generated method stub - return false; - } - - @Override - public void parseProblemData(File file, ModifiableResources resources) { - // TODO Auto-generated method stub - } - - @Override - public boolean isImprovement(Chromosome fittest) { - // TODO Auto-generated method stub - return false; - } -} |