MinimizingMakeChangeFitnessFunction


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 examples;
11  
12  import org.jgap.*;
13  
14  /**
15   * Sample fitness function for the MakeChange example.
16   *
17   * @author Neil Rotstan
18   * @author Klaus Meffert
19   * @since 1.0
20   */
21  public class MinimizingMakeChangeFitnessFunction
22      extends FitnessFunction {
23    /** String containing the CVS revision. Read out via reflection!*/
24    private final static String   CVS_REVISION = "$Revision: 1.17 $";
25  
26    private final int m_targetAmount;
27  
28    public static final int MAX_BOUND = 4000;
29  
30    public MinimizingMakeChangeFitnessFunction(int a_targetAmount) {
31      if (a_targetAmount < 1 || a_targetAmount >= MAX_BOUND) {
32        throw new IllegalArgumentException  (
33            "Change amount must be between 1 and " + MAX_BOUND + " cents.");
34      }
35      m_targetAmount = a_targetAmount;
36    }
37  
38    /**
39     * Determine the fitness of the given Chromosome instance. The higher the
40     * return value, the more fit the instance. This method should always
41     * return the same fitness value for two equivalent Chromosome instances.
42     *
43     * @param a_subject the Chromosome instance to evaluate
44     *
45     * @return positive double reflecting the fitness rating of the given
46     * Chromosome
47     * @since 2.0 (until 1.1: return type int)
48     * @author Neil Rotstan, Klaus Meffert, John Serri
49     */
50    public double evaluate(IChromosome a_subject) {
51      // Take care of the fitness evaluator. It could either be weighting higher
52      // fitness values higher (e.g.DefaultFitnessEvaluator). Or it could weight
53      // lower fitness values higher, because the fitness value is seen as a
54      // defect rate (e.g. DeltaFitnessEvaluator)
55      boolean defaultComparation = a_subject.getConfiguration().
56          getFitnessEvaluator().isFitter(2, 1);
57  
58      // The fitness value measures both how close the value is to the
59      // target amount supplied by the user and the total number of coins
60      // represented by the solution. We do this in two steps: first,
61      // we consider only the represented amount of change vs. the target
62      // amount of change and return higher fitness values for amounts
63      // closer to the target, and lower fitness values for amounts further
64      // away from the target. Then we go to step 2, which returns a higher
65      // fitness value for solutions representing fewer total coins, and
66      // lower fitness values for solutions representing more total coins.
67      // ------------------------------------------------------------------
68      int changeAmount = amountOfChange(a_subject);
69      int totalCoins = getTotalNumberOfCoins(a_subject);
70      int changeDifference = Math.abs(m_targetAmount - changeAmount);
71      double fitness;
72      if (defaultComparation) {
73        fitness = 0.0d;
74      }
75      else {
76        fitness = MAX_BOUND/2;
77      }
78      // Step 1: Determine distance of amount represented by solution from
79      // the target amount. If the change difference is greater than zero we
80      // will divide one by the difference in change between the
81      // solution amount and the target amount. That will give the desired
82      // effect of returning higher values for amounts closer to the target
83      // amount and lower values for amounts further away from the target
84      // amount.
85      // In the case where the change difference is zero it means that we have
86      // the correct amount and we assign a higher fitness value.
87      // ---------------------------------------------------------------------
88      if (defaultComparation) {
89        fitness += changeDifferenceBonus(MAX_BOUND/2, changeDifference);
90      }
91      else {
92        fitness -= changeDifferenceBonus(MAX_BOUND/2, changeDifference);
93      }
94      // Step 2: We divide the fitness value by a penalty based on the number of
95      // coins. The higher the number of coins the higher the penalty and the
96      // smaller the fitness value.
97      // And inversely the smaller number of coins in the solution the higher
98      // the resulting fitness value.
99      // -----------------------------------------------------------------------
100     if (defaultComparation) {
101       fitness -= computeCoinNumberPenalty(MAX_BOUND/2, totalCoins);
102     }
103     else {
104       fitness += computeCoinNumberPenalty(MAX_BOUND/2, totalCoins);
105     }
106     // Make sure fitness value is always positive.
107     // -------------------------------------------
108     return Math.max(1.0d, fitness);
109   }
110 
111   /**
112    * Bonus calculation of fitness value.
113    * @param a_maxFitness maximum fitness value appliable
114    * @param a_changeDifference change difference in coins for the coins problem
115    * @return bonus for given change difference
116    *
117    * @author Klaus Meffert
118    * @since 2.3
119    */
120   protected double changeDifferenceBonus(double a_maxFitness,
121                                          int a_changeDifference) {
122     if (a_changeDifference == 0) {
123       return a_maxFitness;
124     }
125     else {
126       // we arbitrarily work with half of the maximum fitness as basis for non-
127       // optimal solutions (concerning change difference)
128       if (a_changeDifference * a_changeDifference >= a_maxFitness / 2) {
129         return 0.0d;
130       }
131       else {
132         return a_maxFitness / 2 - a_changeDifference * a_changeDifference;
133       }
134     }
135   }
136 
137   /**
138    * Calculates the penalty to apply to the fitness value based on the ammount
139    * of coins in the solution
140    *
141    * @param a_maxFitness maximum fitness value allowed
142    * @param a_coins number of coins in the solution
143    * @return penalty for the fitness value base on the number of coins
144    *
145    * @author John Serri
146    * @since 2.2
147    */
148   protected double computeCoinNumberPenalty(double a_maxFitness, int a_coins) {
149     if (a_coins == 1) {
150       // we know the solution cannot have less than one coin
151       return 0;
152     }
153     else {
154       // The more coins the more penalty, but not more than the maximum fitness
155       // value possible. Let's avoid linear behavior and use
156       // exponential penalty calculation instead
157       return (Math.min(a_maxFitness, a_coins * a_coins));
158     }
159   }
160 
161   /**
162    * Calculates the total amount of change (in cents) represented by
163    * the given potential solution and returns that amount.
164    *
165    * @param a_potentialSolution the potential solution to evaluate
166    * @return The total amount of change (in cents) represented by the
167    * given solution
168    *
169    * @author Neil Rotstan
170    * @since 1.0
171    */
172   public static int amountOfChange(IChromosome a_potentialSolution) {
173     int numQuarters = getNumberOfCoinsAtGene(a_potentialSolution, 0);
174     int numDimes = getNumberOfCoinsAtGene(a_potentialSolution, 1);
175     int numNickels = getNumberOfCoinsAtGene(a_potentialSolution, 2);
176     int numPennies = getNumberOfCoinsAtGene(a_potentialSolution, 3);
177     return (numQuarters * 25) + (numDimes * 10) + (numNickels * 5) +
178         numPennies;
179   }
180 
181   /**
182    * Retrieves the number of coins represented by the given potential
183    * solution at the given gene position.
184    *
185    * @param a_potentialSolution the potential solution to evaluate
186    * @param a_position the gene position to evaluate
187    * @return the number of coins represented by the potential solution at the
188    * given gene position
189    *
190    * @author Neil Rotstan
191    * @since 1.0
192    */
193   public static int getNumberOfCoinsAtGene(IChromosome a_potentialSolution,
194                                            int a_position) {
195     Integer   numCoins =
196         (Integer  ) a_potentialSolution.getGene(a_position).getAllele();
197     return numCoins.intValue();
198   }
199 
200   /**
201    * Returns the total number of coins represented by all of the genes in
202    * the given potential solution.
203    *
204    * @param a_potentialsolution the potential solution to evaluate
205    * @return total number of coins represented by the given Chromosome
206    *
207    * @author Neil Rotstan
208    * @since 1.0
209    */
210   public static int getTotalNumberOfCoins(IChromosome a_potentialsolution) {
211     int totalCoins = 0;
212     int numberOfGenes = a_potentialsolution.size();
213     for (int i = 0; i < numberOfGenes; i++) {
214       totalCoins += getNumberOfCoinsAtGene(a_potentialsolution, i);
215     }
216     return totalCoins;
217   }
218 }
219
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Free Books Free Magazines
Popular Tags