You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ps...@apache.org on 2009/06/14 21:04:34 UTC
svn commit: r784604 [2/2] - in /commons/proper/math/trunk/src:
java/org/apache/commons/math/genetics/ site/xdoc/
test/org/apache/commons/math/genetics/
Added: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/ChromosomeTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/ChromosomeTest.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/ChromosomeTest.java (added)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/ChromosomeTest.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,111 @@
+/*
+ * 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.math.genetics;
+
+import static org.junit.Assert.*;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.junit.Test;
+
+public class ChromosomeTest {
+
+ @Test
+ public void testCompareTo() {
+ Chromosome c1 = new Chromosome() {
+ public double fitness() {
+ return 0;
+ }
+ };
+ Chromosome c2 = new Chromosome() {
+ public double fitness() {
+ return 10;
+ }
+ };
+ Chromosome c3 = new Chromosome() {
+ public double fitness() {
+ return 10;
+ }
+ };
+
+ assertTrue(c1.compareTo(c2) < 0);
+ assertTrue(c2.compareTo(c1) > 0);
+ assertEquals(0,c3.compareTo(c2));
+ assertEquals(0,c2.compareTo(c3));
+ }
+
+ private abstract static class DummyChromosome extends Chromosome {
+ private final int repr;
+
+ public DummyChromosome(final int repr) {
+ this.repr = repr;
+ }
+ @Override
+ protected boolean isSame(Chromosome another) {
+ return ((DummyChromosome) another).repr == repr;
+ }
+ }
+
+ @Test
+ public void testFindSameChromosome() {
+ Chromosome c1 = new DummyChromosome(1) {
+ public double fitness() {
+ return 1;
+ }
+ };
+ Chromosome c2 = new DummyChromosome(2) {
+ public double fitness() {
+ return 2;
+ }
+ };
+ Chromosome c3 = new DummyChromosome(3) {
+ public double fitness() {
+ return 3;
+ }
+ };
+ Chromosome c4 = new DummyChromosome(1) {
+ public double fitness() {
+ return 5;
+ }
+ };
+ Chromosome c5 = new DummyChromosome(15) {
+ public double fitness() {
+ return 15;
+ }
+ };
+
+ List<Chromosome> popChr = new ArrayList<Chromosome>();
+ popChr.add(c1);
+ popChr.add(c2);
+ popChr.add(c3);
+ Population pop = new ListPopulation(popChr,3) {
+ public Population nextGeneration() {
+ // not important
+ return null;
+ }
+ };
+
+ assertNull(c5.findSameChromosome(pop));
+ assertEquals(c1, c4.findSameChromosome(pop));
+
+ c4.searchForFitnessUpdate(pop);
+ assertEquals(1, c4.getFitness(),0);
+ }
+
+}
+
Propchange: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/ChromosomeTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/DummyBinaryChromosome.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/DummyBinaryChromosome.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/DummyBinaryChromosome.java (added)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/DummyBinaryChromosome.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,44 @@
+/*
+ * 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.math.genetics;
+
+import java.util.List;
+
+/**
+ * Implementation of BinaryChromosome for testing purposes
+ */
+public class DummyBinaryChromosome extends BinaryChromosome {
+
+ public DummyBinaryChromosome(List<Integer> representation) {
+ super(representation);
+ }
+
+ public DummyBinaryChromosome(Integer[] representation) {
+ super(representation);
+ }
+
+ @Override
+ public AbstractListChromosome<Integer> newFixedLengthChromosome(List<Integer> representation) {
+ return new DummyBinaryChromosome(representation);
+ }
+
+ public double fitness() {
+ // uninteresting
+ return 0;
+ }
+
+}
Propchange: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/DummyBinaryChromosome.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/DummyRandomKey.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/DummyRandomKey.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/DummyRandomKey.java (added)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/DummyRandomKey.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,44 @@
+/*
+ * 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.math.genetics;
+
+import java.util.List;
+
+/**
+ * Implementation of RandomKey for testing purposes
+ */
+public class DummyRandomKey extends RandomKey<String> {
+
+ public DummyRandomKey(List<Double> representation) {
+ super(representation);
+ }
+
+ public DummyRandomKey(Double[] representation) {
+ super(representation);
+ }
+
+ @Override
+ public AbstractListChromosome<Double> newFixedLengthChromosome(List<Double> representation) {
+ return new DummyRandomKey(representation);
+ }
+
+ public double fitness() {
+ // unimportant
+ return 0;
+ }
+
+}
Propchange: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/DummyRandomKey.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/ElitisticListPopulationTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/ElitisticListPopulationTest.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/ElitisticListPopulationTest.java (added)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/ElitisticListPopulationTest.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,53 @@
+/*
+ * 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.math.genetics;
+
+import static org.junit.Assert.*;
+
+import org.junit.Test;
+
+public class ElitisticListPopulationTest {
+
+ private static int counter = 0;
+
+ @Test
+ public void testNextGeneration() {
+ ElitisticListPopulation pop = new ElitisticListPopulation(100, 0.203);
+
+ for (int i=0; i<pop.getPopulationLimit(); i++) {
+ pop.addChromosome(new DummyChromosome());
+ }
+
+ Population nextGeneration = pop.nextGeneration();
+
+ assertEquals(20, nextGeneration.getPopulationSize());
+ }
+
+ private static class DummyChromosome extends Chromosome {
+ private final int fitness;
+
+ public DummyChromosome() {
+ this.fitness = counter;
+ counter++;
+ }
+
+ public double fitness() {
+ return this.fitness;
+ }
+ }
+
+}
Propchange: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/ElitisticListPopulationTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/FitnessCachingTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/FitnessCachingTest.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/FitnessCachingTest.java (added)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/FitnessCachingTest.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,94 @@
+/*
+ * 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.math.genetics;
+
+import static org.junit.Assert.*;
+
+import java.util.LinkedList;
+import java.util.List;
+import org.junit.Test;
+
+
+public class FitnessCachingTest {
+
+ // parameters for the GA
+ private static final int DIMENSION = 50;
+ private static final double CROSSOVER_RATE = 1;
+ private static final double MUTATION_RATE = 0.1;
+ private static final int TOURNAMENT_ARITY = 5;
+
+ private static final int POPULATION_SIZE = 10;
+ private static final int NUM_GENERATIONS = 50;
+ private static final double ELITISM_RATE = 0.2;
+
+ // how many times was the fitness computed
+ public static int fitnessCalls = 0;
+
+
+ @Test
+ public void testFitnessCaching() {
+ // initialize a new genetic algorithm
+ GeneticAlgorithm ga = new GeneticAlgorithm(
+ new OnePointCrossover<Integer>(),
+ CROSSOVER_RATE, // all selected chromosomes will be recombined (=crosssover)
+ new BinaryMutation(),
+ MUTATION_RATE, // no mutation
+ new TournamentSelection(TOURNAMENT_ARITY)
+ );
+
+ // initial population
+ Population initial = randomPopulation();
+ // stopping conditions
+ StoppingCondition stopCond = new FixedGenerationCount(NUM_GENERATIONS);
+
+ // run the algorithm
+ ga.evolve(initial, stopCond);
+
+ int neededCalls =
+ POPULATION_SIZE /*initial population*/ +
+ (NUM_GENERATIONS - 1) /*for each population*/ * (int)(POPULATION_SIZE * (1.0 - ELITISM_RATE)) /*some chromosomes are copied*/
+ ;
+ assertTrue(fitnessCalls <= neededCalls); // some chromosomes after crossover may be the same os old ones
+ }
+
+
+ /**
+ * Initializes a random population.
+ */
+ private static ElitisticListPopulation randomPopulation() {
+ List<Chromosome> popList = new LinkedList<Chromosome>();
+
+ for (int i=0; i<POPULATION_SIZE; i++) {
+ BinaryChromosome randChrom = new DummyCountingBinaryChromosome(BinaryChromosome.randomBinaryRepresentation(DIMENSION));
+ popList.add(randChrom);
+ }
+ return new ElitisticListPopulation(popList, popList.size(), ELITISM_RATE);
+ }
+
+ private static class DummyCountingBinaryChromosome extends DummyBinaryChromosome {
+
+ public DummyCountingBinaryChromosome(List<Integer> representation) {
+ super(representation);
+ }
+
+ @Override
+ public double fitness() {
+ fitnessCalls++;
+ return 0;
+ }
+ }
+}
Propchange: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/FitnessCachingTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/FixedGenerationCountTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/FixedGenerationCountTest.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/FixedGenerationCountTest.java (added)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/FixedGenerationCountTest.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,63 @@
+/*
+ * 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.math.genetics;
+
+import static org.junit.Assert.*;
+
+import java.util.Iterator;
+
+import org.junit.Test;
+
+public class FixedGenerationCountTest {
+
+ @Test
+ public void testIsSatisfied() {
+ FixedGenerationCount fgc = new FixedGenerationCount(20);
+
+ int cnt = 0;
+ Population pop = new Population() {
+ public void addChromosome(Chromosome chromosome) {
+ // unimportant
+ }
+ public Chromosome getFittestChromosome() {
+ // unimportant
+ return null;
+ }
+ public int getPopulationLimit() {
+ // unimportant
+ return 0;
+ }
+ public int getPopulationSize() {
+ // unimportant
+ return 0;
+ }
+ public Population nextGeneration() {
+ // unimportant
+ return null;
+ }
+ public Iterator<Chromosome> iterator() {
+ // unimportant
+ return null;
+ }
+ };
+
+ while (!fgc.isSatisfied(pop))
+ cnt++;
+ assertEquals(20, cnt);
+ }
+
+}
Propchange: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/FixedGenerationCountTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/GeneticAlgorithmTestBinary.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/GeneticAlgorithmTestBinary.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/GeneticAlgorithmTestBinary.java (added)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/GeneticAlgorithmTestBinary.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,121 @@
+/*
+ * 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.math.genetics;
+
+import static org.junit.Assert.*;
+
+import java.util.LinkedList;
+import java.util.List;
+import org.junit.Test;
+
+/**
+ * This is also an example of usage.
+ */
+public class GeneticAlgorithmTestBinary {
+
+ // parameters for the GA
+ private static final int DIMENSION = 50;
+ private static final int POPULATION_SIZE = 50;
+ private static final int NUM_GENERATIONS = 50;
+ private static final double ELITISM_RATE = 0.2;
+ private static final double CROSSOVER_RATE = 1;
+ private static final double MUTATION_RATE = 0.1;
+ private static final int TOURNAMENT_ARITY = 2;
+
+ @Test
+ public void test() {
+ // to test a stochastic algorithm is hard, so this will rather be an usage example
+
+ // initialize a new genetic algorithm
+ GeneticAlgorithm ga = new GeneticAlgorithm(
+ new OnePointCrossover<Integer>(),
+ CROSSOVER_RATE, // all selected chromosomes will be recombined (=crosssover)
+ new BinaryMutation(),
+ MUTATION_RATE,
+ new TournamentSelection(TOURNAMENT_ARITY)
+ );
+
+ // initial population
+ Population initial = randomPopulation();
+ // stopping conditions
+ StoppingCondition stopCond = new FixedGenerationCount(NUM_GENERATIONS);
+
+ // best initial chromosome
+ Chromosome bestInitial = initial.getFittestChromosome();
+
+ // run the algorithm
+ Population finalPopulation = ga.evolve(initial, stopCond);
+
+ // best chromosome from the final population
+ Chromosome bestFinal = finalPopulation.getFittestChromosome();
+
+ // the only thing we can test is whether the final solution is not worse than the initial one
+ // however, for some implementations of GA, this need not be true :)
+
+ assertTrue(bestFinal.compareTo(bestInitial) > 0);
+
+ //System.out.println(bestInitial);
+ //System.out.println(bestFinal);
+ }
+
+
+
+
+ /**
+ * Initializes a random population.
+ */
+ private static ElitisticListPopulation randomPopulation() {
+ List<Chromosome> popList = new LinkedList<Chromosome>();
+
+ for (int i=0; i<POPULATION_SIZE; i++) {
+ BinaryChromosome randChrom = new FindOnes(BinaryChromosome.randomBinaryRepresentation(DIMENSION));
+ popList.add(randChrom);
+ }
+ return new ElitisticListPopulation(popList, popList.size(), ELITISM_RATE);
+ }
+
+ /**
+ * Chromosomes represented by a binary chromosome.
+ *
+ * The goal is to set all bits (genes) to 1.
+ */
+ private static class FindOnes extends BinaryChromosome {
+
+ public FindOnes(List<Integer> representation) {
+ super(representation);
+ }
+
+ /**
+ * Returns number of elements != 0
+ */
+ public double fitness() {
+ int num = 0;
+ for (int val : this.getRepresentation()) {
+ if (val != 0)
+ num++;
+ }
+ // number of elements >= 0
+ return num;
+ }
+
+ @Override
+ public AbstractListChromosome<Integer> newFixedLengthChromosome(List<Integer> representation) {
+ return new FindOnes(representation);
+ }
+
+ }
+}
Propchange: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/GeneticAlgorithmTestBinary.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/GeneticAlgorithmTestPermutations.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/GeneticAlgorithmTestPermutations.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/GeneticAlgorithmTestPermutations.java (added)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/GeneticAlgorithmTestPermutations.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,132 @@
+/*
+ * 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.math.genetics;
+
+import static org.junit.Assert.assertTrue;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.junit.Test;
+
+/**
+ * This is also an example of usage.
+ *
+ * This algorithm does "stochastic sorting" of a sequence 0,...,N.
+ *
+ */
+public class GeneticAlgorithmTestPermutations {
+
+ // parameters for the GA
+ private static final int DIMENSION = 20;
+ private static final int POPULATION_SIZE = 80;
+ private static final int NUM_GENERATIONS = 200;
+ private static final double ELITISM_RATE = 0.2;
+ private static final double CROSSOVER_RATE = 1;
+ private static final double MUTATION_RATE = 0.08;
+ private static final int TOURNAMENT_ARITY = 2;
+
+ // numbers from 0 to N-1
+ private static List<Integer> sequence = new ArrayList<Integer>();
+ static {
+ for (int i=0; i<DIMENSION; i++) {
+ sequence.add(i);
+ }
+ }
+
+ @Test
+ public void test() {
+ // to test a stochastic algorithm is hard, so this will rather be an usage example
+
+ // initialize a new genetic algorithm
+ GeneticAlgorithm ga = new GeneticAlgorithm(
+ new OnePointCrossover<Integer>(),
+ CROSSOVER_RATE,
+ new RandomKeyMutation(),
+ MUTATION_RATE,
+ new TournamentSelection(TOURNAMENT_ARITY)
+ );
+
+ // initial population
+ Population initial = randomPopulation();
+ // stopping conditions
+ StoppingCondition stopCond = new FixedGenerationCount(NUM_GENERATIONS);
+
+ // best initial chromosome
+ Chromosome bestInitial = initial.getFittestChromosome();
+
+ // run the algorithm
+ Population finalPopulation = ga.evolve(initial, stopCond);
+
+ // best chromosome from the final population
+ Chromosome bestFinal = finalPopulation.getFittestChromosome();
+
+ // the only thing we can test is whether the final solution is not worse than the initial one
+ // however, for some implementations of GA, this need not be true :)
+
+ assertTrue(bestFinal.compareTo(bestInitial) > 0);
+
+ //System.out.println(bestInitial);
+ //System.out.println(bestFinal);
+ }
+
+
+ /**
+ * Initializes a random population
+ */
+ private static ElitisticListPopulation randomPopulation() {
+ List<Chromosome> popList = new ArrayList<Chromosome>();
+ for (int i=0; i<POPULATION_SIZE; i++) {
+ Chromosome randChrom = new MinPermutations(RandomKey.randomPermutation(DIMENSION));
+ popList.add(randChrom);
+ }
+ return new ElitisticListPopulation(popList, popList.size(), ELITISM_RATE);
+ }
+
+ /**
+ * Chromosomes representing a permutation of (0,1,2,...,DIMENSION-1).
+ *
+ * The goal is to sort the sequence.
+ */
+ private static class MinPermutations extends RandomKey<Integer> {
+
+ public MinPermutations(List<Double> representation) {
+ super(representation);
+ // TODO Auto-generated constructor stub
+ }
+
+ public double fitness() {
+ int res = 0;
+ List<Integer> decoded = decode(sequence);
+ for (int i=0; i<decoded.size(); i++) {
+ int value = (Integer) decoded.get(i);
+ if (value != i) {
+ // bad position found
+ res += Math.abs(value - i);
+ }
+ }
+ // the most fitted chromosome is the one with minimal error
+ // therefore we must return negative value
+ return -res;
+ }
+
+ @Override
+ public AbstractListChromosome<Double> newFixedLengthChromosome(List<Double> representation) {
+ return new MinPermutations(representation);
+ }
+ }
+}
Propchange: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/GeneticAlgorithmTestPermutations.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/ListPopulationTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/ListPopulationTest.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/ListPopulationTest.java (added)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/ListPopulationTest.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,61 @@
+/*
+ * 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.math.genetics;
+
+import static org.junit.Assert.*;
+
+import java.util.ArrayList;
+
+import org.junit.Test;
+
+public class ListPopulationTest {
+
+ @Test
+ public void testGetFittestChromosome() {
+ Chromosome c1 = new Chromosome() {
+ public double fitness() {
+ return 0;
+ }
+ };
+ Chromosome c2 = new Chromosome() {
+ public double fitness() {
+ return 10;
+ }
+ };
+ Chromosome c3 = new Chromosome() {
+ public double fitness() {
+ return 15;
+ }
+ };
+
+ ArrayList<Chromosome> chromosomes = new ArrayList<Chromosome> ();
+ chromosomes.add(c1);
+ chromosomes.add(c2);
+ chromosomes.add(c3);
+
+ ListPopulation population = new ListPopulation(chromosomes,10) {
+
+ public Population nextGeneration() {
+ // not important
+ return null;
+ }
+ };
+
+ assertEquals(c3, population.getFittestChromosome());
+ }
+
+}
Propchange: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/ListPopulationTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/OnePointCrossoverTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/OnePointCrossoverTest.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/OnePointCrossoverTest.java (added)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/OnePointCrossoverTest.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,59 @@
+/*
+ * 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.math.genetics;
+
+import static org.junit.Assert.*;
+import org.junit.Test;
+
+public class OnePointCrossoverTest {
+
+ @Test
+ public void testCrossover() {
+ Integer[] p1 = new Integer[] {1,0,1,0,0,1,0,1,1};
+ Integer[] p2 = new Integer[] {0,1,1,0,1,0,1,1,1};
+
+ BinaryChromosome p1c = new DummyBinaryChromosome(p1);
+ BinaryChromosome p2c = new DummyBinaryChromosome(p2);
+
+ OnePointCrossover<Integer> opc = new OnePointCrossover<Integer>();
+
+ // how to test a stochastic method?
+ for (int i=0; i<20; i++) {
+ ChromosomePair pair = opc.crossover(p1c,p2c);
+
+ Integer[] c1 = new Integer[p1.length];
+ Integer[] c2 = new Integer[p2.length];
+
+ c1 = ((BinaryChromosome) pair.getFirst()).getRepresentation().toArray(c1);
+ c2 = ((BinaryChromosome) pair.getSecond()).getRepresentation().toArray(c2);
+
+ // first and last values will be the same
+ assertEquals((int) p1[0], (int) c1[0]);
+ assertEquals((int) p2[0], (int) c2[0]);
+ assertEquals((int) p1[p1.length-1], (int) c1[c1.length-1]);
+ assertEquals((int) p2[p2.length-1], (int) c2[c2.length-1]);
+ // moreover, in the above setting, the 2nd, 3rd and 7th values will be the same
+ assertEquals((int) p1[2], (int) c1[2]);
+ assertEquals((int) p2[2], (int) c2[2]);
+ assertEquals((int) p1[3], (int) c1[3]);
+ assertEquals((int) p2[3], (int) c2[3]);
+ assertEquals((int) p1[7], (int) c1[7]);
+ assertEquals((int) p2[7], (int) c2[7]);
+ }
+ }
+
+}
Propchange: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/OnePointCrossoverTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/RandomKeyMutationTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/RandomKeyMutationTest.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/RandomKeyMutationTest.java (added)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/RandomKeyMutationTest.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,44 @@
+/*
+ * 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.math.genetics;
+
+import static org.junit.Assert.*;
+
+import org.junit.Test;
+
+public class RandomKeyMutationTest {
+
+ @Test
+ public void testMutate() {
+ MutationPolicy mutation = new RandomKeyMutation();
+ int l=10;
+ for (int i=0; i<20; i++) {
+ DummyRandomKey origRk = new DummyRandomKey(RandomKey.randomPermutation(l));
+ Chromosome mutated = mutation.mutate(origRk);
+ DummyRandomKey mutatedRk = (DummyRandomKey) mutated;
+
+ int changes = 0;
+ for (int j=0; j<origRk.getLength(); j++) {
+ if (origRk.getRepresentation().get(j) != mutatedRk.getRepresentation().get(j)) {
+ changes++;
+ }
+ }
+ assertEquals(1,changes);
+ }
+ }
+
+}
Propchange: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/RandomKeyMutationTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/RandomKeyTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/RandomKeyTest.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/RandomKeyTest.java (added)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/RandomKeyTest.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,166 @@
+/*
+ * 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.math.genetics;
+
+import static org.junit.Assert.*;
+
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+
+import org.junit.Test;
+
+public class RandomKeyTest {
+
+ @Test(expected=IllegalArgumentException.class)
+ public void testConstructor1() {
+ @SuppressWarnings("unused")
+ DummyRandomKey drk = new DummyRandomKey(new Double[] {0.2, 0.3, 1.2});
+ }
+
+ @Test(expected=IllegalArgumentException.class)
+ public void testConstructor2() {
+ @SuppressWarnings("unused")
+ DummyRandomKey drk = new DummyRandomKey(new Double[] {0.2, 0.3, -0.2});
+ }
+
+ @Test
+ public void testIsSame() {
+ DummyRandomKey drk1 = new DummyRandomKey(new Double[] {0.4, 0.1, 0.5, 0.8, 0.2});
+ DummyRandomKey drk2 = new DummyRandomKey(new Double[] {0.4, 0.1, 0.5, 0.8, 0.2});
+ DummyRandomKey drk3 = new DummyRandomKey(new Double[] {0.4, 0.15, 0.5, 0.8, 0.2});
+ DummyRandomKey drk4 = new DummyRandomKey(new Double[] {0.4, 0.25, 0.5, 0.8, 0.2});
+ DummyRandomKey drk5 = new DummyRandomKey(new Double[] {0.4, 0.25, 0.5, 0.8, 0.2, 0.5});
+
+ assertTrue(drk1.isSame(drk2));
+ assertTrue(drk2.isSame(drk3));
+ assertFalse(drk3.isSame(drk4));
+ assertFalse(drk4.isSame(drk5));
+ }
+
+ @Test
+ public void testDecode() {
+ DummyRandomKey drk = new DummyRandomKey(new Double[] {0.4, 0.1, 0.5, 0.8, 0.2});
+ List<String> decoded = drk.decode(Arrays.asList(new String[] {"a", "b", "c", "d", "e"}));
+
+ assertEquals("b", decoded.get(0));
+ assertEquals("e", decoded.get(1));
+ assertEquals("a", decoded.get(2));
+ assertEquals("c", decoded.get(3));
+ assertEquals("d", decoded.get(4));
+ }
+
+ @Test
+ public void testRandomPermutation() {
+ // never generate an invalid one
+ for (int i=0; i<10; i++) {
+ @SuppressWarnings("unused")
+ DummyRandomKey drk = new DummyRandomKey(RandomKey.randomPermutation(20));
+ }
+ }
+
+ @Test
+ public void testIdentityPermutation() {
+ DummyRandomKey drk = new DummyRandomKey(RandomKey.identityPermutation(5));
+ List<String> decoded = drk.decode(Arrays.asList(new String[] {"a", "b", "c", "d", "e"}));
+
+ assertEquals("a", decoded.get(0));
+ assertEquals("b", decoded.get(1));
+ assertEquals("c", decoded.get(2));
+ assertEquals("d", decoded.get(3));
+ assertEquals("e", decoded.get(4));
+ }
+
+ @Test
+ public void testComparatorPermutation() {
+ List<String> data = Arrays.asList(new String[] {"x", "b", "c", "z", "b"});
+
+ List<Double> permutation = RandomKey.comparatorPermutation(data, new Comparator<String>() {
+ public int compare(String o1, String o2) {
+ return o1.compareTo(o2);
+ }
+ });
+ Double[] permArr = new Double[data.size()];
+ permArr = permutation.toArray(permArr);
+ assertArrayEquals(new Double[] {0.6,0.0,0.4,0.8,0.2}, permArr);
+ List<String> decodedData = new DummyRandomKey(permutation).decode(data);
+ assertEquals("b", decodedData.get(0));
+ assertEquals("b", decodedData.get(1));
+ assertEquals("c", decodedData.get(2));
+ assertEquals("x", decodedData.get(3));
+ assertEquals("z", decodedData.get(4));
+
+ permutation = RandomKey.comparatorPermutation(data, new Comparator<String>() {
+ public int compare(String o1, String o2) {
+ return o2.compareTo(o1);
+ }
+ });
+ permArr = new Double[data.size()];
+ permArr = permutation.toArray(permArr);
+ assertArrayEquals(new Double[] {0.2,0.6,0.4,0.0,0.8}, permArr);
+ decodedData = new DummyRandomKey(permutation).decode(data);
+ assertEquals("z", decodedData.get(0));
+ assertEquals("x", decodedData.get(1));
+ assertEquals("c", decodedData.get(2));
+ assertEquals("b", decodedData.get(3));
+ assertEquals("b", decodedData.get(4));
+ }
+
+ @Test
+ public void testInducedPermutation() {
+ List<String> origData = Arrays.asList(new String[] {"a", "b", "c", "d", "d"});
+ List<String> permutedData = Arrays.asList(new String[] {"d", "b", "c", "a", "d"});
+
+ DummyRandomKey drk = new DummyRandomKey(RandomKey.inducedPermutation(origData, permutedData));
+ List<String> decoded = drk.decode(origData);
+
+ assertEquals("d", decoded.get(0));
+ assertEquals("b", decoded.get(1));
+ assertEquals("c", decoded.get(2));
+ assertEquals("a", decoded.get(3));
+ assertEquals("d", decoded.get(4));
+
+ try {
+ RandomKey.inducedPermutation(
+ Arrays.asList(new String[] {"a", "b", "c", "d", "d"}),
+ Arrays.asList(new String[] {"a", "b", "c", "d"})
+ );
+ fail("Uncaught exception");
+ } catch (IllegalArgumentException e) {
+ // no-op
+ }
+ try {
+ RandomKey.inducedPermutation(
+ Arrays.asList(new String[] {"a", "b", "c", "d", "d"}),
+ Arrays.asList(new String[] {"a", "b", "c", "d", "f"})
+ );
+ fail("Uncaught exception");
+ } catch (IllegalArgumentException e) {
+ // no-op
+ }
+ }
+
+ @Test
+ public void testEqualRepr() {
+ DummyRandomKey drk = new DummyRandomKey(new Double[] {0.2, 0.2, 0.5});
+ List<String> decodedData = drk.decode(Arrays.asList(new String[] {"a", "b", "c"}));
+ assertEquals("a", decodedData.get(0));
+ assertEquals("b", decodedData.get(1));
+ assertEquals("c", decodedData.get(2));
+ }
+
+}
Propchange: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/RandomKeyTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/TournamentSelectionTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/TournamentSelectionTest.java?rev=784604&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/TournamentSelectionTest.java (added)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/TournamentSelectionTest.java Sun Jun 14 19:04:32 2009
@@ -0,0 +1,56 @@
+/*
+ * 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.math.genetics;
+
+import static org.junit.Assert.*;
+import org.junit.Test;
+
+public class TournamentSelectionTest {
+
+ private static int counter = 0;
+
+ @Test
+ public void testSelect() {
+ TournamentSelection ts = new TournamentSelection(2);
+ ElitisticListPopulation pop = new ElitisticListPopulation(100, 0.203);
+
+ for (int i=0; i<pop.getPopulationLimit(); i++) {
+ pop.addChromosome(new DummyChromosome());
+ }
+ // how to write a test for stochastic method?
+ for (int i=0; i<20; i++) {
+ ChromosomePair pair = ts.select(pop);
+ // the worst chromosome should NEVER be selected
+ assertTrue(pair.getFirst().getFitness() > 0);
+ assertTrue(pair.getSecond().getFitness() > 0);
+ }
+ }
+
+ private static class DummyChromosome extends Chromosome {
+ private final int fitness;
+
+ public DummyChromosome() {
+ this.fitness = counter;
+ counter++;
+ }
+
+ public double fitness() {
+ return this.fitness;
+ }
+ }
+
+}
Propchange: commons/proper/math/trunk/src/test/org/apache/commons/math/genetics/TournamentSelectionTest.java
------------------------------------------------------------------------------
svn:eol-style = native