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