You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by er...@apache.org on 2022/06/27 13:24:57 UTC
[commons-math] 03/05: MATH-1618: Replace class "OnePointCrossover" with "NPointCrossover".
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 <gi...@gmail.com>
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);
}
}