KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > examples > MinimizingMakeChange


1 /*
2  * This file is part of JGAP.
3  *
4  * JGAP offers a dual license model containing the LGPL as well as the MPL.
5  *
6  * For licencing information please see the file license.txt included with JGAP
7  * or have a look at the top of class org.jgap.Chromosome which representatively
8  * includes the JGAP license policy applicable for any file delivered with JGAP.
9  */
10 package examples;
11
12 import java.io.*;
13
14 import org.jgap.*;
15 import org.jgap.data.*;
16 import org.jgap.impl.*;
17 import org.jgap.xml.*;
18 import org.w3c.dom.*;
19
20 /**
21  * This class provides an implementation of the classic "Make change" problem
22  * using a genetic algorithm. The goal of the problem is to provide a
23  * specified amount of change (from a cash purchase) in the fewest coins
24  * possible. This example implementation uses American currency (quarters,
25  * dimes, nickels, and pennies).
26  * <p>
27  * This example may be seen as somewhat significant because it demonstrates
28  * the use of a genetic algorithm in a less-than-optimal problem space.
29  * The genetic algorithm does best when there is a smooth slope of fitness
30  * over the problem space towards the optimum solution. This problem exhibits
31  * a more choppy space with more local optima. However, as can be seen from
32  * running this example, the genetic algorithm still will get the correct
33  * (or a very close) answer virtually everytime.
34  *
35  * @author Neil Rotstan
36  * @author Klaus Meffert
37  * @since 1.0
38  */
39 public class MinimizingMakeChange {
40   /** String containing the CVS revision. Read out via reflection!*/
41   private final static String JavaDoc CVS_REVISION = "$Revision: 1.19 $";
42
43   /**
44    * The total number of times we'll let the population evolve.
45    */
46   private static final int MAX_ALLOWED_EVOLUTIONS = 200;
47
48   /**
49    * Executes the genetic algorithm to determine the minimum number of
50    * coins necessary to make up the given target amount of change. The
51    * solution will then be written to System.out.
52    *
53    * @param a_targetChangeAmount the target amount of change for which this
54    * method is attempting to produce the minimum number of coins
55    * @throws Exception
56    *
57    * @author Neil Rotstan
58    * @author Klaus Meffert
59    * @since 1.0
60    */
61   public static void makeChangeForAmount(int a_targetChangeAmount)
62       throws Exception JavaDoc {
63     // Start with a DefaultConfiguration, which comes setup with the
64 // most common settings.
65 // -------------------------------------------------------------
66 Configuration conf = new DefaultConfiguration();
67     conf.setPreservFittestIndividual(true);
68     conf.setKeepPopulationSizeConstant(false);
69     // Set the fitness function we want to use, which is our
70 // MinimizingMakeChangeFitnessFunction. We construct it with
71 // the target amount of change passed in to this method.
72 // ---------------------------------------------------------
73 FitnessFunction myFunc =
74         new MinimizingMakeChangeFitnessFunction(a_targetChangeAmount);
75 // conf.setFitnessFunction(myFunc);
76 conf.setBulkFitnessFunction(new BulkFitnessOffsetRemover(myFunc));
77     // Optionally, this example is working with DeltaFitnessEvaluator.
78 // See MinimizingMakeChangeFitnessFunction for details!
79 // ---------------------------------------------------------------
80 // conf.setFitnessEvaluator(new DeltaFitnessEvaluator());
81
82     // Now we need to tell the Configuration object how we want our
83 // Chromosomes to be setup. We do that by actually creating a
84 // sample Chromosome and then setting it on the Configuration
85 // object. As mentioned earlier, we want our Chromosomes to each
86 // have four genes, one for each of the coin types. We want the
87 // values (alleles) of those genes to be integers, which represent
88 // how many coins of that type we have. We therefore use the
89 // IntegerGene class to represent each of the genes. That class
90 // also lets us specify a lower and upper bound, which we set
91 // to sensible values for each coin type.
92 // --------------------------------------------------------------
93 Gene[] sampleGenes = new Gene[4];
94     sampleGenes[0] = new IntegerGene(conf, 0, 3 * 10); // Quarters
95 sampleGenes[1] = new IntegerGene(conf, 0, 2 * 10); // Dimes
96 sampleGenes[2] = new IntegerGene(conf, 0, 1 * 10); // Nickels
97 sampleGenes[3] = new IntegerGene(conf, 0, 4 * 10); // Pennies
98 IChromosome sampleChromosome = new Chromosome(conf, sampleGenes);
99     conf.setSampleChromosome(sampleChromosome);
100     // Finally, we need to tell the Configuration object how many
101 // Chromosomes we want in our population. The more Chromosomes,
102 // the larger number of potential solutions (which is good for
103 // finding the answer), but the longer it will take to evolve
104 // the population (which could be seen as bad).
105 // ------------------------------------------------------------
106 conf.setPopulationSize(80);
107
108     // Create random initial population of Chromosomes.
109 // Here we try to read in a previous run via XMLManager.readFile(..)
110 // for demonstration purpose only!
111 // -----------------------------------------------------------------
112 Genotype population;
113     try {
114       Document doc = XMLManager.readFile(new File("JGAPExample26.xml"));
115       population = XMLManager.getGenotypeFromDocument(conf, doc);
116     }
117     catch (UnsupportedRepresentationException uex) {
118       // JGAP codebase might have changed between two consecutive runs
119 population = Genotype.randomInitialGenotype(conf);
120     }
121     catch (FileNotFoundException fex) {
122       population = Genotype.randomInitialGenotype(conf);
123     }
124     // Now we initialize the population randomly, anyway!
125 // If you want to load previous results from file, remove the next line!
126 population = Genotype.randomInitialGenotype(conf);
127     // Evolve the population. Since we don't know what the best answer
128 // is going to be, we just evolve the max number of times.
129 // ---------------------------------------------------------------
130 for (int i = 0; i < MAX_ALLOWED_EVOLUTIONS; i++) {
131       population.evolve();
132     }
133     // Save progress to file. A new run of this example will then be able to
134 // resume where it stopped before!
135 // ---------------------------------------------------------------------
136
137     // Represent Genotype as tree with elements Chromomes and Genes.
138 DataTreeBuilder builder = DataTreeBuilder.getInstance();
139     IDataCreators doc2 = builder.representGenotypeAsDocument(population);
140     // create XML document from generated tree
141 XMLDocumentBuilder docbuilder = new XMLDocumentBuilder();
142     Document xmlDoc = (Document) docbuilder.buildDocument(doc2);
143     XMLManager.writeFile(xmlDoc, new File("JGAPExample26.xml"));
144     // Display the best solution we found.
145 // -----------------------------------
146 IChromosome bestSolutionSoFar = population.getFittestChromosome();
147     System.out.println("The best solution has a fitness value of " +
148                        bestSolutionSoFar.getFitnessValue());
149     System.out.println("It contained the following: ");
150     System.out.println("\t" +
151                        MinimizingMakeChangeFitnessFunction.
152                        getNumberOfCoinsAtGene(
153         bestSolutionSoFar, 0) + " quarters.");
154     System.out.println("\t" +
155                        MinimizingMakeChangeFitnessFunction.
156                        getNumberOfCoinsAtGene(
157         bestSolutionSoFar, 1) + " dimes.");
158     System.out.println("\t" +
159                        MinimizingMakeChangeFitnessFunction.
160                        getNumberOfCoinsAtGene(
161         bestSolutionSoFar, 2) + " nickels.");
162     System.out.println("\t" +
163                        MinimizingMakeChangeFitnessFunction.
164                        getNumberOfCoinsAtGene(
165         bestSolutionSoFar, 3) + " pennies.");
166     System.out.println("For a total of " +
167                        MinimizingMakeChangeFitnessFunction.amountOfChange(
168         bestSolutionSoFar) + " cents in " +
169                        MinimizingMakeChangeFitnessFunction.
170                        getTotalNumberOfCoins(
171         bestSolutionSoFar) + " coins.");
172   }
173
174   /**
175    * Main method. A single command-line argument is expected, which is the
176    * amount of change to create (in other words, 75 would be equal to 75
177    * cents).
178    *
179    * @param args amount of change in cents to create
180    * @throws Exception
181    *
182    * @author Neil Rotstan
183    * @author Klaus Meffert
184    * @since 1.0
185    */
186   public static void main(String JavaDoc[] args)
187       throws Exception JavaDoc {
188     if (args.length != 1) {
189       System.out.println("Syntax: MinimizingMakeChange <amount>");
190     }
191     else {
192       int amount = 0;
193       try {
194         amount = Integer.parseInt(args[0]);
195       }
196       catch (NumberFormatException JavaDoc e) {
197         System.out.println(
198             "The <amount> argument must be a valid integer value");
199         System.exit(1);
200       }
201       if (amount < 1 ||
202           amount >= MinimizingMakeChangeFitnessFunction.MAX_BOUND) {
203         System.out.println("The <amount> argument must be between 1 and "
204                            +
205                            (MinimizingMakeChangeFitnessFunction.MAX_BOUND - 1)
206                            + ".");
207       }
208       else {
209         makeChangeForAmount(amount);
210       }
211     }
212   }
213
214 }
215
Popular Tags