Complete Guide > Algorithm

The evolutionary algorithm

There are a number of ways an evolutionary algorithm may be organised. It is difficult to say that one way is better or more right than another way, but here we outline the exact evolutionary algorithm EpochX uses. The flow diagram below gives a good idea about the order of events in the algorithm. Each evolutionary run with EpochX uses this algorithm, regardless of which program representation is being used.

A run starts with the initialisation of a new population with all the programs of the population evaluated afterwards. Execution then moves into the generational loop. Each generation starts with elitism being performed, where the best programs are put into the next population. The rest of the population is filled by the result of genetic operators. A breeding pool is selected from the population, then we enter a loop which continues until the next population is full. Within this loop a genetic operator is randomly chosen and performed, with the result of the genetic operation being inserted into the next population. Once the next population is full, all its programs undergo fitness evaluation. If a program has reached the designated termination fitness then the run terminates, otherwise the next generation starts.

Of course, the exact way in which each step happens or whether it happens at all, is changeable

In code

This section will detail how the above algorithm flow is achieved by which components in the EpochX code. The whole algorithm is encapsulated within the RunManager class, which performs executions of the algorithm by making use of the components mentioned below.

  1. Initialisation - is controlled by the InitialisationManager, which retrieves an Initialiser from the model and requests an initial population from it. This initialiser must return a list of programs, typically it would find out how many to initialise and return from the model's getPopSize() method.
  2. Elitism - is performed by the ElitismManager, which is passed the population returned from initialisation. The number of elites is obtained from the model's getNoElites() method, and a list containing that many programs are returned from the elitism step. The programs are selected by being those with the smallest fitness values. If there are multiple programs of equal best fitness, then the choice between them will be arbitrary. The number of elites requested may be zero, which effectively disables elitism.
  3. Pool Selection - is handled by the PoolSelectionManager, with the actual task of selecting the pool performed by the PoolSelector retrieved from the model. The size of the breeding pool to be selected is typically obtained from the model's getPoolSize() method. Pool selection can be disabled by using a pool size of -1, in which case the population itself is used as the breeding pool.
  4. Genetic Operators - these are repeated until the next population is full, randomly selecting which operator with probability according to the values returned by the model's getCrossoverProbability() and getMutationProbability() methods. Reproduction takes the remaining probability so they sum up to 1.0.
    • Crossover - the CrossoverManager takes responsibility for selecting two programs using the ProgramSelector obtained from the model's getProgramSelector() method. Then it applies the Crossover implementation that is return by the model's getCrossover() method to the programs. The result of the crossover is a List of any number of programs which are inserted into the next population.
    • Mutation - the MutationManager takes responsibility for selecting one program using the ProgramSelector obtained from the model's getProgramSelector() method, which it passes to the Mutation implementation returned by the model's getMutation() method. The result of the mutation is a program which is inserted into the next population.
    • Reproduction - the ReproductionManager uses the model's ProgramSelector to select one program, which is inserted directly into the next population without manipulation.
  5. Fitness Evaluation - there is currently not a well defined component that manages fitness evaluation, rather this is handled internally in the RunManager. This will change in later releases to make it more easily extendable. If any program achieves a fitness equal or lower than the termination fitness specified by the model's getTerminationFitness() method, then the run is considered successful and terminates. Otherwise execution will continue until a later generation when the termination fitness is achieved or the number of generations specified in the model's getNoGenerations() method is reached.

Next: Life cycle listeners
Previous: Models