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

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