This is an automated email from the ASF dual-hosted git repository. erans pushed a commit to branch feature__MATH-1563__genetic_algorithm in repository https://gitbox.apache.org/repos/asf/commons-math.git
The following commit(s) were added to refs/heads/feature__MATH-1563__genetic_algorithm by this push: new ddfd5bf85 MATH-1618: Design proposal (WIP). ddfd5bf85 is described below commit ddfd5bf859d04cc5da604b20021ceaba9de7def6 Author: Gilles Sadowski <gillese...@gmail.com> AuthorDate: Sun May 1 22:19:08 2022 +0200 MATH-1618: Design proposal (WIP). --- .../{Coordinate.java => Coordinates.java} | 25 +-- .../ga/mathfunctions/MathFunctionOptimizer.java | 45 ++-- .../ga/mathfunctions/MathFunctionOptimizer2.java | 189 ++++++++++++++++ .../examples/ga/mathfunctions/StandAlone.java | 81 +++++-- commons-math-examples/examples-ga/pom.xml | 5 + commons-math-examples/pom.xml | 6 + commons-math-ga2/LICENCE | 201 +++++++++++++++++ commons-math-ga2/NOTICE | 5 + .../examples-ga => commons-math-ga2}/pom.xml | 36 ++-- .../commons/math4/ga2/AbstractCrossover.java | 78 +++++++ .../apache/commons/math4/ga2/AbstractMutation.java | 95 ++++++++ .../apache/commons/math4/ga2/ApplicationRate.java | 92 ++++++++ .../commons/math4/ga2/ChromosomeFactory.java | 40 +--- .../apache/commons/math4/ga2/FitnessService.java | 47 ++-- .../commons/math4/ga2/GenerationCallback.java | 41 +--- .../commons/math4/ga2/GeneticAlgorithmFactory.java | 240 +++++++++++++++++++++ .../apache/commons/math4/ga2/GeneticOperator.java | 45 ++-- .../org/apache/commons/math4/ga2/Population.java | 191 ++++++++++++++++ .../org/apache/commons/math4/ga2/Selection.java | 43 ++-- .../ga2/fitness/FitnessConcurrentCalculator.java | 98 +++++++++ .../commons/math4/ga2/fitness/package-info.java | 38 +--- .../commons/math4/ga2/gene/binary/Chromosome.java | 109 ++++++++++ .../commons/math4/ga2/gene/binary/Mutation.java | 50 ++--- .../math4/ga2/gene/binary/OnePointCrossover.java | 75 +++++++ .../commons/math4/ga2/gene/binary/Operators.java | 41 ++-- .../math4/ga2/gene/binary/package-info.java | 38 +--- .../org/apache/commons/math4/ga2/package-info.java | 38 +--- .../math4/ga2/rate/AverageRankLinearRate.java | 52 +++++ .../commons/math4/ga2/rate/ConstantRate.java | 38 ++-- .../commons/math4/ga2/rate/RateGenerators.java | 46 ++-- .../commons/math4/ga2/rate/package-info.java | 38 +--- .../commons/math4/ga2/select/Tournament.java | 77 +++++++ .../commons/math4/ga2/select/package-info.java | 38 +--- .../commons/math4/ga2/stop/UnchangedFitness.java | 116 ++++++++++ .../commons/math4/ga2/stop/package-info.java | 38 +--- pom.xml | 1 + .../checkstyle/checkstyle-suppressions.xml | 3 + 37 files changed, 1892 insertions(+), 547 deletions(-) diff --git a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java b/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinates.java similarity index 69% copy from commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java copy to commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinates.java index eee31fbc8..30ce0d63d 100644 --- a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java +++ b/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinates.java @@ -16,31 +16,28 @@ */ package org.apache.commons.math4.examples.ga.mathfunctions; -import java.util.List; +import java.util.Arrays; /** - * This class represents the coordinate of the problem domain i.e. the phenotype - * of chromosome. + * Chromosome phenotype. */ -public class Coordinate { - - /** coordinate of all dimensions. **/ - private final List<Double> values; +public class Coordinates { + /** Coordinates. **/ + private final double[] values; /** - * constructor. - * @param values coordinates of all dimensions. + * @param values Coordinates. */ - public Coordinate(List<Double> values) { - this.values = values; + public Coordinates(double[] values) { + this.values = values.clone(); } /** * Returns the values of all coordinates. * @return values of coordinates */ - public List<Double> getValues() { - return values; + public double[] getValues() { + return values.clone(); } /** @@ -48,7 +45,7 @@ public class Coordinate { */ @Override public String toString() { - return "Coordinate [values=" + values + "]"; + return "Coordinates [values=" + Arrays.toString(values) + "]"; } } diff --git a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/MathFunctionOptimizer.java b/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/MathFunctionOptimizer.java index 73b00a08e..4d8543ba6 100644 --- a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/MathFunctionOptimizer.java +++ b/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/MathFunctionOptimizer.java @@ -17,9 +17,6 @@ package org.apache.commons.math4.examples.ga.mathfunctions; -import java.util.ArrayList; -import java.util.List; - import org.apache.commons.math4.ga.GeneticAlgorithm; import org.apache.commons.math4.ga.chromosome.BinaryChromosome; import org.apache.commons.math4.ga.chromosome.Chromosome; @@ -65,50 +62,52 @@ public final class MathFunctionOptimizer { int populationSize) { // initialize a new genetic algorithm - final GeneticAlgorithm<Coordinate> ga = new GeneticAlgorithm<Coordinate>( - new OnePointBinaryCrossover<Coordinate>(), crossoverRate, new BinaryMutation<Coordinate>(), - mutationRate, new TournamentSelection<Coordinate>(tournamentSize), elitismRate, - new PopulationStatisticsLogger<Coordinate>()); + final GeneticAlgorithm<Coordinates> ga = new GeneticAlgorithm<Coordinates>( + new OnePointBinaryCrossover<Coordinates>(), crossoverRate, new BinaryMutation<Coordinates>(), + mutationRate, new TournamentSelection<Coordinates>(tournamentSize), elitismRate, + new PopulationStatisticsLogger<Coordinates>()); // stopping condition - final StoppingCondition<Coordinate> stopCond = new UnchangedBestFitness<>( + final StoppingCondition<Coordinates> stopCond = new UnchangedBestFitness<>( generationCountWithUnchangedBestFitness); // run the algorithm - final Population<Coordinate> finalPopulation = ga.evolve(getInitialPopulation(dimension, populationSize), + final Population<Coordinates> finalPopulation = ga.evolve(getInitialPopulation(dimension, populationSize), stopCond, Runtime.getRuntime().availableProcessors()); // best chromosome from the final population - final Chromosome<Coordinate> bestFinal = finalPopulation.getFittestChromosome(); + final Chromosome<Coordinates> bestFinal = finalPopulation.getFittestChromosome(); logger.info(bestFinal.toString()); } - private static Population<Coordinate> getInitialPopulation(int dimension, int populationSize) { - final Population<Coordinate> population = new ListPopulation<>(populationSize); + private static Population<Coordinates> getInitialPopulation(int dimension, int populationSize) { + final Population<Coordinates> population = new ListPopulation<>(populationSize); for (int i = 0; i < populationSize; i++) { population.addChromosome(BinaryChromosome - .<Coordinate>randomChromosome(dimension * CHROMOSOME_LENGTH_PER_DIMENSION, coordinate -> { + .<Coordinates>randomChromosome(dimension * CHROMOSOME_LENGTH_PER_DIMENSION, coordinate -> { double sumOfSquare = 0.0; - for (Double value : coordinate.getValues()) { - sumOfSquare += Math.pow(value, 2); + for (double value : coordinate.getValues()) { + sumOfSquare += Math.pow(value - 10, 2); } return -Math.pow(sumOfSquare, .25) * (Math.pow(Math.sin(50 * Math.pow(sumOfSquare, .1)), 2) + 1); }, chromosome -> { - final BinaryChromosome<Coordinate> binaryChromosome = - (BinaryChromosome<Coordinate>) chromosome; + final BinaryChromosome<Coordinates> binaryChromosome = + (BinaryChromosome<Coordinates>) chromosome; final long length = binaryChromosome.getLength(); - final List<Double> coordinates = new ArrayList<>(); - - for (int j = 0; j < length; j += 12) { - final String dimensionStrValue = binaryChromosome.getStringRepresentation(j, j + 12); - coordinates.add(Integer.parseUnsignedInt(dimensionStrValue, 2) / 100d); + final double[] coordinates = new double[dimension]; + for (int j = 0; j < dimension; j++) { + final int start = j * CHROMOSOME_LENGTH_PER_DIMENSION; + final String dimensionStrValue = + binaryChromosome.getStringRepresentation(start, + start + CHROMOSOME_LENGTH_PER_DIMENSION); + coordinates[j] = Integer.parseInt(dimensionStrValue, 2) / 100d; } - return new Coordinate(coordinates); + return new Coordinates(coordinates); })); } return population; diff --git a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/MathFunctionOptimizer2.java b/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/MathFunctionOptimizer2.java new file mode 100644 index 000000000..e8a16a375 --- /dev/null +++ b/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/MathFunctionOptimizer2.java @@ -0,0 +1,189 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.commons.math4.examples.ga.mathfunctions; + +import java.util.BitSet; +import java.util.Map; +import java.util.HashMap; +import java.util.List; +import java.util.function.Function; +import java.util.function.ToDoubleFunction; +import java.util.function.Predicate; +import java.util.concurrent.Executors; +import java.util.concurrent.ExecutorService; +import java.util.concurrent.Callable; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; +import org.apache.commons.rng.simple.RandomSource; +import org.apache.commons.math3.stat.descriptive.SummaryStatistics; +import org.apache.commons.math4.ga2.gene.binary.Chromosome; +import org.apache.commons.math4.ga2.gene.binary.Operators; +import org.apache.commons.math4.ga2.Population; +import org.apache.commons.math4.ga2.GeneticOperator; +import org.apache.commons.math4.ga2.FitnessService; +import org.apache.commons.math4.ga2.Selection; +import org.apache.commons.math4.ga2.GeneticAlgorithmFactory; +import org.apache.commons.math4.ga2.ChromosomeFactory; +import org.apache.commons.math4.ga2.GenerationCallback; +import org.apache.commons.math4.ga2.ApplicationRate; +import org.apache.commons.math4.ga2.stop.UnchangedFitness; +import org.apache.commons.math4.ga2.select.Tournament; +import org.apache.commons.math4.ga2.fitness.FitnessConcurrentCalculator; +import org.apache.commons.math4.ga2.rate.RateGenerators; + +/** + * Optimizer example. + */ +public final class MathFunctionOptimizer2 { + /** Chromosome length. */ + private static final int GENES_PER_DIMENSION = 12; + /** Scaling factor. */ + private static final double SCALE = 0.01; + + /** + * @param dim Dimension. + * @param crossover Crossover rate. + * @param mutation Mutation rate. + * @param elitism Elitism rate. + * @param tournament Tournament size. + * @param numGeneration Number of generations unchanged best fitness. + * @param popSize Population size. + * @param jobs Number of threads for computing the fitnesses. + */ + public void optimize(int dim, + double crossover, + double mutation, + double elitism, + int tournament, + int numGeneration, + int popSize, + int jobs) { + final int numGenes = dim * GENES_PER_DIMENSION; + + // Random genotypes generator. + final ChromosomeFactory<Chromosome> initFactory = + new Chromosome.RandomFactory(RandomSource.ISAAC); + + // Genotype to phenotype decoder. + final Function<Chromosome, Coordinates> decoder = gene -> { + final BitSet rep = gene.asBitSet(); + final double[] coord = new double[dim]; + for (int i = 0; i < dim; i++) { + final int start = i * GENES_PER_DIMENSION; + final long[] coordRep = rep.get(start, start + GENES_PER_DIMENSION).toLongArray(); + if (coordRep.length == 0) { + coord[i] = 0; + } else if (coordRep.length == 1) { + coord[i] = coordRep[0] * SCALE; + } else { + // Should not happen. + throw new IllegalStateException("Unsupported representation size: " + + coordRep.length); + } + } + return new Coordinates(coord); + }; + + // Stopping condition (not thread-safe). + final Predicate<Population<Chromosome, Coordinates>> stop = + new UnchangedFitness(UnchangedFitness.Type.BEST, + numGeneration); + + final ToDoubleFunction<Coordinates> fitnessFunction = coord -> { + double s = 0; + for (double v : coord.getValues()) { + final double vM10 = v - 10; + s += vM10 * vM10; + } + final double a = Math.sin(50 * Math.pow(s, 0.1)); + final double b = -Math.pow(s, 0.25) * (a * a + 1); + return b; + }; + + // Setup for parallel computation of fitnesses. + final ExecutorService exec = Executors.newFixedThreadPool(jobs); + final FitnessService<Chromosome, Coordinates> fitness = + new FitnessConcurrentCalculator(fitnessFunction, + exec); + + // Parents selection scheme. + final Selection<Chromosome, Coordinates> selection = + new Tournament(tournament, + RandomSource.SPLIT_MIX_64); + + // Offspring generators. + final Map<GeneticOperator<Chromosome>, ApplicationRate> operators = new HashMap<>(); + operators.put(Operators.mutation(mutation), RateGenerators.constant(1)); + operators.put(Operators.onePointCrossover(), RateGenerators.constant(crossover)); + + final Callable<Population<Chromosome, Coordinates>> ga = + GeneticAlgorithmFactory.<Chromosome, Coordinates>create(numGenes, + initFactory, + popSize, + decoder, + stop, + fitness, + selection, + operators, + elitism, + RandomSource.KISS, + new GenerationLogger()); + + try { + // Run the GA and retrieve contents of the last generation. + final List<Map.Entry<Chromosome, Double>> lastGen = ga.call().contents(true); + final Map.Entry<Chromosome, Double> top = lastGen.get(0); + final Coordinates best = decoder.apply(top.getKey()); + final double bestValue = fitnessFunction.applyAsDouble(best); + + // CHECKSTYLE: stop all + System.out.println("fitness=" + bestValue + " for " + best.toString()); + // CHECKSTYLE: resume all + } catch (Exception e) { + // Rethrow. + throw new RuntimeException(e); + } finally { + exec.shutdown(); + } + } +} + +/** + * Log evolution. + */ +class GenerationLogger implements GenerationCallback<Chromosome> { + /** Logger. */ + private static final Logger LOG = LoggerFactory.getLogger(GenerationLogger.class); + + /** {@inheritDoc} */ + @Override + public void update(List<Map.Entry<Chromosome, Double>> contents, + int generation) { + final SummaryStatistics stats = new SummaryStatistics(); + for (Map.Entry<Chromosome, Double> e : contents) { + stats.addValue(e.getValue()); + } + + LOG.info("fitness at generation {}: min={} max={} mean={} stddev={}", + generation, + stats.getMin(), + stats.getMax(), + stats.getMean(), + stats.getStandardDeviation()); + } +} diff --git a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/StandAlone.java b/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/StandAlone.java index 4d54ac58f..ea4f406e0 100644 --- a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/StandAlone.java +++ b/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/StandAlone.java @@ -25,63 +25,100 @@ import picocli.CommandLine.Option; @Command(name = "mathfunction-optimizer", mixinStandardHelpOptions = true, version = "mathfunction-optimizer 1.0") public class StandAlone implements Runnable { - /** number of dimension. **/ + /** number of dimension. */ @Option(names = "-d", paramLabel = "DIMENSION", required = true, description = "Dimension of problem domain.") private int dimension; - /** size of tournament. **/ + /** size of tournament. */ @Option(names = "-t", paramLabel = "TOURNAMENT_SIZE", required = true, description = "Tournament size.") private int tournamentSize; - /** size of population. **/ + /** size of population. */ @Option(names = "-p", paramLabel = "POPULATION_SIZE", required = true, description = "Size of population.") private int populationSize; - /** rate of crossover. **/ + /** rate of crossover. */ @Option(names = "-c", paramLabel = "CROSSOVER_RATE", description = "Crossover rate (default: ${DEFAULT-VALUE}).") private double crossoverRate = 1.0; - /** rate of elitism. **/ + /** rate of elitism. */ @Option(names = "-e", paramLabel = "ELITISM_RATE", description = "Elitism rate (default: ${DEFAULT-VALUE}).") private double elitismRate = 0.25; - /** rate of mutation. **/ + /** rate of mutation. */ @Option(names = "-m", paramLabel = "MUTATION_RATE", description = "Mutation rate (default: ${DEFAULT-VALUE}).") private double mutationRate = 0.01; - /** number of generations with unchanged best fitness. **/ + /** number of generations with unchanged best fitness. */ @Option(names = "-g", paramLabel = "GENERATIONS_EVOLVED_WITH_UNCHANGED_BEST_FITNESS", description = "No of generations evolved with unchanged best fitness (default: ${DEFAULT-VALUE}).") private int generationsEvolvedWithUnchangedBestFitness = 50; - /** indicates whether the algorithm should be legacy or not. **/ - @Option(names = "--legacy", description = "Indicates which version of algorithm to execute current or legacy.") - private boolean legacy; + /** indicates what to run. */ + @Option(names = "--api", + description = "Indicates which version of the algorithm to execute: ${COMPLETION-CANDIDATES}.") + private API variant; + + /** Number of threads for computing fitnesses. */ + @Option(names = { "--jobs", "-j" }, description = "Number of fitness threads (default: ${DEFAULT-VALUE}).") + private int numThreads = 1; public static void main(String[] args) { CommandLine.run(new StandAlone(), args); } - /** - * This method is responsible for validating input and then invoking math - * function optimizer. - */ + enum API { + /** Legacy. */ + LEGACY, + /** Proposal. */ + AVIJIT, + /** Proposal. */ + GILLES + } + + /** {@inheritDoc} */ @Override public void run() { - - // validate all input options. validateInput(); - if (!legacy) { - new MathFunctionOptimizer().optimize(dimension, crossoverRate, mutationRate, elitismRate, tournamentSize, - generationsEvolvedWithUnchangedBestFitness, populationSize); - } else { - new LegacyMathFunctionOptimizer().optimize(dimension, crossoverRate, mutationRate, elitismRate, - tournamentSize, generationsEvolvedWithUnchangedBestFitness, populationSize); + switch (variant) { + case LEGACY: + new LegacyMathFunctionOptimizer().optimize(dimension, + crossoverRate, + mutationRate, + elitismRate, + tournamentSize, + generationsEvolvedWithUnchangedBestFitness, + populationSize); + break; + case AVIJIT: + new MathFunctionOptimizer().optimize(dimension, + crossoverRate, + mutationRate, + elitismRate, + tournamentSize, + generationsEvolvedWithUnchangedBestFitness, + populationSize); + break; + case GILLES: + new MathFunctionOptimizer2().optimize(dimension, + crossoverRate, + mutationRate, + elitismRate, + tournamentSize, + generationsEvolvedWithUnchangedBestFitness, + populationSize, + numThreads); + break; + default: + throw new IllegalStateException(); } } + /** + * Validate algorithm parameters. + */ private void validateInput() { if (this.dimension < 1) { throw new IllegalArgumentException("Dimension should be > 0."); diff --git a/commons-math-examples/examples-ga/pom.xml b/commons-math-examples/examples-ga/pom.xml index 462daf2c4..51a9f207b 100644 --- a/commons-math-examples/examples-ga/pom.xml +++ b/commons-math-examples/examples-ga/pom.xml @@ -40,6 +40,11 @@ <artifactId>commons-math4-ga</artifactId> </dependency> + <dependency> + <groupId>org.apache.commons</groupId> + <artifactId>commons-math4-ga2</artifactId> + </dependency> + <dependency> <groupId>info.picocli</groupId> <artifactId>picocli</artifactId> diff --git a/commons-math-examples/pom.xml b/commons-math-examples/pom.xml index c848836c1..2be02a1b8 100644 --- a/commons-math-examples/pom.xml +++ b/commons-math-examples/pom.xml @@ -75,6 +75,12 @@ <version>${math.version}</version> </dependency> + <dependency> + <groupId>org.apache.commons</groupId> + <artifactId>commons-math4-ga2</artifactId> + <version>${math.version}</version> + </dependency> + <dependency> <groupId>org.apache.commons</groupId> <artifactId>commons-math4-legacy</artifactId> diff --git a/commons-math-ga2/LICENCE b/commons-math-ga2/LICENCE new file mode 100644 index 000000000..261eeb9e9 --- /dev/null +++ b/commons-math-ga2/LICENCE @@ -0,0 +1,201 @@ + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + + TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + + 1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + + 2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + + 3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + + 4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + + 5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + + 6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + + 7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + + 8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + + 9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + + END OF TERMS AND CONDITIONS + + APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + + Copyright [yyyy] [name of copyright owner] + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. diff --git a/commons-math-ga2/NOTICE b/commons-math-ga2/NOTICE new file mode 100644 index 000000000..28031e8ef --- /dev/null +++ b/commons-math-ga2/NOTICE @@ -0,0 +1,5 @@ +Apache Commons Math +Copyright 2001-2022 The Apache Software Foundation + +This product includes software developed at +The Apache Software Foundation (http://www.apache.org/). diff --git a/commons-math-examples/examples-ga/pom.xml b/commons-math-ga2/pom.xml similarity index 61% copy from commons-math-examples/examples-ga/pom.xml copy to commons-math-ga2/pom.xml index 462daf2c4..fe9407878 100644 --- a/commons-math-examples/examples-ga/pom.xml +++ b/commons-math-ga2/pom.xml @@ -1,4 +1,4 @@ -<?xml version="1.0"?> +<?xml version="1.0" encoding="UTF-8"?> <!-- Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements. See the NOTICE file distributed with @@ -21,42 +21,44 @@ <modelVersion>4.0.0</modelVersion> <parent> <groupId>org.apache.commons</groupId> - <artifactId>commons-math-examples</artifactId> + <artifactId>commons-math-parent</artifactId> <version>4.0-SNAPSHOT</version> </parent> - <artifactId>examples-ga</artifactId> - <packaging>pom</packaging> - <name>GA</name> + <artifactId>commons-math4-ga2</artifactId> + <name>Genetic Algorithms</name> + + <description>Genetic Algorithms</description> <properties> + <!-- The Java Module System Name --> + <commons.module.name>org.apache.commons.math4.ga2</commons.module.name> + <!-- This value must reflect the current name of the base package. --> + <commons.osgi.symbolicName>org.apache.commons.math4.ga2</commons.osgi.symbolicName> + <!-- OSGi --> + <commons.osgi.export>org.apache.commons.math4.ga</commons.osgi.export> <!-- Workaround to avoid duplicating config files. --> - <math.parent.dir>${basedir}/../..</math.parent.dir> + <math.parent.dir>${basedir}/..</math.parent.dir> + <math.slf4j.version>1.7.32</math.slf4j.version> </properties> <dependencies> <dependency> <groupId>org.apache.commons</groupId> - <artifactId>commons-math4-ga</artifactId> + <artifactId>commons-rng-simple</artifactId> </dependency> <dependency> - <groupId>info.picocli</groupId> - <artifactId>picocli</artifactId> + <groupId>org.apache.commons</groupId> + <artifactId>commons-rng-sampling</artifactId> </dependency> <dependency> <groupId>org.slf4j</groupId> - <artifactId>slf4j-simple</artifactId> + <artifactId>slf4j-api</artifactId> + <version>${math.slf4j.version}</version> </dependency> </dependencies> - <modules> - <module>examples-ga-math-functions</module> - <module>examples-ga-math-functions-adaptive</module> - <module>examples-ga-tsp</module> - <module>examples-parallel-ga-math-functions</module> - </modules> - </project> diff --git a/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/AbstractCrossover.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/AbstractCrossover.java new file mode 100644 index 000000000..df003b79c --- /dev/null +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/AbstractCrossover.java @@ -0,0 +1,78 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.commons.math4.ga2; + +import java.util.List; +import org.apache.commons.rng.UniformRandomProvider; + +/** + * Base class for "crossover" operators. + * + * @param <G> Genotype. + */ +public abstract class AbstractCrossover<G> implements GeneticOperator<G> { + /** Number of parents and number of offsprings. */ + private static final int NUM_CHROMOSOMES = 2; + + /** {@inheritDoc} */ + @Override + public final int numberOfParents() { + return NUM_CHROMOSOMES; + } + + /** {@inheritDoc} */ + @Override + public final int numberOfOffsprings() { + return NUM_CHROMOSOMES; + } + + /** + * {@inheritDoc} + * + * @throws IllegalArgumentException if there are less than two parents + * or they are of different sizes. + */ + @Override + public List<G> apply(List<G> parents, + UniformRandomProvider rng) { + if (parents.size() != NUM_CHROMOSOMES) { + throw new IllegalArgumentException("Unexpected number of parents"); + } + + final List<G> offsprings = apply(parents.get(0), + parents.get(1), + rng); + if (offsprings.size() != NUM_CHROMOSOMES) { + throw new IllegalArgumentException("Unexpected number of offsprings"); + } + + return offsprings; + } + + /** + * Unconditionally apply operator. + * + * @param parent1 Parent. + * @param parent2 Parent. + * @param rng RNG. + * @return a list containing two offpsrings. + */ + protected abstract List<G> apply(G parent1, + G parent2, + UniformRandomProvider rng); +} diff --git a/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/AbstractMutation.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/AbstractMutation.java new file mode 100644 index 000000000..c00e72ab6 --- /dev/null +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/AbstractMutation.java @@ -0,0 +1,95 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.commons.math4.ga2; + +import java.util.List; +import java.util.ArrayList; +import org.apache.commons.rng.UniformRandomProvider; + +/** + * Base class for "mutation" operators. + * + * @param <G> Genotype. + */ +public abstract class AbstractMutation<G> implements GeneticOperator<G> { + /** Number of parents and number of offsprings. */ + private static final int NUM_CHROMOSOMES = 1; + /** Mutation probability, per gene. */ + private final double probability; + + /** + * @param probability Probability that any gene should mutate. + */ + protected AbstractMutation(double probability) { + if (probability <= 0 || + probability > 1) { + throw new IllegalArgumentException("Out of range"); + } + + this.probability = probability; + } + + /** @return the probability of gene mutation. */ + protected double getProbability() { + return probability; + } + + /** {@inheritDoc} */ + @Override + public final int numberOfParents() { + return NUM_CHROMOSOMES; + } + + /** {@inheritDoc} */ + @Override + public final int numberOfOffsprings() { + return NUM_CHROMOSOMES; + } + + /** + * {@inheritDoc} + * + * @throws IllegalArgumentException if there are less than two parents + * or they are of different sizes. + */ + @Override + public List<G> apply(List<G> parents, + UniformRandomProvider rng) { + if (parents.size() != NUM_CHROMOSOMES) { + throw new IllegalArgumentException("Incompatible number of parents"); + } + + final G mutated = apply(parents.get(0), + rng); + + final List<G> offsprings = new ArrayList<>(1); + offsprings.add(mutated); + + return offsprings; + } + + /** + * Apply operator. + * + * @param parent Parent. + * @param rng RNG. + * @return a list containing one offpsring. + */ + protected abstract G apply(G parent, + UniformRandomProvider rng); +} diff --git a/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/ApplicationRate.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/ApplicationRate.java new file mode 100644 index 000000000..46c148657 --- /dev/null +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/ApplicationRate.java @@ -0,0 +1,92 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math4.ga2; + +import java.util.List; + +/** + * Computes the probability to apply a genetic operator (the higher the + * probability, the higher the chance that offsrpings will be different + * from their parents. + */ +public abstract class ApplicationRate { + /** Minimum probability. */ + private final double min; + /** Maximum probability. */ + private final double max; + + /** + * @param min Minimum probability. + * @param max Maximum probability. + * @throws IllegalArgumentException if either probability is out of + * the {@code [0 1]} interval or {@code min > max}. + */ + protected ApplicationRate(double min, + double max) { + if (min < 0 || + min > 1) { + throw new IllegalArgumentException("Probability (min) is out of range"); + } + if (max < 0 || + max > 1) { + throw new IllegalArgumentException("Probability (max) is out of range"); + } + if (min >= max) { + throw new IllegalArgumentException("max <= min"); + } + + this.min = min; + this.max = max; + } + + /** + * @param p Probability. + * @throws IllegalArgumentException if the probability is out of + * the {@code [0 1]} interval. + */ + protected ApplicationRate(double p) { + if (p < 0 || + p > 1) { + throw new IllegalArgumentException("Probability is out of range"); + } + this.min = p; + this.max = p; + } + + /** @return the minimum probability. */ + protected double min() { + return min; + } + /** @return the maximum probability. */ + protected double max() { + return max; + } + + /** + * Computes the probability that some operator will be applied to the + * given {@code chromosomes}. + * + * @param population Population. + * @param chromosomes Chromosomes that belong to the {@code population}. + * @return the probability to apply the operator. + * + * @param <G> Genotype. + * @param <P> Phenotype. + */ + public abstract <G, P> double compute(Population<G, P> population, + List<G> chromosomes); +} diff --git a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/ChromosomeFactory.java similarity index 52% copy from commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java copy to commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/ChromosomeFactory.java index eee31fbc8..4a615eef9 100644 --- a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/ChromosomeFactory.java @@ -14,41 +14,17 @@ * See the License for the specific language governing permissions and * limitations under the License. */ -package org.apache.commons.math4.examples.ga.mathfunctions; - -import java.util.List; +package org.apache.commons.math4.ga2; /** - * This class represents the coordinate of the problem domain i.e. the phenotype - * of chromosome. + * Chromosome generator. + * + * @param <G> Genotype. */ -public class Coordinate { - - /** coordinate of all dimensions. **/ - private final List<Double> values; - +public interface ChromosomeFactory<G> { /** - * constructor. - * @param values coordinates of all dimensions. + * @param size Number of genes. + * @return a chromosome of the specified {@code size}. */ - public Coordinate(List<Double> values) { - this.values = values; - } - - /** - * Returns the values of all coordinates. - * @return values of coordinates - */ - public List<Double> getValues() { - return values; - } - - /** - * {@inheritDoc} - */ - @Override - public String toString() { - return "Coordinate [values=" + values + "]"; - } - + G with(int size); } diff --git a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/FitnessService.java similarity index 52% copy from commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java copy to commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/FitnessService.java index eee31fbc8..84ba0b6d0 100644 --- a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/FitnessService.java @@ -14,41 +14,26 @@ * See the License for the specific language governing permissions and * limitations under the License. */ -package org.apache.commons.math4.examples.ga.mathfunctions; -import java.util.List; +package org.apache.commons.math4.ga2; + +import java.util.Collection; +import java.util.function.Function; /** - * This class represents the coordinate of the problem domain i.e. the phenotype - * of chromosome. + * Fitness function. + * + * @param <G> Genotype. + * @param <P> Phenotype. */ -public class Coordinate { - - /** coordinate of all dimensions. **/ - private final List<Double> values; - +public interface FitnessService<G, P> { /** - * constructor. - * @param values coordinates of all dimensions. + * Computes the fitness value. + * + * @param decoder Genotype to phenotype converter. + * @param chromosomes Chromosomes. + * @return the fitness values, in the same order as the input. */ - public Coordinate(List<Double> values) { - this.values = values; - } - - /** - * Returns the values of all coordinates. - * @return values of coordinates - */ - public List<Double> getValues() { - return values; - } - - /** - * {@inheritDoc} - */ - @Override - public String toString() { - return "Coordinate [values=" + values + "]"; - } - + double[] apply(Function<G, P> decoder, + Collection<G> chromosomes); } diff --git a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/GenerationCallback.java similarity index 53% copy from commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java copy to commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/GenerationCallback.java index eee31fbc8..6e7163176 100644 --- a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/GenerationCallback.java @@ -14,41 +14,22 @@ * See the License for the specific language governing permissions and * limitations under the License. */ -package org.apache.commons.math4.examples.ga.mathfunctions; +package org.apache.commons.math4.ga2; import java.util.List; +import java.util.Map; /** - * This class represents the coordinate of the problem domain i.e. the phenotype - * of chromosome. + * Function for passing a copy of the current population contents to + * external code. + * + * @param <G> Genotype. */ -public class Coordinate { - - /** coordinate of all dimensions. **/ - private final List<Double> values; - - /** - * constructor. - * @param values coordinates of all dimensions. - */ - public Coordinate(List<Double> values) { - this.values = values; - } - +public interface GenerationCallback<G> { /** - * Returns the values of all coordinates. - * @return values of coordinates + * @param contents Population (sorted in decreasing order of fitness). + * @param generation Current generation. */ - public List<Double> getValues() { - return values; - } - - /** - * {@inheritDoc} - */ - @Override - public String toString() { - return "Coordinate [values=" + values + "]"; - } - + void update(List<Map.Entry<G, Double>> contents, + int generation); } diff --git a/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/GeneticAlgorithmFactory.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/GeneticAlgorithmFactory.java new file mode 100644 index 000000000..40ec98249 --- /dev/null +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/GeneticAlgorithmFactory.java @@ -0,0 +1,240 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math4.ga2; + +import java.util.Collection; +import java.util.Collections; +import java.util.List; +import java.util.ArrayList; +import java.util.Map; +import java.util.concurrent.Callable; +import java.util.function.Function; +import java.util.function.Predicate; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; +import org.apache.commons.rng.simple.RandomSource; +import org.apache.commons.rng.UniformRandomProvider; + +/** + * Genetic algorithm factory. + * + * @param <G> Genotype. + * @param <P> Phenotype. + */ +public final class GeneticAlgorithmFactory<G, P> implements Callable<Population<G, P>> { + /** Logger. */ + private static final Logger LOG = LoggerFactory.getLogger(GeneticAlgorithmFactory.class); + /** Initial list of chromosomes. */ + private final Collection<G> init; + /** Genotype to phenotype converter. */ + private final Function<G, P> decoder; + /** Criterion for stopping the evolution. */ + private final Predicate<Population<G, P>> stop; + /** Fitness calculator. */ + private final FitnessService<G, P> fitness; + /** Chromosome selector. */ + private final Selection<G, P> selection; + /** Offspring generators. */ + private final Map<GeneticOperator<G>, ApplicationRate> operators; + /** Elitism. */ + private final double elitism; + /** RNG. */ + private final RandomSource random; + /** Callback. */ + private final GenerationCallback<G> callback; + + /** + * @param init Initial list of chromosomes. + * @param decoder Genotype to phenotype converter. + * @param stop Criterion for stopping the evolution. + * @param fitness Fitness calculator. + * @param selection Chromosome selector. + * @param operators Offspring generators. + * @param elitism Fraction of the population that will be unconditionally + * transferred to the next generation. + * @param random Source of randomness. + * @param callback Callback. + */ + private GeneticAlgorithmFactory(Collection<G> init, + Function<G, P> decoder, + Predicate<Population<G, P>> stop, + FitnessService<G, P> fitness, + Selection<G, P> selection, + Map<GeneticOperator<G>, ApplicationRate> operators, + double elitism, + RandomSource random, + GenerationCallback<G> callback) { + this.init = init; + this.decoder = decoder; + this.stop = stop; + this.fitness = fitness; + this.selection = selection; + this.operators = Collections.unmodifiableMap(operators); + this.elitism = elitism; + this.random = random; + this.callback = callback; + } + + /** + * @param init Initial list of chromosomes. + * @param decoder Genotype to phenotype converter. + * @param stop Criterion for stopping the evolution. + * @param fitness Fitness calculator. + * @param selection Chromosome selector. + * @param operators Offspring generators. + * @param elitism Fraction of the population that will be unconditionally + * transferred to the next generation. + * @param random Source of randomness. + * @param callback Callback. + * @return a new instance. + * + * @param <G> Genotype. + * @param <P> Phenotype. + */ + public static <G, P> Callable<Population<G, P>> create(Collection<G> init, + Function<G, P> decoder, + Predicate<Population<G, P>> stop, + FitnessService<G, P> fitness, + Selection<G, P> selection, + Map<GeneticOperator<G>, ApplicationRate> operators, + double elitism, + RandomSource random, + GenerationCallback<G> callback) { + return new GeneticAlgorithmFactory<>(init, + decoder, + stop, + fitness, + selection, + operators, + elitism, + random, + callback); + } + + /** + * @param chromosomeSize Number of genes. + * @param initFactory Factory for creating the initial chromosomes. + * @param populationSize Number of chromosomes per generation. + * @param decoder Genotype to phenotype converter. + * @param stop Criterion for stopping the evolution. + * @param fitness Fitness calculator. + * @param selection Chromosome selector. + * @param operators Offspring generators. + * @param elitism Fraction of the population that will be unconditionally + * transferred to the next generation. + * @param random Source of randomness. + * @param callback Callback. + * @return a new instance. + * + * @param <G> Genotype. + * @param <P> Phenotype. + */ + public static <G, P> Callable<Population<G, P>> create(int chromosomeSize, + ChromosomeFactory<G> initFactory, + int populationSize, + Function<G, P> decoder, + Predicate<Population<G, P>> stop, + FitnessService<G, P> fitness, + Selection<G, P> selection, + Map<GeneticOperator<G>, ApplicationRate> operators, + double elitism, + RandomSource random, + GenerationCallback<G> callback) { + // Create initial population. + final List<G> init = new ArrayList<>(populationSize); + for (int i = 0; i < populationSize; i++) { + init.add(initFactory.with(chromosomeSize)); + } + + return create(init, + decoder, + stop, + fitness, + selection, + operators, + elitism, + random, + callback); + } + + /** {@inheritDoc} */ + @Override + public Population<G, P> call() { + int generation = 0; + final int popSize = init.size(); + + Population<G, P> currentGen = new Population<>(popSize, decoder, fitness); + currentGen.add(init); + final UniformRandomProvider rng = random.create(); + + while (!stop.test(currentGen)) { + ++generation; + final Population<G, P> nextGen = new Population<>(popSize, decoder, fitness); + + applyElitism(currentGen, nextGen); + + // Loop for allowing that some fitnesses are "NaN" (thus + // avoiding that the new generation is not fuly populated). + while (true) { + final int numCandidates = nextGen.allowedInsertions(); + if (numCandidates == 0) { + break; + } + + // Generate and compute fitness. + nextGen.add(currentGen.offsprings(numCandidates, + selection, + operators, + rng)); + + if (nextGen.allowedInsertions() == numCandidates) { + LOG.error("Zero insertion at generation {}", + generation); + } + } + + if (callback != null) { + // Notify caller. + callback.update(nextGen.contents(true), generation); + } + + // Replace with new generation. + currentGen = nextGen; + } + + return currentGen; + } + + /** + * @param from Population from which to retrieve the best individuals. + * @param to Population to which the individuals must be added. + */ + private void applyElitism(Population<G, P> from, + Population<G, P> to) { + final List<Map.Entry<G, Double>> contents = from.contents(true); + + // Number of elite individuals to be transferred. + final int elite = (int) (contents.size() * elitism); + + final List<G> eliteList = new ArrayList<>(elite); + for (int i = 0; i < elite; i++) { + eliteList.add(contents.get(i).getKey()); + } + + to.add(eliteList); + } +} diff --git a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/GeneticOperator.java similarity index 54% copy from commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java copy to commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/GeneticOperator.java index eee31fbc8..31ae216b3 100644 --- a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/GeneticOperator.java @@ -14,41 +14,30 @@ * See the License for the specific language governing permissions and * limitations under the License. */ -package org.apache.commons.math4.examples.ga.mathfunctions; + +package org.apache.commons.math4.ga2; import java.util.List; +import org.apache.commons.rng.UniformRandomProvider; /** - * This class represents the coordinate of the problem domain i.e. the phenotype - * of chromosome. + * Represents any operator that applies on chromosomes of the + * appropriate type. + * + * @param <G> Genotype. */ -public class Coordinate { - - /** coordinate of all dimensions. **/ - private final List<Double> values; +public interface GeneticOperator<G> { + /** @return the number of parents. */ + int numberOfParents(); - /** - * constructor. - * @param values coordinates of all dimensions. - */ - public Coordinate(List<Double> values) { - this.values = values; - } + /** @return the number of offsprings. */ + int numberOfOffsprings(); /** - * Returns the values of all coordinates. - * @return values of coordinates + * @param parents Parents. + * @param rng Source of randomness. + * @return the offsprings. */ - public List<Double> getValues() { - return values; - } - - /** - * {@inheritDoc} - */ - @Override - public String toString() { - return "Coordinate [values=" + values + "]"; - } - + List<G> apply(List<G> parents, + UniformRandomProvider rng); } diff --git a/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/Population.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/Population.java new file mode 100644 index 000000000..a75979acc --- /dev/null +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/Population.java @@ -0,0 +1,191 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math4.ga2; + +import java.util.Collection; +import java.util.Collections; +import java.util.List; +import java.util.ArrayList; +import java.util.Map; +import java.util.AbstractMap; +import java.util.HashMap; +import java.util.function.Function; +import org.apache.commons.rng.UniformRandomProvider; + +/** + * Collection of chromosomes and associated fitness. + * + * Class is <em>not</em> thread-safe. + * + * @param <G> Genotype. + * @param <P> Phenotype. + */ +public class Population<G, P> { + /** Population data (fitness). */ + private final Map<G, Double> chromo2fit = new HashMap<>(); + /** Population data (rank). */ + private final Map<G, Integer> chromo2rank = new HashMap<>(); + /** Decoder. */ + private final Function<G, P> decoder; + /** Fitness function. */ + private final FitnessService<G, P> fitnessCalculator; + /** Maximum population size. */ + private final int maxSize; + + /** + * @param max Maximum allowed number of chromosomes. + * @param geno2pheno Genotype to phenotype converter. + * @param function Fitness calculator. + */ + public Population(int max, + Function<G, P> geno2pheno, + FitnessService<G, P> function) { + maxSize = max; + decoder = geno2pheno; + fitnessCalculator = function; + } + + /** @return the number of free slots in the population. */ + public int allowedInsertions() { + return Math.max(0, maxSize - chromo2fit.size()); + } + + /** @return the number of individuals in the population. */ + public int size() { + return chromo2fit.size(); + } + + /** + * Insert chromosomes into the population. + * Fitness and rank are calculated. + * If the fitness is {@code NaN}, the corresponding chromosome is + * <em>not</em> added to the population. + * + * @param chromosomes Chromosomes. + */ + public void add(Collection<G> chromosomes) { + if (chromosomes.size() > allowedInsertions()) { + throw new IllegalArgumentException("Too many chromosomes"); + } + + final double[] fitness = fitnessCalculator.apply(decoder, chromosomes); + int c = 0; + boolean atLeastOneInsertion = false; + for (G chromosome : chromosomes) { + final double value = fitness[c++]; + if (!Double.isNaN(value)) { + // Insert. + chromo2fit.put(chromosome, value); + atLeastOneInsertion = true; + } + } + + if (atLeastOneInsertion) { // Recompute ranks. + final List<Map.Entry<G, Double>> list = contents(true); + for (int i = 0; i < list.size(); i++) { + chromo2rank.put(list.get(i).getKey(), i); + } + } + } + + /** + * + /** + * Retrieves the rank. + * Ranks are attributed in the range [0, N - 1] (where N is the + * number of individuals in the population) in inverse order of + * fitness (i.e. the chromosome with highest fitness has rank 0). + * + * @param chromosome Chromosome. + * @return the rank of the given {@code chromosome}. + * @throws IllegalArgumentException if the {@code chromosome} does + * not belong to this population. + */ + public int rank(G chromosome) { + final Integer r = chromo2rank.get(chromosome); + + if (r == null) { + throw new IllegalArgumentException("Chromosome not found"); + } + + return r; + } + + /** + * @param sorted If {@code true}, the contents will be sorted in decreasing + * order of fitness. + * @return a copy of the population contents. + */ + public List<Map.Entry<G, Double>> contents(boolean sorted) { + final List<Map.Entry<G, Double>> out = new ArrayList<>(chromo2fit.size()); + + for (Map.Entry<G, Double> e : chromo2fit.entrySet()) { + out.add(new AbstractMap.SimpleImmutableEntry<>(e)); + } + + if (sorted) { + sort(out); + } + + return out; + } + + /** + * @param numOffsprings Number of offsprings to generate. + * @param selection Parents selector. + * @param operators Generators to be applied on the parents. + * @param rng RNG. + * @return the offsprings. + */ + public Collection<G> offsprings(int numOffsprings, + Selection<G, P> selection, + Map<GeneticOperator<G>, ApplicationRate> operators, + UniformRandomProvider rng) { + final List<G> candidates = new ArrayList<>(numOffsprings); + OFFSPRING: while (true) { + for (Map.Entry<GeneticOperator<G>, ApplicationRate> e : operators.entrySet()) { + final GeneticOperator<G> op = e.getKey(); + final List<G> parents = selection.apply(op.numberOfParents(), this); + final double prob = e.getValue().compute(this, parents); + final List<G> offsprings = rng.nextDouble() < prob ? + op.apply(parents, rng) : + parents; + + for (int i = 0; i < offsprings.size(); i++) { + if (candidates.size() >= numOffsprings) { + break OFFSPRING; + } + candidates.add(offsprings.get(i)); + } + } + } + + return Collections.unmodifiableList(candidates); + } + + /** + * Sort (in-place) in decreasing order of fitness. + * + * @param contents List of individuals. + * + * @param <G> Genotype. + */ + public static <G> void sort(List<Map.Entry<G, Double>> contents) { + Collections.sort(contents, + Map.Entry.<G, Double>comparingByValue().reversed()); + } +} diff --git a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/Selection.java similarity index 53% copy from commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java copy to commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/Selection.java index eee31fbc8..9ed47ae28 100644 --- a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/Selection.java @@ -14,41 +14,24 @@ * See the License for the specific language governing permissions and * limitations under the License. */ -package org.apache.commons.math4.examples.ga.mathfunctions; +package org.apache.commons.math4.ga2; import java.util.List; /** - * This class represents the coordinate of the problem domain i.e. the phenotype - * of chromosome. + * Select chromosomes from a population. + * + * @param <G> Genotype. + * @param <P> Phenotype. */ -public class Coordinate { - - /** coordinate of all dimensions. **/ - private final List<Double> values; - - /** - * constructor. - * @param values coordinates of all dimensions. - */ - public Coordinate(List<Double> values) { - this.values = values; - } - +public interface Selection<G, P> { /** - * Returns the values of all coordinates. - * @return values of coordinates + * Select chromosomes from a population. + * + * @param population Population from which chromosomes are chosen. + * @param n Number of chromosomes to select. + * @return the selected chromosomes. */ - public List<Double> getValues() { - return values; - } - - /** - * {@inheritDoc} - */ - @Override - public String toString() { - return "Coordinate [values=" + values + "]"; - } - + List<G> apply(int n, + Population<G, P> population); } diff --git a/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/fitness/FitnessConcurrentCalculator.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/fitness/FitnessConcurrentCalculator.java new file mode 100644 index 000000000..93c616966 --- /dev/null +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/fitness/FitnessConcurrentCalculator.java @@ -0,0 +1,98 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.commons.math4.ga2.fitness; + +import java.util.Collection; +import java.util.List; +import java.util.ArrayList; +import java.util.concurrent.Future; +import java.util.concurrent.ExecutionException; +import java.util.concurrent.ExecutorService; +import java.util.function.Function; +import java.util.function.ToDoubleFunction; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; +import org.apache.commons.math4.ga2.FitnessService; + +/** + * Perform parallel computation of fitnesses. + * + * @param <G> Genotype. + * @param <P> Phenotype. + */ +public class FitnessConcurrentCalculator<G, P> implements FitnessService<G, P> { + /** Logger. */ + private static final Logger LOG = LoggerFactory.getLogger(FitnessConcurrentCalculator.class); + /** Fitness function. */ + private final ToDoubleFunction<P> function; + /** Executor. */ + private final ExecutorService executor; + + /** + * @param fitness Fitness function. + * Note: This class <em>must</em> be thrad-safe. + * @param service Executor. + */ + public FitnessConcurrentCalculator(ToDoubleFunction<P> fitness, + ExecutorService service) { + function = fitness; + executor = service; + } + + /** + * {@inheritDoc} + * + * Note: If the fitness fails, or is interrupted, the corresponding slot + * will contain {@link Double#NaN NaN}. + */ + @Override + public double[] apply(Function<G, P> decoder, + Collection<G> chromosomes) { + final double[] fitnesses = new double[chromosomes.size()]; + int c = 0; + for (Future<Double> f : compute(decoder, chromosomes)) { + double value = Double.NaN; // Default. + try { + // Fitness computations were submitted to the executor: + // Wait for all results. + value = f.get(); + } catch (InterruptedException | + ExecutionException e) { + LOG.error("Unexpected failure: {}", e.getMessage()); + } + fitnesses[c++] = value; + } + return fitnesses; + } + + /** + * Compute fitness of every chromosome, using all available threads. + * + * @param decoder Genotype to phenotype converter. + * @param chromosomes Chromosomes. + * @return the fitness values, in the same order as the input. + */ + private List<Future<Double>> compute(Function<G, P> decoder, + Collection<G> chromosomes) { + final List<Future<Double>> futures = new ArrayList<>(); + for (G chromosome : chromosomes) { + futures.add(executor.submit(() -> function.applyAsDouble(decoder.apply(chromosome)))); + } + return futures; + } +} diff --git a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/fitness/package-info.java similarity index 51% copy from commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java copy to commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/fitness/package-info.java index eee31fbc8..05e68cda2 100644 --- a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/fitness/package-info.java @@ -14,41 +14,7 @@ * See the License for the specific language governing permissions and * limitations under the License. */ -package org.apache.commons.math4.examples.ga.mathfunctions; - -import java.util.List; - /** - * This class represents the coordinate of the problem domain i.e. the phenotype - * of chromosome. + * Functionality for computation of fitness. */ -public class Coordinate { - - /** coordinate of all dimensions. **/ - private final List<Double> values; - - /** - * constructor. - * @param values coordinates of all dimensions. - */ - public Coordinate(List<Double> values) { - this.values = values; - } - - /** - * Returns the values of all coordinates. - * @return values of coordinates - */ - public List<Double> getValues() { - return values; - } - - /** - * {@inheritDoc} - */ - @Override - public String toString() { - return "Coordinate [values=" + values + "]"; - } - -} +package org.apache.commons.math4.ga2.fitness; diff --git a/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/gene/binary/Chromosome.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/gene/binary/Chromosome.java new file mode 100644 index 000000000..9878ccbc7 --- /dev/null +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/gene/binary/Chromosome.java @@ -0,0 +1,109 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.commons.math4.ga2.gene.binary; + +import java.util.BitSet; +import org.apache.commons.rng.UniformRandomProvider; +import org.apache.commons.rng.simple.RandomSource; +import org.apache.commons.math4.ga2.ChromosomeFactory; + +/** + * Represents a chromosome. + */ +public final class Chromosome { + /** Length. */ + private final int size; + /** Internal representation. */ + private final BitSet representation; + + /** + * Forbid direct instantiation. + * + * @param representation Representation. Reference is copied: Factory + * methods that call this constructor <em>must</em> pass a defensive copy. + * @param size Number of genes. + */ + private Chromosome(BitSet representation, + int size) { + this.size = size; + this.representation = representation; + } + + /** @return the number of genes. */ + public int size() { + return size; + } + + /** + * Factory method. + * + * @param r Representation. + * @param size Number of genes. + * @return a new instance whose internal representation is a copy of the + * bits of {@code r} (truncating, or expanding with {@code false}, so that + * the number of genes is equal to {@code size}). + */ + public static Chromosome from(BitSet r, + int size) { + return new Chromosome((BitSet) r.clone(), size); + } + + /** + * Factory method. + * + * @param rng Random generator. + * @param size Number of genes. + * @return a new instance whose genes are drawn from the given generator. + */ + public static Chromosome from(UniformRandomProvider rng, + int size) { + final BitSet r = new BitSet(size); + for (int i = 0; i < size; i++) { + r.set(i, rng.nextBoolean()); + } + + return new Chromosome(r, size); + } + + /** @return a copy of the internal representation. */ + public BitSet asBitSet() { + return (BitSet) representation.clone(); + } + + /** + * Generate chromosomes with random genes. + * Class is <em>not</em> thread-safe. + */ + public static class RandomFactory implements ChromosomeFactory<Chromosome> { + /** RNG. */ + private final UniformRandomProvider rng; + + /** + * @param random Source of randomness. + */ + public RandomFactory(RandomSource random) { + rng = random.create(); + } + + /** {@inheritDoc} */ + @Override + public Chromosome with(int size) { + return Chromosome.from(rng, size); + } + } +} diff --git a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/gene/binary/Mutation.java similarity index 50% copy from commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java copy to commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/gene/binary/Mutation.java index eee31fbc8..193f79809 100644 --- a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/gene/binary/Mutation.java @@ -14,41 +14,37 @@ * See the License for the specific language governing permissions and * limitations under the License. */ -package org.apache.commons.math4.examples.ga.mathfunctions; -import java.util.List; +package org.apache.commons.math4.ga2.gene.binary; + +import java.util.BitSet; +import org.apache.commons.rng.UniformRandomProvider; +import org.apache.commons.math4.ga2.AbstractMutation; /** - * This class represents the coordinate of the problem domain i.e. the phenotype - * of chromosome. + * Genetic operator. + * Class is immutable. */ -public class Coordinate { - - /** coordinate of all dimensions. **/ - private final List<Double> values; - +/* package-private */ class Mutation extends AbstractMutation<Chromosome> { /** - * constructor. - * @param values coordinates of all dimensions. + * @param probability Probability that a gene will mutate. */ - public Coordinate(List<Double> values) { - this.values = values; + Mutation(double probability) { + super(probability); } - /** - * Returns the values of all coordinates. - * @return values of coordinates - */ - public List<Double> getValues() { - return values; - } - - /** - * {@inheritDoc} - */ + /** {@inheritDoc} */ @Override - public String toString() { - return "Coordinate [values=" + values + "]"; - } + protected Chromosome apply(Chromosome parent, + UniformRandomProvider rng) { + final int size = parent.size(); + final BitSet c = parent.asBitSet(); + for (int i = 0; i < size; i++) { + if (rng.nextDouble() < getProbability()) { + c.flip(i); + } + } + return Chromosome.from(c, size); + } } diff --git a/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/gene/binary/OnePointCrossover.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/gene/binary/OnePointCrossover.java new file mode 100644 index 000000000..95342a7bb --- /dev/null +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/gene/binary/OnePointCrossover.java @@ -0,0 +1,75 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.commons.math4.ga2.gene.binary; + +import java.util.BitSet; +import java.util.List; +import java.util.ArrayList; +import org.apache.commons.rng.UniformRandomProvider; +import org.apache.commons.math4.ga2.AbstractCrossover; + +/** + * Genetic operator. + * Class is immutable. + */ +/* package-private */ class OnePointCrossover extends AbstractCrossover<Chromosome> { + /** {@inheritDoc} */ + @Override + protected List<Chromosome> apply(Chromosome parent1, + Chromosome parent2, + UniformRandomProvider rng) { + final int size = parent1.size(); + if (size != parent2.size()) { + throw new IllegalArgumentException("Parents of unequal sizes: " + + size + " != " + + parent2.size()); + } + + // Index of crossover point. + final int xIndex = 1 + rng.nextInt(size - 1); + final BitSet p1 = parent1.asBitSet(); + final BitSet p2 = parent2.asBitSet(); + final BitSet c1; + final BitSet c2; + + final int midIndex = size / 2; + if (xIndex > midIndex) { + c1 = parent1.asBitSet(); + c2 = parent2.asBitSet(); + + for (int i = xIndex; i < size; i++) { + c1.set(i, p2.get(i)); + c2.set(i, p1.get(i)); + } + } else { + c1 = parent2.asBitSet(); + c2 = parent1.asBitSet(); + + for (int i = 0; i < xIndex; i++) { + c1.set(i, p1.get(i)); + c2.set(i, p2.get(i)); + } + } + + final List<Chromosome> offsprings = new ArrayList<>(2); + offsprings.add(Chromosome.from(c1, size)); + offsprings.add(Chromosome.from(c2, size)); + + return offsprings; + } +} diff --git a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/gene/binary/Operators.java similarity index 54% copy from commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java copy to commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/gene/binary/Operators.java index eee31fbc8..7030134f5 100644 --- a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/gene/binary/Operators.java @@ -14,41 +14,30 @@ * See the License for the specific language governing permissions and * limitations under the License. */ -package org.apache.commons.math4.examples.ga.mathfunctions; -import java.util.List; +package org.apache.commons.math4.ga2.gene.binary; + +import org.apache.commons.math4.ga2.GeneticOperator; /** - * This class represents the coordinate of the problem domain i.e. the phenotype - * of chromosome. + * Genetic operators factory. + * It creates instances that operate on "binary" genotypes. */ -public class Coordinate { - - /** coordinate of all dimensions. **/ - private final List<Double> values; - - /** - * constructor. - * @param values coordinates of all dimensions. - */ - public Coordinate(List<Double> values) { - this.values = values; - } +public final class Operators { + /** Prevent instantiation of utility class. */ + private Operators() {} /** - * Returns the values of all coordinates. - * @return values of coordinates + * @param probability Probability that a gene flip will occur. + * @return a mutation operator. */ - public List<Double> getValues() { - return values; + public static GeneticOperator<Chromosome> mutation(double probability) { + return new Mutation(probability); } - /** - * {@inheritDoc} + * @return a one-point crossover operator. */ - @Override - public String toString() { - return "Coordinate [values=" + values + "]"; + public static GeneticOperator<Chromosome> onePointCrossover() { + return new OnePointCrossover(); } - } diff --git a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/gene/binary/package-info.java similarity index 51% copy from commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java copy to commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/gene/binary/package-info.java index eee31fbc8..960ed5302 100644 --- a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/gene/binary/package-info.java @@ -14,41 +14,7 @@ * See the License for the specific language governing permissions and * limitations under the License. */ -package org.apache.commons.math4.examples.ga.mathfunctions; - -import java.util.List; - /** - * This class represents the coordinate of the problem domain i.e. the phenotype - * of chromosome. + * Classes that define functionality specific to "binary" genotypes. */ -public class Coordinate { - - /** coordinate of all dimensions. **/ - private final List<Double> values; - - /** - * constructor. - * @param values coordinates of all dimensions. - */ - public Coordinate(List<Double> values) { - this.values = values; - } - - /** - * Returns the values of all coordinates. - * @return values of coordinates - */ - public List<Double> getValues() { - return values; - } - - /** - * {@inheritDoc} - */ - @Override - public String toString() { - return "Coordinate [values=" + values + "]"; - } - -} +package org.apache.commons.math4.ga2.gene.binary; diff --git a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/package-info.java similarity index 51% copy from commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java copy to commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/package-info.java index eee31fbc8..5930d9eb3 100644 --- a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/package-info.java @@ -14,41 +14,7 @@ * See the License for the specific language governing permissions and * limitations under the License. */ -package org.apache.commons.math4.examples.ga.mathfunctions; - -import java.util.List; - /** - * This class represents the coordinate of the problem domain i.e. the phenotype - * of chromosome. + * Genetic Algorithm. */ -public class Coordinate { - - /** coordinate of all dimensions. **/ - private final List<Double> values; - - /** - * constructor. - * @param values coordinates of all dimensions. - */ - public Coordinate(List<Double> values) { - this.values = values; - } - - /** - * Returns the values of all coordinates. - * @return values of coordinates - */ - public List<Double> getValues() { - return values; - } - - /** - * {@inheritDoc} - */ - @Override - public String toString() { - return "Coordinate [values=" + values + "]"; - } - -} +package org.apache.commons.math4.ga2; diff --git a/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/rate/AverageRankLinearRate.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/rate/AverageRankLinearRate.java new file mode 100644 index 000000000..c1e056328 --- /dev/null +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/rate/AverageRankLinearRate.java @@ -0,0 +1,52 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math4.ga2.rate; + +import java.util.List; +import org.apache.commons.math4.ga2.ApplicationRate; +import org.apache.commons.math4.ga2.Population; + +/** + * Average-rank-weighted linear interpolation. + */ +/* package-private */ class AverageRankLinearRate extends ApplicationRate { + /** + * @param min Minimum probability. + * @param max Maximum probability. + */ + AverageRankLinearRate(double min, + double max) { + super(min, max); + } + + /** {@inheritDoc} */ + @Override + public <G, P> double compute(Population<G, P> population, + List<G> chromosomes) { + if (chromosomes.isEmpty()) { + throw new IllegalArgumentException("Empty list"); + } + + double avg = 0; + for (G c : chromosomes) { + avg += population.rank(c); + } + avg /= chromosomes.size(); + + return min() + (max() - min()) * avg / (population.size() - 1); + } +} diff --git a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/rate/ConstantRate.java similarity index 55% copy from commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java copy to commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/rate/ConstantRate.java index eee31fbc8..41d1e9333 100644 --- a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/rate/ConstantRate.java @@ -14,41 +14,27 @@ * See the License for the specific language governing permissions and * limitations under the License. */ -package org.apache.commons.math4.examples.ga.mathfunctions; +package org.apache.commons.math4.ga2.rate; import java.util.List; +import org.apache.commons.math4.ga2.ApplicationRate; +import org.apache.commons.math4.ga2.Population; /** - * This class represents the coordinate of the problem domain i.e. the phenotype - * of chromosome. + * Constant. */ -public class Coordinate { - - /** coordinate of all dimensions. **/ - private final List<Double> values; - +/* package-private */ class ConstantRate extends ApplicationRate { /** - * constructor. - * @param values coordinates of all dimensions. + * @param value Probability. */ - public Coordinate(List<Double> values) { - this.values = values; + ConstantRate(double value) { + super(value); } - /** - * Returns the values of all coordinates. - * @return values of coordinates - */ - public List<Double> getValues() { - return values; - } - - /** - * {@inheritDoc} - */ + /** {@inheritDoc} */ @Override - public String toString() { - return "Coordinate [values=" + values + "]"; + public <G, P> double compute(Population<G, P> population, + List<G> chromosomes) { + return min(); } - } diff --git a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/rate/RateGenerators.java similarity index 50% copy from commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java copy to commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/rate/RateGenerators.java index eee31fbc8..5ea563606 100644 --- a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/rate/RateGenerators.java @@ -14,41 +14,37 @@ * See the License for the specific language governing permissions and * limitations under the License. */ -package org.apache.commons.math4.examples.ga.mathfunctions; -import java.util.List; +package org.apache.commons.math4.ga2.rate; + +import org.apache.commons.math4.ga2.ApplicationRate; /** - * This class represents the coordinate of the problem domain i.e. the phenotype - * of chromosome. + * Rate generator factory. */ -public class Coordinate { - - /** coordinate of all dimensions. **/ - private final List<Double> values; +public final class RateGenerators { + /** Prevent instantiation of utility class. */ + private RateGenerators() {} /** - * constructor. - * @param values coordinates of all dimensions. + * Creates a generator that always returns the given {@code value}. + * + * @param value Probability. + * @return a new instance. */ - public Coordinate(List<Double> values) { - this.values = values; + public static ApplicationRate constant(double value) { + return new ConstantRate(value); } /** - * Returns the values of all coordinates. - * @return values of coordinates + * Creates a generator that returns a linear interpolation. + * + * @param min Minimum probability. + * @param max Maximum probability. + * @return a new instance. */ - public List<Double> getValues() { - return values; + public static ApplicationRate averageRankLinear(double min, + double max) { + return new AverageRankLinearRate(min, max); } - - /** - * {@inheritDoc} - */ - @Override - public String toString() { - return "Coordinate [values=" + values + "]"; - } - } diff --git a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/rate/package-info.java similarity index 51% copy from commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java copy to commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/rate/package-info.java index eee31fbc8..8eebb1622 100644 --- a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/rate/package-info.java @@ -14,41 +14,7 @@ * See the License for the specific language governing permissions and * limitations under the License. */ -package org.apache.commons.math4.examples.ga.mathfunctions; - -import java.util.List; - /** - * This class represents the coordinate of the problem domain i.e. the phenotype - * of chromosome. + * Probability generators. */ -public class Coordinate { - - /** coordinate of all dimensions. **/ - private final List<Double> values; - - /** - * constructor. - * @param values coordinates of all dimensions. - */ - public Coordinate(List<Double> values) { - this.values = values; - } - - /** - * Returns the values of all coordinates. - * @return values of coordinates - */ - public List<Double> getValues() { - return values; - } - - /** - * {@inheritDoc} - */ - @Override - public String toString() { - return "Coordinate [values=" + values + "]"; - } - -} +package org.apache.commons.math4.ga2.rate; diff --git a/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/select/Tournament.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/select/Tournament.java new file mode 100644 index 000000000..8e2f06179 --- /dev/null +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/select/Tournament.java @@ -0,0 +1,77 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math4.ga2.select; + +import java.util.List; +import java.util.ArrayList; +import java.util.Map; +import org.apache.commons.rng.UniformRandomProvider; +import org.apache.commons.rng.simple.RandomSource; +import org.apache.commons.rng.sampling.ListSampler; +import org.apache.commons.math4.ga2.Population; +import org.apache.commons.math4.ga2.Selection; + +/** + * Select chromosomes from a population. + * + * @param <G> Genotype. + * @param <P> Phenotype. + */ +public class Tournament<G, P> implements Selection<G, P> { + /** RNG. */ + private final UniformRandomProvider rng; + /** Number of chromosomes that take part in a tournament. */ + private final int poolSize; + + /** + * @param poolSize Number of chromosomes that take part in each tournament. + * @param source Source of randomness. + */ + public Tournament(int poolSize, + RandomSource source) { + this.poolSize = poolSize; + rng = source.create(); + } + + /** {@inheritDoc} */ + @Override + public List<G> apply(int n, + Population<G, P> population) { + final List<Map.Entry<G, Double>> all = population.contents(false); + + final List<G> selected = new ArrayList<G>(n); + for (int i = 0; i < n; i++) { + selected.add(selectFrom(all)); + } + + return selected; + } + + /** + * @param population Population. + * @return the winner of a tournament. + */ + private G selectFrom(List<Map.Entry<G, Double>> population) { + // Randomly draw participants to the tournament. + final List<Map.Entry<G, Double>> pool = ListSampler.sample(rng, + population, + poolSize); + // Within the pool, choose the best individual. + Population.sort(pool); + return pool.get(0).getKey(); + } +} diff --git a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/select/package-info.java similarity index 51% copy from commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java copy to commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/select/package-info.java index eee31fbc8..c771dee00 100644 --- a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/select/package-info.java @@ -14,41 +14,7 @@ * See the License for the specific language governing permissions and * limitations under the License. */ -package org.apache.commons.math4.examples.ga.mathfunctions; - -import java.util.List; - /** - * This class represents the coordinate of the problem domain i.e. the phenotype - * of chromosome. + * Selecting individuals from a population. */ -public class Coordinate { - - /** coordinate of all dimensions. **/ - private final List<Double> values; - - /** - * constructor. - * @param values coordinates of all dimensions. - */ - public Coordinate(List<Double> values) { - this.values = values; - } - - /** - * Returns the values of all coordinates. - * @return values of coordinates - */ - public List<Double> getValues() { - return values; - } - - /** - * {@inheritDoc} - */ - @Override - public String toString() { - return "Coordinate [values=" + values + "]"; - } - -} +package org.apache.commons.math4.ga2.select; diff --git a/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/stop/UnchangedFitness.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/stop/UnchangedFitness.java new file mode 100644 index 000000000..c261c434f --- /dev/null +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/stop/UnchangedFitness.java @@ -0,0 +1,116 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math4.ga2.stop; + +import java.util.Map; +import java.util.function.ToDoubleFunction; +import java.util.function.Predicate; +import org.apache.commons.math4.ga2.Population; + +/** + * Criterion for asserting convergence of a population. + * Note: Class is <em>not</em> thread-safe. + * + * @param <G> Genotype. + * @param <P> Phenotype. + */ +public class UnchangedFitness<G, P> implements Predicate<Population<G, P>> { + /** Function that computes the reference value. */ + private final ToDoubleFunction<Population<G, P>> calculator; + /** Number of generations during which no change has happened. */ + private final int maxGenerations; + /** Value for previous population. */ + private double previousFitness = Double.NaN; + /** Number of generations without changes. */ + private int generations = 0; + + /** What needs to be unchanged. */ + public enum Type { + /** Best fitness. */ + BEST, + /** Mean fitness. */ + MEAN; + } + + /** + * @param criterion Reference value that when unchanged for the given + * number of {@code generations}, signals convergence. + * @param maxGenerations Number of generations during which the reference + * value must have been the same. + */ + public UnchangedFitness(Type criterion, + int maxGenerations) { + switch (criterion) { + case BEST: + calculator = p -> bestFitness(p); + break; + case MEAN: + calculator = p -> meanFitness(p); + break; + default: + calculator = null; + throw new IllegalStateException(); // Should never happen. + } + + this.maxGenerations = maxGenerations; + } + + /** {@inheritDoc} */ + @Override + public boolean test(Population<G, P> population) { + final double fitness = calculator.applyAsDouble(population); + if (fitness == previousFitness) { + if (++generations > maxGenerations) { + return true; + } + } else { + generations = 0; + previousFitness = fitness; + } + + return false; + } + + /** + * @param population Population. + * @return the best fitness. + * + * @param <G> Genotype. + * @param <P> Phenotype. + */ + private static <G, P> double bestFitness(Population<G, P> population) { + return population.contents(true).get(0).getValue(); + } + + /** + * @param population Population. + * @return the mean fitness. + * + * @param <G> Genotype. + * @param <P> Phenotype. + */ + private static <G, P> double meanFitness(Population<G, P> population) { + double mean = 0; + int count = 0; + + for (Map.Entry<G, Double> e : population.contents(false)) { + mean += e.getValue(); + } + + return mean / count; + } +} diff --git a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/stop/package-info.java similarity index 51% rename from commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java rename to commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/stop/package-info.java index eee31fbc8..bb0b7772d 100644 --- a/commons-math-examples/examples-ga/examples-ga-math-functions/src/main/java/org/apache/commons/math4/examples/ga/mathfunctions/Coordinate.java +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/stop/package-info.java @@ -14,41 +14,7 @@ * See the License for the specific language governing permissions and * limitations under the License. */ -package org.apache.commons.math4.examples.ga.mathfunctions; - -import java.util.List; - /** - * This class represents the coordinate of the problem domain i.e. the phenotype - * of chromosome. + * Convergence criteria. */ -public class Coordinate { - - /** coordinate of all dimensions. **/ - private final List<Double> values; - - /** - * constructor. - * @param values coordinates of all dimensions. - */ - public Coordinate(List<Double> values) { - this.values = values; - } - - /** - * Returns the values of all coordinates. - * @return values of coordinates - */ - public List<Double> getValues() { - return values; - } - - /** - * {@inheritDoc} - */ - @Override - public String toString() { - return "Coordinate [values=" + values + "]"; - } - -} +package org.apache.commons.math4.ga2.stop; diff --git a/pom.xml b/pom.xml index 1fef46725..23e2a096d 100644 --- a/pom.xml +++ b/pom.xml @@ -117,6 +117,7 @@ <module>commons-math-neuralnet</module> <module>commons-math-transform</module> <module>commons-math-ga</module> + <module>commons-math-ga2</module> <!-- 2. Modularized (but not refactored) legacy functionalities. --> <module>commons-math-legacy-exception</module> diff --git a/src/main/resources/checkstyle/checkstyle-suppressions.xml b/src/main/resources/checkstyle/checkstyle-suppressions.xml index 64edbff2b..00efd1ccf 100644 --- a/src/main/resources/checkstyle/checkstyle-suppressions.xml +++ b/src/main/resources/checkstyle/checkstyle-suppressions.xml @@ -36,6 +36,9 @@ <suppress checks="TypeName" files=".*[/\\]AccurateMath\.java" /> <suppress checks="ParameterName" files=".*[/\\]AccurateMathCalc\.java" /> <suppress checks="ParameterNumber" files=".*[/\\]AdaptiveMathFunctionOptimizer\.java" /> + <suppress checks="ParameterNumber" files=".*[/\\]GeneticAlgorithmFactory\.java" /> + <suppress checks="ParameterNumber" files=".*[/\\]MathFunctionOptimizer2\.java" /> + <suppress checks="IllegalCatch" files=".*[/\\]MathFunctionOptimizer2\.java" /> <!-- Be more lenient on tests. --> <suppress checks="Javadoc" files=".*[/\\]test[/\\].*" />