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;
011:
012: import java.io.*;
013:
014: import org.jgap.*;
015: import org.jgap.data.*;
016: import org.jgap.impl.*;
017: import org.jgap.xml.*;
018: import org.w3c.dom.*;
019:
020: /**
021: * This class provides an implementation of the classic "Make change" problem
022: * using a genetic algorithm. The goal of the problem is to provide a
023: * specified amount of change (from a cash purchase) in the fewest coins
024: * possible. This example implementation uses American currency (quarters,
025: * dimes, nickels, and pennies).
026: * <p>
027: * This example may be seen as somewhat significant because it demonstrates
028: * the use of a genetic algorithm in a less-than-optimal problem space.
029: * The genetic algorithm does best when there is a smooth slope of fitness
030: * over the problem space towards the optimum solution. This problem exhibits
031: * a more choppy space with more local optima. However, as can be seen from
032: * running this example, the genetic algorithm still will get the correct
033: * (or a very close) answer virtually everytime.
034: *
035: * @author Neil Rotstan
036: * @author Klaus Meffert
037: * @since 1.0
038: */
039: public class MinimizingMakeChange {
040: /** String containing the CVS revision. Read out via reflection!*/
041: private final static String CVS_REVISION = "$Revision: 1.22 $";
042:
043: /**
044: * The total number of times we'll let the population evolve.
045: */
046: private static final int MAX_ALLOWED_EVOLUTIONS = 200;
047:
048: /**
049: * Executes the genetic algorithm to determine the minimum number of
050: * coins necessary to make up the given target amount of change. The
051: * solution will then be written to System.out.
052: *
053: * @param a_targetChangeAmount the target amount of change for which this
054: * method is attempting to produce the minimum number of coins
055: * @throws Exception
056: *
057: * @author Neil Rotstan
058: * @author Klaus Meffert
059: * @since 1.0
060: */
061: public static void makeChangeForAmount(int a_targetChangeAmount)
062: throws Exception {
063: // Start with a DefaultConfiguration, which comes setup with the
064: // most common settings.
065: // -------------------------------------------------------------
066: Configuration conf = new DefaultConfiguration();
067: conf.setPreservFittestIndividual(true);
068: conf.setKeepPopulationSizeConstant(true);
069: // Set the fitness function we want to use, which is our
070: // MinimizingMakeChangeFitnessFunction. We construct it with
071: // the target amount of change passed in to this method.
072: // ---------------------------------------------------------
073: FitnessFunction myFunc = new MinimizingMakeChangeFitnessFunction(
074: a_targetChangeAmount);
075: // conf.setFitnessFunction(myFunc);
076: conf
077: .setBulkFitnessFunction(new BulkFitnessOffsetRemover(
078: myFunc));
079: // Optionally, this example is working with DeltaFitnessEvaluator.
080: // See MinimizingMakeChangeFitnessFunction for details!
081: // ---------------------------------------------------------------
082: // conf.setFitnessEvaluator(new DeltaFitnessEvaluator());
083:
084: // Now we need to tell the Configuration object how we want our
085: // Chromosomes to be setup. We do that by actually creating a
086: // sample Chromosome and then setting it on the Configuration
087: // object. As mentioned earlier, we want our Chromosomes to each
088: // have four genes, one for each of the coin types. We want the
089: // values (alleles) of those genes to be integers, which represent
090: // how many coins of that type we have. We therefore use the
091: // IntegerGene class to represent each of the genes. That class
092: // also lets us specify a lower and upper bound, which we set
093: // to sensible values for each coin type.
094: // --------------------------------------------------------------
095: Gene[] sampleGenes = new Gene[4];
096: sampleGenes[0] = new IntegerGene(conf, 0, 3 * 10); // Quarters
097: sampleGenes[1] = new IntegerGene(conf, 0, 2 * 10); // Dimes
098: sampleGenes[2] = new IntegerGene(conf, 0, 1 * 10); // Nickels
099: sampleGenes[3] = new IntegerGene(conf, 0, 4 * 10); // Pennies
100: IChromosome sampleChromosome = new Chromosome(conf, sampleGenes);
101: conf.setSampleChromosome(sampleChromosome);
102: // Finally, we need to tell the Configuration object how many
103: // Chromosomes we want in our population. The more Chromosomes,
104: // the larger number of potential solutions (which is good for
105: // finding the answer), but the longer it will take to evolve
106: // the population (which could be seen as bad).
107: // ------------------------------------------------------------
108: conf.setPopulationSize(80);
109:
110: // Create random initial population of Chromosomes.
111: // Here we try to read in a previous run via XMLManager.readFile(..)
112: // for demonstration purpose only!
113: // -----------------------------------------------------------------
114: Genotype population;
115: try {
116: Document doc = XMLManager.readFile(new File(
117: "JGAPExample32.xml"));
118: population = XMLManager.getGenotypeFromDocument(conf, doc);
119: } catch (UnsupportedRepresentationException uex) {
120: // JGAP codebase might have changed between two consecutive runs
121: population = Genotype.randomInitialGenotype(conf);
122: } catch (FileNotFoundException fex) {
123: population = Genotype.randomInitialGenotype(conf);
124: }
125: // Now we initialize the population randomly, anyway!
126: // If you want to load previous results from file, remove the next line!
127: population = Genotype.randomInitialGenotype(conf);
128: // Evolve the population. Since we don't know what the best answer
129: // is going to be, we just evolve the max number of times.
130: // ---------------------------------------------------------------
131: long startTime = System.currentTimeMillis();
132: for (int i = 0; i < MAX_ALLOWED_EVOLUTIONS; i++) {
133: if (!uniqueChromosomes(population.getPopulation())) {
134: throw new RuntimeException(
135: "Invalid state in generation " + i);
136: }
137: population.evolve();
138: }
139: long endTime = System.currentTimeMillis();
140: System.out.println("Total evolution time: "
141: + (endTime - startTime) + " ms");
142: // Save progress to file. A new run of this example will then be able to
143: // resume where it stopped before!
144: // ---------------------------------------------------------------------
145:
146: // Represent Genotype as tree with elements Chromomes and Genes.
147: DataTreeBuilder builder = DataTreeBuilder.getInstance();
148: IDataCreators doc2 = builder
149: .representGenotypeAsDocument(population);
150: // create XML document from generated tree
151: XMLDocumentBuilder docbuilder = new XMLDocumentBuilder();
152: Document xmlDoc = (Document) docbuilder.buildDocument(doc2);
153: XMLManager.writeFile(xmlDoc, new File("JGAPExample26.xml"));
154: // Display the best solution we found.
155: // -----------------------------------
156: IChromosome bestSolutionSoFar = population
157: .getFittestChromosome();
158: System.out.println("The best solution has a fitness value of "
159: + bestSolutionSoFar.getFitnessValue());
160: System.out.println("It contained the following: ");
161: System.out.println("\t"
162: + MinimizingMakeChangeFitnessFunction
163: .getNumberOfCoinsAtGene(bestSolutionSoFar, 0)
164: + " quarters.");
165: System.out.println("\t"
166: + MinimizingMakeChangeFitnessFunction
167: .getNumberOfCoinsAtGene(bestSolutionSoFar, 1)
168: + " dimes.");
169: System.out.println("\t"
170: + MinimizingMakeChangeFitnessFunction
171: .getNumberOfCoinsAtGene(bestSolutionSoFar, 2)
172: + " nickels.");
173: System.out.println("\t"
174: + MinimizingMakeChangeFitnessFunction
175: .getNumberOfCoinsAtGene(bestSolutionSoFar, 3)
176: + " pennies.");
177: System.out.println("For a total of "
178: + MinimizingMakeChangeFitnessFunction
179: .amountOfChange(bestSolutionSoFar)
180: + " cents in "
181: + MinimizingMakeChangeFitnessFunction
182: .getTotalNumberOfCoins(bestSolutionSoFar)
183: + " coins.");
184: }
185:
186: /**
187: * Main method. A single command-line argument is expected, which is the
188: * amount of change to create (in other words, 75 would be equal to 75
189: * cents).
190: *
191: * @param args amount of change in cents to create
192: * @throws Exception
193: *
194: * @author Neil Rotstan
195: * @author Klaus Meffert
196: * @since 1.0
197: */
198: public static void main(String[] args) throws Exception {
199: if (args.length != 1) {
200: System.out.println("Syntax: MinimizingMakeChange <amount>");
201: } else {
202: int amount = 0;
203: try {
204: amount = Integer.parseInt(args[0]);
205: } catch (NumberFormatException e) {
206: System.out
207: .println("The <amount> argument must be a valid integer value");
208: System.exit(1);
209: }
210: if (amount < 1
211: || amount >= MinimizingMakeChangeFitnessFunction.MAX_BOUND) {
212: System.out
213: .println("The <amount> argument must be between 1 and "
214: + (MinimizingMakeChangeFitnessFunction.MAX_BOUND - 1)
215: + ".");
216: } else {
217: makeChangeForAmount(amount);
218: }
219: }
220: }
221:
222: /**
223: * @param a_pop the population to verify
224: * @return true if all chromosomes in the populationa are unique
225: *
226: * @author Klaus Meffert
227: * @since 3.3.1
228: */
229: public static boolean uniqueChromosomes(Population a_pop) {
230: // Check that all chromosomes are unique
231: for (int i = 0; i < a_pop.size() - 1; i++) {
232: IChromosome c = a_pop.getChromosome(i);
233: for (int j = i + 1; j < a_pop.size(); j++) {
234: IChromosome c2 = a_pop.getChromosome(j);
235: if (c == c2) {
236: return false;
237: }
238: }
239: }
240: return true;
241: }
242: }
|