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.audit;
011:
012: //Uncomment imports and code below to use JFreeChart functionality
013: //import java.io.*;
014: //import java.awt.image.*;
015:
016: //import org.jfree.chart.*;
017: //import org.jfree.chart.plot.*;
018: //import org.jfree.data.category.*;
019: import org.jgap.*;
020: import org.jgap.impl.*;
021: import org.jgap.audit.*;
022:
023: /**
024: * Same logic as in MinimizingMakeChange except that we are using the new
025: * audit capabilities provided by JGAP 2.2
026: *
027: * @author Klaus Meffert
028: * @since 2.2
029: */
030: public class CoinsExample {
031: /** String containing the CVS revision. Read out via reflection!*/
032: private final static String CVS_REVISION = "$Revision: 1.24 $";
033:
034: /**
035: * The total number of times we'll let the population evolve.
036: */
037: private static final int MAX_ALLOWED_EVOLUTIONS = 80;
038:
039: /**
040: * Executes the genetic algorithm to determine the minimum number of
041: * coins necessary to make up the given target amount of change. The
042: * solution will then be written to System.out.
043: *
044: * @param a_targetChangeAmount the target amount of change for which this
045: * method is attempting to produce the minimum number of coins
046: * @throws Exception
047: *
048: * @author Neil Rotstan
049: * @author Klaus Meffert
050: * @since 1.0
051: */
052: public static void makeChangeForAmount(int a_targetChangeAmount)
053: throws Exception {
054: // Start with a DefaultConfiguration, which comes setup with the
055: // most common settings.
056: // -------------------------------------------------------------
057: Configuration conf = new DefaultConfiguration();
058: conf.setPreservFittestIndividual(true);
059: // Set the fitness function we want to use, which is our
060: // MinimizingMakeChangeFitnessFunction. We construct it with
061: // the target amount of change passed in to this method.
062: // ---------------------------------------------------------
063: FitnessFunction myFunc = new CoinsExampleFitnessFunction(
064: a_targetChangeAmount);
065: conf.setFitnessFunction(myFunc);
066: // Now we need to tell the Configuration object how we want our
067: // Chromosomes to be setup. We do that by actually creating a
068: // sample Chromosome and then setting it on the Configuration
069: // object. As mentioned earlier, we want our Chromosomes to each
070: // have four genes, one for each of the coin types. We want the
071: // values (alleles) of those genes to be integers, which represent
072: // how many coins of that type we have. We therefore use the
073: // IntegerGene class to represent each of the genes. That class
074: // also lets us specify a lower and upper bound, which we set
075: // to sensible values for each coin type.
076: // --------------------------------------------------------------
077: Gene[] sampleGenes = new Gene[4];
078: sampleGenes[0] = new IntegerGene(conf, 0, 3 * 10); // Quarters
079: sampleGenes[1] = new IntegerGene(conf, 0, 2 * 10); // Dimes
080: sampleGenes[2] = new IntegerGene(conf, 0, 1 * 10); // Nickels
081: sampleGenes[3] = new IntegerGene(conf, 0, 4 * 10); // Pennies
082: Chromosome sampleChromosome = new Chromosome(conf, sampleGenes);
083: conf.setSampleChromosome(sampleChromosome);
084: // Finally, we need to tell the Configuration object how many
085: // Chromosomes we want in our population. The more Chromosomes,
086: // the larger number of potential solutions (which is good for
087: // finding the answer), but the longer it will take to evolve
088: // the population (which could be seen as bad).
089: // ------------------------------------------------------------
090: conf.setPopulationSize(50);
091: // Added here for demonstrating purposes is a permuting configuration.
092: // It allows for evaluating which configuration could work best for
093: // the given problem.
094: // -------------------------------------------------------------------
095: PermutingConfiguration pconf = new PermutingConfiguration(conf);
096: pconf.addGeneticOperatorSlot(new CrossoverOperator(conf));
097: pconf.addGeneticOperatorSlot(new MutationOperator(conf));
098: pconf.addNaturalSelectorSlot(new BestChromosomesSelector(conf));
099: pconf
100: .addNaturalSelectorSlot(new WeightedRouletteSelector(
101: conf));
102: pconf.addRandomGeneratorSlot(new StockRandomGenerator());
103: RandomGeneratorForTesting rn = new RandomGeneratorForTesting();
104: rn.setNextDouble(0.7d);
105: rn.setNextInt(2);
106: pconf.addRandomGeneratorSlot(rn);
107: pconf.addRandomGeneratorSlot(new GaussianRandomGenerator());
108: pconf.addFitnessFunctionSlot(new CoinsExampleFitnessFunction(
109: a_targetChangeAmount));
110: Evaluator eval = new Evaluator(pconf);
111: /**@todo class Evaluator:
112: * input:
113: * + PermutingConfiguration
114: * + Number of evaluation runs pers config (to turn off randomness
115: * as much as possible)
116: * + output facility (data container)
117: * + optional: event subscribers
118: * output:
119: * + averaged curve of fitness value thru all generations
120: * + best fitness value accomplished
121: * + average number of performance improvements for all generations
122: */
123: int permutation = 0;
124: while (eval.hasNext()) {
125: // Create random initial population of Chromosomes.
126: // ------------------------------------------------
127: Genotype population = Genotype.randomInitialGenotype(eval
128: .next());
129: for (int run = 0; run < 10; run++) {
130: // Evolve the population. Since we don't know what the best answer
131: // is going to be, we just evolve the max number of times.
132: // ---------------------------------------------------------------
133: for (int i = 0; i < MAX_ALLOWED_EVOLUTIONS; i++) {
134: population.evolve();
135: // add current best fitness to chart
136: double fitness = population.getFittestChromosome()
137: .getFitnessValue();
138: if (i % 3 == 0) {
139: String s = String.valueOf(i);
140: // Number n = eval.getValue("Fitness " + permutation, s);
141: // double d;
142: // if (n != null) {
143: // // calculate historical average
144: // d = n.doubleValue() + fitness/(run+1);
145: // }
146: // else {
147: // d = fitness;
148: // }
149: eval.setValue(permutation, run, fitness, ""
150: + permutation, s);
151: eval
152: .storeGenotype(permutation, run,
153: population);
154: // eval.setValue(permutation,run,fitness, new Integer(0), s);
155: }
156: }
157: }
158: // Display the best solution we found.
159: // -----------------------------------
160: IChromosome bestSolutionSoFar = population
161: .getFittestChromosome();
162: System.out
163: .println("The best solution has a fitness value of "
164: + bestSolutionSoFar.getFitnessValue());
165: System.out.println("It contained the following: ");
166: System.out.println("\t"
167: + CoinsExampleFitnessFunction
168: .getNumberOfCoinsAtGene(bestSolutionSoFar,
169: 0) + " quarters.");
170: System.out.println("\t"
171: + CoinsExampleFitnessFunction
172: .getNumberOfCoinsAtGene(bestSolutionSoFar,
173: 1) + " dimes.");
174: System.out.println("\t"
175: + CoinsExampleFitnessFunction
176: .getNumberOfCoinsAtGene(bestSolutionSoFar,
177: 2) + " nickels.");
178: System.out.println("\t"
179: + CoinsExampleFitnessFunction
180: .getNumberOfCoinsAtGene(bestSolutionSoFar,
181: 3) + " pennies.");
182: System.out.println("For a total of "
183: + CoinsExampleFitnessFunction
184: .amountOfChange(bestSolutionSoFar)
185: + " cents in "
186: + CoinsExampleFitnessFunction
187: .getTotalNumberOfCoins(bestSolutionSoFar)
188: + " coins.");
189: permutation++;
190: }
191: // Create chart: fitness values average over all permutations.
192: // -----------------------------------------------------------
193:
194: // construct JFreeChart Dataset.
195: // -----------------------------
196: // DefaultKeyedValues2D myDataset = eval.calcAvgFitness(-1);//eval.getData();
197: // DefaultCategoryDataset dataset = new DefaultCategoryDataset();
198: // for (int ii=0;ii<myDataset.getColumnCount();ii++) {
199: // for (int jj=0;jj<myDataset.getRowCount();jj++) {
200: // dataset.setValue(myDataset.getValue(myDataset.getRowKey(jj),
201: // myDataset.getColumnKey(ii)),
202: // "Perm "+myDataset.getRowKey(jj), myDataset.getColumnKey(ii));
203: // }
204: // }
205:
206: // PlotOrientation or = PlotOrientation.VERTICAL;
207: // JFreeChart chart = ChartFactory.createLineChart(
208: // "JGAP: Evolution progress",
209: // "Evolution cycle", "Fitness value", dataset, or, true /*legend*/,
210: // true
211: // /*tooltips*/
212: // , false /*urls*/);
213: // BufferedImage image = chart.createBufferedImage(640, 480);
214: // FileOutputStream fo = new FileOutputStream("c:\\JGAP_chart_fitness_values.jpg");
215: // ChartUtilities.writeBufferedImageAsJPEG(fo, 0.7f, image);
216:
217: // Performance metrics for each single permutation.
218: // ------------------------------------------------
219: int maxPerm = permutation - 1;
220: double avgBestFitness = 0.0d;
221: int avgBestGen = 0;
222: double avgAvgFitness = 0.0d;
223: double avgAvgDiv = 0.0d;
224: double avgAvgBestD = 0.0d;
225: for (int i = 0; i < maxPerm; i++) {
226: // myDataset = eval.calcAvgFitness(i);
227: Evaluator.GenotypeDataAvg dataAvg = eval.calcPerformance(i);
228: System.err.println("-----------------------------");
229: System.err.println("Perm " + i);
230: System.err.println("Best Fitness "
231: + dataAvg.bestFitnessValue);
232: System.err.println(" Generation "
233: + dataAvg.bestFitnessValueGeneration);
234: System.err.println(" BestFit/Gen "
235: + dataAvg.bestFitnessValue
236: / dataAvg.bestFitnessValueGeneration);
237: System.err.println("Avg. Fitness "
238: + dataAvg.avgFitnessValue);
239: System.err.println("Avg. Div. "
240: + dataAvg.avgDiversityFitnessValue);
241: System.err.println("Avg. BestD "
242: + dataAvg.avgBestDeltaFitnessValue);
243: avgBestFitness += dataAvg.bestFitnessValue;
244: avgBestGen += dataAvg.bestFitnessValueGeneration;
245: avgAvgFitness += dataAvg.avgFitnessValue;
246: avgAvgDiv += dataAvg.avgDiversityFitnessValue;
247: avgAvgBestD += dataAvg.avgBestDeltaFitnessValue;
248: }
249: // Performance metrics for all permutations.
250: // -----------------------------------------
251: System.err.println("\nOverall Statistics for all permutations");
252: System.err.println("----------------------------------------");
253: System.err.println("Avg. Best Fitness " + avgBestFitness
254: / maxPerm);
255: System.err.println("Avg. Best Generation " + avgBestGen
256: / maxPerm);
257: System.err.println("Avg. Avg. Fitness " + avgAvgFitness
258: / maxPerm);
259: System.err.println("Avg. Avg. Diversity " + avgAvgDiv
260: / maxPerm);
261: System.err.println("Avg. Avg. BestD " + avgAvgBestD
262: / maxPerm);
263: // Create chart: performance metrics for all permutations.
264: // -----------------------------------------------------------
265:
266: // dataset = new DefaultCategoryDataset();
267: // for (int ii=0;ii<myDataset.getColumnCount();ii++) {
268: // for (int jj=0;jj<myDataset.getRowCount();jj++) {
269: // dataset.setValue(myDataset.getValue(myDataset.getRowKey(jj),
270: // myDataset.getColumnKey(ii)),
271: // myDataset.getRowKey(jj), myDataset.getColumnKey(ii));
272: // }
273: // }
274: //
275: // chart = ChartFactory.createLineChart(
276: // "JGAP: Evolution progress",
277: // "Evolution cycle", "Fitness value", dataset, or, true /*legend*/,
278: // true
279: // /*tooltips*/
280: // , false /*urls*/);
281: // image = chart.createBufferedImage(640, 480);
282: // fo = new FileOutputStream("c:\\JGAP_chart_fitness_values_1.jpg");
283: // ChartUtilities.writeBufferedImageAsJPEG(fo, 0.7f, image);
284: }
285:
286: public static void main(String[] args) {
287: if (args.length != 1) {
288: System.out.println("Syntax: CoinsExample <amount>");
289: } else {
290: try {
291: int amount = Integer.parseInt(args[0]);
292: if (amount < 1
293: || amount >= CoinsExampleFitnessFunction.MAX_BOUND) {
294: System.out
295: .println("The <amount> argument must be between 1 and "
296: + (CoinsExampleFitnessFunction.MAX_BOUND - 1)
297: + ".");
298: } else {
299: try {
300: makeChangeForAmount(amount);
301: } catch (Exception e) {
302: e.printStackTrace();
303: }
304: }
305: } catch (NumberFormatException e) {
306: System.out
307: .println("The <amount> argument must be a valid integer value");
308: }
309: }
310: }
311: }
|