1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.math.genetics;
18
19 import static org.junit.Assert.assertTrue;
20
21 import java.util.ArrayList;
22 import java.util.List;
23
24 import org.junit.Test;
25
26 /**
27 * This is also an example of usage.
28 *
29 * This algorithm does "stochastic sorting" of a sequence 0,...,N.
30 *
31 */
32 public class GeneticAlgorithmTestPermutations {
33
34 // parameters for the GA
35 private static final int DIMENSION = 20;
36 private static final int POPULATION_SIZE = 80;
37 private static final int NUM_GENERATIONS = 200;
38 private static final double ELITISM_RATE = 0.2;
39 private static final double CROSSOVER_RATE = 1;
40 private static final double MUTATION_RATE = 0.08;
41 private static final int TOURNAMENT_ARITY = 2;
42
43 // numbers from 0 to N-1
44 private static List<Integer> sequence = new ArrayList<Integer>();
45 static {
46 for (int i=0; i<DIMENSION; i++) {
47 sequence.add(i);
48 }
49 }
50
51 @Test
52 public void test() {
53 // to test a stochastic algorithm is hard, so this will rather be an usage example
54
55 // initialize a new genetic algorithm
56 GeneticAlgorithm ga = new GeneticAlgorithm(
57 new OnePointCrossover<Integer>(),
58 CROSSOVER_RATE,
59 new RandomKeyMutation(),
60 MUTATION_RATE,
61 new TournamentSelection(TOURNAMENT_ARITY)
62 );
63
64 // initial population
65 Population initial = randomPopulation();
66 // stopping conditions
67 StoppingCondition stopCond = new FixedGenerationCount(NUM_GENERATIONS);
68
69 // best initial chromosome
70 Chromosome bestInitial = initial.getFittestChromosome();
71
72 // run the algorithm
73 Population finalPopulation = ga.evolve(initial, stopCond);
74
75 // best chromosome from the final population
76 Chromosome bestFinal = finalPopulation.getFittestChromosome();
77
78 // the only thing we can test is whether the final solution is not worse than the initial one
79 // however, for some implementations of GA, this need not be true :)
80
81 assertTrue(bestFinal.compareTo(bestInitial) > 0);
82
83 //System.out.println(bestInitial);
84 //System.out.println(bestFinal);
85 }
86
87
88 /**
89 * Initializes a random population
90 */
91 private static ElitisticListPopulation randomPopulation() {
92 List<Chromosome> popList = new ArrayList<Chromosome>();
93 for (int i=0; i<POPULATION_SIZE; i++) {
94 Chromosome randChrom = new MinPermutations(RandomKey.randomPermutation(DIMENSION));
95 popList.add(randChrom);
96 }
97 return new ElitisticListPopulation(popList, popList.size(), ELITISM_RATE);
98 }
99
100 /**
101 * Chromosomes representing a permutation of (0,1,2,...,DIMENSION-1).
102 *
103 * The goal is to sort the sequence.
104 */
105 private static class MinPermutations extends RandomKey<Integer> {
106
107 public MinPermutations(List<Double> representation) {
108 super(representation);
109 }
110
111 public double fitness() {
112 int res = 0;
113 List<Integer> decoded = decode(sequence);
114 for (int i=0; i<decoded.size(); i++) {
115 int value = (Integer) decoded.get(i);
116 if (value != i) {
117 // bad position found
118 res += Math.abs(value - i);
119 }
120 }
121 // the most fitted chromosome is the one with minimal error
122 // therefore we must return negative value
123 return -res;
124 }
125
126 @Override
127 public AbstractListChromosome<Double> newFixedLengthChromosome(List<Double> representation) {
128 return new MinPermutations(representation);
129 }
130 }
131 }