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 java.util.ArrayList; 020 import java.util.List; 021 022 /** 023 * Tournament selection scheme. Each of the two selected chromosomes is selected 024 * based on n-ary tournament -- this is done by drawing {@link #arity} random 025 * chromosomes without replacement from the population, and then selecting the 026 * fittest chromosome among them. 027 * 028 * @since 2.0 029 * @version $Revision: 811685 $ $Date: 2009-09-05 13:36:48 -0400 (Sat, 05 Sep 2009) $ 030 */ 031 public class TournamentSelection implements SelectionPolicy { 032 033 /** number of chromosomes included in the tournament selections */ 034 private int arity; 035 036 /** 037 * Creates a new TournamentSelection instance. 038 * 039 * @param arity 040 * how many chromosomes will be drawn to the tournament 041 */ 042 public TournamentSelection(int arity) { 043 this.arity = arity; 044 } 045 046 /** 047 * Select two chromosomes from the population. Each of the two selected 048 * chromosomes is selected based on n-ary tournament -- this is done by 049 * drawing {@link #arity} random chromosomes without replacement from the 050 * population, and then selecting the fittest chromosome among them. 051 * 052 * @param population 053 * the population from which the chromosomes are choosen. 054 * @return the selected chromosomes. 055 */ 056 public ChromosomePair select(Population population) { 057 return new ChromosomePair( 058 tournament((ListPopulation) population), 059 tournament((ListPopulation)population) 060 ); 061 } 062 063 /** 064 * Helper for {@link #select(Population)}. Draw {@link #arity} random 065 * chromosomes without replacement from the population, and then select the 066 * fittest chromosome among them. 067 * 068 * @param population 069 * the population from which the chromosomes are choosen. 070 * @return the selected chromosome. 071 */ 072 private Chromosome tournament(ListPopulation population) { 073 if (population.getPopulationSize() < this.arity) 074 throw new IllegalArgumentException("Tournament arity cannot be bigger than population size."); 075 // auxiliary population 076 ListPopulation tournamentPopulation = new ListPopulation(this.arity) { 077 public Population nextGeneration() { 078 // not useful here 079 return null; 080 } 081 }; 082 083 // create a copy of the chromosome list 084 List<Chromosome> chromosomes = new ArrayList<Chromosome> (population.getChromosomes()); 085 for (int i=0; i<this.arity; i++) { 086 // select a random individual and add it to the tournament 087 int rind = GeneticAlgorithm.getRandomGenerator().nextInt(chromosomes.size()); 088 tournamentPopulation.addChromosome(chromosomes.get(rind)); 089 // do not select it again 090 chromosomes.remove(rind); 091 } 092 // the winner takes it all 093 return tournamentPopulation.getFittestChromosome(); 094 } 095 096 /** 097 * Gets the arity (number of chromosomes drawn to the tournament). 098 * 099 * @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 }