KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > examples > knapsack > KnapsackMain


1 /*
2  * This file is part of JGAP.
3  *
4  * JGAP offers a dual license model containing the LGPL as well as the MPL.
5  *
6  * For licencing information please see the file license.txt included with JGAP
7  * or have a look at the top of class org.jgap.Chromosome which representatively
8  * includes the JGAP license policy applicable for any file delivered with JGAP.
9  */
10 package examples.knapsack;
11
12 import java.io.*;
13 import org.jgap.*;
14 import org.jgap.data.*;
15 import org.jgap.impl.*;
16 import org.jgap.xml.*;
17 import org.w3c.dom.*;
18
19 /**
20  * This class provides an implementation of the classic knapsack problem
21  * using a genetic algorithm. The goal of the problem is to reach a given
22  * volume (of a knapsack) by putting a number of items into the knapsack.
23  * The closer the sum of the item volumes to the given volume the better.
24  * <p>
25  * For further descriptions, compare the "coins" example also provided.
26  *
27  * @author Klaus Meffert
28  * @since 2.3
29  */
30 public class KnapsackMain {
31   /** String containing the CVS revision. Read out via reflection!*/
32   private final static String JavaDoc CVS_REVISION = "$Revision: 1.9 $";
33
34   /**
35    * The total number of times we'll let the population evolve.
36    */
37   private static final int MAX_ALLOWED_EVOLUTIONS = 140;
38
39   /** Volumes of arbitrary items in ccm*/
40   public final static double[] itemVolumes = {
41       50.2d, 14.8d, 27.5d, 6800.0d, 25.0d, 4.75d, 95.36d, 1500.7d, 18365.9d,
42       83571.1d};
43
44   /** Names of arbitrary items, only for outputting something imaginable*/
45   public final static String JavaDoc[] itemNames = {
46       "Torch", "Banana", "Miniradio", "TV", "Gameboy", "Small thingie",
47       "Medium thingie", "Big thingie", "Huge thingie", "Gigantic thingie"};
48
49   /**
50    * Executes the genetic algorithm to determine the minimum number of
51    * items necessary to make up the given target volume. The solution will then
52    * be written to the console.
53    *
54    * @param a_knapsackVolume the target volume for which this method is
55    * attempting to produce the optimal list of items
56    *
57    * @throws Exception
58    *
59    * @author Klaus Meffert
60    * @since 2.3
61    */
62   public static void findItemsForVolume(double a_knapsackVolume)
63       throws Exception JavaDoc {
64     // Start with a DefaultConfiguration, which comes setup with the
65 // most common settings.
66 // -------------------------------------------------------------
67 Configuration conf = new DefaultConfiguration();
68     conf.setPreservFittestIndividual(true);
69     // Set the fitness function we want to use. We construct it with
70 // the target volume passed in to this method.
71 // ---------------------------------------------------------
72 FitnessFunction myFunc =
73         new KnapsackFitnessFunction(a_knapsackVolume);
74     conf.setFitnessFunction(myFunc);
75     // Now we need to tell the Configuration object how we want our
76 // Chromosomes to be setup. We do that by actually creating a
77 // sample Chromosome and then setting it on the Configuration
78 // object. As mentioned earlier, we want our Chromosomes to each
79 // have as many genes as there are different items available. We want the
80 // values (alleles) of those genes to be integers, which represent
81 // how many items of that type we have. We therefore use the
82 // IntegerGene class to represent each of the genes. That class
83 // also lets us specify a lower and upper bound, which we set
84 // to senseful values (i.e. maximum possible) for each item type.
85 // --------------------------------------------------------------
86 Gene[] sampleGenes = new Gene[itemVolumes.length];
87     for (int i = 0; i < itemVolumes.length; i++) {
88       sampleGenes[i] = new IntegerGene(conf, 0,
89                                        (int) Math.ceil(a_knapsackVolume /
90           itemVolumes[i]));
91     }
92     IChromosome sampleChromosome = new Chromosome(conf, sampleGenes);
93     conf.setSampleChromosome(sampleChromosome);
94     // Finally, we need to tell the Configuration object how many
95 // Chromosomes we want in our population. The more Chromosomes,
96 // the larger number of potential solutions (which is good for
97 // finding the answer), but the longer it will take to evolve
98 // the population (which could be seen as bad).
99 // ------------------------------------------------------------
100 conf.setPopulationSize(50);
101     // Create random initial population of Chromosomes.
102 // Here we try to read in a previous run via XMLManager.readFile(..)
103 // for demonstration purpose!
104 // -----------------------------------------------------------------
105 Genotype population;
106     try {
107       Document doc = XMLManager.readFile(new File("knapsackJGAP.xml"));
108       population = XMLManager.getGenotypeFromDocument(conf, doc);
109     }
110     catch (FileNotFoundException fex) {
111       population = Genotype.randomInitialGenotype(conf);
112     }
113     population = Genotype.randomInitialGenotype(conf);
114     // Evolve the population. Since we don't know what the best answer
115 // is going to be, we just evolve the max number of times.
116 // ---------------------------------------------------------------
117 for (int i = 0; i < MAX_ALLOWED_EVOLUTIONS; i++) {
118       population.evolve();
119     }
120     // Save progress to file. A new run of this example will then be able to
121 // resume where it stopped before!
122 // ---------------------------------------------------------------------
123
124     // represent Genotype as tree with elements Chromomes and Genes
125 // ------------------------------------------------------------
126 DataTreeBuilder builder = DataTreeBuilder.getInstance();
127     IDataCreators doc2 = builder.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.getFittestChromosome();
136     System.out.println("The best solution has a fitness value of " +
137                        bestSolutionSoFar.getFitnessValue());
138     System.out.println("It contained the following: ");
139     int count;
140     double totalVolume = 0.0d;
141     for (int i = 0; i < bestSolutionSoFar.size(); i++) {
142       count = ( (Integer JavaDoc) bestSolutionSoFar.getGene(i).getAllele()).intValue();
143       if (count > 0) {
144         System.out.println("\t " + count + " x " + itemNames[i]);
145         totalVolume += itemVolumes[i] * count;
146       }
147     }
148     System.out.println("\nFor a total volume of " + totalVolume + " ccm");
149     System.out.println("Expected volume was " + a_knapsackVolume + " ccm");
150     System.out.println("Volume difference is " +
151                        Math.abs(totalVolume - a_knapsackVolume) + " ccm");
152   }
153
154   /**
155    * Main method. A single command-line argument is expected, which is the
156    * volume to create (in other words, 75 would be equal to 75 ccm).
157    *
158    * @param args first and single element in the array = volume of the knapsack
159    * to fill as a double value
160    *
161    * @author Klaus Meffert
162    * @since 2.3
163    */
164   public static void main(String JavaDoc[] args) {
165     if (args.length != 1) {
166       System.out.println("Syntax: " + KnapsackMain.class.getName() +
167                          " <volume>");
168     }
169     else {
170       try {
171         double volume = Double.parseDouble(args[0]);
172         if (volume < 1 ||
173             volume >= KnapsackFitnessFunction.MAX_BOUND) {
174           System.out.println("The <volume> argument must be between 1 and "
175                              +
176                              (KnapsackFitnessFunction.MAX_BOUND - 1)
177                              + " and can be a decimal.");
178         }
179         else {
180           try {
181             findItemsForVolume(volume);
182           }
183           catch (Exception JavaDoc e) {
184             e.printStackTrace();
185           }
186         }
187       }
188       catch (NumberFormatException JavaDoc e) {
189         System.out.println(
190             "The <volume> argument must be a valid double value");
191       }
192     }
193   }
194 }
195
Popular Tags