Let's start with a simple problem. Given a search space made of boolean variables, we aim at finding a solution made entirely of true values (or false values). This problem is faced by designing a genetic algorithm working on boolean chromosomes. The fitness function is computed by counting the number of true values within the chromosome. So in order to find the solution with all true values we can maximize the fitness function, whilst we minimize the fitness function in order to find a solution made of all false values.

This tutorial will give the opportunity of understanding how a genetic algorithm is structured and taylored to an optimization problem. Moreover, we will see how listeners can be used to capture the algorithms events.

Package:
jenes.tutorials.problem1

Files:
BooleanProblem.java

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

Choosing a suitable chromosome representation is the most important task to do before running a genetic algorithm. Which representation to use depends on the structure of problem solutions.  In our case, solutions are made of boolean arrays. Thus, BooleanChromosome looks to be the approppriate choice. Chromosomes represent the key component of solutions (i.e. Individuals). For building the initial population we need a prototype of solutions (sample), as shown by the following code.

060         Individual<BooleanChromosome> sample = new Individual<BooleanChromosome> (new BooleanChromosome(CHROMOSOME_LENGTH));
061         Population<BooleanChromosome> pop = new Population<BooleanChromosome>(sample, POPULATION_SIZE);


where

045     private static int POPULATION_SIZE=50;
046     private static int CHROMOSOME_LENGTH=100;
047     private static int GENERATION_LIMIT=1000;



2. Set-up the genetic algorithm.

Any algorithm in Jenes 2.0 is based on GeneticAlgorithm, for wich it must define a fitness function that is used to evaluate individuals. To define a fitness function in Jenes 2.0 we just need to subclass Fitness, an abstract class, implementing the method evaluate(Individual).

Any algorithm in jenes is based on GeneticAlgorithm, an abstract class whose only abstract method is evaluateIndividual that is problem dependant. The code to subclass GeneticAlgorithm and to evaluate an individual in our problem is shown below.

For instance it could be easy to define a fitness function by using an anonimous inner class as follow

063         Fitness<BooleanChromosome> fit = new Fitness<BooleanChromosome>(false) {
064 
065             @Override
066             public void evaluate(Individual<BooleanChromosome> individual) {
067                 BooleanChromosome chrom = individual.getChromosome();
068                 int count = 0;
069                 int length=chrom.length();
070                 for(int i=0;i<length;i++)
071                     if(chrom.getValue(i))
072                         count++;
073                 
074                 individual.setScore(count);
075             }
076             
077         };


and then pass this object as first parameter to GeneticAlgorithm (or any predefined subclass)

079         GeneticAlgorithm<BooleanChromosome> ga = new GeneticAlgorithm<BooleanChromosome>
080                 (fit, pop, GENERATION_LIMIT);

The Fitness class provides two different constructors in order to define the number of objectives to consider in evaluating individuals, and for each objective the flag indicating if it is a maximize function or not. In the code listed above, we create a fitness for a single objective problem (only one flag as parameters).

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

After the genetic algorithm is defined, we need to specify the sequence of operators population will pass through. The simplest scheme contains only three operators in sequence: one selector, one crossover and one mutator. However it is possible to create a more complex pipe having paralleles and sequences. For the purpose of this tutorial we will adopt the following simple structure (see APIs form more details on operators adopted):

082   AbstractStage<BooleanChromosome> selection = new TournamentSelector<BooleanChromosome>(3);
083   AbstractStage<BooleanChromosome> crossover = new OnePointCrossover<BooleanChromosome>(0.8);
084   AbstractStage<BooleanChromosome> mutation = new SimpleMutator<BooleanChromosome>(0.02);
085   ga.addStage(selection);
086   ga.addStage(crossover);
087   ga.addStage(mutation);



4. Set the algorithm parameters and run the evolution.

It is possible to customize the genetic algorithm setting the elitism value and the optimization goal before to run the evolution. The elitism is the number of best individuals to hold in the next generation (1 in our case).

089         ga.setElitism(1);

Finally, we can make the algorithm running.

091         ga.evolve();


5. Obtaining the result of evolution.

Jenes provides statistics for both the algorithm and the population. The first refer to statistics concerning the algorithm run, namely the times of initialization, starting, evolution, and generations. The second to the distribution of solutions and related fitness values, such as the individuals ordered by decreasing fitness function, the mean max, and min of fitness values. They can be retrieved at any moment. We will use them when the algorithm has finished.

093         Population.Statistics stats = ga.getCurrentPopulation().getStatistics();
094         GeneticAlgorithm.Statistics algostats = ga.getStatistics();
095         
096         System.out.println("Objective: " + (fit.getBiggerIsBetter()[0] ? "Max! (All true)" : "Min! (None true)"));
097         System.out.println();
098         
099         Group legals = stats.getGroup(Population.LEGALS);
100         
101         Individual solution = legals.get(0);
102                 
103         System.out.println("Solution: ");
104         System.out.println( solution );
105         System.out.format("found in %d ms.\n", algostats.getExecutionTime() );
106         System.out.println();
107         
108         Utils.printStatistics(stats);