Tutorials‎ > ‎

Anatomy of a genetic algorithm in Jenes

Programming in Jenes is easy, intuitive and funny. In this section, we will provide few concepts you need to keep in mind in outlining a solution in Jenes. These concepts will help you to move effectively among the classes provided in Jenes API. You will be surprised how quickly a genetic algorithm can be defined, implemented and tested.

Chromosomes, Individuals and Populations.

The first thing to have in mind is the difference between chromosomes, individuals and populations.

Solutions in a search space are represented by individuals. They are made of a chromosome and fitness value:  INDIVIDUAL = CHROMOSOME + FITNESS.

Chromosomes are solution codings. In Jenes, they are regarded as an array of genes. Here is a list of the chromosome classes provided by Jenes.
  • BitwiseChromosome: models a chromosome of bits. Its genoma contains values coded accorded to the specified bit coding.
  • BooleanChromosome: models a chromosome of boolean values. Each allele gene can be true or false.
  • DoubleChromosome: models a chromosome of double values. Each value is in the range [lowerBound,upperBound]. These bounds are specified at the instantiation time.
  • IntegerChromosome: models a chromosome of integer values. Each value is in the range [lowerBound,upperBound]. These bounds are specified at the instantiation time.
  • ObjectChromosome: represents a chromosome with genes containing an object allele value.
  • PermutationChromosome: provides a chromosome able to model permutations. An array of integer values is its genoma. The most important property is that the genoma does not contain duplicated values.
All chromosome classes are implementation of Chromosome interface. In general, chromosomes have fixed number of genes, but their lenght can vary during the algorithm execution in order to implement a lenght variable solution coding. A Population is simply a collection of individuals (i.e. solutions).

Individuals are all instances of parametric class Individual<T extends Chromosome>, in order to have a stronger control on types. An individual can be legal or not legal. It's possible to set the lagality of an individual by invoking the setLegal(boolen) method on its instance. In default af a user specification each individual is set as legal.

During the algorithm evolution, past populations are buffered in the algorithm's history. At each evolutionary iteration, the oldest population and its individuals are reused. Past populations, instead of being deallocated, are mantained in memory and reused. This technique avoids the allocation in memory of the new populations and limits the use of the garbage collector.

As said, a genetic algorithm processes a population of individuals. At each generation there are input and output populations. It is important to consider that the output population is pre-inizialized with "recycled" individuals taken from history (for performance reasons). So Jenes generally does not allocate new individuals.

Algorithm Structure

Jenes provides a flexible structure for evolving a population of individuals. In general a genetic algorithm is structured as depicted in Fig. 1.

Basically a genetic algorithm performs the following loop:
  1. Randomly create an initial population
  2. repeat
  3.       Valuate the fitness of each individual
  4.       Select one or more individuals from the population with a probability based on fitness to partecipate in genetic operations
  5.       Create new  individuals by applying genetic operations with specified probabilities
  6. until an acceptable solution is found or some other stopping condition is met
  7. return the best-so-far individual
In Jenes a genetic algorithm can be implemented by subclassing GeneticAlgorithm and implementing the method evaluateIndividual(Individual). This method is used to evaluate the fitness of one single individual. The implementation of this method is specifically related to the problem to solve.

In Jenes the genetic algorithm body is a "pipe"
of stages. Stages are executed sequentially in the order they are added to the sequence. Each stage receives an input population (produced as output by the previous stage) and produces an output population. Which stages and in which order to consider is left to the algorithm needs.

The reference to current and in-process population  can be respectively obtained by the methods getCurrentPopulation() and getNextPopulation().

Jenes also allows to define parallel stages. A parallel stage is formed by different branches, each branch is a stage which receives a subpopulation according to the population dispenser used. A dispenser distributes a population between the branches of a parallel stage and merges the output of each branch in the output population of the parallel.
The break point and the genetic operators represent the simplest general pipe stages.

A BreakPoint stage notifies its listeners when its process method is invocated.It doesn't alterate the input population.

Genetic operators used in genetic algorithms are analogous to these which occur in the natural world:
  • Selection: which gives preference to better individuals, allowing them to pass on the next generation.
  • Crossover: which represents mating between individuals.
  • Mutation: which introduces random modifications.
Jenes provides the implementation of the most common genetic operators:
  • TournamentSelector: choses at random a number of individuals from the population. These are compared each other and the best of them is chosen to be a parent. Tournament selector does ensure that even average-quality individuals have some chance of having children. In Jenes you need to specify the number of tournament attempts.
  • RouletteWheelSelector: picks a particular population member to be a parent with a probability equals to its fitness divided by the total fitness of the population.
  • OnePointCrossover: chooses randomly one crossover point from parent chromosomes and creates a new offspring. One point crossover can look like this (where "|" is the crossover point):

    Chromosome 1 11101 | 001000
    Chromosome 2 00001 | 010101
    Offspring 1 11101 | 010101
    Offspring 2 00001 | 001000

  • TwoPointsCrossover: chooses randomly two crossover point from parent chromosomes and creates a new offspring. Two point crossover can look like this:

    Chromosome 1 11 | 10100 | 1000
    Chromosome 2 00 | 00101 | 0101
    Offspring 1 11 | 00101 | 1000
    Offspring 2 00 | 10100 | 0101

    In Jenes you need to specify the probability by which crossover operator will be used. Generally for a crossover operator the probability is set to 80%

  • Simple Mutator: choses randomly a mutation point and randomizes its gene. Mutation operator also needs a probability number which specifies its use.
    Generally for a mutation operator the probability is set to 20%.

