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.GeneticAlgorithm;
037 import jenes.chromosome.BooleanChromosome;
038 import jenes.population.Individual;
039 import jenes.population.Population;
040 import jenes.stage.ExclusiveDispenser;
041 import jenes.stage.Parallel;
042 import jenes.stage.Sequence;
043 import jenes.stage.operator.common.OnePointCrossover;
044 import jenes.stage.operator.common.SimpleMutator;
045 import jenes.stage.operator.common.TournamentSelector;
046
047 public class KnapsackGA extends GeneticAlgorithm<BooleanChromosome>{
048
049 private double capacity;
050 private double[] weights;
051 private double[] utilities;
052
053 public KnapsackGA( int popsize, int generations, double[] utilities, double[] weights) {
054 super( new Population<BooleanChromosome>(new Individual<BooleanChromosome>(new BooleanChromosome(utilities.length)), popsize), generations);
055
056 this.utilities = utilities;
057 this.weights = weights;
058
059 Parallel<BooleanChromosome> parallel =
060 new Parallel<BooleanChromosome>(new ExclusiveDispenser<BooleanChromosome>(2){
061
062 @Override
063 public int distribute(Individual<BooleanChromosome> ind) {
064 return ind.isLegal() ? 0 :1;
065 }
066
067 });
068
069 Sequence<BooleanChromosome> seq_legal = new Sequence<BooleanChromosome>();
070 seq_legal.appendStage(new TournamentSelector<BooleanChromosome>(2));
071 seq_legal.appendStage(new OnePointCrossover<BooleanChromosome>(0.8));
072 seq_legal.appendStage(new SimpleMutator<BooleanChromosome>(0.02));
073
074 Sequence<BooleanChromosome> seq_illegal = new Sequence<BooleanChromosome>();
075 seq_illegal.appendStage(new TournamentSelector<BooleanChromosome>(2));
076 seq_illegal.appendStage(new OnePointCrossover<BooleanChromosome>(0.8));
077 seq_illegal.appendStage(new SimpleMutator<BooleanChromosome>(0.02));
078
079 parallel.add(seq_legal);
080 parallel.add(seq_illegal);
081
082 this.addStage(parallel);
083
084 seq_legal.setBiggerIsBetter(true);
085 seq_illegal.setBiggerIsBetter(false);
086 }
087
088 public double getCapacity() {
089 return capacity;
090 }
091
092
093 public void setCapacity(double capacity) {
094 this.capacity = capacity;
095 }
096
097 public double getUtilityOf(Individual<BooleanChromosome> individual) {
098 BooleanChromosome chrom = individual.getChromosome();
099 double utility = 0.0;
100 int size = chrom.length();
101 for(int i = 0; i < size; ++i){
102 utility += chrom.getValue(i) ? this.utilities[i] : 0.0;
103 }
104 return utility;
105 }
106
107 public double getWeightOf(Individual<BooleanChromosome> individual) {
108 BooleanChromosome chrom = individual.getChromosome();
109 double weight=0.0;
110 int size = chrom.length();
111 for(int i = 0; i < size; ++i){
112 weight += chrom.getValue(i) ? this.weights[i] : 0.0;
113 }
114 return weight;
115 }
116
117 @Override
118 protected void evaluateIndividual(Individual<BooleanChromosome> individual) {
119 double utility = getUtilityOf(individual);
120 double weight = getWeightOf(individual);
121 individual.setScore(utility);
122 individual.setLegal(weight <= this.capacity);
123 }
124
125
126 }
127
128
|
|
|