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 java.io.*;
013:
014: import org.jgap.*;
015: import org.jgap.impl.*;
016:
017: /**
018: * See class MinimizingMakeChanged.<p>
019: * Here a cached fitness function is used instead of an ordinary fitness
020: * function.
021: *
022: * @author Klaus Meffert
023: * @since 3.2
024: */
025: public class MinimizingMakeChangeCached {
026: /** String containing the CVS revision. Read out via reflection!*/
027: private final static String CVS_REVISION = "$Revision: 1.1 $";
028:
029: /**
030: * The total number of times we'll let the population evolve.
031: */
032: private static final int MAX_ALLOWED_EVOLUTIONS = 200;
033:
034: /**
035: * Executes the genetic algorithm to determine the minimum number of
036: * coins necessary to make up the given target amount of change. The
037: * solution will then be written to System.out.
038: *
039: * @param a_targetChangeAmount the target amount of change for which this
040: * method is attempting to produce the minimum number of coins
041: * @throws Exception
042: *
043: * @author Neil Rotstan
044: * @author Klaus Meffert
045: * @since 1.0
046: */
047: public static void makeChangeForAmount(int a_targetChangeAmount)
048: throws Exception {
049: // Start with a DefaultConfiguration, which comes setup with the
050: // most common settings.
051: // -------------------------------------------------------------
052: Configuration conf = new DefaultConfiguration();
053: conf.setPreservFittestIndividual(true);
054: conf.setKeepPopulationSizeConstant(false);
055: // Set the fitness function we want to use, which is our
056: // MinimizingMakeChangeFitnessFunction. We construct it with
057: // the target amount of change passed in to this method.
058: // ---------------------------------------------------------
059: FitnessFunction myFunc = new MinimizingFitnessFunctionCached(
060: a_targetChangeAmount);
061: conf.setFitnessFunction(myFunc);
062: conf.resetProperty(Configuration.PROPERTY_FITEVAL_INST);
063: conf.setFitnessEvaluator(new DeltaFitnessEvaluator());
064:
065: // Now we need to tell the Configuration object how we want our
066: // Chromosomes to be setup. We do that by actually creating a
067: // sample Chromosome and then setting it on the Configuration
068: // object. As mentioned earlier, we want our Chromosomes to each
069: // have four genes, one for each of the coin types. We want the
070: // values (alleles) of those genes to be integers, which represent
071: // how many coins of that type we have. We therefore use the
072: // IntegerGene class to represent each of the genes. That class
073: // also lets us specify a lower and upper bound, which we set
074: // to sensible values for each coin type.
075: // --------------------------------------------------------------
076: Gene[] sampleGenes = new Gene[4];
077: sampleGenes[0] = new IntegerGene(conf, 0, 3 * 10); // Quarters
078: sampleGenes[1] = new IntegerGene(conf, 0, 2 * 10); // Dimes
079: sampleGenes[2] = new IntegerGene(conf, 0, 1 * 10); // Nickels
080: sampleGenes[3] = new IntegerGene(conf, 0, 4 * 10); // Pennies
081: IChromosome sampleChromosome = new Chromosome(conf, sampleGenes);
082: conf.setSampleChromosome(sampleChromosome);
083: // Finally, we need to tell the Configuration object how many
084: // Chromosomes we want in our population. The more Chromosomes,
085: // the larger number of potential solutions (which is good for
086: // finding the answer), but the longer it will take to evolve
087: // the population (which could be seen as bad).
088: // ------------------------------------------------------------
089: conf.setPopulationSize(80);
090:
091: // Create random initial population of Chromosomes.
092: // ------------------------------------------------
093: Genotype population = Genotype.randomInitialGenotype(conf);
094: // Evolve the population. Since we don't know what the best answer
095: // is going to be, we just evolve the max number of times.
096: // ---------------------------------------------------------------
097: long startTime = System.currentTimeMillis();
098: for (int i = 0; i < MAX_ALLOWED_EVOLUTIONS; i++) {
099: population.evolve();
100: }
101: long endTime = System.currentTimeMillis();
102: System.out.println("Total evolution time: "
103: + (endTime - startTime) + " ms");
104: // Save progress to file. A new run of this example will then be able to
105: // resume where it stopped before!
106: // ---------------------------------------------------------------------
107:
108: // Display the best solution we found.
109: // -----------------------------------
110: IChromosome bestSolutionSoFar = population
111: .getFittestChromosome();
112: System.out.println("The best solution has a fitness value of "
113: + bestSolutionSoFar.getFitnessValue());
114: System.out.println("It contained the following: ");
115: System.out.println("\t"
116: + MinimizingFitnessFunctionCached
117: .getNumberOfCoinsAtGene(bestSolutionSoFar, 0)
118: + " quarters.");
119: System.out.println("\t"
120: + MinimizingFitnessFunctionCached
121: .getNumberOfCoinsAtGene(bestSolutionSoFar, 1)
122: + " dimes.");
123: System.out.println("\t"
124: + MinimizingFitnessFunctionCached
125: .getNumberOfCoinsAtGene(bestSolutionSoFar, 2)
126: + " nickels.");
127: System.out.println("\t"
128: + MinimizingFitnessFunctionCached
129: .getNumberOfCoinsAtGene(bestSolutionSoFar, 3)
130: + " pennies.");
131: System.out.println("For a total of "
132: + MinimizingFitnessFunctionCached
133: .amountOfChange(bestSolutionSoFar)
134: + " cents in "
135: + MinimizingFitnessFunctionCached
136: .getTotalNumberOfCoins(bestSolutionSoFar)
137: + " coins.");
138: }
139:
140: /**
141: * Main method. A single command-line argument is expected, which is the
142: * amount of change to create (in other words, 75 would be equal to 75
143: * cents).
144: *
145: * @param args amount of change in cents to create
146: * @throws Exception
147: *
148: * @author Neil Rotstan
149: * @author Klaus Meffert
150: * @since 1.0
151: */
152: public static void main(String[] args) throws Exception {
153: if (args.length != 1) {
154: System.out.println("Syntax: MinimizingMakeChange <amount>");
155: } else {
156: int amount = 0;
157: try {
158: amount = Integer.parseInt(args[0]);
159: } catch (NumberFormatException e) {
160: System.out
161: .println("The <amount> argument must be a valid integer value");
162: System.exit(1);
163: }
164: if (amount < 1
165: || amount >= MinimizingFitnessFunctionCached.MAX_BOUND) {
166: System.out
167: .println("The <amount> argument must be between 1 and "
168: + (MinimizingFitnessFunctionCached.MAX_BOUND - 1)
169: + ".");
170: } else {
171: makeChangeForAmount(amount);
172: }
173: }
174: }
175:
176: }
|