Jenes provides also a simple interface to GeneticAlgorithm. It is SimpleGA class which implements a three stages genetic algorithm made of one Selector, one Crossover and one Mutator in sequence.
It offers a simple way to implement your own genetic algorithm allowing you to neglect the problems related to the building of the stages.

                        |----------|      |-----------|      |---------|   
Current Generation ---> | Selector | ---> | Crossover | ---> | Mutator | ---> Next Generation
|-----------|      |---------|

The class provides a set of constructors by which to instantiate a SimpleGA algorithm. Constructors allows to decide which selection method (i.e. Tournament or Roulette Wheel) or crossover method (i.e. One Point or Two Points) to adopt. Also crossover and mutation probability can be specified at constraction time. SimpleGA is GeneticAlgorithm subclass and it's abstract since the evaluation of individuals is problem dependent. It is possible to subclass SimpleGA in different ways.

For instance

        SimpleGA<BooleanChromosome> sga = new SimpleGA<BooleanChromosome>
            (pop, GENERATION_LIMIT) {
            protected void evaluateIndividual(Individual<BooleanChromosome> individual) {
            // Make your evaluation here ... 

provides an anonimous inner subclass of SimpleGA. Moreover, it's possible to use all inheritated methods and properties from the super class.

Jenes includes a support for elitism, that is best individuals at each generation are assured to be at the next generation. The number of elite individuals is set by the method setElitism(int).
These individuals are substituted to some individuals to the processed population according to the following strategies:
  • Random Elitism Strategy: next population individuals are randomly selected and substituted by elite.
  • Worst Elitism Strategy: next population worst individuals are substituted by elite.
You can set your preferred elitism strategy as follows:

                sga.setElitismStrategy(ElitismStrategy.RANDOM); or sga.setElitismStrategy(ElitismStrategy.WORST);

The first strategy is more efficient as it does not require to order the population. The drawback is that individuals with a good fitness could be substituted by elite. The second strategy is slower, but assures that only worst individuals are substituted.

Jenes uses the class MersenneTwisterRandom for the generation of pseudo-random numbers and values. This an optimized class which provides for fast generation of very high-quality random numbers. For this reason it is used instead of  java.util.Random. The generation of pseudorandom number is very useful during all the phases of the algorithm evolution (such as the initialization of the population, the use of selection operators, the determination of crossover and mutation points, and so on).

Events, Listeners and Statistics

The genetic algorithm execution is invoked by the method evolve(). The algorithm execution passes through the following events:
  • Start: the algorithm evolution starts.
  • Init: internal structures, such as the population given as input at generation 0 and history, are initialized.
  • Generation: a generation has been just performed.
  • Stop: the algorithm terminates its executions.
Each of these events can be captured by AlgorithmEventListeners and GenerationEventListeners. They can also be caputured by the GeneticAlgorithm subclass, by overriding the methods onStart(long), onInit(long), onGeneration(long), and onStop(long). Capturing events is useful to collect statistics and to perform analyses.

AlgorithmEventListeners provides the interface for capturing events at algorithm level. This interface should be implemented by all classes interested in beign notified by algorithm events (Start, Init, Stop). An AlgorithmEventListener can be registered to the algorithm by the method GeneticAlgorithm.addAlgorithmEventListener(AlgorithmEventListener). The listener can be removed by invoking the method GeneticAlgorithm.removeAlgorithmEventListener(AlgorithmEventListener).

is a listener of the genetic algorithm generation event. Such listener is notified after a generation step is executed. A GenerationEventListener can be registered to the algorithm by the method GeneticAlgorithm.addGenerationEventListener(GenerationEventListener). The listener can be removed by invoking the method GeneticAlgorithm.removeGenerationEventListener(GenerationEventListener).

During the genetic algorithm evolution, Jenes collects statistics about:
  1. Algorithm execution: The GeneticAlgorithm.Statistics class is responsible for storing statistics about the time spent by the whole evolutionary process and the number of  generations created. You can invoke the GeneticAlgorithm.getStatistics() method to get the algorithm statistics.
  2. Population: The Population.Statistics class is responsible for storing statistics about a population. As each population can contains legal and illegal individuals, it holds the individuals with the higher and lower fitness, the average and deviation values both regard legal individuals and illegal ones. You can invoke the Population.getStatistics() method to obtain its statistics.
  3. Operators: The Selection.Statistics, Crossover.Statistics and Mutator.Statistics classes are responsible for storing statistics about the used operators and the time spent to execute them. They respectively hold the number of crossover, selection and mutation performed. You can invoke the Operator.getStatistics() method on an instance of the Operator class to obtain its statistics.