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