001    /*
002     * Licensed to the Apache Software Foundation (ASF) under one or more
003     * contributor license agreements.  See the NOTICE file distributed with
004     * this work for additional information regarding copyright ownership.
005     * The ASF licenses this file to You under the Apache License, Version 2.0
006     * (the "License"); you may not use this file except in compliance with
007     * the License.  You may obtain a copy of the License at
008     *
009     *      http://www.apache.org/licenses/LICENSE-2.0
010     *
011     * Unless required by applicable law or agreed to in writing, software
012     * distributed under the License is distributed on an "AS IS" BASIS,
013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     * See the License for the specific language governing permissions and
015     * limitations under the License.
016     */
017    package org.apache.commons.math.genetics;
018    
019    import static org.junit.Assert.*;
020    
021    import java.util.LinkedList;
022    import java.util.List;
023    import org.junit.Test;
024    
025    /**
026     * This is also an example of usage.
027     */
028    public class GeneticAlgorithmTestBinary {
029        
030        // parameters for the GA
031        private static final int DIMENSION = 50;    
032        private static final int POPULATION_SIZE = 50; 
033        private static final int NUM_GENERATIONS = 50;
034        private static final double ELITISM_RATE = 0.2;
035        private static final double CROSSOVER_RATE = 1;
036        private static final double MUTATION_RATE = 0.1;
037        private static final int TOURNAMENT_ARITY = 2;
038    
039        @Test
040        public void test() {
041            // to test a stochastic algorithm is hard, so this will rather be an usage example
042            
043            // initialize a new genetic algorithm
044            GeneticAlgorithm ga = new GeneticAlgorithm(
045                    new OnePointCrossover<Integer>(),
046                    CROSSOVER_RATE, // all selected chromosomes will be recombined (=crosssover)
047                    new BinaryMutation(),
048                    MUTATION_RATE,
049                    new TournamentSelection(TOURNAMENT_ARITY)
050            );
051            
052            // initial population
053            Population initial = randomPopulation();
054            // stopping conditions
055            StoppingCondition stopCond = new FixedGenerationCount(NUM_GENERATIONS);
056            
057            // best initial chromosome
058            Chromosome bestInitial = initial.getFittestChromosome();
059            
060            // run the algorithm
061            Population finalPopulation = ga.evolve(initial, stopCond);
062            
063            // best chromosome from the final population
064            Chromosome bestFinal = finalPopulation.getFittestChromosome();
065            
066            // the only thing we can test is whether the final solution is not worse than the initial one
067            // however, for some implementations of GA, this need not be true :)
068            
069            assertTrue(bestFinal.compareTo(bestInitial) > 0);
070            
071            //System.out.println(bestInitial);
072            //System.out.println(bestFinal);
073        }
074        
075        
076        
077        
078        /**
079         * Initializes a random population.
080         */
081        private static ElitisticListPopulation randomPopulation() {
082            List<Chromosome> popList = new LinkedList<Chromosome>();
083            
084            for (int i=0; i<POPULATION_SIZE; i++) {
085                BinaryChromosome randChrom = new FindOnes(BinaryChromosome.randomBinaryRepresentation(DIMENSION));
086                popList.add(randChrom);
087            }        
088            return new ElitisticListPopulation(popList, popList.size(), ELITISM_RATE);
089        }
090        
091        /**
092         * Chromosomes represented by a binary chromosome.
093         * 
094         * The goal is to set all bits (genes) to 1.
095         */
096        private static class FindOnes extends BinaryChromosome {
097    
098            public FindOnes(List<Integer> representation) {
099                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    }