Source Code Cross Referenced for KnapsackFitnessFunction.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 org.jgap.*;
013:
014:        /**
015:         * Fitness function for the knapsack example.
016:         *
017:         * @author Klaus Meffert
018:         * @since 2.3
019:         */
020:        public class KnapsackFitnessFunction extends FitnessFunction {
021:            /** String containing the CVS revision. Read out via reflection!*/
022:            private final static String CVS_REVISION = "$Revision: 1.4 $";
023:
024:            private final double m_knapsackVolume;
025:
026:            public static final double MAX_BOUND = 1000000000.0d;
027:
028:            private static final double ZERO_DIFFERENCE_FITNESS = Math
029:                    .sqrt(MAX_BOUND);
030:
031:            public KnapsackFitnessFunction(double a_knapsackVolume) {
032:                if (a_knapsackVolume < 1 || a_knapsackVolume >= MAX_BOUND) {
033:                    throw new IllegalArgumentException(
034:                            "Knapsack volumen must be between 1 and "
035:                                    + MAX_BOUND + ".");
036:                }
037:                m_knapsackVolume = a_knapsackVolume;
038:            }
039:
040:            /**
041:             * Determine the fitness of the given Chromosome instance. The higher the
042:             * return value, the more fit the instance. This method should always
043:             * return the same fitness value for two equivalent Chromosome instances.
044:             *
045:             * @param a_subject the Chromosome instance to evaluate
046:             * @return a positive double reflecting the fitness rating of the given
047:             * Chromosome
048:             *
049:             * @author Klaus Meffert
050:             * @since 2.3
051:             */
052:            public double evaluate(IChromosome a_subject) {
053:                // The fitness value measures both how close the value is to the
054:                // target amount supplied by the user and the total number of items
055:                // represented by the solution. We do this in two steps: first,
056:                // we consider only the represented amount of change vs. the target
057:                // amount of change and return higher fitness values for amounts
058:                // closer to the target, and lower fitness values for amounts further
059:                // away from the target. Then we go to step 2, which returns a higher
060:                // fitness value for solutions representing fewer total items, and
061:                // lower fitness values for solutions representing more total items.
062:                // ------------------------------------------------------------------
063:                double totalVolume = getTotalVolume(a_subject);
064:                int numberOfItems = getTotalNumberOfItems(a_subject);
065:                double volumeDifference = Math.abs(m_knapsackVolume
066:                        - totalVolume);
067:                double fitness = 0.0d;
068:                // Step 1: Determine distance of amount represented by solution from
069:                // the target amount. If the change difference is greater than zero we
070:                // will divide one by the difference in change between the
071:                // solution amount and the target amount. That will give the desired
072:                // effect of returning higher values for amounts closer to the target
073:                // amount and lower values for amounts further away from the target
074:                // amount.
075:                // In the case where the change difference is zero it means that we have
076:                // the correct amount and we assign a higher fitness value
077:                // -----------------------------------------------------------------
078:                fitness += volumeDifferenceBonus(MAX_BOUND, volumeDifference);
079:                // Step 2: We divide the fitness value by a penalty based on the number of
080:                // items. The higher the number of items the higher the penalty and the
081:                // smaller the fitness value.
082:                // And inversely the smaller number of items in the solution the higher
083:                // the resulting fitness value.
084:                // -----------------------------------------------------------------------
085:                fitness -= computeItemNumberPenalty(MAX_BOUND, numberOfItems);
086:                // Make sure fitness value is always positive.
087:                // -------------------------------------------
088:                return Math.max(1.0d, fitness);
089:            }
090:
091:            /**
092:             * Bonus calculation of fitness value.
093:             * @param a_maxFitness maximum fitness value appliable
094:             * @param a_volumeDifference volume difference in ccm for the items problem
095:             * @return bonus for given volume difference
096:             *
097:             * @author Klaus Meffert
098:             * @since 2.3
099:             */
100:            protected double volumeDifferenceBonus(double a_maxFitness,
101:                    double a_volumeDifference) {
102:                if (a_volumeDifference == 0) {
103:                    return a_maxFitness;
104:                } else {
105:                    // we arbitrarily work with half of the maximum fitness as basis for non-
106:                    // optimal solutions (concerning volume difference)
107:                    return a_maxFitness / 2
108:                            - (a_volumeDifference * a_volumeDifference);
109:                }
110:            }
111:
112:            /**
113:             * Calculates the penalty to apply to the fitness value based on the amount
114:             * of items in the solution.
115:             *
116:             * @param a_maxFitness upper boundary for fitness value possible
117:             * @param a_items number of items in the solution
118:             * @return a penalty for the fitness value based on the number of items
119:             *
120:             * @author Klaus Meffert
121:             * @since 2.3
122:             */
123:            protected double computeItemNumberPenalty(double a_maxFitness,
124:                    int a_items) {
125:                if (a_items == 0) {
126:                    // We know the solution cannot have less than zero items.
127:                    // ------------------------------------------------------
128:                    return 0;
129:                } else {
130:                    // The more items the more penalty, but not more than the maximum fitness
131:                    // value possible. Let's avoid linear behavior and use
132:                    // exponential penalty calculation instead.
133:                    // ----------------------------------------------------------------------
134:                    return (Math.min(a_maxFitness, a_items * a_items));
135:                }
136:            }
137:
138:            /**
139:             * Calculates the total amount of change (in cents) represented by
140:             * the given potential solution and returns that amount.
141:             *
142:             * @param a_potentialSolution the potential solution to evaluate
143:             * @return the total amount of change (in cents) represented by the
144:             * given solution
145:             *
146:             * @author Klaus Meffert
147:             * @since 2.3
148:             */
149:            public static double getTotalVolume(IChromosome a_potentialSolution) {
150:                double volume = 0.0d;
151:                for (int i = 0; i < a_potentialSolution.size(); i++) {
152:                    volume += getNumberOfItemsAtGene(a_potentialSolution, i)
153:                            * KnapsackMain.itemVolumes[i];
154:                }
155:                return volume;
156:            }
157:
158:            /**
159:             * Retrieves the number of items represented by the given potential
160:             * solution at the given gene position.
161:             *
162:             * @param a_potentialSolution the potential solution to evaluate
163:             * @param a_position the gene position to evaluate
164:             * @return the number of items represented by the potential solution
165:             * at the given gene position
166:             *
167:             * @author Klaus Meffert
168:             * @since 2.3
169:             */
170:            public static int getNumberOfItemsAtGene(
171:                    IChromosome a_potentialSolution, int a_position) {
172:                Integer numItems = (Integer) a_potentialSolution.getGene(
173:                        a_position).getAllele();
174:                return numItems.intValue();
175:            }
176:
177:            /**
178:             * Returns the total number of items represented by all of the genes in
179:             * the given potential solution.
180:             *
181:             * @param a_potentialSolution the potential solution to evaluate
182:             * @return the total number of items represented by the given Chromosome
183:             *
184:             * @author Klaus Meffert
185:             * @since 2.3
186:             */
187:            public static int getTotalNumberOfItems(
188:                    IChromosome a_potentialSolution) {
189:                int totalItems = 0;
190:                int numberOfGenes = a_potentialSolution.size();
191:                for (int i = 0; i < numberOfGenes; i++) {
192:                    totalItems += getNumberOfItemsAtGene(a_potentialSolution, i);
193:                }
194:                return totalItems;
195:            }
196:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.