001 /*
002 * JENES
003 * A time asnd 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.old.problem6;
020
021 import jenes.utils.Random;
022 import jenes.population.Individual;
023 import jenes.population.Population.Statistics;
024 import jenes.tutorials.utils.Utils;
025
026 /**
027 * Tutorial showing how to minimization and maximization sub-prolems can cohesists in
028 * the breeding structure of Jenes.
029 *
030 * This class defines the problem to solve.
031 *
032 * @author Luigi Troiano
033 * @author Pierpaolo Lombardi
034 *
035 * @version 1.0
036 * @since 1.0
037 */
038 public class KnapsackProblem {
039
040 private static int POPSIZE=100;
041 private static int GENERATION_LIMIT=100;
042
043 private static final double[] WEIGHTS = {1, 5, 3, 2, 8, 6, 4, 7, 9, 6};
044 private static final double[] UTILITIES = {7, 2, 7, 1, 6, 4, 2, 8, 9, 2};
045
046 private KnapsackGA algorithm;
047 private double[] utilities;
048 private double[] weights;
049
050 public KnapsackProblem(double[] utilities, double[] weights) {
051 algorithm = new KnapsackGA(POPSIZE, GENERATION_LIMIT, utilities, weights);
052 this.weights = weights;
053 this.utilities = utilities;
054 }
055
056 @SuppressWarnings("unchecked")
057 public void run() {
058 this.algorithm.evolve();
059
060 Statistics stat=algorithm.getCurrentPopulation().getStatistics();
061 Individual solution=stat.getLegalHighestIndividual();
062 System.out.println(solution.getChromosome());
063 System.out.format("W: %f U: %f\n", algorithm.getWeightOf(solution), algorithm.getUtilityOf(solution) );
064 }
065
066 public double getCapacity() {
067 return this.algorithm.getCapacity();
068 }
069
070 public void setCapacity(double c) {
071 this.algorithm.setCapacity(c);
072 }
073
074 public double[] getUtilities() {
075 return utilities;
076 }
077
078 public double[] getWeights() {
079 return weights;
080 }
081
082 public static KnapsackProblem build(int n) {
083
084 Random r = Random.getInstance();
085
086 double[] utilities = new double[n];
087 for( int i = 0; i < n; ++i ) {
088 utilities[i] = r.nextInt(10);
089 }
090
091 double[] weights = new double[n];
092 for( int i = 0; i < n; ++i ) {
093 weights[i] = r.nextInt(10);
094 }
095
096 return new KnapsackProblem(utilities, weights);
097 }
098
099 public static void main(String[] args) {
100
101 Utils.printHeader();
102 System.out.println();
103
104 System.out.println("TUTORIAL 6:");
105 System.out.println("The Knapsack Problem.");
106 System.out.println();
107
108 KnapsackProblem p1 = new KnapsackProblem(UTILITIES, WEIGHTS);
109
110 System.out.println("Case 1: 10 elements, capacity 15");
111 System.out.println("Utilities: " + toString(p1.getUtilities()) );
112 System.out.println(" Weights: " + toString(p1.getWeights()) );
113 p1.setCapacity(15);
114 p1.run();
115 System.out.println();
116
117 System.out.println("Case 2: 10 elements, capacity 30");
118 System.out.println("Utilities: " + toString(p1.getUtilities()) );
119 System.out.println(" Weights: " + toString(p1.getWeights()) );
120 p1.setCapacity(30);
121 p1.run();
122 System.out.println();
123
124 KnapsackProblem p2 = KnapsackProblem.build(20);
125
126 System.out.println("Case 3: 20 random elements, capacity 50");
127 System.out.println("Utilities: " + toString(p2.getUtilities()) );
128 System.out.println(" Weights: " + toString(p2.getWeights()) );
129 p2.setCapacity(50);
130 p2.run();
131 System.out.println();
132 }
133
134 private static String toString(double[] values) {
135 String s = "[";
136 for(int i = 0; i < values.length; ++i ){
137 s += values[i]+ (i < values.length-1 ? " " : "]");
138 }
139 return s;
140 }
141
142 }
|
|
|
