1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 package org.apache.commons.math.genetics; 18 19 import java.util.ArrayList; 20 import java.util.List; 21 22 /** 23 * Tournament selection scheme. Each of the two selected chromosomes is selected 24 * based on n-ary tournament -- this is done by drawing {@link #arity} random 25 * chromosomes without replacement from the population, and then selecting the 26 * fittest chromosome among them. 27 * 28 * @since 2.0 29 * @version $Revision: 811685 $ $Date: 2009-09-05 19:36:48 +0200 (sam. 05 sept. 2009) $ 30 */ 31 public class TournamentSelection implements SelectionPolicy { 32 33 /** number of chromosomes included in the tournament selections */ 34 private int arity; 35 36 /** 37 * Creates a new TournamentSelection instance. 38 * 39 * @param arity 40 * how many chromosomes will be drawn to the tournament 41 */ 42 public TournamentSelection(int arity) { 43 this.arity = arity; 44 } 45 46 /** 47 * Select two chromosomes from the population. Each of the two selected 48 * chromosomes is selected based on n-ary tournament -- this is done by 49 * drawing {@link #arity} random chromosomes without replacement from the 50 * population, and then selecting the fittest chromosome among them. 51 * 52 * @param population 53 * the population from which the chromosomes are choosen. 54 * @return the selected chromosomes. 55 */ 56 public ChromosomePair select(Population population) { 57 return new ChromosomePair( 58 tournament((ListPopulation) population), 59 tournament((ListPopulation)population) 60 ); 61 } 62 63 /** 64 * Helper for {@link #select(Population)}. Draw {@link #arity} random 65 * chromosomes without replacement from the population, and then select the 66 * fittest chromosome among them. 67 * 68 * @param population 69 * the population from which the chromosomes are choosen. 70 * @return the selected chromosome. 71 */ 72 private Chromosome tournament(ListPopulation population) { 73 if (population.getPopulationSize() < this.arity) 74 throw new IllegalArgumentException("Tournament arity cannot be bigger than population size."); 75 // auxiliary population 76 ListPopulation tournamentPopulation = new ListPopulation(this.arity) { 77 public Population nextGeneration() { 78 // not useful here 79 return null; 80 } 81 }; 82 83 // create a copy of the chromosome list 84 List<Chromosome> chromosomes = new ArrayList<Chromosome> (population.getChromosomes()); 85 for (int i=0; i<this.arity; i++) { 86 // select a random individual and add it to the tournament 87 int rind = GeneticAlgorithm.getRandomGenerator().nextInt(chromosomes.size()); 88 tournamentPopulation.addChromosome(chromosomes.get(rind)); 89 // do not select it again 90 chromosomes.remove(rind); 91 } 92 // the winner takes it all 93 return tournamentPopulation.getFittestChromosome(); 94 } 95 96 /** 97 * Gets the arity (number of chromosomes drawn to the tournament). 98 * 99 * @return arity of the tournament 100 */ 101 public int getArity() { 102 return arity; 103 } 104 105 /** 106 * Sets the arity (number of chromosomes drawn to the tournament). 107 * 108 * @param arity arity of the tournament 109 */ 110 public void setArity(int arity) { 111 this.arity = arity; 112 } 113 114 } 115
