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    public class FitnessCachingTest {
027        
028        // parameters for the GA
029        private static final int DIMENSION = 50; 
030        private static final double CROSSOVER_RATE = 1;
031        private static final double MUTATION_RATE = 0.1;
032        private static final int TOURNAMENT_ARITY = 5;
033        
034        private static final int POPULATION_SIZE = 10;
035        private static final int NUM_GENERATIONS = 50;
036        private static final double ELITISM_RATE = 0.2;
037    
038        // how many times was the fitness computed
039        public static int fitnessCalls = 0;
040    
041    
042        @Test
043        public void testFitnessCaching() {
044            // initialize a new genetic algorithm
045            GeneticAlgorithm ga = new GeneticAlgorithm(
046                    new OnePointCrossover<Integer>(),
047                    CROSSOVER_RATE, // all selected chromosomes will be recombined (=crosssover)
048                    new BinaryMutation(),
049                    MUTATION_RATE, // no mutation
050                    new TournamentSelection(TOURNAMENT_ARITY)
051            );
052            
053            // initial population
054            Population initial = randomPopulation();
055            // stopping conditions
056            StoppingCondition stopCond = new FixedGenerationCount(NUM_GENERATIONS);
057            
058            // run the algorithm
059            ga.evolve(initial, stopCond);
060            
061            int neededCalls =
062                POPULATION_SIZE /*initial population*/ +
063                (NUM_GENERATIONS - 1) /*for each population*/ * (int)(POPULATION_SIZE * (1.0 - ELITISM_RATE)) /*some chromosomes are copied*/
064                ;
065            assertTrue(fitnessCalls <= neededCalls); // some chromosomes after crossover may be the same os old ones
066        }
067    
068    
069        /**
070         * Initializes a random population.
071         */
072        private static ElitisticListPopulation randomPopulation() {
073            List<Chromosome> popList = new LinkedList<Chromosome>();
074            
075            for (int i=0; i<POPULATION_SIZE; i++) {
076                BinaryChromosome randChrom = new DummyCountingBinaryChromosome(BinaryChromosome.randomBinaryRepresentation(DIMENSION));
077                popList.add(randChrom);
078            }        
079            return new ElitisticListPopulation(popList, popList.size(), ELITISM_RATE);
080        }
081        
082        private static class DummyCountingBinaryChromosome extends DummyBinaryChromosome {
083    
084            public DummyCountingBinaryChromosome(List<Integer> representation) {
085                super(representation);
086            }        
087    
088            @Override
089            public double fitness() {
090                fitnessCalls++;
091                return 0;
092            }
093        }
094    }