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.*;
20  
21  import java.util.LinkedList;
22  import java.util.List;
23  import org.junit.Test;
24  
25  /**
26   * This is also an example of usage.
27   */
28  public class GeneticAlgorithmTestBinary {
29      
30      // parameters for the GA
31      private static final int DIMENSION = 50;    
32      private static final int POPULATION_SIZE = 50; 
33      private static final int NUM_GENERATIONS = 50;
34      private static final double ELITISM_RATE = 0.2;
35      private static final double CROSSOVER_RATE = 1;
36      private static final double MUTATION_RATE = 0.1;
37      private static final int TOURNAMENT_ARITY = 2;
38  
39      @Test
40      public void test() {
41          // to test a stochastic algorithm is hard, so this will rather be an usage example
42          
43          // initialize a new genetic algorithm
44          GeneticAlgorithm ga = new GeneticAlgorithm(
45                  new OnePointCrossover<Integer>(),
46                  CROSSOVER_RATE, // all selected chromosomes will be recombined (=crosssover)
47                  new BinaryMutation(),
48                  MUTATION_RATE,
49                  new TournamentSelection(TOURNAMENT_ARITY)
50          );
51          
52          // initial population
53          Population initial = randomPopulation();
54          // stopping conditions
55          StoppingCondition stopCond = new FixedGenerationCount(NUM_GENERATIONS);
56          
57          // best initial chromosome
58          Chromosome bestInitial = initial.getFittestChromosome();
59          
60          // run the algorithm
61          Population finalPopulation = ga.evolve(initial, stopCond);
62          
63          // best chromosome from the final population
64          Chromosome bestFinal = finalPopulation.getFittestChromosome();
65          
66          // the only thing we can test is whether the final solution is not worse than the initial one
67          // however, for some implementations of GA, this need not be true :)
68          
69          assertTrue(bestFinal.compareTo(bestInitial) > 0);
70          
71          //System.out.println(bestInitial);
72          //System.out.println(bestFinal);
73      }
74      
75      
76      
77      
78      /**
79       * Initializes a random population.
80       */
81      private static ElitisticListPopulation randomPopulation() {
82          List<Chromosome> popList = new LinkedList<Chromosome>();
83          
84          for (int i=0; i<POPULATION_SIZE; i++) {
85              BinaryChromosome randChrom = new FindOnes(BinaryChromosome.randomBinaryRepresentation(DIMENSION));
86              popList.add(randChrom);
87          }        
88          return new ElitisticListPopulation(popList, popList.size(), ELITISM_RATE);
89      }
90      
91      /**
92       * Chromosomes represented by a binary chromosome.
93       * 
94       * The goal is to set all bits (genes) to 1.
95       */
96      private static class FindOnes extends BinaryChromosome {
97  
98          public FindOnes(List<Integer> representation) {
99              super(representation);
100         }
101 
102         /**
103          * Returns number of elements != 0
104          */
105         public double fitness() {
106             int num = 0;
107             for (int val : this.getRepresentation()) {
108                 if (val != 0)
109                     num++;
110             }
111             // number of elements >= 0
112             return num;
113         }
114 
115         @Override
116         public AbstractListChromosome<Integer> newFixedLengthChromosome(List<Integer> representation) {
117             return new FindOnes(representation);
118         }
119 
120     }
121 }