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