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 }