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.assertTrue;
020
021 import java.util.ArrayList;
022 import java.util.List;
023
024 import org.junit.Test;
025
026 /**
027 * This is also an example of usage.
028 *
029 * This algorithm does "stochastic sorting" of a sequence 0,...,N.
030 *
031 */
032 public class GeneticAlgorithmTestPermutations {
033
034 // parameters for the GA
035 private static final int DIMENSION = 20;
036 private static final int POPULATION_SIZE = 80;
037 private static final int NUM_GENERATIONS = 200;
038 private static final double ELITISM_RATE = 0.2;
039 private static final double CROSSOVER_RATE = 1;
040 private static final double MUTATION_RATE = 0.08;
041 private static final int TOURNAMENT_ARITY = 2;
042
043 // numbers from 0 to N-1
044 private static List<Integer> sequence = new ArrayList<Integer>();
045 static {
046 for (int i=0; i<DIMENSION; i++) {
047 sequence.add(i);
048 }
049 }
050
051 @Test
052 public void test() {
053 // to test a stochastic algorithm is hard, so this will rather be an usage example
054
055 // initialize a new genetic algorithm
056 GeneticAlgorithm ga = new GeneticAlgorithm(
057 new OnePointCrossover<Integer>(),
058 CROSSOVER_RATE,
059 new RandomKeyMutation(),
060 MUTATION_RATE,
061 new TournamentSelection(TOURNAMENT_ARITY)
062 );
063
064 // initial population
065 Population initial = randomPopulation();
066 // stopping conditions
067 StoppingCondition stopCond = new FixedGenerationCount(NUM_GENERATIONS);
068
069 // best initial chromosome
070 Chromosome bestInitial = initial.getFittestChromosome();
071
072 // run the algorithm
073 Population finalPopulation = ga.evolve(initial, stopCond);
074
075 // best chromosome from the final population
076 Chromosome bestFinal = finalPopulation.getFittestChromosome();
077
078 // the only thing we can test is whether the final solution is not worse than the initial one
079 // however, for some implementations of GA, this need not be true :)
080
081 assertTrue(bestFinal.compareTo(bestInitial) > 0);
082
083 //System.out.println(bestInitial);
084 //System.out.println(bestFinal);
085 }
086
087
088 /**
089 * Initializes a random population
090 */
091 private static ElitisticListPopulation randomPopulation() {
092 List<Chromosome> popList = new ArrayList<Chromosome>();
093 for (int i=0; i<POPULATION_SIZE; i++) {
094 Chromosome randChrom = new MinPermutations(RandomKey.randomPermutation(DIMENSION));
095 popList.add(randChrom);
096 }
097 return new ElitisticListPopulation(popList, popList.size(), ELITISM_RATE);
098 }
099
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 }