General: Algorithm-Based - Component-Based - Programming hints - EO documentation
Local:
Introduction  - Selection - Replacement - General Replacement - Popular evolution engines - Tournaments - Merge - Reduce - HowMany - SurviveAndDie

Evolution Engine



Evolution Engines

The term evolution engine denotes the different parts of an Evolutionary Algorithm that simulate the Darwinism:

The fittest individuals are more likely to reproduce and survive.

Darwinism takes place in two different phases of an EA, though in many popular variants, only one phase is activated.

Selection is the Darwinistic choice of parents that will be allowed to reproduce.
Replacement takes place after reproduction, and is the Darwinistic choice of those individuals that will survive, i.e. become the parents of the next generation.

Both selection and replacement will be discussed in turn, before some helper classes that are used within selection and replacement procedures are presented.


Selection

The very beginning of the generation loop is the selection phase, where some individuals from the population are chosen to become the parents, to be later modified by the variation operators and become the offspring. This is the first step of the artificial Darwinism, where the fittest individuals are allowed to reproduce.
Conceptually, there are two distinct ways to choose the lucky ones: one by one from the very same population (i.e. with replacement), which means that at the extreme the same individual can be chosen every time; or as a whole, in some sort of batch procedure. Of course, repeated selection of one individual results in a batch selection!

There are hence two basic EO classes for selection: eoSelectOne and eoSelect, with different interfaces.



eoSelectOne: The interface

The abstract class for selection of a single individual from a population is eoSelectOne, and the interface for its operator() is

const EOT & operator()(const eoPop<EOT>& _parents)

which you could have guessed from the inheritance tree for class eoSelectOne., as you see there that eoSelectOne derives from class eoUF<const eoPop<EOT>&, const EOT&>.
This means that it takes 1 population (without the right to modify it - see the const keyword in argument) and returns a const reference to an individual (again, the const keyword ensures that nothing will happen to the individual in the population - remember it returns a reference).



eoSelectOne: Instances

eoSelect: The interface

The abstract class for batch selection of a  whole set of individuals from a population is eoSelect, and the interface for its operator() is

void operator()(const eoPop<EOT>& _source, eoPop<EOT>& _dest)

which you could have guessed from the inheritance tree for class eoSelect., as you see there that eoSelect derives from class eoBF<const eoPop<EOT>&, eoPop<EOT>&, void>.
This means that it takes 2 populations, and fills the second one with individuals from the first one without modifying it (see the const keyword). This raises two questions:



eoSelect: HowMany

There are two ways an  can derive the number of individuals it has to select: either it is a fixed number, or it is some percentage of the source population size (any positive real number). In both case, this must be passed to the constructor. In most instances, however, the constructor will accept a real number (double) and a boolean indicating whether this real number should be used as an absolute integer or as a rate, thanks to the eoHowMany class.

Note: an eoSelect can select more individuals than there are in the original population. It is the job of the replacement to ensure that the population size does not grow along the generations.


eoSelectMany: Encapsulating eoSelectOne

It is clear that repeated selection of a single individual is a way to do batch selection. This is why it is possible to encapsulate an object of class eoSelectOne into an object of class eoSelect using the class eoSelectMany. Class eoSelectMany is derived from class eoSelect and takes in its constructor an eoSelectOne (plus the number of individuals it should select, according to the eoHowMany paradigm).

Note: some procedures for selecting a single individual require some pre-processing of the whole population that takes place before any selection, and will be repeated identically for every individual. The encapsulation of an  into an  allows to call such technical processing only once through the use of method setup of class . This method does nothing by default, but is mandatory



eoSelect: Other instances No other instances of eoSelect that are not encapsualtions of eoSelectOne procedures are avaiable as of today (Jan. 4 2001).


Replacement

The replacement phase takes place after the birth of all offspring through variation operators. This is the second step of the artificial Darwinism, where the fittest individuals are allowed to survive.
It can also be viewed on the algorithmic side as closing the generation loop, i.e. building the population that will be the initial population of next generation. That population will be built upon the old parents and the new-born offspring. In all algorithms that come up with EO, the population size is supposed to be constant from one generation to the next one - though nothing stops you from writing an algorithm with varying population size.



