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.tutorials.problem6

Files:
KnapsackProblem.java
KnapsackGA.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.

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  

2. Set-up the genetic algorithm

We implement the KnapsackGA class by subclassing GeneticAlgorithm and implementing the fitness function as reported below.

053         @Override
054         public void evaluate(Individual<BooleanChromosome> individual) {
055             double utility = KnapsackGA.this.getUtilityOf(individual);
056             double weight = KnapsackGA.this.getWeightOf(individual);
057             individual.setScore(utility);
058             individual.setLegal(weight <= KnapsackGA.this.capacity);
059         }

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. The function coded above, use the following utility methods to evaluate the utility and weight of a particular solution.

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     }



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

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);