001 package org.jaga.selection;
002
003 import org.jaga.definitions.*;
004
005
006 /**
007 * TODO: Complete these comments.
008 *
009 * <p><u>Project:</u> JAGA - Java API for Genetic Algorithms.</p>
010 *
011 * <p><u>Company:</u> University College London and JAGA.Org
012 * (<a href="http://www.jaga.org" target="_blank">http://www.jaga.org</a>).
013 * </p>
014 *
015 * <p><u>Copyright:</u> (c) 2004 by G. Paperin.<br/>
016 * This program is free software; you can redistribute it and/or modify
017 * it under the terms of the GNU General Public License as published by
018 * the Free Software Foundation, ONLY if you include a note of the original
019 * author(s) in any redistributed/modified copy.<br/>
020 * This program is distributed in the hope that it will be useful,
021 * but WITHOUT ANY WARRANTY; without even the implied warranty of
022 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
023 * GNU General Public License for more details.<br/>
024 * You should have received a copy of the GNU General Public License
025 * along with this program; if not, write to the Free Software
026 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
027 * or see http://www.gnu.org/licenses/gpl.html</p>
028 *
029 * @author Greg Paperin (greg@jaga.org)
030 *
031 * @version JAGA public release 1.0 beta
032 */
033
034 public class RouletteWheelSelection implements SelectionAlgorithm {
035
036 private static final Class applicableFitnessClass = AbsoluteFitness.class;
037 public static final double MIN_FITNESS_LIMIT = -Double.MAX_VALUE;
038
039 private double minFitness = MIN_FITNESS_LIMIT;
040
041 public RouletteWheelSelection() {}
042
043 public RouletteWheelSelection(double minFitness) {
044 setMinFitness(minFitness);
045 }
046
047 public double getMinFitness() {
048 return this.minFitness;
049 }
050
051 public void setMinFitness(double minFitness) {
052 if (Double.isNaN(minFitness)
053 || Double.NEGATIVE_INFINITY == minFitness
054 || Double.POSITIVE_INFINITY == minFitness)
055 throw new IllegalArgumentException("Minumum fitness is an illegal "
056 + "value or larger then maximum "
057 + " fitness (" + minFitness + ")");
058 this.minFitness = minFitness;
059 }
060
061 public Class getApplicableFitnessClass() {
062 return applicableFitnessClass;
063 }
064
065 public Individual select(Population population, int age, GAParameterSet params) {
066 double cumSum = calculateCumulativeFitness(population);
067 return spinRoulette(cumSum, population, params);
068 }
069
070 public Individual [] select(Population population, int howMany, int age, GAParameterSet params) {
071 double cumSum = calculateCumulativeFitness(population);
072 Individual [] selection = new Individual[howMany];
073 for (int i = 0; i < howMany; i++) {
074 selection[i] = spinRoulette(cumSum, population, params);
075 }
076 return selection;
077 }
078
079 private double calculateCumulativeFitness(Population population) {
080 double sum = 0;
081 for (int i = 0; i < population.getSize(); i++) {
082 double fitVal = getRelativeFitnessValue(population.getMember(i));
083 sum += fitVal;
084 }
085 if (sum == Double.POSITIVE_INFINITY || Double.isNaN(sum))
086 throw new IllegalStateException("\nCumulative fitness is " + sum
087 + ", which is over the bound. "
088 + "Maybe lower fitness bound is "
089 + "set too low? (" + this.minFitness + ")");
090 return sum;
091 }
092
093 private Individual spinRoulette(double cumSum, Population pop, GAParameterSet params) {
094
095 int popSize = pop.getSize();
096
097 if (0 == cumSum)
098 return pop.getMember(params.getRandomGenerator().nextInt(0, popSize));
099
100 double roulette = params.getRandomGenerator().nextDouble(0, cumSum);
101
102 double loB = 0.0;
103 double upB = 0.0;
104 for (int i = 0; i < popSize; i++) {
105 Individual indv = pop.getMember(i);
106 double fval = getRelativeFitnessValue(indv);
107 upB += fval;
108 if (loB <= roulette && roulette < upB)
109 return indv;
110 loB = upB;
111 }
112
113 throw new Error("Something is dodgy, this line should never be executed!");
114 }
115
116 private double getRelativeFitnessValue(Individual indv) {
117 Fitness f = indv.getFitness();
118 assert null != f : "Individuall has null fitness";
119 AbsoluteFitness fit = (AbsoluteFitness) f;
120 double rval = fit.getValue() - this.minFitness;
121 if (0 > rval)
122 throw new IllegalArgumentException("\nIndividual has a fitness value smaller "
123 + "then the boundary (" + fit.getValue() + " < " + this.minFitness);
124 return rval;
125 }
126
127 }