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