Replacement: The interface

The abstract class for replacement procedures is the functor class eoReplacement, and the interface for its operator() is

void operator()(eoPop<EOT>& _parents, eoPop<EOT>& _offspring)

which you could have guessed from the inheritance tree for class eoReplacement., as you see there that eoReplacement derives from class eoBF<eoPop<EOT>&, eoPop<EOT>&, void>.
This means that it takes 2 populations (called, for obvious anthropomorphic reasons, _parents and _offspring :-) and is free to modify both, but the resulting population should be placed in the first argument (usually called_parents) to close the loop and go to next generation.



Replacement: Instances

Replacement: Adding (weak) elitism

You can add what is called weak elitism to any replacement by encapsulating it into an eoWeakElitismReplacement object. Weak elitism ensures that the overall best fitness in the population will never decrease: if the best fitness in the new population is less than the best fitness of the parent population, then the best parent is added back to the new population, replacing the worse.

Within EO, this is very easy to add:

First, declare your replacement functor (here, generational, but it can be any replacement object):
eoGenerationalReplacement<Indi> genReplace;
Then wrap the weak elitism around it:
eoWeakElitismReplacement<Indi> replace(genReplace);
and use now replace as your replacement procedure within your algorithm.

Note: of course, adding weak elitism to an elitist replacement makes no sense - but will not harm either :-)



Replacement: Test file

The file t-eoReplacement in the test directory implements all above replacement procedures within a very simple and easy-to-monitor Dummy EO class.



General Replacement: eoReduceMergeReduce

In an attempt to unify all the well-known replacements, plus most of the less-known-though-often-used, the eoReduceMergeReduce replacement has been designed, and supersedes all of the above instances.
It allows to implement strong elistism (i.e. some parents survive, whatever their fitness and that of the offspring), as well as multiple weak elistism (the best parents are put back in the next population if they outperform the best offspring).

Basically, an eoReduceMergeReduce starts by eventually preserving the (strong) elite parents, proceeds by reducing both the parent and offspring populations, merges those populations, and eventually reduces the resulting populations (augmented with the elite parents) to the right size. Last, the weak elitism is taken care of if necessary.
The following image, taken from the graphical interface of EASEA, somehow demonstrates the different parameters of an eoReduceMergeReduce.



eoReduceMergeReduce: The  interface
Of course the interface is that of eoReplacement. Let's concentrate on the constructor.

The constructor takes 6 arguments:

  1. eoHowMany elite determines the number of parents to be treated as elite (actual behavior determined by next parameter) using the eoHowMany behavior.
  2. bool strongElitism tells whether the elite above corresponds to strong (true) or false(weak) elitism.

  3. Note: the case of no elitism is obtained by setting elite to 0
  4. eoHowMany reducedParents gives the number of parents remaining after reducing them

  5. Note: 0 means that no parent survive (except the possible elite), as in eoCommaReplacement
                -1 is used inside eoSSGAReplacements (one parent is killed to make room for the newborn)
  6. eoReduce<EOT> & reduceParents indicates how the parents will be reduced (see available instances).
  7. eoHowMany reducedOffspring gives the number of offspring remaining after reducing them

  8. Note: 0 is impossible (no evolution!!!)
  9. eoReduce<EOT> & reduceOffspring indicates how the offspring will be reduced (see available instances).
  10. eoReduce<EOT> & reduceFinal indicates how the merged reduced-parents/reduced-offspring will be reduced (see available instances).

  11. Note: the number of individuals remaining after that reduction is of course the original size of the population.
All popular evolution engines use some replacement procedure that can be viewed as an instance of an eoReduceMergeReduce.
Moreover, a parser-based input of a general  is proposed in file do/make_checkpoint.h.


Popular evolution engines

The most popular evolution engines are listed below, together with the way to use them in EO. If you don't find your particuler algorithm, please send it to us, and we might include it here! In the following, P will denote the number of individuals in the initial population.



Tournaments

