001 /*
002 * JENES
003 * A time and memory efficient Java library for genetic algorithms and more
004 * Copyright (C) 2011 Intelligentia srl
005 *
006 * This program is free software: you can redistribute it and/or modify
007 * it under the terms of the GNU General Public License as published by
008 * the Free Software Foundation, either version 3 of the License, or
009 * (at your option) any later version.
010 *
011 * This program is distributed in the hope that it will be useful,
012 * but WITHOUT ANY WARRANTY; without even the implied warranty of
013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
014 * GNU General Public License for more details.
015 *
016 * You should have received a copy of the GNU General Public License
017 * along with this program. If not, see <http://www.gnu.org/licenses/>.
018 */
019 package jenes.tutorials.problem6;
020
021 import jenes.utils.Random;
022 import jenes.population.Individual;
023 import jenes.population.Population;
024 import jenes.population.Population.Statistics;
025 import jenes.population.Population.Statistics.Group;
026 import jenes.tutorials.utils.Utils;
027
028 /**
029 * Tutorial showing how to minimization and maximization sub-prolems can cohesists in
030 * the breeding structure of Jenes.
031 *
032 * This class defines the problem to solve.
033 *
034 * @author Luigi Troiano
035 *
036 * @version 1.0
037 * @since 1.0
038 */
039 public class KnapsackProblem {
040
041 private static int POPSIZE=100;
042 private static int GENERATION_LIMIT=100;
043
044 private static final double[] WEIGHTS = {1, 5, 3, 2, 8, 6, 4, 7, 9, 6};
045 private static final double[] UTILITIES = {7, 2, 7, 1, 6, 4, 2, 8, 9, 2};
046
047 private KnapsackGA algorithm;
048 private double[] utilities;
049 private double[] weights;
050
051 public KnapsackProblem(double[] utilities, double[] weights) {
052 algorithm = new KnapsackGA(POPSIZE, GENERATION_LIMIT, utilities, weights);
053 this.weights = weights;
054 this.utilities = utilities;
055 }
056
057 @SuppressWarnings("unchecked")
058 public void run() {
059 this.algorithm.evolve();
060
061 Statistics stat=algorithm.getCurrentPopulation().getStatistics();
062 Group legals = stat.getGroup(Population.LEGALS);
063 Individual solution= legals.get(0);
064 System.out.println(solution.getChromosome());
065 System.out.format("W: %f U: %f\n", algorithm.getWeightOf(solution), algorithm.getUtilityOf(solution) );
066 }
067
068 public double getCapacity() {
069 return this.algorithm.getCapacity();
070 }
071
072 public void setCapacity(double c) {
073 this.algorithm.setCapacity(c);
074 }
075
076 public double[] getUtilities() {
077 return utilities;
078 }
079
080 public double[] getWeights() {
081 return weights;
082 }
083
084 public static KnapsackProblem build(int n) {
085
086 Random r = Random.getInstance();
087
088 double[] utilities = new double[n];
089 for( int i = 0; i < n; ++i ) {
090 utilities[i] = r.nextInt(10);
091 }
092
093 double[] weights = new double[n];
094 for( int i = 0; i < n; ++i ) {
095 weights[i] = r.nextInt(10);
096 }
097
098 return new KnapsackProblem(utilities, weights);
099 }
100
101 public static void main(String[] args) {
102
103 Utils.printHeader();
104 System.out.println();
105
106 System.out.println("TUTORIAL 6:");
107 System.out.println("The Knapsack Problem.");
108 System.out.println();
109
110 KnapsackProblem p1 = new KnapsackProblem(UTILITIES, WEIGHTS);
111
112 System.out.println("Case 1: 10 elements, capacity 15");
113 System.out.println("Utilities: " + toString(p1.getUtilities()) );
114 System.out.println(" Weights: " + toString(p1.getWeights()) );
115 p1.setCapacity(15);
116 p1.run();
117 System.out.println();
118
119 System.out.println("Case 2: 10 elements, capacity 30");
120 System.out.println("Utilities: " + toString(p1.getUtilities()) );
121 System.out.println(" Weights: " + toString(p1.getWeights()) );
122 p1.setCapacity(30);
123 p1.run();
124 System.out.println();
125
126 KnapsackProblem p2 = KnapsackProblem.build(20);
127
128 System.out.println("Case 3: 20 random elements, capacity 50");
129 System.out.println("Utilities: " + toString(p2.getUtilities()) );
130 System.out.println(" Weights: " + toString(p2.getWeights()) );
131 p2.setCapacity(50);
132 p2.run();
133 System.out.println();
134 }
135
136 private static String toString(double[] values) {
137 String s = "[";
138 for(int i = 0; i < values.length; ++i ){
139 s += values[i]+ (i < values.length-1 ? " " : "]");
140 }
141 return s;
142 }
143
144 }
|
|
|
