KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > examples > multidimension > 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.multidimension;
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 extended classic knapsack
21  * problem 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  * The extension to the classic knapsack is that each item can have a specific
26  * color. The fewer colors the items in the packed knapsack have, the better
27  * the solution is regarded.<p>
28  * For further descriptions, compare the "coins" example also provided.
29  *
30  * @author Klaus Meffert
31  * @since 3.0
32  */
33 public class KnapsackMain {
34   /** String containing the CVS revision. Read out via reflection!*/
35   private final static String JavaDoc CVS_REVISION = "$Revision: 1.1 $";
36
37   /**
38    * The total number of times we'll let the population evolve.
39    */
40   private static final int MAX_ALLOWED_EVOLUTIONS = 170;
41
42   /** Volumes of arbitrary items in ccm*/
43   public final static double[] itemVolumes = {
44       50.2d, 14.8d, 27.5d, 6800.0d, 25.0d, 4.75d, 95.36d, 1500.7d, 18365.9d,
45       83571.1d};
46
47   /** Names of arbitrary items, only for outputting something imaginable*/
48   public final static String JavaDoc[] itemNames = {
49       "Torch", "Banana", "Miniradio", "TV", "Gameboy", "Small thingie",
50       "Medium thingie", "Big thingie", "Huge thingie", "Gigantic thingie"};
51
52   public final static String JavaDoc[] COLORS = {
53       "red", "green", "blue", "yellow", "brown", "orange",
54       "mint", "purple", "black", "white"};
55
56
57   /**
58    * Executes the genetic algorithm to determine the minimum number of
59    * items necessary to make up the given target volume. The solution will then
60    * be written to the console.
61    *
62    * @param a_knapsackVolume the target volume for which this method is
63    * attempting to produce the optimal list of items
64    * @param a_numCols max. number of colors being available for items
65    *
66    * @throws Exception
67    *
68    * @author Klaus Meffert
69    * @since 3.0
70    */
71   public static void findItemsForVolume(double a_knapsackVolume, int a_numCols)
72       throws Exception JavaDoc {
73     // Start with a DefaultConfiguration, which comes setup with the
74 // most common settings.
75 // -------------------------------------------------------------
76 Configuration conf = new DefaultConfiguration();
77     conf.setPreservFittestIndividual(true);
78     // Set the fitness function we want to use. We construct it with
79 // the target volume passed in to this method.
80 // ---------------------------------------------------------
81 FitnessFunction myFunc =
82         new KnapsackFitnessFunction(a_knapsackVolume);
83     conf.setFitnessFunction(myFunc);
84     // Now we need to tell the Configuration object how we want our
85 // Chromosomes to be setup. We do that by actually creating a
86 // sample Chromosome and then setting it on the Configuration
87 // object. As mentioned earlier, we want our Chromosomes to each
88 // have as many genes as there are different items available. We want the
89 // values (alleles) of those genes to be integers, which represent
90 // how many items of that type we have. We therefore use the
91 // IntegerGene class to represent each of the genes. That class
92 // also lets us specify a lower and upper bound, which we set
93 // to senseful values (i.e. maximum possible) for each item type.
94 // --------------------------------------------------------------
95 Gene[] sampleGenes = new Gene[itemVolumes.length];
96     for (int i = 0; i < itemVolumes.length; i++) {
97       CompositeGene compositeGene = new CompositeGene(conf);
98       IntegerGene color = new IntegerGene(conf, 0, a_numCols - 1);
99       IntegerGene item = new IntegerGene(conf, 0,
100                                        (int) Math.ceil(a_knapsackVolume /
101           itemVolumes[i]));
102       compositeGene.addGene(color);
103       compositeGene.addGene(item);
104       sampleGenes[i] = compositeGene;
105     }
106     IChromosome sampleChromosome = new Chromosome(conf, sampleGenes);
107     conf.setSampleChromosome(sampleChromosome);
108     // Finally, we need to tell the Configuration object how many
109 // Chromosomes we want in our population. The more Chromosomes,
110 // the larger number of potential solutions (which is good for
111 // finding the answer), but the longer it will take to evolve
112 // the population (which could be seen as bad).
113 // ------------------------------------------------------------
114 conf.setPopulationSize(80);
115     // Create random initial population of Chromosomes.
116 // ------------------------------------------------
117 Genotype population = Genotype.randomInitialGenotype(conf);
118     // Evolve the population. Since we don't know what the best answer
119 // is going to be, we just evolve the max number of times.
120 // ---------------------------------------------------------------
121 for (int i = 0; i < MAX_ALLOWED_EVOLUTIONS; i++) {
122       population.evolve();
123     }
124     // Save progress to file. A new run of this example will then be able to
125 // resume where it stopped before!
126 // ---------------------------------------------------------------------
127
128     // represent Genotype as tree with elements Chromomes and Genes
129 // ------------------------------------------------------------
130 DataTreeBuilder builder = DataTreeBuilder.getInstance();
131     IDataCreators doc2 = builder.representGenotypeAsDocument(population);
132     // create XML document from generated tree
133 // ---------------------------------------
134 XMLDocumentBuilder docbuilder = new XMLDocumentBuilder();
135     Document xmlDoc = (Document) docbuilder.buildDocument(doc2);
136     XMLManager.writeFile(xmlDoc, new File("knapsackJGAP.xml"));
137     // Display the best solution we found.
138 // -----------------------------------
139 IChromosome bestSolutionSoFar = population.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.getGene(i);
147       IntegerGene color = (IntegerGene)comp.geneAt(0);
148       IntegerGene item = (IntegerGene)comp.geneAt(1);
149       count = ( (Integer JavaDoc) item.getAllele()).intValue();
150       if (count > 0) {
151         String JavaDoc colorName = COLORS[color.intValue()];
152         System.out.println("\t " + count + " x " + itemNames[i] + " color "+colorName);
153         totalVolume += itemVolumes[i] * count;
154       }
155     }
156     System.out.println("\nFor a total volume of " + totalVolume + " ccm");
157     System.out.println("Expected volume was " + a_knapsackVolume + " ccm");
158     System.out.println("Volume difference is " +
159                        Math.abs(totalVolume - a_knapsackVolume) + " ccm");
160   }
161
162   /**
163    * Main method. A single command-line argument is expected, which is the
164    * volume to create (in other words, 75 would be equal to 75 ccm).
165    *
166    * @param args first element in the array = volume of the knapsack
167    * to fill as a double value, second element = max. no. of colors
168    *
169    * @author Klaus Meffert
170    * @since 3.0
171    */
172   public static void main(String JavaDoc[] args) {
173     if (args.length != 2) {
174       System.out.println("Syntax: " + KnapsackMain.class.getName() +
175                          " <volume> <number of colors>");
176     }
177     else {
178       try {
179         double volume = Double.parseDouble(args[0]);
180         if (volume < 1 ||
181             volume >= KnapsackFitnessFunction.MAX_BOUND) {
182           System.out.println("The <volume> argument must be between 1 and "
183                              +
184                              (KnapsackFitnessFunction.MAX_BOUND - 1)
185                              + " and can be a decimal.");
186         }
187         else {
188           int colors = Integer.parseInt(args[1]);
189           if (colors < 1 || colors > KnapsackMain.COLORS.length) {
190             System.out.println("The <number of colors> argument must be between"
191                                +" 1 and "+
192                                 KnapsackMain.COLORS.length);
193           }
194           else {
195             try {
196               findItemsForVolume(volume, colors);
197             }
198             catch (Exception JavaDoc e) {
199               e.printStackTrace();
200             }
201           }
202         }
203       }
204       catch (NumberFormatException JavaDoc e) {
205         System.out.println(
206             "The <volume> argument must be a valid double value,"
207             +" <colors> must be a valid integer number.");
208       }
209     }
210   }
211 }
212
Popular Tags