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: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 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    }