Source Code Cross Referenced for KnapsackMain.java in  » Development » jgap » examples » knapsack » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » Development » jgap » examples.knapsack 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


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:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.