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