From 36f4393bcc9e55afa2334baa33e603ce839741a1 Mon Sep 17 00:00:00 2001 From: Eduardo Pedroni Date: Thu, 1 May 2014 13:05:27 +0100 Subject: Did more commenting, implemented reflection and statistics --- .../modules/problem/DigitalCircuitProblem.java | 43 ++++-- src/jcgp/backend/modules/problem/Problem.java | 142 +++++++++++++++++--- .../modules/problem/SymbolicRegressionProblem.java | 72 +++++++--- .../backend/modules/problem/TestCaseProblem.java | 148 +++++++++++++-------- .../modules/problem/TravellingSalesmanProblem.java | 35 +++-- 5 files changed, 327 insertions(+), 113 deletions(-) (limited to 'src/jcgp/backend/modules/problem') diff --git a/src/jcgp/backend/modules/problem/DigitalCircuitProblem.java b/src/jcgp/backend/modules/problem/DigitalCircuitProblem.java index 099f527..6654928 100644 --- a/src/jcgp/backend/modules/problem/DigitalCircuitProblem.java +++ b/src/jcgp/backend/modules/problem/DigitalCircuitProblem.java @@ -6,12 +6,28 @@ import jcgp.backend.population.Chromosome; import jcgp.backend.population.Population; import jcgp.backend.resources.Resources; +/** + * Digital circuit problem + *

+ * Using this problem type, digital logic circuits can be evolved. + * {@code parseData()} must be used to load the desired circuit + * truth table in the standard CGP .plu format. + * + * @see DigitalCircuitFunctions + * @author Eduardo Pedroni + * + */ public class DigitalCircuitProblem extends TestCaseProblem { + /** + * Construct a new instance of DigitalCircuitProblem. + * + * @param resources a reference to the experiment's resources. + */ public DigitalCircuitProblem(Resources resources) { super(resources); - functionSet = new DigitalCircuitFunctions(); - setProblemName("Symbolic regression"); + setFunctionSet(new DigitalCircuitFunctions()); + setName("Digital circuit"); setFileExtension(".plu"); } @@ -49,17 +65,14 @@ public class DigitalCircuitProblem extends TestCaseProblem { @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(); return maxFitness; } - - @Override - public String toString() { - return "Digital circuit"; - } @Override - public void addTestCase(String[] inputs, String[] outputs) { + public TestCase parseTestCase(String[] inputs, String[] outputs) { + // cast the test case values to UnsignedInteger UnsignedInteger[] inputCases = new UnsignedInteger[inputs.length]; UnsignedInteger[] outputCases = new UnsignedInteger[outputs.length]; for (int i = 0; i < inputCases.length; i++) { @@ -69,11 +82,23 @@ public class DigitalCircuitProblem extends TestCaseProblem { outputCases[o] = new UnsignedInteger(outputs[o]); } - addTestCase(new TestCase(inputCases, outputCases)); + return new TestCase(inputCases, outputCases); } @Override public boolean isPerfectSolution(Chromosome fittest) { + // higher fitness is better return fittest.getFitness() >= maxFitness.get(); } + + @Override + public boolean isImprovement(Chromosome fittest) { + // higher fitness is better + if (fittest.getFitness() > bestFitness.get()) { + bestFitness.set(fittest.getFitness()); + return true; + } else { + return false; + } + } } diff --git a/src/jcgp/backend/modules/problem/Problem.java b/src/jcgp/backend/modules/problem/Problem.java index 368d512..721b9b3 100644 --- a/src/jcgp/backend/modules/problem/Problem.java +++ b/src/jcgp/backend/modules/problem/Problem.java @@ -4,6 +4,8 @@ import java.io.File; 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; @@ -11,11 +13,18 @@ import jcgp.backend.resources.Resources; /** * Defines the general behaviour of a CGP problem. The primary function of Problem - * is to evaluate a population and assign + * is to evaluate a population and assign a fitness value to each chromosome. + *
+ * 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. *

- * Parameters may be specified to control the implemented problem. Any parameters - * returned by {@code getLocalParameters()} should be displayed by the user interface, - * if it is being used. See {@link Parameter} for more information. + * When extending this class, the constructor should call a couple methods in order to + * properly construct the problem type: {@code setFunctionSet()} and {@code setFileExtension()}, + * with the respective arguments. As with all subclasses of {@code Module}, {@code setName()} and + * {@code registerParameters()} should be used where appropriate as well. *

* It is advisable to use {@code Resources.reportln()} and {@code Resources.report()} * to print any relevant information. Note that reportln() and report() are affected @@ -24,44 +33,133 @@ import jcgp.backend.resources.Resources; * See {@link Resources} for more information. * * @see Module - * * @author Eduardo Pedroni * */ -public abstract class Problem implements Module { +public abstract class Problem extends Module { - protected FunctionSet functionSet; + private FunctionSet functionSet; private String fileExtension = ".*"; - private String name = this.getClass().getSimpleName(); - public abstract void evaluate(Population population, Resources resources); + protected DoubleParameter maxFitness, bestFitness; - public FunctionSet getFunctionSet() { - return functionSet; + /** + * Initialises the two problem-wide parameters, maxFitness and bestFitness. + */ + public Problem() { + maxFitness = new DoubleMonitor(0, "Max fitness"); + bestFitness = new DoubleMonitor(0, "Best fitness"); + registerParameters(maxFitness, bestFitness); } - public abstract boolean isPerfectSolution(Chromosome fittest); + /** + * The most important method of the problem type. This is called once + * per generation, when the new population has been generated. + *

+ * The basic functionality of this method is to loop through all chromosomes + * in the population and decode them according to the problem type. The + * fitness of each chromosome is then calculated using the problem data + * or otherwise (subjective problem types such as art generation might + * leave fitness evaluations up to the user) and assigned to the appropriate + * chromosome. + *

+ * In addition, realisations of this method should update the value of + * bestFitness as appropriate, since the value of this parameter is displayed + * if a GUI is in use. + * + * @param population the population to be evaluated. + * @param resources parameters and utilities for optional reference. + */ + public abstract void evaluate(Population population, Resources resources); + + /** + * Used to assert whether a given chromosome is 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. + *

+ * 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. + */ + public abstract boolean isPerfectSolution(Chromosome candidate); + /** + * Used to assert whether a given chromosome 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. + */ + public abstract boolean isImprovement(Chromosome candidate); + + /** + * Parses the specified file and uses the parsed data to + * set up the problem type instance appropriately. Any necessary + * resource changes can be performed using the provided {@code ModifiableResources} + * instance. + *

+ * In addition, realisations of this method should update the value of + * maxFitness where appropriate, as this may be displayed to the user + * if a GUI is in use. + * + * @param file the data file to parse. + * @param resources a modifiable reference to the experiment's resources. + */ public abstract void parseProblemData(File file, ModifiableResources resources); - public void setFileExtension(String fileExtension) { + /** + * For internal use in subclass constructor, sets the functions to be + * used for this problem type. See {@link FunctionSet} for more details. + * + * @param newFunctionSet the function set to use. + */ + protected void setFunctionSet(FunctionSet newFunctionSet) { + this.functionSet = newFunctionSet; + } + + /** + * @return the FunctionSet object used by this problem type. + */ + public FunctionSet getFunctionSet() { + return functionSet; + } + + /** + * For internal use in subclass constructors, sets the file extension accepted + * by this problem type's parser. This is used by the GUI to filter loaded files + * by extension in a file chooser. File extensions should be set in the form ".*", + * so for plain text files, ".txt" would be used. + * + * @param fileExtension the accepted file extension. + */ + protected void setFileExtension(String fileExtension) { this.fileExtension = fileExtension; } + /** + * @return the file extension accepted by this problem type for problem data files. + */ public String getFileExtension() { return fileExtension; } - public void setProblemName(String newName) { - this.name = newName; - } - - public String getProblemName() { - return name; + /** + * @return the current best fitness, in other words, the fitness + * value of the fittest chromosome in the current generation. + */ + public double getBestFitness() { + return bestFitness.get(); } - @Override - public String toString() { - return name; + /** + * Resets the bestFitness parameter. + */ + public void reset() { + bestFitness.set(0); } } diff --git a/src/jcgp/backend/modules/problem/SymbolicRegressionProblem.java b/src/jcgp/backend/modules/problem/SymbolicRegressionProblem.java index 5468157..04e9fe8 100644 --- a/src/jcgp/backend/modules/problem/SymbolicRegressionProblem.java +++ b/src/jcgp/backend/modules/problem/SymbolicRegressionProblem.java @@ -1,24 +1,54 @@ package jcgp.backend.modules.problem; 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; -import jcgp.backend.resources.parameters.BooleanParameter; -import jcgp.backend.resources.parameters.DoubleParameter; -import jcgp.backend.resources.parameters.Parameter; -import jcgp.backend.resources.parameters.ParameterStatus; +/** + * Symbolic regression functions + *

+ * Using this problem type, regression problems can be solved. + * {@code parseData()} must be used to load the desired function + * data in the standard CGP .dat format. + *

+ * This problem uses quite a few parameters: + *
    + *
  • 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.
    • + *
  • Perfection threshold: if the fitness is calculated without + * 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.
    • + *
  • HITS-based fitness: increment the fitness by 1 whenever the + * chromosome output is within the error threshold.
+ * + * + * @see SymbolicRegressionFunctions + * @author Eduardo Pedroni + * + */ public class SymbolicRegressionProblem extends TestCaseProblem { private DoubleParameter errorThreshold, perfectionThreshold; private BooleanParameter hitsBasedFitness; - + + /** + * Creates a new instance of SymbolicRegressionProblem. + * + * @param resources a reference to the experiment's resources. + */ public SymbolicRegressionProblem(Resources resources) { super(resources); - functionSet = new SymbolicRegressionFunctions(); - setProblemName("Symbolic regression"); + setFunctionSet(new SymbolicRegressionFunctions()); + setName("Symbolic regression"); setFileExtension(".dat"); + errorThreshold = new DoubleParameter(0.01, "Error threshold") { @Override public void validate(Number newValue) { @@ -33,6 +63,7 @@ public class SymbolicRegressionProblem extends TestCaseProblem { } } }; + perfectionThreshold = new DoubleParameter(0.000001, "Perfection threshold") { @Override public void validate(Number newValue) { @@ -47,12 +78,10 @@ public class SymbolicRegressionProblem extends TestCaseProblem { } } }; - hitsBasedFitness = new BooleanParameter(true, "HITS-based fitness") { - @Override - public void validate(Boolean newValue) { - // blank - } - }; + + hitsBasedFitness = new BooleanParameter(true, "HITS-based fitness"); + + registerParameters(errorThreshold, perfectionThreshold, hitsBasedFitness); } @Override @@ -75,7 +104,6 @@ public class SymbolicRegressionProblem extends TestCaseProblem { } else { fitness += 1 - Math.abs(cgpValue - dataValue); } - } } // assign the resulting fitness to the respective individual @@ -87,7 +115,8 @@ public class SymbolicRegressionProblem extends TestCaseProblem { } @Override - public void addTestCase(String[] inputs, String[] outputs) { + public TestCase parseTestCase(String[] inputs, String[] outputs) { + // cast the test case values to UnsignedInteger Double[] inputCases = new Double[inputs.length]; Double[] outputCases = new Double[outputs.length]; for (int i = 0; i < inputCases.length; i++) { @@ -97,16 +126,23 @@ public class SymbolicRegressionProblem extends TestCaseProblem { outputCases[o] = Double.parseDouble(outputs[o]); } - addTestCase(new TestCase(inputCases, outputCases)); + return new TestCase(inputCases, outputCases); } @Override public boolean isPerfectSolution(Chromosome fittest) { + // higher fitness is better return fittest.getFitness() >= maxFitness.get() - perfectionThreshold.get(); } @Override - public Parameter[] getLocalParameters() { - return new Parameter[]{maxFitness, errorThreshold, perfectionThreshold, hitsBasedFitness}; + public boolean isImprovement(Chromosome fittest) { + // higher fitness is better + if (fittest.getFitness() > bestFitness.get()) { + bestFitness.set(fittest.getFitness()); + return true; + } else { + return false; + } } } diff --git a/src/jcgp/backend/modules/problem/TestCaseProblem.java b/src/jcgp/backend/modules/problem/TestCaseProblem.java index 7ce0327..c11fab4 100644 --- a/src/jcgp/backend/modules/problem/TestCaseProblem.java +++ b/src/jcgp/backend/modules/problem/TestCaseProblem.java @@ -1,100 +1,144 @@ package jcgp.backend.modules.problem; import java.io.File; -import java.util.List; import javafx.collections.FXCollections; import javafx.collections.ObservableList; import jcgp.backend.parsers.TestCaseParser; import jcgp.backend.resources.ModifiableResources; import jcgp.backend.resources.Resources; -import jcgp.backend.resources.parameters.DoubleParameter; -import jcgp.backend.resources.parameters.Parameter; /** + * Abstract model for a problem that uses test cases. A test case + * problem is any problem that compares the chromosome output to + * an expected output taken from a table of input-output mappings. + *

+ * This class defines a basic data type for storing test cases, + * TestCase, and provides core functionality to add and manipulate + * test cases in the problem. A subclass of {@code TestCaseProblem} + * must simply override {@code parseTestCase()} to convert parsed + * problem data strings into the required data type (T). * - * This fitness function module implements a simple test case evaluator. - * - * A TestCase object is a - * - * + * @see Problem * @author Eduardo Pedroni - * + * @param the data type to be used by the TestCaseProblem. */ -public abstract class TestCaseProblem extends Problem { +public abstract class TestCaseProblem extends Problem { - public static class TestCase { - private T[] inputs; - private T[] outputs; + /** + * Basic data type for encapsulating test cases, it simply + * contains arrays of inputs and outputs and associated getters. + * + * @author Eduardo Pedroni + * @param + */ + public static class TestCase { + private U[] inputs; + private U[] outputs; - public TestCase(T[] inputs, T[] outputs) { + /** + * Creates a new test case, inputs and outputs + * must be specified upon instantiation. + * + * @param inputs the array of inputs. + * @param outputs the array of outputs. + */ + public TestCase(U[] inputs, U[] outputs) { this.inputs = inputs; this.outputs = outputs; } - public T getInput(int index) { + /** + * @param index the index to return. + * @return the indexed input. + */ + public U getInput(int index) { return inputs[index]; } - public T getOutput(int index) { + /** + * @param index the index to return. + * @return the indexed output. + */ + public U getOutput(int index) { return outputs[index]; } - public T[] getInputs() { + /** + * @return the complete array of inputs. + */ + public U[] getInputs() { return inputs; } - public T[] getOutputs() { + /** + * @return the complete array of outputs. + */ + public U[] getOutputs() { return outputs; } } - protected ObservableList> testCases; - protected DoubleParameter maxFitness; + protected ObservableList> testCases; protected Resources resources; + /** + * Creates a new TestCaseProblem object. + * + * @param resources a reference to the experiment's resources. + */ public TestCaseProblem(Resources resources) { super(); - this.resources = resources; - - maxFitness = new DoubleParameter(0, "Max fitness", true, false) { - @Override - public void validate(Number newValue) { - // blank - } - }; testCases = FXCollections.observableArrayList(); } - @Override - public Parameter[] getLocalParameters() { - return new Parameter[]{maxFitness}; - } - + /** + * For internal use only, this method computes and returns the maximum fitness + * based on the number of test cases. Subclasses should override this method + * as necessary. + * + * @return the maximum fitness based on number of test cases. + */ protected double getMaxFitness() { int fitness = 0; - - for (TestCase tc : testCases) { + for (TestCase tc : testCases) { fitness += tc.getOutputs().length; } - return fitness; } - public void setTestCases(List> testCases) { - this.testCases.clear(); - this.testCases.addAll(testCases); - maxFitness.set(getMaxFitness()); - } - - public ObservableList> getTestCases() { + /** + * @return a list containing the test cases. + */ + public ObservableList> getTestCases() { return testCases; } - public abstract void addTestCase(String[] inputs, String[] outputs); + /** + * This method is used internally by {@code addTestCase()} in order + * to appropriately parse strings into the right data type for the + * test cases. Since the data type is problem-dependent, subclasses must + * implement this method. This method must return a built {@code TestCase} + * object from the arguments given. + * + * @param inputs the inputs represented as strings. + * @param outputs the outputs represented as strings. + * @return the parsed test case. + */ + protected abstract TestCase parseTestCase(String[] inputs, String[] outputs); - protected final void addTestCase(TestCase testCase) { + /** + * Adds test cases to the problem instance as they get parsed from a + * problem data file. This template method uses {@code parseTestCase}, which + * must be implemented by subclasses. + * + * @param inputs the inputs represented as strings. + * @param outputs the outputs represented as strings. + */ + public final void addTestCase(String[] inputs, String[] outputs) { + TestCase testCase = parseTestCase(inputs, outputs); + if (testCase.getInputs().length != resources.inputs()) { throw new IllegalArgumentException("Received test case with " + testCase.getInputs().length + " inputs but need exactly " + resources.inputs()); @@ -106,20 +150,18 @@ public abstract class TestCaseProblem extends Problem { maxFitness.set(getMaxFitness()); } } - - public int getInputCount() { - return resources.inputs(); - } - - public int getOutputCount() { - return resources.outputs(); - } + /** + * Remove all test cases. + */ public void clearTestCases() { testCases.clear(); + maxFitness.set(getMaxFitness()); } + @Override public void parseProblemData(File file, ModifiableResources resources) { + // use standard test case parser for this TestCaseParser.parse(file, this, resources); } } diff --git a/src/jcgp/backend/modules/problem/TravellingSalesmanProblem.java b/src/jcgp/backend/modules/problem/TravellingSalesmanProblem.java index 8363ef8..94417ae 100644 --- a/src/jcgp/backend/modules/problem/TravellingSalesmanProblem.java +++ b/src/jcgp/backend/modules/problem/TravellingSalesmanProblem.java @@ -7,26 +7,34 @@ import jcgp.backend.population.Chromosome; import jcgp.backend.population.Population; import jcgp.backend.resources.ModifiableResources; import jcgp.backend.resources.Resources; -import jcgp.backend.resources.parameters.Parameter; +/** + * Travelling salesman problem + *

+ * 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) { - functionSet = new TravellingSalesmanFunctions(); - setProblemName("Travelling salesman"); + setFunctionSet(new TravellingSalesmanFunctions()); + setName("Travelling salesman"); setFileExtension(".tsp"); } - @Override - public Parameter[] getLocalParameters() { - // TODO Auto-generated method stub - return null; - } - @Override public void evaluate(Population population, Resources resources) { // TODO Auto-generated method stub - } @Override @@ -38,6 +46,11 @@ public class TravellingSalesmanProblem extends Problem { @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; } } -- cgit v1.2.3