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

065         IntegerChromosome chrom = new IntegerChromosome(CHROMOSOME_LENGTH,0,MAX_INT);
066         Individual<IntegerChromosome> ind = new Individual<IntegerChromosome>(chrom);

where MAX_INT is defined as

059     private static int MAX_INT = 49;




2. Set-up the genetic algorithm

In this tutorial we create a subclass of GeneticAlogithm named PatternGA in wich we customize the termination condition of the algorithm ovverriding the method end() as better exposed in paragraph 4.    


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 fitness function is coded in PatternFitness class defined as inner class in PatternGA. In this case we provide a definition for a single-objective problem giving to programmer the possibility to configure the expected solution schema and the minimal precision to reach to stop the search.


The evaluate method is showed below:

67         @Override
68         public void evaluate(Individual<IntegerChromosome> individual) {
69             IntegerChromosome chrom = individual.getChromosome();
70             int diff = 0;
71             int length = chrom.length();
72             for (int i = 0; i < length; i++) {
73                 diff += Math.abs(chrom.getValue(i) - target[i]);
74             }
75             individual.setScore(diff);
76         }




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

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

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.

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




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

52     @Override
53     protected boolean end() {
54         jenes.population.Population.Statistics stat = this.getCurrentPopulation(). getStatistics();
55         return stat.getGroup(Population.LEGALS).getMin()[0] <= this.fitness.precision;
56     }

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

113     public void onGeneration(GeneticAlgorithm ga, long time) {
114         Statistics stat = ga.getCurrentPopulation().getStatistics();
115         Group legals = stat.getGroup(Population.LEGALS);
116         System.out.println("Current generation: " + ga.getGeneration());
117         System.out.println("\tBest score: " + legals.getMin()[0]);
118         System.out.println("\tAvg score : " + legals.getMean()[0]);
119     }

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

087         algorithm.addGenerationEventListener(this);

The following code summarises the main steps to setting up the genetic algorithm.65         IntegerChromosome chrom = new IntegerChromosome(CHROMOSOME_LENGTH,0,MAX_INT);
066         Individual<IntegerChromosome> ind = new Individual<IntegerChromosome>(chrom);
067         Population<IntegerChromosome> pop = new Population<IntegerChromosome>(ind,  POPULATION_SIZE);
068         
069         algorithm = new PatternGA(pop, GENERATION_LIMIT);
070         algorithm.setElitism(5);
071         
072         AbstractStage<IntegerChromosome> selection =  new TournamentSelector<IntegerChromosome>(2);
073         
074         Parallel<IntegerChromosome> parallel =  new Parallel<IntegerChromosome>(new SimpleDispenser<IntegerChromosome>(2));
075         
076         AbstractStage<IntegerChromosome> crossover1p =  new OnePointCrossover<IntegerChromosome>(0.8);
077         parallel.add(crossover1p);
078         
079         AbstractStage<IntegerChromosome> crossover2p =  new TwoPointsCrossover<IntegerChromosome>(0.5);
080         parallel.add(crossover2p);
081         
082         AbstractStage<IntegerChromosome> mutation = new SimpleMutator<IntegerChromosome>(0.02);

083         
084         algorithm.addStage(selection);
085         algorithm.addStage(parallel);
086         algorithm.addStage(mutation);
087         algorithm.addGenerationEventListener(this);