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 licensing 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.energy;
011:
012: import org.jgap.*;
013:
014: /**
015: * Sample fitness function for the CoinsEnergy example. Adapted from
016: * examples.MinimizingMakeChangeFitnessFunction
017: *
018: * @author Klaus Meffert
019: * @since 2.4
020: */
021: public class CoinsEnergyFitnessFunction extends FitnessFunction {
022: /** String containing the CVS revision. Read out via reflection!*/
023: private final static String CVS_REVISION = "$Revision: 1.5 $";
024:
025: private final int m_targetAmount;
026:
027: private final double m_maxWeight;
028:
029: public static final int MAX_BOUND = 10000;
030: public static final double MAX_WEIGHT = 500;
031:
032: private static final double ZERO_DIFFERENCE_FITNESS = Math
033: .sqrt(MAX_BOUND);
034:
035: public CoinsEnergyFitnessFunction(int a_targetAmount,
036: double a_maxWeight) {
037: if (a_targetAmount < 1 || a_targetAmount >= MAX_BOUND) {
038: throw new IllegalArgumentException(
039: "Change amount must be between 1 and " + MAX_BOUND
040: + " cents.");
041: }
042:
043: if (a_maxWeight < 0 || a_maxWeight >= MAX_WEIGHT) {
044: throw new IllegalArgumentException(
045: "Max weight must be greater than 0 and not greater than "
046: + MAX_WEIGHT + " grammes");
047: }
048: m_targetAmount = a_targetAmount;
049: m_maxWeight = a_maxWeight;
050: }
051:
052: /**
053: * Determine the fitness of the given Chromosome instance. The higher the
054: * return value, the more fit the instance. This method should always
055: * return the same fitness value for two equivalent Chromosome instances.
056: *
057: * @param a_subject the Chromosome instance to evaluate
058: *
059: * @return positive double reflecting the fitness rating of the given
060: * Chromosome
061: * @since 2.0 (until 1.1: return type int)
062: * @author Neil Rotstan, Klaus Meffert, John Serri
063: */
064: public double evaluate(IChromosome a_subject) {
065: // The fitness value measures both how close the value is to the
066: // target amount supplied by the user and the total number of coins
067: // represented by the solution. We do this in two steps: first,
068: // we consider only the represented amount of change vs. the target
069: // amount of change and return higher fitness values for amounts
070: // closer to the target, and lower fitness values for amounts further
071: // away from the target. Then we go to step 2, which returns a higher
072: // fitness value for solutions representing fewer total coins, and
073: // lower fitness values for solutions representing more total coins.
074: // ------------------------------------------------------------------
075: int changeAmount = amountOfChange(a_subject);
076: int totalCoins = getTotalNumberOfCoins(a_subject);
077: int changeDifference = Math.abs(m_targetAmount - changeAmount);
078:
079: double fitness;
080:
081: // Step 1: Determine total sum of energies (interpreted as weights here)
082: // of coins. If higher than the given maximum value, the solution is not
083: // accepted in any way, i.e. the fitness value is then set to the worst
084: // value.
085: double totalWeight = getTotalWeight(a_subject);
086: if (totalWeight > m_maxWeight) {
087: if (a_subject.getConfiguration().getFitnessEvaluator()
088: .isFitter(2, 1)) {
089: return 1.0d;
090: } else {
091: return MAX_BOUND;
092: }
093: }
094:
095: if (a_subject.getConfiguration().getFitnessEvaluator()
096: .isFitter(2, 1)) {
097: fitness = MAX_BOUND;
098: } else {
099: fitness = 0.0d;
100: }
101:
102: // Step 2: Determine distance of amount represented by solution from
103: // the target amount.
104: // -----------------------------------------------------------------
105: if (a_subject.getConfiguration().getFitnessEvaluator()
106: .isFitter(2, 1)) {
107: fitness -= changeDifferenceBonus(MAX_BOUND / 3,
108: changeDifference);
109: } else {
110: fitness += changeDifferenceBonus(MAX_BOUND / 3,
111: changeDifference);
112: }
113:
114: // Step 3: We divide the fitness value by a penalty based on the number of
115: // coins. The higher the number of coins the higher the penalty and the
116: // smaller the fitness value.
117: // And inversely the smaller number of coins in the solution the higher
118: // the resulting fitness value.
119: // -----------------------------------------------------------------------
120: if (a_subject.getConfiguration().getFitnessEvaluator()
121: .isFitter(2, 1)) {
122: fitness -= computeCoinNumberPenalty(MAX_BOUND / 3,
123: totalCoins);
124: } else {
125: fitness += computeCoinNumberPenalty(MAX_BOUND / 3,
126: totalCoins);
127: }
128:
129: // Step 4: Penalize higher weight (= engery) values.
130: // -------------------------------------------------
131: if (a_subject.getConfiguration().getFitnessEvaluator()
132: .isFitter(2, 1)) {
133: fitness -= computeWeightPenalty(MAX_BOUND / 3, totalWeight);
134: } else {
135: fitness += computeWeightPenalty(MAX_BOUND / 3, totalWeight);
136: }
137:
138: // Make sure fitness value is always positive.
139: // -------------------------------------------
140: return Math.max(1.0d, fitness);
141: }
142:
143: /**
144: * Bonus calculation of fitness value.
145: * @param a_maxFitness maximum fitness value appliable
146: * @param a_changeDifference change difference in coins for the coins problem
147: * @return bonus for given change difference
148: * @author Klaus Meffert
149: * @since 2.3
150: */
151: protected double changeDifferenceBonus(double a_maxFitness,
152: int a_changeDifference) {
153: if (a_changeDifference == 0) {
154: return a_maxFitness;
155: } else {
156: // we arbitrarily work with half of the maximum fitness as basis for
157: // non-optimal solutions (concerning change difference)
158: return Math.min(a_maxFitness, Math.pow(a_changeDifference,
159: 2.2d));
160: }
161: }
162:
163: /**
164: * Calculates the penalty to apply to the fitness value based on the ammount
165: * of coins in the solution
166: *
167: * @param a_maxFitness maximum fitness value allowed
168: * @param a_coins number of coins in the solution
169: * @return penalty for the fitness value base on the number of coins
170: *
171: * @author John Serri
172: * @since 2.4
173: */
174: protected double computeCoinNumberPenalty(double a_maxFitness,
175: int a_coins) {
176: if (a_coins == 1) {
177: // we know the solution cannot have less than one coin
178: return 0;
179: } else {
180: if (a_coins < 1) {
181: return a_maxFitness;
182: }
183: // The more coins the more penalty, but not more than the maximum
184: // fitness value possible. Let's avoid linear behavior and use
185: // exponential penalty calculation instead
186: return (Math.min(a_maxFitness, Math.pow(a_coins, 1.3d)));
187: }
188: }
189:
190: /**
191: * Calculates the total amount of change (in cents) represented by
192: * the given potential solution and returns that amount.
193: *
194: * @param a_potentialSolution the potential solution to evaluate
195: * @return the total amount of change (in cents) represented by the
196: * given solution
197: *
198: * @author Neil Rotstan
199: * @since 1.0
200: */
201: public static int amountOfChange(IChromosome a_potentialSolution) {
202: int numQuarters = getNumberOfCoinsAtGene(a_potentialSolution, 0);
203: int numDimes = getNumberOfCoinsAtGene(a_potentialSolution, 1);
204: int numNickels = getNumberOfCoinsAtGene(a_potentialSolution, 2);
205: int numPennies = getNumberOfCoinsAtGene(a_potentialSolution, 3);
206: return (numQuarters * 25) + (numDimes * 10) + (numNickels * 5)
207: + numPennies;
208: }
209:
210: /**
211: * Retrieves the number of coins represented by the given potential
212: * solution at the given gene position.
213: *
214: * @param a_potentialSolution the potential solution to evaluate
215: * @param a_position the gene position to evaluate
216: * @return the number of coins represented by the potential solution at the
217: * given gene position
218: *
219: * @author Neil Rotstan
220: * @since 1.0
221: */
222: public static int getNumberOfCoinsAtGene(
223: IChromosome a_potentialSolution, int a_position) {
224: Integer numCoins = (Integer) a_potentialSolution.getGene(
225: a_position).getAllele();
226: return numCoins.intValue();
227: }
228:
229: /**
230: * Returns the total number of coins represented by all of the genes in
231: * the given potential solution.
232: *
233: * @param a_potentialsolution the potential solution to evaluate
234: * @return total number of coins represented by the given Chromosome
235: *
236: * @author Neil Rotstan
237: * @since 2.4
238: */
239: public static int getTotalNumberOfCoins(
240: IChromosome a_potentialsolution) {
241: int totalCoins = 0;
242: int numberOfGenes = a_potentialsolution.size();
243: for (int i = 0; i < numberOfGenes; i++) {
244: totalCoins += getNumberOfCoinsAtGene(a_potentialsolution, i);
245: }
246: return totalCoins;
247: }
248:
249: /**
250: * Returns the total weight of all coins.
251: *
252: * @param a_potentialSolution the potential solution to evaluate
253: * @return total weight of all coins
254: *
255: * @author Klaus Meffert
256: * @since 2.4
257: */
258: public static double getTotalWeight(IChromosome a_potentialSolution) {
259: double totalWeight = 0.0d;
260: int numberOfGenes = a_potentialSolution.size();
261: for (int i = 0; i < numberOfGenes; i++) {
262: int coinsNumber = getNumberOfCoinsAtGene(
263: a_potentialSolution, i);
264: totalWeight += a_potentialSolution.getGene(i).getEnergy()
265: * coinsNumber;
266: }
267: return totalWeight;
268: }
269:
270: /**
271: *
272: * @param a_maxFitness the maximum fitness value allowed
273: * @param a_weight the coins weight of the current solution
274: * @return the penalty computed
275: * @author Klaus Meffert
276: * @since 2.4
277: */
278: protected double computeWeightPenalty(double a_maxFitness,
279: double a_weight) {
280: if (a_weight <= 0) {
281: // we know the solution cannot have less than one coin
282: return 0;
283: } else {
284: // The more weight the more penalty, but not more than the maximum
285: // fitness value possible. Let's avoid linear behavior and use
286: // exponential penalty calculation instead
287: return (Math.min(a_maxFitness, a_weight * a_weight));
288: }
289: }
290:
291: }
|