001 /*
002 * CISELab, Computational and Intelligent Systems Engineering Laboratory
003 * Department of Engineering
004 * University of Sannio, 82100 Benevento (ITALY)
005 * web-site: www.ciselab.org
006 *
007 * JENES, A Java Library for Genetic Algorithms
008 * Copyright (C) 2009, Luigi Troiano
009 *
010 * This library is free software; you can redistribute it and/or
011 * modify it under the terms of the GNU Lesser General Public
012 * License as published by the Free Software Foundation; either
013 * version 2.1 of the License, or (at your option) any later version.
014 *
015 * This library is distributed in the hope that it will be useful,
016 * but WITHOUT ANY WARRANTY; without even the implied warranty of
017 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
018 * Lesser General Public License for more details.
019 *
020 * You should have received a copy of the GNU Lesser General Public
021 * License along with this library; if not, write to the Free Software
022 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
023 02110-1301 USA
024 *
025 * COPYRIGHT DISCLAIMER
026 * CISELab, hereby disclaims all copyright interest in the
027 * library `JENES' (A Java Library for Genetic Algorithms)
028 * written by Luigi Troiano et al.
029 *
030 * Luigi Troiano, 1 January 2009
031 * CISELab Coordinator
032 *
033 */
034 package jenes.tutorials.problem6;
035
036 import jenes.Random;
037 import jenes.population.Individual;
038 import jenes.population.Population.Statistics;
039 import jenes.tutorials.utils.Utils;
040
041 public class KnapsackProblem {
042
043 private static int POPSIZE=100;
044 private static int GENERATION_LIMIT=100;
045
046 private static final double[] WEIGHTS = {1, 5, 3, 2, 8, 6, 4, 7, 9, 6};
047 private static final double[] UTILITIES = {7, 2, 7, 1, 6, 4, 2, 8, 9, 2};
048
049 private KnapsackGA algorithm;
050 private double[] utilities;
051 private double[] weights;
052
053 public KnapsackProblem(double[] utilities, double[] weights) {
054 algorithm = new KnapsackGA(POPSIZE, GENERATION_LIMIT, utilities, weights);
055 this.weights = weights;
056 this.utilities = utilities;
057 }
058
059 @SuppressWarnings("unchecked")
060 public void run() {
061 this.algorithm.evolve();
062
063 Statistics stat=algorithm.getCurrentPopulation().getStatistics();
064 Individual solution=stat.getLegalHighestIndividual();
065 System.out.println(solution.getChromosome());
066 System.out.format("W: %f U: %f\n", algorithm.getWeightOf(solution), algorithm.getUtilityOf(solution) );
067 }
068
069 public double getCapacity() {
070 return this.algorithm.getCapacity();
071 }
072
073 public void setCapacity(double c) {
074 this.algorithm.setCapacity(c);
075 }
076
077 public double[] getUtilities() {
078 return utilities;
079 }
080
081 public double[] getWeights() {
082 return weights;
083 }
084
085 public static KnapsackProblem build(int n) {
086
087 Random r = Random.getInstance();
088
089 double[] utilities = new double[n];
090 for( int i = 0; i < n; ++i ) {
091 utilities[i] = r.nextInt(10);
092 }
093
094 double[] weights = new double[n];
095 for( int i = 0; i < n; ++i ) {
096 weights[i] = r.nextInt(10);
097 }
098
099 return new KnapsackProblem(utilities, weights);
100 }
101
102 public static void main(String[] args) {
103
104 Utils.printHeader();
105 System.out.println();
106
107 System.out.println("TUTORIAL 6:");
108 System.out.println("The Knapsack Problem.");
109 System.out.println();
110
111 KnapsackProblem p1 = new KnapsackProblem(UTILITIES, WEIGHTS);
112
113 System.out.println("Case 1: 10 elements, capacity 15");
114 System.out.println("Utilities: " + toString(p1.getUtilities()) );
115 System.out.println(" Weights: " + toString(p1.getWeights()) );
116 p1.setCapacity(15);
117 p1.run();
118 System.out.println();
119
120 System.out.println("Case 2: 10 elements, capacity 30");
121 System.out.println("Utilities: " + toString(p1.getUtilities()) );
122 System.out.println(" Weights: " + toString(p1.getWeights()) );
123 p1.setCapacity(30);
124 p1.run();
125 System.out.println();
126
127 KnapsackProblem p2 = KnapsackProblem.build(20);
128
129 System.out.println("Case 3: 20 random elements, capacity 50");
130 System.out.println("Utilities: " + toString(p2.getUtilities()) );
131 System.out.println(" Weights: " + toString(p2.getWeights()) );
132 p2.setCapacity(50);
133 p2.run();
134 System.out.println();
135 }
136
137 private static String toString(double[] values) {
138 String s = "[";
139 for(int i = 0; i < values.length; ++i ){
140 s += values[i]+ (i < values.length-1 ? " " : "]");
141 }
142 return s;
143 }
144
145 }
146
147
148
|
|
|
