KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > examples > knapsack > KnapsackFitnessFunction


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.knapsack;
11
12 import org.jgap.*;
13
14 /**
15  * Fitness function for the knapsack example.
16  *
17  * @author Klaus Meffert
18  * @since 2.3
19  */
20 public class KnapsackFitnessFunction
21     extends FitnessFunction {
22   /** String containing the CVS revision. Read out via reflection!*/
23   private final static String JavaDoc CVS_REVISION = "$Revision: 1.4 $";
24
25   private final double m_knapsackVolume;
26
27   public static final double MAX_BOUND = 1000000000.0d;
28
29   private static final double ZERO_DIFFERENCE_FITNESS = Math.sqrt(MAX_BOUND);
30
31   public KnapsackFitnessFunction(double a_knapsackVolume) {
32     if (a_knapsackVolume < 1 || a_knapsackVolume >= MAX_BOUND) {
33       throw new IllegalArgumentException JavaDoc(
34           "Knapsack volumen must be between 1 and " + MAX_BOUND + ".");
35     }
36     m_knapsackVolume = a_knapsackVolume;
37   }
38
39   /**
40    * Determine the fitness of the given Chromosome instance. The higher the
41    * return value, the more fit the instance. This method should always
42    * return the same fitness value for two equivalent Chromosome instances.
43    *
44    * @param a_subject the Chromosome instance to evaluate
45    * @return a positive double reflecting the fitness rating of the given
46    * Chromosome
47    *
48    * @author Klaus Meffert
49    * @since 2.3
50    */
51   public double evaluate(IChromosome a_subject) {
52     // The fitness value measures both how close the value is to the
53 // target amount supplied by the user and the total number of items
54 // represented by the solution. We do this in two steps: first,
55 // we consider only the represented amount of change vs. the target
56 // amount of change and return higher fitness values for amounts
57 // closer to the target, and lower fitness values for amounts further
58 // away from the target. Then we go to step 2, which returns a higher
59 // fitness value for solutions representing fewer total items, and
60 // lower fitness values for solutions representing more total items.
61 // ------------------------------------------------------------------
62 double totalVolume = getTotalVolume(a_subject);
63     int numberOfItems = getTotalNumberOfItems(a_subject);
64     double volumeDifference = Math.abs(m_knapsackVolume - totalVolume);
65     double fitness = 0.0d;
66     // Step 1: Determine distance of amount represented by solution from
67 // the target amount. If the change difference is greater than zero we
68 // will divide one by the difference in change between the
69 // solution amount and the target amount. That will give the desired
70 // effect of returning higher values for amounts closer to the target
71 // amount and lower values for amounts further away from the target
72 // amount.
73 // In the case where the change difference is zero it means that we have
74 // the correct amount and we assign a higher fitness value
75 // -----------------------------------------------------------------
76 fitness += volumeDifferenceBonus(MAX_BOUND, volumeDifference);
77     // Step 2: We divide the fitness value by a penalty based on the number of
78 // items. The higher the number of items the higher the penalty and the
79 // smaller the fitness value.
80 // And inversely the smaller number of items in the solution the higher
81 // the resulting fitness value.
82 // -----------------------------------------------------------------------
83 fitness -= computeItemNumberPenalty(MAX_BOUND, numberOfItems);
84     // Make sure fitness value is always positive.
85 // -------------------------------------------
86 return Math.max(1.0d, fitness);
87   }
88
89   /**
90    * Bonus calculation of fitness value.
91    * @param a_maxFitness maximum fitness value appliable
92    * @param a_volumeDifference volume difference in ccm for the items problem
93    * @return bonus for given volume difference
94    *
95    * @author Klaus Meffert
96    * @since 2.3
97    */
98   protected double volumeDifferenceBonus(double a_maxFitness,
99                                          double a_volumeDifference) {
100     if (a_volumeDifference == 0) {
101       return a_maxFitness;
102     }
103     else {
104       // we arbitrarily work with half of the maximum fitness as basis for non-
105 // optimal solutions (concerning volume difference)
106 return a_maxFitness / 2 - (a_volumeDifference * a_volumeDifference);
107     }
108   }
109
110   /**
111    * Calculates the penalty to apply to the fitness value based on the amount
112    * of items in the solution.
113    *
114    * @param a_maxFitness upper boundary for fitness value possible
115    * @param a_items number of items in the solution
116    * @return a penalty for the fitness value based on the number of items
117    *
118    * @author Klaus Meffert
119    * @since 2.3
120    */
121   protected double computeItemNumberPenalty(double a_maxFitness, int a_items) {
122     if (a_items == 0) {
123       // We know the solution cannot have less than zero items.
124 // ------------------------------------------------------
125 return 0;
126     }
127     else {
128       // The more items the more penalty, but not more than the maximum fitness
129 // value possible. Let's avoid linear behavior and use
130 // exponential penalty calculation instead.
131 // ----------------------------------------------------------------------
132 return (Math.min(a_maxFitness, a_items * a_items));
133     }
134   }
135
136   /**
137    * Calculates the total amount of change (in cents) represented by
138    * the given potential solution and returns that amount.
139    *
140    * @param a_potentialSolution the potential solution to evaluate
141    * @return the total amount of change (in cents) represented by the
142    * given solution
143    *
144    * @author Klaus Meffert
145    * @since 2.3
146    */
147   public static double getTotalVolume(IChromosome a_potentialSolution) {
148     double volume = 0.0d;
149     for (int i = 0; i < a_potentialSolution.size(); i++) {
150       volume += getNumberOfItemsAtGene(a_potentialSolution, i) *
151           KnapsackMain.itemVolumes[i];
152     }
153     return volume;
154   }
155
156   /**
157    * Retrieves the number of items represented by the given potential
158    * solution at the given gene position.
159    *
160    * @param a_potentialSolution the potential solution to evaluate
161    * @param a_position the gene position to evaluate
162    * @return the number of items represented by the potential solution
163    * at the given gene position
164    *
165    * @author Klaus Meffert
166    * @since 2.3
167    */
168   public static int getNumberOfItemsAtGene(IChromosome a_potentialSolution,
169                                            int a_position) {
170     Integer JavaDoc numItems =
171         (Integer JavaDoc) a_potentialSolution.getGene(a_position).getAllele();
172     return numItems.intValue();
173   }
174
175   /**
176    * Returns the total number of items represented by all of the genes in
177    * the given potential solution.
178    *
179    * @param a_potentialSolution the potential solution to evaluate
180    * @return the total number of items represented by the given Chromosome
181    *
182    * @author Klaus Meffert
183    * @since 2.3
184    */
185   public static int getTotalNumberOfItems(IChromosome a_potentialSolution) {
186     int totalItems = 0;
187     int numberOfGenes = a_potentialSolution.size();
188     for (int i = 0; i < numberOfGenes; i++) {
189       totalItems += getNumberOfItemsAtGene(a_potentialSolution, i);
190     }
191     return totalItems;
192   }
193 }
194
Popular Tags