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;
011:
012: import org.jgap.*;
013:
014: /**
015: * Sample fitness function for the MakeChange example.
016: *
017: * @author Neil Rotstan
018: * @author Klaus Meffert
019: * @since 1.0
020: */
021: public class MinimizingMakeChangeFitnessFunction extends
022: FitnessFunction {
023: /** String containing the CVS revision. Read out via reflection!*/
024: private final static String CVS_REVISION = "$Revision: 1.17 $";
025:
026: private final int m_targetAmount;
027:
028: public static final int MAX_BOUND = 4000;
029:
030: public MinimizingMakeChangeFitnessFunction(int a_targetAmount) {
031: if (a_targetAmount < 1 || a_targetAmount >= MAX_BOUND) {
032: throw new IllegalArgumentException(
033: "Change amount must be between 1 and " + MAX_BOUND
034: + " cents.");
035: }
036: m_targetAmount = a_targetAmount;
037: }
038:
039: /**
040: * Determine the fitness of the given Chromosome instance. The higher the
041: * return value, the more fit the instance. This method should always
042: * return the same fitness value for two equivalent Chromosome instances.
043: *
044: * @param a_subject the Chromosome instance to evaluate
045: *
046: * @return positive double reflecting the fitness rating of the given
047: * Chromosome
048: * @since 2.0 (until 1.1: return type int)
049: * @author Neil Rotstan, Klaus Meffert, John Serri
050: */
051: public double evaluate(IChromosome a_subject) {
052: // Take care of the fitness evaluator. It could either be weighting higher
053: // fitness values higher (e.g.DefaultFitnessEvaluator). Or it could weight
054: // lower fitness values higher, because the fitness value is seen as a
055: // defect rate (e.g. DeltaFitnessEvaluator)
056: boolean defaultComparation = a_subject.getConfiguration()
057: .getFitnessEvaluator().isFitter(2, 1);
058:
059: // The fitness value measures both how close the value is to the
060: // target amount supplied by the user and the total number of coins
061: // represented by the solution. We do this in two steps: first,
062: // we consider only the represented amount of change vs. the target
063: // amount of change and return higher fitness values for amounts
064: // closer to the target, and lower fitness values for amounts further
065: // away from the target. Then we go to step 2, which returns a higher
066: // fitness value for solutions representing fewer total coins, and
067: // lower fitness values for solutions representing more total coins.
068: // ------------------------------------------------------------------
069: int changeAmount = amountOfChange(a_subject);
070: int totalCoins = getTotalNumberOfCoins(a_subject);
071: int changeDifference = Math.abs(m_targetAmount - changeAmount);
072: double fitness;
073: if (defaultComparation) {
074: fitness = 0.0d;
075: } else {
076: fitness = MAX_BOUND / 2;
077: }
078: // Step 1: Determine distance of amount represented by solution from
079: // the target amount. If the change difference is greater than zero we
080: // will divide one by the difference in change between the
081: // solution amount and the target amount. That will give the desired
082: // effect of returning higher values for amounts closer to the target
083: // amount and lower values for amounts further away from the target
084: // amount.
085: // In the case where the change difference is zero it means that we have
086: // the correct amount and we assign a higher fitness value.
087: // ---------------------------------------------------------------------
088: if (defaultComparation) {
089: fitness += changeDifferenceBonus(MAX_BOUND / 2,
090: changeDifference);
091: } else {
092: fitness -= changeDifferenceBonus(MAX_BOUND / 2,
093: changeDifference);
094: }
095: // Step 2: We divide the fitness value by a penalty based on the number of
096: // coins. The higher the number of coins the higher the penalty and the
097: // smaller the fitness value.
098: // And inversely the smaller number of coins in the solution the higher
099: // the resulting fitness value.
100: // -----------------------------------------------------------------------
101: if (defaultComparation) {
102: fitness -= computeCoinNumberPenalty(MAX_BOUND / 2,
103: totalCoins);
104: } else {
105: fitness += computeCoinNumberPenalty(MAX_BOUND / 2,
106: totalCoins);
107: }
108: // Make sure fitness value is always positive.
109: // -------------------------------------------
110: return Math.max(1.0d, fitness);
111: }
112:
113: /**
114: * Bonus calculation of fitness value.
115: * @param a_maxFitness maximum fitness value appliable
116: * @param a_changeDifference change difference in coins for the coins problem
117: * @return bonus for given change difference
118: *
119: * @author Klaus Meffert
120: * @since 2.3
121: */
122: protected double changeDifferenceBonus(double a_maxFitness,
123: int a_changeDifference) {
124: if (a_changeDifference == 0) {
125: return a_maxFitness;
126: } else {
127: // we arbitrarily work with half of the maximum fitness as basis for non-
128: // optimal solutions (concerning change difference)
129: if (a_changeDifference * a_changeDifference >= a_maxFitness / 2) {
130: return 0.0d;
131: } else {
132: return a_maxFitness / 2 - a_changeDifference
133: * a_changeDifference;
134: }
135: }
136: }
137:
138: /**
139: * Calculates the penalty to apply to the fitness value based on the ammount
140: * of coins in the solution
141: *
142: * @param a_maxFitness maximum fitness value allowed
143: * @param a_coins number of coins in the solution
144: * @return penalty for the fitness value base on the number of coins
145: *
146: * @author John Serri
147: * @since 2.2
148: */
149: protected double computeCoinNumberPenalty(double a_maxFitness,
150: int a_coins) {
151: if (a_coins == 1) {
152: // we know the solution cannot have less than one coin
153: return 0;
154: } else {
155: // The more coins the more penalty, but not more than the maximum fitness
156: // value possible. Let's avoid linear behavior and use
157: // exponential penalty calculation instead
158: return (Math.min(a_maxFitness, a_coins * a_coins));
159: }
160: }
161:
162: /**
163: * Calculates the total amount of change (in cents) represented by
164: * the given potential solution and returns that amount.
165: *
166: * @param a_potentialSolution the potential solution to evaluate
167: * @return The total amount of change (in cents) represented by the
168: * given solution
169: *
170: * @author Neil Rotstan
171: * @since 1.0
172: */
173: public static int amountOfChange(IChromosome a_potentialSolution) {
174: int numQuarters = getNumberOfCoinsAtGene(a_potentialSolution, 0);
175: int numDimes = getNumberOfCoinsAtGene(a_potentialSolution, 1);
176: int numNickels = getNumberOfCoinsAtGene(a_potentialSolution, 2);
177: int numPennies = getNumberOfCoinsAtGene(a_potentialSolution, 3);
178: return (numQuarters * 25) + (numDimes * 10) + (numNickels * 5)
179: + numPennies;
180: }
181:
182: /**
183: * Retrieves the number of coins represented by the given potential
184: * solution at the given gene position.
185: *
186: * @param a_potentialSolution the potential solution to evaluate
187: * @param a_position the gene position to evaluate
188: * @return the number of coins represented by the potential solution at the
189: * given gene position
190: *
191: * @author Neil Rotstan
192: * @since 1.0
193: */
194: public static int getNumberOfCoinsAtGene(
195: IChromosome a_potentialSolution, int a_position) {
196: Integer numCoins = (Integer) a_potentialSolution.getGene(
197: a_position).getAllele();
198: return numCoins.intValue();
199: }
200:
201: /**
202: * Returns the total number of coins represented by all of the genes in
203: * the given potential solution.
204: *
205: * @param a_potentialsolution the potential solution to evaluate
206: * @return total number of coins represented by the given Chromosome
207: *
208: * @author Neil Rotstan
209: * @since 1.0
210: */
211: public static int getTotalNumberOfCoins(
212: IChromosome a_potentialsolution) {
213: int totalCoins = 0;
214: int numberOfGenes = a_potentialsolution.size();
215: for (int i = 0; i < numberOfGenes; i++) {
216: totalCoins += getNumberOfCoinsAtGene(a_potentialsolution, i);
217: }
218: return totalCoins;
219: }
220: }
|