    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 19:36:48 +0200 (sam. 05 sept. 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    }