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.multidimension;
011:
012: import java.io.*;
013: import org.jgap.*;
014: import org.jgap.data.*;
015: import org.jgap.impl.*;
016: import org.jgap.xml.*;
017: import org.w3c.dom.*;
018:
019: /**
020: * This class provides an implementation of the extended classic knapsack
021: * problem using a genetic algorithm. The goal of the problem is to reach a given
022: * volume (of a knapsack) by putting a number of items into the knapsack.
023: * The closer the sum of the item volumes to the given volume the better.
024: * <p>
025: * The extension to the classic knapsack is that each item can have a specific
026: * color. The fewer colors the items in the packed knapsack have, the better
027: * the solution is regarded.<p>
028: * For further descriptions, compare the "coins" example also provided.
029: *
030: * @author Klaus Meffert
031: * @since 3.0
032: */
033: public class KnapsackMain {
034: /** String containing the CVS revision. Read out via reflection!*/
035: private final static String CVS_REVISION = "$Revision: 1.1 $";
036:
037: /**
038: * The total number of times we'll let the population evolve.
039: */
040: private static final int MAX_ALLOWED_EVOLUTIONS = 170;
041:
042: /** Volumes of arbitrary items in ccm*/
043: public final static double[] itemVolumes = { 50.2d, 14.8d, 27.5d,
044: 6800.0d, 25.0d, 4.75d, 95.36d, 1500.7d, 18365.9d, 83571.1d };
045:
046: /** Names of arbitrary items, only for outputting something imaginable*/
047: public final static String[] itemNames = { "Torch", "Banana",
048: "Miniradio", "TV", "Gameboy", "Small thingie",
049: "Medium thingie", "Big thingie", "Huge thingie",
050: "Gigantic thingie" };
051:
052: public final static String[] COLORS = { "red", "green", "blue",
053: "yellow", "brown", "orange", "mint", "purple", "black",
054: "white" };
055:
056: /**
057: * Executes the genetic algorithm to determine the minimum number of
058: * items necessary to make up the given target volume. The solution will then
059: * be written to the console.
060: *
061: * @param a_knapsackVolume the target volume for which this method is
062: * attempting to produce the optimal list of items
063: * @param a_numCols max. number of colors being available for items
064: *
065: * @throws Exception
066: *
067: * @author Klaus Meffert
068: * @since 3.0
069: */
070: public static void findItemsForVolume(double a_knapsackVolume,
071: int a_numCols) throws Exception {
072: // Start with a DefaultConfiguration, which comes setup with the
073: // most common settings.
074: // -------------------------------------------------------------
075: Configuration conf = new DefaultConfiguration();
076: conf.setPreservFittestIndividual(true);
077: // Set the fitness function we want to use. We construct it with
078: // the target volume passed in to this method.
079: // ---------------------------------------------------------
080: FitnessFunction myFunc = new KnapsackFitnessFunction(
081: a_knapsackVolume);
082: conf.setFitnessFunction(myFunc);
083: // Now we need to tell the Configuration object how we want our
084: // Chromosomes to be setup. We do that by actually creating a
085: // sample Chromosome and then setting it on the Configuration
086: // object. As mentioned earlier, we want our Chromosomes to each
087: // have as many genes as there are different items available. We want the
088: // values (alleles) of those genes to be integers, which represent
089: // how many items of that type we have. We therefore use the
090: // IntegerGene class to represent each of the genes. That class
091: // also lets us specify a lower and upper bound, which we set
092: // to senseful values (i.e. maximum possible) for each item type.
093: // --------------------------------------------------------------
094: Gene[] sampleGenes = new Gene[itemVolumes.length];
095: for (int i = 0; i < itemVolumes.length; i++) {
096: CompositeGene compositeGene = new CompositeGene(conf);
097: IntegerGene color = new IntegerGene(conf, 0, a_numCols - 1);
098: IntegerGene item = new IntegerGene(conf, 0, (int) Math
099: .ceil(a_knapsackVolume / itemVolumes[i]));
100: compositeGene.addGene(color);
101: compositeGene.addGene(item);
102: sampleGenes[i] = compositeGene;
103: }
104: IChromosome sampleChromosome = new Chromosome(conf, sampleGenes);
105: conf.setSampleChromosome(sampleChromosome);
106: // Finally, we need to tell the Configuration object how many
107: // Chromosomes we want in our population. The more Chromosomes,
108: // the larger number of potential solutions (which is good for
109: // finding the answer), but the longer it will take to evolve
110: // the population (which could be seen as bad).
111: // ------------------------------------------------------------
112: conf.setPopulationSize(80);
113: // Create random initial population of Chromosomes.
114: // ------------------------------------------------
115: Genotype population = Genotype.randomInitialGenotype(conf);
116: // Evolve the population. Since we don't know what the best answer
117: // is going to be, we just evolve the max number of times.
118: // ---------------------------------------------------------------
119: for (int i = 0; i < MAX_ALLOWED_EVOLUTIONS; i++) {
120: population.evolve();
121: }
122: // Save progress to file. A new run of this example will then be able to
123: // resume where it stopped before!
124: // ---------------------------------------------------------------------
125:
126: // represent Genotype as tree with elements Chromomes and Genes
127: // ------------------------------------------------------------
128: DataTreeBuilder builder = DataTreeBuilder.getInstance();
129: IDataCreators doc2 = builder
130: .representGenotypeAsDocument(population);
131: // create XML document from generated tree
132: // ---------------------------------------
133: XMLDocumentBuilder docbuilder = new XMLDocumentBuilder();
134: Document xmlDoc = (Document) docbuilder.buildDocument(doc2);
135: XMLManager.writeFile(xmlDoc, new File("knapsackJGAP.xml"));
136: // Display the best solution we found.
137: // -----------------------------------
138: IChromosome bestSolutionSoFar = population
139: .getFittestChromosome();
140: System.out.println("The best solution has a fitness value of "
141: + bestSolutionSoFar.getFitnessValue());
142: System.out.println("It contained the following: ");
143: int count;
144: double totalVolume = 0.0d;
145: for (int i = 0; i < bestSolutionSoFar.size(); i++) {
146: CompositeGene comp = (CompositeGene) bestSolutionSoFar
147: .getGene(i);
148: IntegerGene color = (IntegerGene) comp.geneAt(0);
149: IntegerGene item = (IntegerGene) comp.geneAt(1);
150: count = ((Integer) item.getAllele()).intValue();
151: if (count > 0) {
152: String colorName = COLORS[color.intValue()];
153: System.out.println("\t " + count + " x " + itemNames[i]
154: + " color " + colorName);
155: totalVolume += itemVolumes[i] * count;
156: }
157: }
158: System.out.println("\nFor a total volume of " + totalVolume
159: + " ccm");
160: System.out.println("Expected volume was " + a_knapsackVolume
161: + " ccm");
162: System.out.println("Volume difference is "
163: + Math.abs(totalVolume - a_knapsackVolume) + " ccm");
164: }
165:
166: /**
167: * Main method. A single command-line argument is expected, which is the
168: * volume to create (in other words, 75 would be equal to 75 ccm).
169: *
170: * @param args first element in the array = volume of the knapsack
171: * to fill as a double value, second element = max. no. of colors
172: *
173: * @author Klaus Meffert
174: * @since 3.0
175: */
176: public static void main(String[] args) {
177: if (args.length != 2) {
178: System.out.println("Syntax: "
179: + KnapsackMain.class.getName()
180: + " <volume> <number of colors>");
181: } else {
182: try {
183: double volume = Double.parseDouble(args[0]);
184: if (volume < 1
185: || volume >= KnapsackFitnessFunction.MAX_BOUND) {
186: System.out
187: .println("The <volume> argument must be between 1 and "
188: + (KnapsackFitnessFunction.MAX_BOUND - 1)
189: + " and can be a decimal.");
190: } else {
191: int colors = Integer.parseInt(args[1]);
192: if (colors < 1
193: || colors > KnapsackMain.COLORS.length) {
194: System.out
195: .println("The <number of colors> argument must be between"
196: + " 1 and "
197: + KnapsackMain.COLORS.length);
198: } else {
199: try {
200: findItemsForVolume(volume, colors);
201: } catch (Exception e) {
202: e.printStackTrace();
203: }
204: }
205: }
206: } catch (NumberFormatException e) {
207: System.out
208: .println("The <volume> argument must be a valid double value,"
209: + " <colors> must be a valid integer number.");
210: }
211: }
212: }
213: }
|