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
commit f0fe9ab8eb73e981cde5c0c15ca9349f1f5a7185 Author: Gilles Sadowski <[email protected]> AuthorDate: Fri Jun 10 10:06:25 2022 +0200 MATH-1618: Replace class "OnePointCrossover" with "NPointCrossover". The former is a particular case of the latter. --- .../ga/mathfunctions/MathFunctionOptimizer2.java | 12 ++-- ...OnePointCrossover.java => NPointCrossover.java} | 77 ++++++++++++++++------ .../commons/math4/ga2/gene/binary/Operators.java | 7 +- 3 files changed, 65 insertions(+), 31 deletions(-) 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 index e8a16a375..96ea5087b 100644 --- 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 @@ -129,7 +129,7 @@ public final class MathFunctionOptimizer2 { // 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)); + operators.put(Operators.nPointCrossover(1), RateGenerators.constant(crossover)); final Callable<Population<Chromosome, Coordinates>> ga = GeneticAlgorithmFactory.<Chromosome, Coordinates>create(numGenes, @@ -145,14 +145,12 @@ public final class MathFunctionOptimizer2 { 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); + // Run the GA and retrieve the best individual from the last generation. + final Map.Entry<Chromosome, Double> best = ga.call().contents(true).get(0); // CHECKSTYLE: stop all - System.out.println("fitness=" + bestValue + " for " + best.toString()); + System.out.println("fitness=" + best.getValue() + + " for " + decoder.apply(best.getKey()).toString()); // CHECKSTYLE: resume all } catch (Exception e) { // Rethrow. 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/NPointCrossover.java similarity index 50% rename from commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/gene/binary/OnePointCrossover.java rename to commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/gene/binary/NPointCrossover.java index 95342a7bb..d7ff29d5b 100644 --- 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/NPointCrossover.java @@ -27,7 +27,21 @@ import org.apache.commons.math4.ga2.AbstractCrossover; * Genetic operator. * Class is immutable. */ -/* package-private */ class OnePointCrossover extends AbstractCrossover<Chromosome> { +/* package-private */ class NPointCrossover extends AbstractCrossover<Chromosome> { + /** Number of crossover points. */ + private final int numberOfPoints; + + /** + * @param n Number of crossover points. + */ + NPointCrossover(int n) { + if (n <= 0) { + throw new IllegalArgumentException("Not strictly positive: " + n); + } + + numberOfPoints = n; + } + /** {@inheritDoc} */ @Override protected List<Chromosome> apply(Chromosome parent1, @@ -40,36 +54,57 @@ import org.apache.commons.math4.ga2.AbstractCrossover; 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 BitSet c1 = parent1.asBitSet(); + final BitSet c2 = parent2.asBitSet(); - final int midIndex = size / 2; - if (xIndex > midIndex) { - c1 = parent1.asBitSet(); - c2 = parent2.asBitSet(); + // Number or remaining crossover points. + int remainingPoints = numberOfPoints; + // Index of crossover end point. + int xEnd = 0; + while (remainingPoints > 0) { + // Index of crossover start point. + final int xStart = xEnd + 1 + rng.nextInt(size - xEnd - remainingPoints); - 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(); + if (--remainingPoints > 0) { + xEnd = xStart + 1 + rng.nextInt(size - xStart - remainingPoints); - for (int i = 0; i < xIndex; i++) { - c1.set(i, p1.get(i)); - c2.set(i, p2.get(i)); + swap(c1, c2, xStart, xEnd); + + --remainingPoints; + } else { + xEnd = xStart; + break; } } + if (numberOfPoints % 2 != 0) { + swap(c1, c2, xEnd, size); + } + final List<Chromosome> offsprings = new ArrayList<>(2); offsprings.add(Chromosome.from(c1, size)); offsprings.add(Chromosome.from(c2, size)); return offsprings; } + + /** + * Swaps contents (in-place) within the given range. + * + * @param a Chromosome. + * @param b Chromosome. + * @param start Index from which contents should be swapped. + * @param end Index at which swapping should stop. + */ + private void swap(BitSet a, + BitSet b, + int start, + int end) { + for (int i = start; i < end; i++) { + final boolean aV = a.get(i); + final boolean bV = b.get(i); + a.set(i, bV); + b.set(i, aV); + } + } } diff --git a/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/gene/binary/Operators.java b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/gene/binary/Operators.java index 7030134f5..c3242956b 100644 --- a/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/gene/binary/Operators.java +++ b/commons-math-ga2/src/main/java/org/apache/commons/math4/ga2/gene/binary/Operators.java @@ -35,9 +35,10 @@ public final class Operators { return new Mutation(probability); } /** - * @return a one-point crossover operator. + * @param n Number of crossover points. + * @return an n-point crossover operator. */ - public static GeneticOperator<Chromosome> onePointCrossover() { - return new OnePointCrossover(); + public static GeneticOperator<Chromosome> nPointCrossover(int n) { + return new NPointCrossover(n); } }
