Tutorials‎ > ‎

Tutorial 2: Structuring an advanced genetic algorithm

In our second tutorial we show how to create a parallel stage and put it into the algorithm sequence, how to distribute and merge parallel strategies, how to set an user-defined termination condition and how to use the listeners to catch algorithm events. The objective in this tutorial problem is to find the nearest integer array (representable with a specified number of decimal ciphers) to a target one with each number within the range [0,49].

Package:
jenes.tutorial.problem2

Files:
PatternProblem.java
SimpleDispencer.java
PatternGA.java.


1. Choose a problem suitable chromosome and create the initial population

An IntegerChromosome is a natural representation of integer array; each gene value will be constrained in the range [0,49] to respect the range constraint problem.

061         IntegerChromosome chrom = new IntegerChromosome(CHROMOSOME_LENGTH,0,MAX_INT);
062         Individual<IntegerChromosome> ind = new Individual<IntegerChromosome>(chrom);

where MAX_INT = 49.


2. Set-up the genetic algorithm

Similarly to the first tutorial, we extend the GeneticAlgorithm class to obtain a genetic algorithm for solving this problem. The fitness of each individual is the absolute error between its chromosome and the target chromosome. Therefore, the best individual is the one with the smallest absolute error.

The evaluate method implementation is showed below.

58     @Override
59     protected void evaluateIndividual(Individual<IntegerChromosome> individual) {
60         IntegerChromosome chrom = individual.getChromosome();
61         int diff = 0;
62         int length=chrom.length();
63         for(int i=0;i<length;i++){
64             diff += Math.abs(chrom.getValue(i)-this.target[i]);
65         }
66         individual.setScore(diff);
67     }


3. Choose the operators to be used by genetic algorithm and add them as stages in the ga

Let's suppose we need two different crossover operators (one point with probability 0.8 and two points with probability 0.5) to apply them on two separated population subsets. In Jenes we can do this through the use of the Parallel class. Therefore we arrange the two crossover operators as two parallel branches of the main pipeline.

The dispenser distributes the population between the branches of the parallel stage and merges the output of each branch in the output population of the parallel. In Jenes there are two kinds of dispencers: the general dispencer and the exclusive dispencer. The general dispencer allows, during the operation of distribution, to add an individual in more branches (copies of the same individual are needed to avoid overlapping of references between branch subpopolations). The exclusive dispencer doesn't allow it: each individual can be added at only one branch (it is not necessary to add a copy of it). We choose to use an exclusive dispencer. The implementation is showed below.

40 public class SimpleDispenser<T extends Chromosome> extends ExclusiveDispenser<T> {
41    
42     private int count;
43    
44     public SimpleDispenser(int span) {
45         super(span);
46     }
47    
48     public void preDistribute(Population<T> population){
49         this.count = 0;
50     }
51    
52     @Override
53     public int distribute(Individual<T> ind) {
54         return count++ % span;
55     }
56    
57 }

This basic implementation of an exclusive dispencer uses a simple distribution policy. It puts the individuals in even positions in the first branch and the individuals in the odd positions in the others branch. The preDistribute method is useful to reset the dispencer state. The distribute method returns the index of the branch where to put the specified individual. We should not worry about the merging of the output of the braches because it is done by the ExclusiveDispencer class. The following code shows how to create a parallel stage and insert it into the pipe.

068         AbstractStage<IntegerChromosome> selection = new TournamentSelector<IntegerChromosome>(2);
069        
070         Parallel<IntegerChromosome> parallel = new Parallel<IntegerChromosome>(new SimpleDispenser<IntegerChromosome>(2));
071        
072         AbstractStage<IntegerChromosome> crossover1p = new OnePointCrossover<IntegerChromosome>(0.8);
073         parallel.add(crossover1p);
074        
075         AbstractStage<IntegerChromosome> crossover2p = new TwoPointsCrossover<IntegerChromosome>(0.5);
076         parallel.add(crossover2p);
077        
078         AbstractStage<IntegerChromosome> mutation = new SimpleMutator<IntegerChromosome>(0.02);
079        
080         algorithm.addStage(selection);
081         algorithm.addStage(parallel);
082         algorithm.addStage(mutation);

Customize the genetic algorithm

As said before the goal of our genetic algorithm is to minimize the absolute error of the generated individuals, in order to obtain an integer array as soon as possible near to the target one.

In Jenes the genetic algorithm evolution runs until it reaches the specified generation limit or until a termination criterion is met. To specify the termination criterion our genetic algorithm has to override the "end" method. By default this method has an empty body so it has no effect on the algorithm evolution. In our example the evolution stops when the lowest fitness value is less than a value (called precision) specified by the user.

69     @Override
70     protected boolean end(){
71         jenes.population.Population.Statistics stat = this.getCurrentPopulation().getStatistics();
72         return stat.getLegalLowestScore() <= this.precision;
73     }

The GeneticAlgorithm class implements the Observer pattern to notify its listeners the occurrence of a particular event. In Jenes there are two kinds of event listeners: the generation event listener (invoked when a generation ends ) and the algorithm event listener (invoked when an algorithm event occours, e.g. the start, the end and at the init of the algorithm).

In this tutorial we choose to use a generation event listener in order to print some informations at the end of each generation. The listener code is showed below

110     public void onGeneration(GeneticAlgorithm ga, long time) {
111         Statistics stat = ga.getCurrentPopulation().getStatistics();
112         System.out.println("Current generation: " + ga.getGeneration());
113         System.out.println("\tBest score: " + stat.getLegalLowestScore());
114         System.out.println("\tAvg score: " + stat.getLegalScoreAvg());
115     }

The code to add a generation event listener to the GeneticAlgorithm class is:

084         algorithm.addGenerationEventListener(this);

The following code summarises the main steps to setting up the genetic algorithm.

061         IntegerChromosome chrom = new IntegerChromosome(CHROMOSOME_LENGTH,0,MAX_INT);
062         Individual<IntegerChromosome> ind = new Individual<IntegerChromosome>(chrom);
063         Population<IntegerChromosome> pop = new Population<IntegerChromosome>(ind, POPULATION_SIZE);
064        
065         algorithm = new PatternGA(pop, GENERATION_LIMIT);
066         algorithm.setElitism(5);
067        
068         AbstractStage<IntegerChromosome> selection = new TournamentSelector<IntegerChromosome>(2);
069        
070         Parallel<IntegerChromosome> parallel = new Parallel<IntegerChromosome>(new SimpleDispenser<IntegerChromosome>(2));
071        
072         AbstractStage<IntegerChromosome> crossover1p = new OnePointCrossover<IntegerChromosome>(0.8);
073         parallel.add(crossover1p);
074        
075         AbstractStage<IntegerChromosome> crossover2p = new TwoPointsCrossover<IntegerChromosome>(0.5);
076         parallel.add(crossover2p);
077        
078         AbstractStage<IntegerChromosome> mutation = new SimpleMutator<IntegerChromosome>(0.02);
079        
080         algorithm.addStage(selection);
081         algorithm.addStage(parallel);
082         algorithm.addStage(mutation);
083         algorithm.setBiggerIsBetter(false);
084         algorithm.addGenerationEventListener(this);