Tournaments are an easy and quick way to select individuals within a population based on simple comparisons. Though usually based on fitness comparisons, they can use any comparison operator.
In EO, there are two variants of tournaments used to select one single individual, namely Deterministic Tournament and Stochastic Tournament, that are used in selection and in replacement procedures, and a global tournament-based selection of a whole bunch of individuals, the EP Tournament. Though the single-selection tournaments can be repeated to select more than one individual, and the batch tournament selection can be used to select a single individual, both uses are probably a waste of CPU time.




Merging populations

In replacement procedures, one frequently needs to merge two populations (computed form old parents and new-born offspring). Classes derived from the abstract class eoMerge are written for that purpose.



eoMerge: interface
The abstract class for merging procedures is the functor class eoMerge, and the interface for its operator() is

void operator()(const eoPop<EOT>& _parents, eoPop<EOT>& _offspring)

which you could have guessed from the inheritance tree for class eoMerge, as you see there that eoMerge derives from
class eoBF<const eoPop<EOT>&, eoPop<EOT>&, void>.
This means that it takes 2 populations and modifies the seond one by adding some individuals from the first one (which is supposed to remain constant).



eoMerge: instances
Available instances of eoMerge objects are eoPlus, that simply adds the parents to the offspring, or eoElitism, that adds only some of the (best) parents to the offspring. A special case of eoElistism is eoNoElitism, an eoMerge that does nothing.



Reducing populations

The other useful component of replacement procedures, eoReduce, kills some individuals from a given population.



eoReduce: interface
The abstract class for reducing procedures is the functor class eoReduce, and the interface for its operator() is

void operator()(eoPop<EOT>& _parents, unsigned int new_size)

which you could have guessed from the inheritance tree for class eoReduce, as you see there that eoReduce derives from
class eoBF<eoPop<EOT>&, unsigned int, void>.
An eoReduce shoud take a population and shrink it to the required size.



eoReduce: instances
Available instances of eoReduce are

eoHowMany: Choosing a number of individuals

Many classes in selection/replacement procedures will handle a number of individuals that may either be fixed or be related to some argument-population size.
Of course, it is possible to write different classes that will only differ by the way they compute the number of individuals they have to treat, as it is done for selectors with the two classes eoSelectPerc and eoSelectNumber (it could also have been possible to have some pure abstrat class and implement the computation of the number of individuals to treat in some derived classes).
However, the class eoHowMany allows one to handle in a single class three different behaviors when given a poopulatio size as argument:



eoHowMany: interface
The class interface for its operator() is

unsigned int operator()(unsigned int _pop_size)

which you could have guessed from the inheritance tree for class eoHowMany, as you see there that eoHowMany derives from
class eoUF<unsigned int, unsigned int>.

It has 3 possible constructors, that determine its behavior:

It is used in eoSelectMany (which supersedes eoSelectPerc and eoSelectNumber, but they are left there for tutorial reasons!) as well as in many truncation methods, and it is used a lot in the eoGeneralReplacement construct.



Survive and Die
This class is highly politically incorrect: it implements strong elitism and eugenism :-)
It starts by killing the worse individuals from the source argument, then appends the best ones to the destination argument and removes them from the source argument. It is used in eoSurviveAndDieReplacement, where the same dest is used successively for the parents and the offspring.

eoSurviveAndDie: interface
The class interface for its operator() is

void operator()(eoPop<EOT>& _source, eoPop<EOT>& _dest)

which you could have guessed from the inheritance tree for class eoSurviveAndDie, as you see there that eoSurviveAndDie derives from class eoBF<eoPop<EOT>&, eoPop<EOT>&, void>.

Its constructor takes 3 argumenrts:

eoHowMany(double _survive, double _die, bool _interpret_as_rate = true)

to indicate how many (or what proportion, according to _interpret_as_rate) of the source should be copied to the dest population, and how many (or what proportion, according to _interpret_as_rate)  should be erased from the source.


Local: Introduction  - Selection - Replacement - General Replacement - Popular evolution engines - Tournaments - Merge - Reduce - HowMany - SurviveAndDie


General: Algorithm-Based - Component-Based - Programming hints - EO documentation
Marc Schoenauer

Last modified: Tue. Jan. 9 2001