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 }