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 }