diff options
Diffstat (limited to 'src/jcgp/backend/modules/es')
| -rw-r--r-- | src/jcgp/backend/modules/es/EvolutionaryStrategy.java | 34 | ||||
| -rw-r--r-- | src/jcgp/backend/modules/es/MuPlusLambda.java | 67 | ||||
| -rw-r--r-- | src/jcgp/backend/modules/es/TournamentSelection.java | 99 |
3 files changed, 167 insertions, 33 deletions
diff --git a/src/jcgp/backend/modules/es/EvolutionaryStrategy.java b/src/jcgp/backend/modules/es/EvolutionaryStrategy.java index 8ab287d..70e3cd2 100644 --- a/src/jcgp/backend/modules/es/EvolutionaryStrategy.java +++ b/src/jcgp/backend/modules/es/EvolutionaryStrategy.java @@ -5,8 +5,42 @@ import jcgp.backend.modules.mutator.Mutator; import jcgp.backend.population.Population; import jcgp.backend.resources.Resources; +/** + * This interface specifies the required behaviour of an evolutionary strategy. The evolutionary + * strategy's job is to generate the next population of solutions. In JCGP this is done by modifying + * the provided population object rather than creating a new one. + * <br><br> + * A typical implementation of EvolutionaryStratey iterates through the chromosomes + * in the population and selects the individual(s) to be promoted. It then uses + * {@code mutator.mutate()} to generically mutate the promoted individual(s). Parameter-dependent + * strategies can be implemented by accessing the parameters via the resources + * argument. + * <br><br> + * Parameters may be specified to control the implemented strategy. Any parameters + * returned by {@code getLocalParameters()} should be displayed by the user interface, + * if it is being used. See {@link Parameter} for more information. + * <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 + * by the report interval base parameter. Use {@code Resources.println()} and + * {@code Resources.print()} to print information regardless of the current generation. + * See {@link Resources} for more information. + * + * @see Module + * + * @author Eduardo Pedroni + * + */ public interface EvolutionaryStrategy extends Module { + /** + * Performs the selection algorithm and uses the mutator to create + * the next generation of solutions. + * + * @param population the population to evolve. + * @param mutator the mutator with which to mutate the promoted individuals. + * @param resources parameters and utilities for optional reference. + */ public abstract void evolve(Population population, Mutator mutator, Resources resources); } diff --git a/src/jcgp/backend/modules/es/MuPlusLambda.java b/src/jcgp/backend/modules/es/MuPlusLambda.java index 6a3883b..50bf265 100644 --- a/src/jcgp/backend/modules/es/MuPlusLambda.java +++ b/src/jcgp/backend/modules/es/MuPlusLambda.java @@ -9,41 +9,59 @@ import jcgp.backend.resources.parameters.Parameter; import jcgp.backend.resources.parameters.ParameterStatus; /** - * (μ + λ) EA. - * + * (μ + λ)-ES + * <br><br> + * This strategy selects the μ fittest chromosomes from the population. + * The promoted individuals are copied into the new population and mutated + * λ times, but also carried forward unchanged. The total population size + * is μ + λ. + * <br><br> + * Two integer parameters are used to control this strategy: parents + * and offspring. They are constrained in that they must always add up to + * the population size, and must never be smaller than 1. + * <br> + * One additional parameter, report, controls whether a detailed log of the + * algorithm's operation is to be printed or not. Reports respect the report + * interval base parameter. * + * @see EvolutionaryStrategy * @author Eduardo Pedroni * */ public class MuPlusLambda implements EvolutionaryStrategy { - private IntegerParameter parents, offspring; + private IntegerParameter mu, lambda; private BooleanParameter report; + /** + * Creates a new instance of MuPlusLambda. + * + * @param resources a reference to the experiment's resources. + */ public MuPlusLambda(final Resources resources) { - parents = new IntegerParameter(1, "Parents") { + mu = new IntegerParameter(1, "Parents (μ)") { @Override public void validate(Number newValue) { - if (newValue.intValue() + offspring.get() != resources.populationSize()) { + if (newValue.intValue() + lambda.get() != resources.populationSize()) { status = ParameterStatus.INVALID; status.setDetails("Parents + offspring must equal population size."); } else if (newValue.intValue() <= 0) { status = ParameterStatus.INVALID; - status.setDetails("EA needs at least 1 parent."); + status.setDetails("ES needs at least 1 parent."); } else { status = ParameterStatus.VALID; } } }; - offspring = new IntegerParameter(4, "Offspring") { + lambda = new IntegerParameter(4, "Offspring (λ)") { @Override public void validate(Number newValue) { - if (newValue.intValue() + parents.get() != resources.populationSize()) { + if (newValue.intValue() + mu.get() != resources.populationSize()) { status = ParameterStatus.INVALID; status.setDetails("Parents + offspring must equal population size."); } else if (newValue.intValue() <= 0) { status = ParameterStatus.INVALID; - status.setDetails("EA needs at least 1 offspring."); + status.setDetails("ES needs at least 1 offspring."); } else { status = ParameterStatus.VALID; } @@ -58,32 +76,31 @@ public class MuPlusLambda implements EvolutionaryStrategy { } @Override - public void evolve(Population population, Mutator mutator, Resources resources) { - // select fittest chromosomes - if (report.get()) resources.reportln("[ES] Selected chromosome: " + population.getFittestIndex()); - - // create copies of fittest chromosome, mutate them - for (int i = 0; i < resources.populationSize(); i++) { - if (i != population.getFittestIndex()) { - if (report.get()) resources.reportln("[ES] Copying fittest chromosome to population position " + i); - population.copyChromosome(population.getFittestIndex(), i); - if (report.get()) resources.reportln("[ES] Mutating copied chromosome"); - mutator.mutate(population.getChromosome(i), resources); - } + public void evolve(Population population, Mutator mutator, Resources resources) { + /* Population is sorted in ascending order of fitness, so leave the last + * mu chromosomes intact + */ + for (int i = 0; i < resources.populationSize() - mu.get(); i++) { + // select a random parent out of the lambda offspring individuals + int randomParent = resources.populationSize() - 1 - resources.getRandomInt(mu.get()); + if (report.get()) resources.reportln("[ES] Copying Chr " + randomParent + " to population position " + i); + population.copyChromosome(randomParent, i); + + // mutate selected chromosome + if (report.get()) resources.reportln("[ES] Mutating copied chromosome"); + mutator.mutate(population.getChromosome(i), resources); } - if (report.get()) resources.reportln("[ES] Generation is complete."); - + if (report.get()) resources.reportln("[ES] Generation is complete"); } @Override public Parameter<?>[] getLocalParameters() { - return new Parameter[] {parents, offspring, report}; + return new Parameter[] {mu, lambda, report}; } @Override public String toString() { return "(μ + λ)"; } - } diff --git a/src/jcgp/backend/modules/es/TournamentSelection.java b/src/jcgp/backend/modules/es/TournamentSelection.java index 7cc9706..43fea81 100644 --- a/src/jcgp/backend/modules/es/TournamentSelection.java +++ b/src/jcgp/backend/modules/es/TournamentSelection.java @@ -1,35 +1,118 @@ package jcgp.backend.modules.es; +import java.util.Arrays; + import jcgp.backend.modules.mutator.Mutator; +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.IntegerParameter; import jcgp.backend.resources.parameters.Parameter; +import jcgp.backend.resources.parameters.ParameterStatus; +/** + * Tournament selection + * <br><br> + * This strategy generates a new population by selecting a specified number + * of chromosomes from the original population and selecting the fittest out + * of the isolated subset (the tournament). The selected individual is mutated + * using the specified mutator. This process is repeated until the new population + * is complete. + * <br><br> + * One integer parameter is used to control this strategy: tournament + * size. This must always be greater than 0 and smaller than or equal to the + * population size. Setting it to equal population size results in the same + * chromosome being selected for every tournament, and setting it to 1 leads + * to an effectively random search. + * <br> + * One additional parameter, report, controls whether a detailed log of the + * algorithm's operation is to be printed or not. Reports respect the report + * interval base parameter. + * + * @see EvolutionaryStrategy + * @author Eduardo Pedroni + * + */ public class TournamentSelection implements EvolutionaryStrategy { private IntegerParameter tournamentSize; + private BooleanParameter report; - public TournamentSelection(Resources resources) { + /** + * Creates a new instance of TournamentSelection. + * + * @param resources a reference to the experiment's resources. + */ + public TournamentSelection(final Resources resources) { tournamentSize = new IntegerParameter(1, "Tournament size") { @Override public void validate(Number newValue) { - // TODO this + if (newValue.intValue() <= 0) { + status = ParameterStatus.INVALID; + status.setDetails("Tournament size must be greater than 0."); + } else if (newValue.intValue() > resources.populationSize()) { + status = ParameterStatus.INVALID; + status.setDetails("Tournament size must not be greater than the population size."); + } else if (newValue.intValue() == 1) { + status = ParameterStatus.WARNING; + status.setDetails("A tournament size of 1 results in a random search."); + } else if (newValue.intValue() == resources.populationSize()) { + status = ParameterStatus.WARNING; + status.setDetails("A tournament size equal to population size results in the same individual being selected every time."); + } else { + status = ParameterStatus.VALID; + } + } + }; + report = new BooleanParameter(false, "Report") { + @Override + public void validate(Boolean newValue) { + // blank } }; } @Override public Parameter<?>[] getLocalParameters() { - return new Parameter[] {tournamentSize}; + return new Parameter[] {tournamentSize, report}; } @Override - public void evolve(Population population, Mutator mutator, - Resources parameters) { - tournamentSize.set(tournamentSize.get() + 1); - // TODO implement this - + public void evolve(Population population, Mutator mutator, Resources resources) { + /* Create an entirely new population by isolating random subsets of + * the original population and choosing the fittest individual within + * that subset. Each chosen individual is mutated and copied back into the + * population. + */ + Chromosome[] newPopulation = new Chromosome[resources.populationSize()]; + + // start by selecting all of the chromosomes that will be promoted + for (int i = 0; i < resources.populationSize(); i++) { + if (report.get()) resources.reportln("[ES] Starting tournament " + i); + + /* the population is sorted in ascending order of fitness, + * meaning the higher the index of the contender, the fitter + * it is + */ + int[] contenders = new int[tournamentSize.get()]; + for (int t = 0; t < tournamentSize.get() - 1; t++) { + contenders[t] = resources.getRandomInt(resources.populationSize()); + } + if (report.get()) resources.reportln("[ES] Selected contenders: " + Arrays.toString(contenders)); + Arrays.sort(contenders); + if (report.get()) resources.reportln("[ES] Chr " + contenders[contenders.length - 1] + " wins the tournament, copying and mutating..."); + // create a copy of the selected chromosome and mutate it + newPopulation[i] = new Chromosome(population.getChromosome(contenders[contenders.length - 1])); + mutator.mutate(newPopulation[i], resources); + } + if (report.get()) resources.reportln("[ES] Tournaments are finished, copying new chromosomes into population"); + // newPopulation has been generated, copy into the population + for (int c = 0; c < resources.populationSize(); c++) { + population.getChromosome(c).copyGenes(newPopulation[c]); + } + + if (report.get()) resources.reportln("[ES] Generation is complete"); } @Override |