View Javadoc

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