aboutsummaryrefslogtreecommitdiffstats
path: root/src/jcgp/backend/modules/problem
diff options
context:
space:
mode:
authorEduardo Pedroni <ep625@york.ac.uk>2014-05-01 13:05:27 +0100
committerEduardo Pedroni <ep625@york.ac.uk>2014-05-01 13:05:27 +0100
commit36f4393bcc9e55afa2334baa33e603ce839741a1 (patch)
treed9a1d55d0d3553193a3fc11a92f11515762d202f /src/jcgp/backend/modules/problem
parent4c8de2402f2878cde7587c7f3bbf4ffaea86efd4 (diff)
Did more commenting, implemented reflection and statistics
Diffstat (limited to 'src/jcgp/backend/modules/problem')
-rw-r--r--src/jcgp/backend/modules/problem/DigitalCircuitProblem.java43
-rw-r--r--src/jcgp/backend/modules/problem/Problem.java142
-rw-r--r--src/jcgp/backend/modules/problem/SymbolicRegressionProblem.java72
-rw-r--r--src/jcgp/backend/modules/problem/TestCaseProblem.java148
-rw-r--r--src/jcgp/backend/modules/problem/TravellingSalesmanProblem.java35
5 files changed, 327 insertions, 113 deletions
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
+ * <br><br>
+ * 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<UnsignedInteger> {
+ /**
+ * 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<UnsignedInteger> {
@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<UnsignedInteger> 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<UnsignedInteger> {
outputCases[o] = new UnsignedInteger(outputs[o]);
}
- addTestCase(new TestCase<UnsignedInteger>(inputCases, outputCases));
+ return new TestCase<UnsignedInteger>(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.
+ * <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.
* <br><br>
- * 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.
* <br><br>
* 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.
+ * <br><br>
+ * 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.
+ * <br><br>
+ * 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.
+ * <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.
+ */
+ 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.
+ * <br><br>
+ * 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
+ * <br><br>
+ * 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.
+ * <br><br>
+ * This problem uses quite a few parameters:
+ * <ul>
+ * <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>
+ * <li>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.</li>
+ * <li>HITS-based fitness: increment the fitness by 1 whenever the
+ * chromosome output is within the error threshold.</li></ul>
+ *
+ *
+ * @see SymbolicRegressionFunctions
+ * @author Eduardo Pedroni
+ *
+ */
public class SymbolicRegressionProblem extends TestCaseProblem<Double> {
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<Double> {
}
}
};
+
perfectionThreshold = new DoubleParameter(0.000001, "Perfection threshold") {
@Override
public void validate(Number newValue) {
@@ -47,12 +78,10 @@ public class SymbolicRegressionProblem extends TestCaseProblem<Double> {
}
}
};
- 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<Double> {
} else {
fitness += 1 - Math.abs(cgpValue - dataValue);
}
-
}
}
// assign the resulting fitness to the respective individual
@@ -87,7 +115,8 @@ public class SymbolicRegressionProblem extends TestCaseProblem<Double> {
}
@Override
- public void addTestCase(String[] inputs, String[] outputs) {
+ public TestCase<Double> 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<Double> {
outputCases[o] = Double.parseDouble(outputs[o]);
}
- addTestCase(new TestCase<Double>(inputCases, outputCases));
+ return new TestCase<Double>(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.
+ * <br><br>
+ * 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 <T> the data type to be used by the TestCaseProblem.
*/
-public abstract class TestCaseProblem<U extends Object> extends Problem {
+public abstract class TestCaseProblem<T> extends Problem {
- public static class TestCase<T> {
- 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 <U>
+ */
+ public static class TestCase<U> {
+ 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<TestCase<U>> testCases;
- protected DoubleParameter maxFitness;
+ protected ObservableList<TestCase<T>> 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<U> tc : testCases) {
+ for (TestCase<T> tc : testCases) {
fitness += tc.getOutputs().length;
}
-
return fitness;
}
- public void setTestCases(List<TestCase<U>> testCases) {
- this.testCases.clear();
- this.testCases.addAll(testCases);
- maxFitness.set(getMaxFitness());
- }
-
- public ObservableList<TestCase<U>> getTestCases() {
+ /**
+ * @return a list containing the test cases.
+ */
+ public ObservableList<TestCase<T>> 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<T> parseTestCase(String[] inputs, String[] outputs);
- protected final void addTestCase(TestCase<U> 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<T> 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<U extends Object> 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
+ * <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) {
- 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;
}
}