CoinsEnergyFitnessFunction


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.energy;
11  
12  import org.jgap.*;
13  
14  /**
15   * Sample fitness function for the CoinsEnergy example. Adapted from
16   * examples.MinimizingMakeChangeFitnessFunction
17   *
18   * @author Klaus Meffert
19   * @since 2.4
20   */
21  public class CoinsEnergyFitnessFunction
22      extends FitnessFunction {
23    /** String containing the CVS revision. Read out via reflection!*/
24    private final static String   CVS_REVISION = "$Revision: 1.4 $";
25  
26    private final int m_targetAmount;
27  
28    private final double m_maxWeight;
29  
30    public static final int MAX_BOUND = 10000;
31    public static final double MAX_WEIGHT = 500;
32  
33    private static final double ZERO_DIFFERENCE_FITNESS = Math.sqrt(MAX_BOUND);
34  
35    public CoinsEnergyFitnessFunction(int a_targetAmount, double a_maxWeight) {
36      if (a_targetAmount < 1 || a_targetAmount >= MAX_BOUND) {
37        throw new IllegalArgumentException  (
38            "Change amount must be between 1 and " + MAX_BOUND + " cents.");
39      }
40  
41      if (a_maxWeight < 0 || a_maxWeight >= MAX_WEIGHT) {
42        throw new IllegalArgumentException  (
43            "Max weight must be greater than 0 and not greater than "
44            + MAX_WEIGHT + " grammes");
45      }
46      m_targetAmount = a_targetAmount;
47      m_maxWeight = a_maxWeight;
48    }
49  
50    /**
51     * Determine the fitness of the given Chromosome instance. The higher the
52     * return value, the more fit the instance. This method should always
53     * return the same fitness value for two equivalent Chromosome instances.
54     *
55     * @param a_subject the Chromosome instance to evaluate
56     *
57     * @return positive double reflecting the fitness rating of the given
58     * Chromosome
59     * @since 2.0 (until 1.1: return type int)
60     * @author Neil Rotstan, Klaus Meffert, John Serri
61     */
62    public double evaluate(IChromosome a_subject) {
63      // The fitness value measures both how close the value is to the
64      // target amount supplied by the user and the total number of coins
65      // represented by the solution. We do this in two steps: first,
66      // we consider only the represented amount of change vs. the target
67      // amount of change and return higher fitness values for amounts
68      // closer to the target, and lower fitness values for amounts further
69      // away from the target. Then we go to step 2, which returns a higher
70      // fitness value for solutions representing fewer total coins, and
71      // lower fitness values for solutions representing more total coins.
72      // ------------------------------------------------------------------
73      int changeAmount = amountOfChange(a_subject);
74      int totalCoins = getTotalNumberOfCoins(a_subject);
75      int changeDifference = Math.abs(m_targetAmount - changeAmount);
76  
77      double fitness;
78  
79      // Step 1: Determine total sum of energies (interpreted as weights here)
80      // of coins. If higher than the given maximum value, the solution is not
81      // accepted in any way, i.e. the fitness value is then set to the worst
82      // value.
83      double totalWeight = getTotalWeight(a_subject);
84      if (totalWeight > m_maxWeight) {
85        if (a_subject.getConfiguration().getFitnessEvaluator().isFitter(2, 1)) {
86          return 1.0d;
87        }
88        else {
89          return MAX_BOUND;
90        }
91      }
92  
93      if (a_subject.getConfiguration().getFitnessEvaluator().isFitter(2, 1)) {
94        fitness = MAX_BOUND;
95      }
96      else {
97        fitness = 0.0d;
98      }
99  
100     // Step 2: Determine distance of amount represented by solution from
101     // the target amount.
102     // -----------------------------------------------------------------
103     if (a_subject.getConfiguration().getFitnessEvaluator().isFitter(2, 1)) {
104       fitness -= changeDifferenceBonus(MAX_BOUND/3, changeDifference);
105     }
106     else {
107       fitness += changeDifferenceBonus(MAX_BOUND/3, changeDifference);
108     }
109 
110     // Step 3: We divide the fitness value by a penalty based on the number of
111     // coins. The higher the number of coins the higher the penalty and the
112     // smaller the fitness value.
113     // And inversely the smaller number of coins in the solution the higher
114     // the resulting fitness value.
115     // -----------------------------------------------------------------------
116     if (a_subject.getConfiguration().getFitnessEvaluator().isFitter(2, 1)) {
117       fitness -= computeCoinNumberPenalty(MAX_BOUND/3, totalCoins);
118     }
119     else {
120       fitness += computeCoinNumberPenalty(MAX_BOUND/3, totalCoins);
121     }
122 
123     // Step 4: Penalize higher weight (= engery) values.
124     // -------------------------------------------------
125     if (a_subject.getConfiguration().getFitnessEvaluator().isFitter(2, 1)) {
126       fitness -= computeWeightPenalty(MAX_BOUND/3, totalWeight);
127     }
128     else {
129       fitness += computeWeightPenalty(MAX_BOUND/3, totalWeight);
130     }
131 
132     // Make sure fitness value is always positive.
133     // -------------------------------------------
134     return Math.max(1.0d, fitness);
135   }
136 
137   /**
138    * Bonus calculation of fitness value.
139    * @param a_maxFitness maximum fitness value appliable
140    * @param a_changeDifference change difference in coins for the coins problem
141    * @return bonus for given change difference
142    * @author Klaus Meffert
143    * @since 2.3
144    */
145   protected double changeDifferenceBonus(double a_maxFitness,
146                                          int a_changeDifference) {
147     if (a_changeDifference == 0) {
148       return a_maxFitness;
149     }
150     else {
151       // we arbitrarily work with half of the maximum fitness as basis for
152       // non-optimal solutions (concerning change difference)
153       return Math.min(a_maxFitness, Math.pow(a_changeDifference, 2.2d));
154     }
155   }
156 
157   /**
158    * Calculates the penalty to apply to the fitness value based on the ammount
159    * of coins in the solution
160    *
161    * @param a_maxFitness maximum fitness value allowed
162    * @param a_coins number of coins in the solution
163    * @return penalty for the fitness value base on the number of coins
164    *
165    * @author John Serri
166    * @since 2.4
167    */
168   protected double computeCoinNumberPenalty(double a_maxFitness, int a_coins) {
169     if (a_coins == 1) {
170       // we know the solution cannot have less than one coin
171       return 0;
172     }
173     else {
174       if (a_coins < 1) {
175         return a_maxFitness;
176       }
177       // The more coins the more penalty, but not more than the maximum
178       // fitness value possible. Let's avoid linear behavior and use
179       // exponential penalty calculation instead
180       return (Math.min(a_maxFitness, Math.pow(a_coins, 1.3d)));
181     }
182   }
183 
184   /**
185    * Calculates the total amount of change (in cents) represented by
186    * the given potential solution and returns that amount.
187    *
188    * @param a_potentialSolution the potential solution to evaluate
189    * @return the total amount of change (in cents) represented by the
190    * given solution
191    *
192    * @author Neil Rotstan
193    * @since 1.0
194    */
195   public static int amountOfChange(IChromosome a_potentialSolution) {
196     int numQuarters = getNumberOfCoinsAtGene(a_potentialSolution, 0);
197     int numDimes = getNumberOfCoinsAtGene(a_potentialSolution, 1);
198     int numNickels = getNumberOfCoinsAtGene(a_potentialSolution, 2);
199     int numPennies = getNumberOfCoinsAtGene(a_potentialSolution, 3);
200     return (numQuarters * 25) + (numDimes * 10) + (numNickels * 5) +
201         numPennies;
202   }
203 
204   /**
205    * Retrieves the number of coins represented by the given potential
206    * solution at the given gene position.
207    *
208    * @param a_potentialSolution the potential solution to evaluate
209    * @param a_position the gene position to evaluate
210    * @return the number of coins represented by the potential solution at the
211    * given gene position
212    *
213    * @author Neil Rotstan
214    * @since 1.0
215    */
216   public static int getNumberOfCoinsAtGene(IChromosome a_potentialSolution,
217                                            int a_position) {
218     Integer   numCoins =
219         (Integer  ) a_potentialSolution.getGene(a_position).getAllele();
220     return numCoins.intValue();
221   }
222 
223   /**
224    * Returns the total number of coins represented by all of the genes in
225    * the given potential solution.
226    *
227    * @param a_potentialsolution the potential solution to evaluate
228    * @return total number of coins represented by the given Chromosome
229    *
230    * @author Neil Rotstan
231    * @since 2.4
232    */
233   public static int getTotalNumberOfCoins(IChromosome a_potentialsolution) {
234     int totalCoins = 0;
235     int numberOfGenes = a_potentialsolution.size();
236     for (int i = 0; i < numberOfGenes; i++) {
237       totalCoins += getNumberOfCoinsAtGene(a_potentialsolution, i);
238     }
239     return totalCoins;
240   }
241 
242   /**
243    * Returns the total weight of all coins.
244    *
245    * @param a_potentialSolution the potential solution to evaluate
246    * @return total weight of all coins
247    *
248    * @author Klaus Meffert
249    * @since 2.4
250    */
251   public static double getTotalWeight(IChromosome a_potentialSolution) {
252     double totalWeight = 0.0d;
253     int numberOfGenes = a_potentialSolution.size();
254     for (int i = 0; i < numberOfGenes; i++) {
255       int coinsNumber = getNumberOfCoinsAtGene(a_potentialSolution,i);
256       totalWeight += a_potentialSolution.getGene(i).getEnergy() * coinsNumber;
257     }
258     return totalWeight;
259   }
260 
261   /**
262    *
263    * @param a_maxFitness the maximum fitness value allowed
264    * @param a_weight the coins weight of the current solution
265    * @return the penalty computed
266    * @author Klaus Meffert
267    * @since 2.4
268    */
269   protected double computeWeightPenalty(double a_maxFitness, double a_weight) {
270     if (a_weight <= 0) {
271       // we know the solution cannot have less than one coin
272       return 0;
273     }
274     else {
275       // The more weight the more penalty, but not more than the maximum
276       // fitness value possible. Let's avoid linear behavior and use
277       // exponential penalty calculation instead
278       return (Math.min(a_maxFitness, a_weight * a_weight));
279     }
280   }
281 
282 }
283
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags