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: import org.jgap.impl.*;
014:
015: /**
016: * THIS EXAMPLE IS NOT IMPLEMENTED FULLY!
017: * For general description, see examples.MinimizingMakeChange.<p>
018: * Additionally, each to coin an energy value is assigned (new feature since
019: * JGAP version 2.4). Energy is interpreted here as weight of a coin. You could
020: * think of a coins holder that wants a low total weight as possible and that
021: * is capable of only holding a given maximum weight.
022: *
023: * @author Klaus Meffert
024: * @since 2.4
025: */
026: public class CoinsEnergy {
027: /** String containing the CVS revision. Read out via reflection!*/
028: private final static String CVS_REVISION = "$Revision: 1.9 $";
029:
030: /**
031: * The total number of times we'll let the population evolve.
032: */
033: private static final int MAX_ALLOWED_EVOLUTIONS = 200;
034:
035: /**
036: * Executes the genetic algorithm to determine the minimum number of
037: * coins necessary to make up the given target amount of change. The
038: * solution will then be written to System.out.
039: *
040: * @param a_targetChangeAmount the target amount of change for which this
041: * method is attempting to produce the minimum number of coins
042: * @param a_maxWeight the maximum weight allowed in sum over all coins
043: * @throws Exception
044: *
045: * @author Neil Rotstan
046: * @author Klaus Meffert
047: * @since 1.0
048: */
049: public static void makeChangeForAmount(int a_targetChangeAmount,
050: double a_maxWeight) throws Exception {
051: // Start with a DefaultConfiguration, which comes setup with the
052: // most common settings.
053: // -------------------------------------------------------------
054: Configuration conf = new DefaultConfiguration();
055: conf.setPreservFittestIndividual(true);
056: conf.setKeepPopulationSizeConstant(false);
057: // Set the fitness function we want to use, which is our
058: // MinimizingMakeChangeFitnessFunction. We construct it with
059: // the target amount of change passed in to this method.
060: // ---------------------------------------------------------
061: FitnessFunction myFunc = new CoinsEnergyFitnessFunction(
062: a_targetChangeAmount, a_maxWeight);
063: // conf.setFitnessFunction(myFunc);
064: conf
065: .setBulkFitnessFunction(new BulkFitnessOffsetRemover(
066: myFunc));
067: // Now we need to tell the Configuration object how we want our
068: // Chromosomes to be setup. We do that by actually creating a
069: // sample Chromosome and then setting it on the Configuration
070: // object. As mentioned earlier, we want our Chromosomes to each
071: // have four genes, one for each of the coin types. We want the
072: // values (alleles) of those genes to be integers, which represent
073: // how many coins of that type we have. We therefore use the
074: // IntegerGene class to represent each of the genes. That class
075: // also lets us specify a lower and upper bound, which we set
076: // to sensible values for each coin type.
077: // --------------------------------------------------------------
078: Gene[] sampleGenes = new Gene[4];
079: IntegerGene gene = new IntegerGene(conf, 0, 3 * 10);
080: gene.setConstraintChecker(new EnergyGeneConstraintChecker());
081: // Initialize energys of Gene's. Each Gene represents a coin with a
082: // specific value, and each coin with different value has a specific
083: // weight. Not necessarily a higher weight for higher coin values!
084: // (as in real life!).
085: sampleGenes[0] = gene; // Quarters
086: sampleGenes[0].setEnergy(20.0d);
087: sampleGenes[1] = new IntegerGene(conf, 0, 2 * 10); // Dimes
088: sampleGenes[1].setEnergy(10.0d);
089: sampleGenes[2] = new IntegerGene(conf, 0, 1 * 10); // Nickels
090: sampleGenes[2].setEnergy(11.0d);
091: sampleGenes[3] = new IntegerGene(conf, 0, 4 * 10); // Pennies
092: sampleGenes[3].setEnergy(7.0d);
093: IChromosome sampleChromosome = new Chromosome(conf, sampleGenes);
094: conf.setSampleChromosome(sampleChromosome);
095: // Finally, we need to tell the Configuration object how many
096: // Chromosomes we want in our population. The more Chromosomes,
097: // the larger number of potential solutions (which is good for
098: // finding the answer), but the longer it will take to evolve
099: // the population (which could be seen as bad).
100: // ------------------------------------------------------------
101: conf.setPopulationSize(80);
102: // Create random initial population of Chromosomes.
103: // ------------------------------------------------
104: Genotype population = Genotype.randomInitialGenotype(conf);
105:
106: // Evolve the population. Since we don't know what the best answer
107: // is going to be, we just evolve the max number of times.
108: // ---------------------------------------------------------------
109: for (int i = 0; i < MAX_ALLOWED_EVOLUTIONS; i++) {
110: population.evolve();
111: }
112: // Display the best solution we found.
113: // -----------------------------------
114: IChromosome bestSolutionSoFar = population
115: .getFittestChromosome();
116: System.out.println("The best solution has a fitness value of "
117: + bestSolutionSoFar.getFitnessValue());
118: System.out.println("It contains the following: ");
119: System.out.println("\t"
120: + CoinsEnergyFitnessFunction.getNumberOfCoinsAtGene(
121: bestSolutionSoFar, 0) + " quarters.");
122: System.out.println("\t"
123: + CoinsEnergyFitnessFunction.getNumberOfCoinsAtGene(
124: bestSolutionSoFar, 1) + " dimes.");
125: System.out.println("\t"
126: + CoinsEnergyFitnessFunction.getNumberOfCoinsAtGene(
127: bestSolutionSoFar, 2) + " nickels.");
128: System.out.println("\t"
129: + CoinsEnergyFitnessFunction.getNumberOfCoinsAtGene(
130: bestSolutionSoFar, 3) + " pennies.");
131: System.out.println("For a total of "
132: + CoinsEnergyFitnessFunction
133: .amountOfChange(bestSolutionSoFar)
134: + " cents in "
135: + CoinsEnergyFitnessFunction
136: .getTotalNumberOfCoins(bestSolutionSoFar)
137: + " coins with a total weight of "
138: + CoinsEnergyFitnessFunction
139: .getTotalWeight(bestSolutionSoFar) + ")");
140: }
141:
142: /**
143: * Main method. A single command-line argument is expected, which is the
144: * amount of change to create (in other words, 75 would be equal to 75
145: * cents).
146: *
147: * @param args amount of change in cents to create
148: * @throws Exception
149: *
150: * @author Neil Rotstan
151: * @author Klaus Meffert
152: * @since 1.0
153: */
154: public static void main(String[] args) throws Exception {
155: if (args.length != 2) {
156: System.out
157: .println("Syntax: CoinsEnergy <amount> <max weight>");
158: } else {
159: int amount = getValue(args, 0);
160: int weight = getValue(args, 1);
161: makeChangeForAmount(amount, weight);
162: }
163: }
164:
165: protected static int getValue(String[] args, int index) {
166: int value;
167: try {
168: value = Integer.parseInt(args[index]);
169: return value;
170: } catch (NumberFormatException e) {
171: System.out.println("The " + (index + 1)
172: + ". argument must be a valid integer value");
173: System.exit(1);
174: return -1; // does not matter
175: }
176: }
177:
178: /**
179: * Uses to set the energy when a new allele is set
180: * @author Klaus Meffert
181: * @since 2.4
182: */
183: public static class EnergyGeneConstraintChecker implements
184: IGeneConstraintChecker {
185: public final static double[] coinWeights = { 1.0d, 2.0d, 8.0d,
186: 3.0d };
187:
188: /**
189: * Check if a given allele value is valid for the given gene instance.
190: * @param a_gene the gene the given allele is to be validated for
191: * @param a_alleleValue the allele value to be validated
192: * @param a_chrom not used yet
193: * @param a_geneIndex not used yet
194: * @return true: allele may be set for gene; false: validity check failed
195: * @throws RuntimeException if the checker cannot decide whether the given
196: * allele is valid or not
197: *
198: * @author Klaus Meffert
199: * @since 2.4
200: */
201: public boolean verify(Gene a_gene, final Object a_alleleValue,
202: final IChromosome a_chrom, final int a_geneIndex)
203: throws RuntimeException {
204: double computedWeight = 0.0d;
205: // We need to figure out what type of coin (penny, nickle, dime, quarter)
206: // the current Gene represents. This is not trivial as it depends on the
207: // index of the Gene within the Chromosome. The Chromosome is not
208: // accessible by the Gene!
209: // ----------------------------------------------------------------------
210: /**todo compute*/
211: // a_gene.setEnergy(computedWeight);
212: // No verification here, always conform.
213: // -------------------------------------
214: return true;
215: }
216: }
217: }
|