Jenes offers the possibility to use local genetic algorithm goals. The global goal is that used by
GeneticAlgorithm during the evolution of the population in its main sequence of stages. Instead, local goal is that used by the single stage (e.g. A sequence contained in a parallel branch, etc..). This tutorials shows how to solve the knapsack problem defining two different parallel sequences with different inner goals. The aim of the knapsack problem is to maximize the total utility of the items within the bag without exceeding the maximum capacity of the bag. We have n items each one with has a footprint and an utility value.
Package:jenes.tutorial.problem6
Files:
KnapsackProblem.javaKnapsackGA.java
1. Choose a problem suitable chromosome and create the initial population
A candidate solution is a set of items with a weight and a utility. The solutions are coded using a boolean chromosome. The boolean values tells if an item is present or not inside the bag. For example if the i-th gene is true, then the i-th item is in the bag. A chromosome with all the genes having a false value represents an empty bag, while a chromosome with all the genes having a true value represents a bag with all the possible items.
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);
2. Set-up the genetic algorithm
We implement the
KnapsackGA class by subclassing
GeneticAlgorithm and implementing the evaluation method.
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 }
The fitness of each solution is equal to the sum of the utilities of the items it contains. If the total weight exceeds the capacity of the bag, then the individual is set as illegal.
3. Choose the operators to be used by genetic algorithm and add them as stages in the ga
We decide to process differently legal and illegal individuals. Therefore we create a sequence, called
seq_legal, to process legal individual and a sequence, called
seq_illegal, to process illegal individuals. These sequences have the same body ( tournament selector, one point crossover and simple mutator ), but different goals. Infact, the goal of
seq_legal is to maximize the fitness of the legal individuals, while that of
seq_illegal is to minimize the fitness of the illegal individuals in order to remove excess items and make the individual legal.
We evolve in parallel legal and illegal individuals and at each generation we pass the legal solutions to
seq_legal and the illegal solutions to
seq_illegal through the use of an exclusive dispenser
.
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);
4. Customize the genetic algorithm
To start the evolution KnapsackGA needs the utilities and the weights arrays (both with the same length) and the maximum bag capacity. The code is showed below.
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 }
