001: /*
002: * This file is part of JGAP.
003: *
004: * JGAP offers a dual license model containing the LGPL as well as the MPL.
005: *
006: * For licencing information please see the file license.txt included with JGAP
007: * or have a look at the top of class org.jgap.Chromosome which representatively
008: * includes the JGAP license policy applicable for any file delivered with JGAP.
009: */
010: package examples.multidimension;
011:
012: import java.util.*;
013: import org.jgap.*;
014: import org.jgap.impl.*;
015:
016: /**
017: * Fitness function for the multidimension knapsack example.
018: *
019: * @author Klaus Meffert
020: * @since 3.0
021: */
022: public class KnapsackFitnessFunction extends FitnessFunction {
023: /** String containing the CVS revision. Read out via reflection!*/
024: private final static String CVS_REVISION = "$Revision: 1.1 $";
025:
026: private final double m_knapsackVolume;
027:
028: public static final double MAX_BOUND = 1000000000.0d;
029:
030: private static final double ZERO_DIFFERENCE_FITNESS = Math
031: .sqrt(MAX_BOUND);
032:
033: public KnapsackFitnessFunction(double a_knapsackVolume) {
034: if (a_knapsackVolume < 1 || a_knapsackVolume >= MAX_BOUND) {
035: throw new IllegalArgumentException(
036: "Knapsack volumen must be between 1 and "
037: + MAX_BOUND + ".");
038: }
039: m_knapsackVolume = a_knapsackVolume;
040: }
041:
042: /**
043: * Determine the fitness of the given Chromosome instance. The higher the
044: * return value, the more fit the instance. This method should always
045: * return the same fitness value for two equivalent Chromosome instances.
046: *
047: * @param a_subject the Chromosome instance to evaluate
048: * @return a positive double reflecting the fitness rating of the given
049: * Chromosome
050: *
051: * @author Klaus Meffert
052: * @since 3.0
053: */
054: public double evaluate(IChromosome a_subject) {
055: // The fitness value measures both how close the value is to the
056: // target amount supplied by the user and the total number of items
057: // represented by the solution. We do this in two steps: first,
058: // we consider only the represented amount of change vs. the target
059: // amount of change and return higher fitness values for amounts
060: // closer to the target, and lower fitness values for amounts further
061: // away from the target. Then we go to step 2, which returns a higher
062: // fitness value for solutions representing fewer total items, and
063: // lower fitness values for solutions representing more total items.
064: // ------------------------------------------------------------------
065: double totalVolume = getTotalVolume(a_subject);
066: int numberOfItems = getTotalNumberOfItems(a_subject);
067: double volumeDifference = Math.abs(m_knapsackVolume
068: - totalVolume);
069: double fitness = 0.0d;
070: // Step 1: Determine distance of amount represented by solution from
071: // the target amount. If the change difference is greater than zero we
072: // will divide one by the difference in change between the
073: // solution amount and the target amount. That will give the desired
074: // effect of returning higher values for amounts closer to the target
075: // amount and lower values for amounts further away from the target
076: // amount.
077: // In the case where the change difference is zero it means that we have
078: // the correct amount and we assign a higher fitness value
079: // -----------------------------------------------------------------
080: fitness += volumeDifferenceBonus(MAX_BOUND, volumeDifference);
081: // Step 2: We divide the fitness value by a penalty based on the number of
082: // items. The higher the number of items the higher the penalty and the
083: // smaller the fitness value.
084: // And inversely the smaller number of items in the solution the higher
085: // the resulting fitness value.
086: // -----------------------------------------------------------------------
087: fitness -= computeItemNumberPenalty(a_subject, MAX_BOUND,
088: numberOfItems);
089: // Make sure fitness value is always positive.
090: // -------------------------------------------
091: return Math.max(1.0d, fitness);
092: }
093:
094: /**
095: * Bonus calculation of fitness value.
096: * @param a_maxFitness maximum fitness value appliable
097: * @param a_volumeDifference volume difference in ccm for the items problem
098: * @return bonus for given volume difference
099: *
100: * @author Klaus Meffert
101: * @since 3.0
102: */
103: protected double volumeDifferenceBonus(double a_maxFitness,
104: double a_volumeDifference) {
105: if (a_volumeDifference == 0) {
106: return a_maxFitness;
107: } else {
108: // we arbitrarily work with half of the maximum fitness as basis for non-
109: // optimal solutions (concerning volume difference)
110: return a_maxFitness / 2
111: - (a_volumeDifference * a_volumeDifference);
112: }
113: }
114:
115: /**
116: * Calculates the penalty to apply to the fitness value based on the amount
117: * of items in the solution.
118: *
119: * @param a_potentialSolution the potential solution to evaluate
120: * @param a_maxFitness upper boundary for fitness value possible
121: * @param a_items number of items in the solution
122: * @return a penalty for the fitness value based on the number of items
123: *
124: * @author Klaus Meffert
125: * @since 3.0
126: */
127: protected double computeItemNumberPenalty(
128: IChromosome a_potentialSolution, double a_maxFitness,
129: int a_items) {
130: if (a_items == 0) {
131: // We know the solution cannot have less than zero items.
132: // ------------------------------------------------------
133: return 0;
134: } else {
135: // The more items the more penalty, but not more than the maximum fitness
136: // value possible. Let's avoid linear behavior and use
137: // exponential penalty calculation instead.
138: // ----------------------------------------------------------------------
139: double penalty = (Math.min(a_maxFitness, a_items * a_items));
140: // The more different colors the more penalty.
141: // -------------------------------------------
142: HashSet colors = new HashSet();
143: for (int i = 0; i < a_potentialSolution.size(); i++) {
144: CompositeGene comp = (CompositeGene) a_potentialSolution
145: .getGene(i);
146: IntegerGene color = (IntegerGene) comp.geneAt(0);
147: colors.add(color.getAllele());
148: }
149: int numColors = colors.size();
150: penalty += Math.pow(numColors, 10);
151: return Math.min(a_maxFitness, penalty);
152: }
153: }
154:
155: /**
156: * Calculates the total amount of change (in cents) represented by
157: * the given potential solution and returns that amount.
158: *
159: * @param a_potentialSolution the potential solution to evaluate
160: * @return the total amount of change (in cents) represented by the
161: * given solution
162: *
163: * @author Klaus Meffert
164: * @since 2.3
165: */
166: public static double getTotalVolume(IChromosome a_potentialSolution) {
167: double volume = 0.0d;
168: for (int i = 0; i < a_potentialSolution.size(); i++) {
169: CompositeGene comp = (CompositeGene) a_potentialSolution
170: .getGene(i);
171: volume += getNumberOfItemsAtGene(comp)
172: * KnapsackMain.itemVolumes[i];
173: }
174: return volume;
175: }
176:
177: /**
178: * Retrieves the number of items represented by the given potential
179: * solution at the given gene position.
180: *
181: * @param a_compositeGene the composite gene to evaluate
182: * @return the number of items represented by the potential solution
183: * at the given gene position
184: *
185: * @author Klaus Meffert
186: * @since 2.3
187: */
188: public static int getNumberOfItemsAtGene(
189: CompositeGene a_compositeGene) {
190: Integer numItems = (Integer) a_compositeGene.geneAt(1)
191: .getAllele();
192: return numItems.intValue();
193: }
194:
195: /**
196: * Returns the total number of items represented by all of the genes in
197: * the given potential solution.
198: *
199: * @param a_potentialSolution the potential solution to evaluate
200: * @return the total number of items represented by the given Chromosome
201: *
202: * @author Klaus Meffert
203: * @since 2.3
204: */
205: public static int getTotalNumberOfItems(
206: IChromosome a_potentialSolution) {
207: int totalItems = 0;
208: int numberOfGenes = a_potentialSolution.size();
209: for (int i = 0; i < numberOfGenes; i++) {
210: CompositeGene comp = (CompositeGene) a_potentialSolution
211: .getGene(i);
212: totalItems += getNumberOfItemsAtGene(comp);
213: }
214: return totalItems;
215: }
216: }
|