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 }