TournamentSelector


1   /*
2    * This file is part of JGAP.
3    *
4    * JGAP offers a dual license model containing the LGPL as well as the MPL.
5    *
6    * For licencing information please see the file license.txt included with JGAP
7    * or have a look at the top of class org.jgap.Chromosome which representatively
8    * includes the JGAP license policy applicable for any file delivered with JGAP.
9    */
10  package org.jgap.impl;
11  
12  import java.util.*;
13  import org.jgap.*;
14  
15  /**
16   * Implementation of a NaturalSelector that plays tournaments to determine
17   * the chromosomes to be taken to the next generation.
18   * <p>
19   * The tournament size can be adjusted as well as the probability for selecting
20   * an individual.
21   *
22   * @author Klaus Meffert
23   * @since 2.0
24   */
25  public class TournamentSelector
26      extends NaturalSelector {
27    /** String containing the CVS revision. Read out via reflection!*/
28    private final static String   CVS_REVISION = "$Revision: 1.19 $";
29  
30    private TournamentSelectorConfigurable m_config
31        = new TournamentSelectorConfigurable();
32  
33    private List m_chromosomes;
34  
35    /**
36     * Comparator that is only concerned about fitness values
37     */
38    private FitnessValueComparator m_fitnessValueComparator;
39  
40    /**
41     * Default constructor.<p>
42     * Attention: The configuration used is the one set with the static method
43     * Genotype.setConfiguration.
44     *
45     * @author Siddhartha Azad
46     * @author Klaus Meffert
47     */
48    public TournamentSelector() {
49      super(Genotype.getStaticConfiguration());
50      init();
51    }
52  
53    private void init() {
54      m_chromosomes = new Vector();
55      m_fitnessValueComparator = new FitnessValueComparator();
56    }
57  
58    /**
59     * @param a_config the configuration to use
60     * @param a_tournament_size the size of each tournament to play
61     * @param a_probability probability for selecting the best individuals
62     *
63     * @author Klaus Meffert
64     * @since 2.0
65     */
66    public TournamentSelector(final Configuration a_config,
67                              final int a_tournament_size,
68                              final double a_probability) {
69      super(a_config);
70      init();
71      if (a_tournament_size < 1) {
72        throw new IllegalArgumentException  ("Tournament size must be at least 1!");
73      }
74      if (a_probability <= 0.0d || a_probability > 1.0d) {
75        throw new IllegalArgumentException  ("Probability must be greater 0.0 and"
76                                           + " less or equal than 1.0!");
77      }
78      m_config.m_tournament_size = a_tournament_size;
79      m_config.m_probability = a_probability;
80    }
81  
82    public void setTournamentSize(final int a_tournament_size) {
83      if (a_tournament_size < 1) {
84        throw new IllegalArgumentException  ("Tournament size must be at least 1!");
85      }
86      m_config.m_tournament_size = a_tournament_size;
87    }
88  
89    public int getTournamentSize() {
90      return m_config.m_tournament_size;
91    }
92  
93    public double getProbability() {
94      return m_config.m_probability;
95    }
96  
97    public void setProbability(final double a_probability) {
98      if (a_probability <= 0.0d || a_probability > 1.0d) {
99        throw new IllegalArgumentException  ("Probability must be greater 0.0 and"
100                                          + " less or equal than 1.0!");
101     }
102     m_config.m_probability = a_probability;
103   }
104 
105   /**
106    * Select a given number of Chromosomes from the pool that will move on
107    * to the next generation population. This selection will be guided by the
108    * fitness values. The chromosomes with the best fitness value win.
109    *
110    * @param a_howManyToSelect int
111    * @param a_from_pop the population the Chromosomes will be selected from
112    * @param a_to_pop the population the Chromosomes will be added to
113    *
114    * @author Klaus Meffert
115    * @since 2.0
116    */
117   public void select(final int a_howManyToSelect, final Population a_from_pop,
118                      Population a_to_pop) {
119     if (a_from_pop != null) {
120       for (int i = 0; i < a_from_pop.size(); i++) {
121         add(a_from_pop.getChromosome(i));
122       }
123     }
124     List tournament = new Vector();
125     RandomGenerator rn = getConfiguration().getRandomGenerator();
126     int size = m_chromosomes.size();
127     if (size == 0) {
128       return;
129     }
130     int k;
131     for (int i = 0; i < a_howManyToSelect; i++) {
132       // choose [tournament size] individuals from the population at random
133       tournament.clear();
134       for (int j = 0; j < m_config.m_tournament_size; j++) {
135         k = rn.nextInt(size);
136         tournament.add(m_chromosomes.get(k));
137       }
138       Collections.sort(tournament, m_fitnessValueComparator);
139       double prob = rn.nextDouble();
140       double probAccumulated = m_config.m_probability;
141       int index = 0;
142       //play the tournament
143       if (m_config.m_tournament_size > 1) {
144         do {
145           if (prob <= probAccumulated) {
146             break;
147           }
148           else {
149             probAccumulated += probAccumulated * (1 - m_config.m_probability);
150             index++;
151           }
152         }
153         while (index < m_config.m_tournament_size - 1);
154       }
155       a_to_pop.addChromosome( (IChromosome) tournament.get(index));
156     }
157   }
158 
159   /**
160    * @return false as we allow to return the same chromosome multiple times
161    *
162    * @author Klaus Meffert
163    * @since 2.0
164    */
165   public boolean returnsUniqueChromosomes() {
166     return false;
167   }
168 
169   public void empty() {
170     m_chromosomes.clear();
171   }
172 
173   /**
174    *
175    * @param a_chromosomeToAdd the Chromosome to add
176    *
177    * @author Klaus Meffert
178    * @since 2.0
179    */
180   protected void add(final IChromosome a_chromosomeToAdd) {
181     m_chromosomes.add(a_chromosomeToAdd);
182   }
183 
184   /**
185    * Comparator regarding only the fitness value. Best fitness value will
186    * be on first position of resulting sorted list
187    *
188    * @author Klaus Meffert
189    * @since 2.0
190    */
191   private class FitnessValueComparator
192       implements Comparator {
193     public int compare(final Object   a_first, final Object   a_second) {
194       IChromosome chrom1 = (IChromosome) a_first;
195       IChromosome chrom2 = (IChromosome) a_second;
196       if (getConfiguration().getFitnessEvaluator().isFitter(chrom2.
197           getFitnessValue(), chrom1.getFitnessValue())) {
198         return 1;
199       }
200       else if (getConfiguration().getFitnessEvaluator().isFitter(
201           chrom1.getFitnessValue(), chrom2.getFitnessValue())) {
202         return -1;
203       }
204       else {
205         return 0;
206       }
207     }
208   }
209 
210   class TournamentSelectorConfigurable {
211     /**
212      * The probability for selecting the best chromosome in a tournament.
213      * For the second-best chromosome it would be p * (1 - p).
214      * For the third-best chromosome it would be p * (p * (1 - p)) and so forth.
215      */
216     public double m_probability;
217 
218     /**
219      * Size of a tournament to be played, i.e. number of chromosomes taken into
220      * account for one selection round
221      */
222     public int m_tournament_size;
223 
224   }
225 }
226
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags