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.GeneticAlgorithm;
022 import jenes.chromosome.BooleanChromosome;
023 import jenes.population.Individual;
024 import jenes.population.Population;
025 import jenes.stage.ExclusiveDispenser;
026 import jenes.stage.Parallel;
027 import jenes.stage.Sequence;
028 import jenes.stage.operator.common.OnePointCrossover;
029 import jenes.stage.operator.common.SimpleMutator;
030 import jenes.stage.operator.common.TournamentSelector;
031
032 /**
033 * Tutorial showing how to minimization and maximization sub-prolems can cohesists in
034 * the breeding structure of Jenes.
035 *
036 * This class implements a genetic algorithm for solving the Knapsack problem.
037 *
038 * @author Luigi Troiano
039 * @author Pierpaolo Lombardi
040 *
041 * @version 1.0
042 *
043 * @since 1.0
044 */
045 public class KnapsackGA extends GeneticAlgorithm<BooleanChromosome>{
046
047 private double capacity;
048 private double[] weights;
049 private double[] utilities;
050
051 public KnapsackGA( int popsize, int generations, double[] utilities, double[] weights) {
052 super( new Population<BooleanChromosome>(new Individual<BooleanChromosome>(new BooleanChromosome(utilities.length)), popsize), generations);
053
054 this.utilities = utilities;
055 this.weights = weights;
056
057 Parallel<BooleanChromosome> parallel =
058 new Parallel<BooleanChromosome>(new ExclusiveDispenser<BooleanChromosome>(2){
059
060 @Override
061 public int distribute(Individual<BooleanChromosome> ind) {
062 return ind.isLegal() ? 0 :1;
063 }
064
065 });
066
067 Sequence<BooleanChromosome> seq_legal = new Sequence<BooleanChromosome>();
068 seq_legal.appendStage(new TournamentSelector<BooleanChromosome>(2));
069 seq_legal.appendStage(new OnePointCrossover<BooleanChromosome>(0.8));
070 seq_legal.appendStage(new SimpleMutator<BooleanChromosome>(0.02));
071
072 Sequence<BooleanChromosome> seq_illegal = new Sequence<BooleanChromosome>();
073 seq_illegal.appendStage(new TournamentSelector<BooleanChromosome>(2));
074 seq_illegal.appendStage(new OnePointCrossover<BooleanChromosome>(0.8));
075 seq_illegal.appendStage(new SimpleMutator<BooleanChromosome>(0.2));
076
077 parallel.add(seq_legal);
078 parallel.add(seq_illegal);
079
080 this.addStage(parallel);
081
082 seq_legal.setBiggerIsBetter(true);
083 seq_illegal.setBiggerIsBetter(false);
084 }
085
086 public double getCapacity() {
087 return capacity;
088 }
089
090
091 public void setCapacity(double capacity) {
092 this.capacity = capacity;
093 }
094
095 public double getUtilityOf(Individual<BooleanChromosome> individual) {
096 BooleanChromosome chrom = individual.getChromosome();
097 double utility = 0.0;
098 int size = chrom.length();
099 for(int i = 0; i < size; ++i){
100 utility += chrom.getValue(i) ? this.utilities[i] : 0.0;
101 }
102 return utility;
103 }
104
105 public double getWeightOf(Individual<BooleanChromosome> individual) {
106 BooleanChromosome chrom = individual.getChromosome();
107 double weight=0.0;
108 int size = chrom.length();
109 for(int i = 0; i < size; ++i){
110 weight += chrom.getValue(i) ? this.weights[i] : 0.0;
111 }
112 return weight;
113 }
114
115 @Override
116 public void evaluateIndividual(Individual<BooleanChromosome> individual) {
117 double utility = getUtilityOf(individual);
118 double weight = getWeightOf(individual);
119 individual.setScore(utility);
120 individual.setLegal(weight <= this.capacity);
121 }
122
123
124 }
|
|
|
