Evolution Engine

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

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.

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.

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

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

• eoDetTournamentSelect uses the (deterministic) tournament to choose one individual. Its constructor has one parameter, the tournament size (integer >= 2).
• eoStochTournamentSelect uses the binary stochastic tournament to choose one individual. Its constructor has one parameter, the tournament rate (real in [0.5,1]).
•  eoProportionalSelect is the original roulette wheel selection: each parent is selected with a probability proportional to its fitness.
• eoRandomSelect is the random selection and should give bad results! At the moment, it selects one individual uniformly, but it would be easy to use any probability distribution.

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

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:

• How does it know how many individuals to select?
• How to use repeated selection of one individual (see above the eoSelectOne class)?

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.

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

• eoDetSelect selects individuals deterministically, i.e. starting from the best ones down to the worse ones. If the total number to select is less than the size of the source populations, the best individuals are selected once. If more individuals are needed after reaching the bottom of the population, then the selection starts again at top. It the total number required is N times that of the source size, all individuals are selected exactly N times.

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.

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

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.

• eoGenerationalReplacement This is the most straightforward replacement, called generational replacement: all offspring replace all parents (used in Holland's and Goldberg's traditional GAs).  It takes no argument, and supposes that offspring and parents are of the same size (but does not check!).

 
• eoMergeReduce This is one the basic types of replacement in EO. It has two major steps, merging both populations of parents and offspring, and reducing this big population to the right size. It contains two objects of respective types eoMerge and eoReduce and you can probably guess what each of them actually does :-)

 

 
 
 

Available instances of eoMergeReduce replacement include

• eoCommaReplacement, one of the two standard strategies in Evolution Strategies, selects the best offspring. It is an eoMergeReduce(eoNoElitism, eoTruncate).
• eoPlusReplacement, the other standard Evolution Startegies replacement, where the best from offspring+parents become the next generation. It is an eoMergeReduce(eoPlus, eoTruncate).
• eoEPReplacement, used in the Evolutionary Programming historical algorithm, does an EP stochastic tournament among parents + offspring. It is an eoMergeReduce(eoPlus, eoEPReduce) and its constructor requires as argument T, the size of the tournament (unsigned int).
• eoReduceMerge is another important type of eoReplacement: the parents are first reduced, and then merged with the offspring. Note that the parent population is reduced of the exact number of offspring.

Though not mandatory, it is implicitely assumed that few offspring have been generated. Hence, all derived replacement procedures of class eoReduceMerge are termed eoSSGAxxx, as they are the ones to use in SteadyState Genetic Algorithm engine. This gives the following instances of eoReduceMerge:
•  eoSSGAWorseReplacement in which the worse parents are killed and replaced by all offsprings (no additional argument needed);
• eoSSGADetTournamentReplacement in which parents to be killed are chosen by a (reverse) determinitic tournament. Additional parameter (in the constructor) is the tournament size, an unsigned int.
• eoSSGAStochTournamentReplacement in which parents to be killed are chosen by a (reverse) stochastic tournament. Additional parameter (in the constructor) is the tournament rate, a double.
• eoSurviveAndDie replacement strategies are a generalization of both the above that allows strong elitist and eugenism in both the parent population and the offspring population. The eoSurviveAndDie building block takes one population, kills the worse and moves the best to some safe place.  The corresponding replacements apply an eoSurviveAndDie to the parents, another one to the offspring, and finally merges the remaining parents and offspring before reducing the resulting population to the right size. Available instances of eoSurviveAndDieReplacement are limited todayto the eoDeterministicSaDReplacement, the  that uses a deterministic MergeReduce.

 

 
 
 

Note: The basic use (and initial motivation) for eoSurviveAndDie takes 2 arguments, an eoMergeReduce and a number of surviving parents. It starts by copying the best parents to the new populations, then merges the remaining parents with the offspring before reducing to the number of remaining seats in the new population.

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 :-)

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

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.

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.

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

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)
4. eoReduce<EOT> & reduceParents indicates how the parents will be reduced (see available instances).
5. eoHowMany reducedOffspring gives the number of offspring remaining after reducing them

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

Note: the number of individuals remaining after that reduction is of course the original size of the population.

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.

• Generational Genetic Algorihtm: popularized by Holland (75) and Goldberg (89), it uses

Number of offspring:  P
Selection: Proportional (the historical roulette wheel) when maximizing a positive scalar fitness, ranking or tournament (stochatic or deterministic) in all cases.
Replacement: Generational.
Remark: You could use also the eoCommaReplacement, with exactly the same result as there are as many offspring as we need indiviudals in the next population. And using the eoSSGAWorseReplacement would also give the same result, but would be very inefficient!
You can also add weak elitism to preserve the best individual.
• Steady-State Genetic Algorithm: widely used in GA/GP community

Number of offspring:  small (historically, 1)
Selection: tournament (you can use ranking or proportional, but it will be rather inefficient).
Replacement: An eoSSGAxxxReplacement.
Remark: You can also use the eoPlusReplacement, but you divert from the original SSGA
• (MU+Lambda)-Evolution Strategy: The elitist ES strategy (Rechenberg 71 and Schwefel 81)

Number of offspring:  Any
Selection: eoDetSelect (batch deterministic).
Replacement: eoPlusReplacement
Remark: You could also use eoEPReplacement, to smoothen the selective pressure during replacement, thus getting close to EP evolution engine
• (MU,Lambda)-Evolution Strategy: The non-elitist ES strategy

Number of offspring:  > P
Selection: eoDetSelect (batch deterministic).
Replacement: eoCommaReplacement
Remark: You can also add weak elitism to preserve the best individual - though you'd probably use the plus strategy if you want (strong) elitism.
• Evolutionary Programming: The historical method of L. Fogel (65)

Number of offspring:  P
Selection: eoDetSelect (batch deterministic). Every individual reproduces exactly once.
Replacement: eoEPReplacement, though one historical replacement was the determnistic replacement - i.e. in EO the eoPlusReplacement).
Remark: Close to an (P+P)-ES
• You name it :-): you can of course choose whatever combination you like - respecting a few constraints and common-sense remarks. For instance, eoProportionalSelect should be used only when maximizing a positive fitness, eoCommaReplacement requires more offspring than parents, and, over all, existing EO algorithms wirk with fixed size population - and it is your responsability to use a cmbinatino of selection/replacement that fulfills this requirement (or to create your own eoAlgo that handles varying size populations).

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.

• Deterministic Tournament of size T returns the best of T uniformly chosen individuals in the population. Its size T should be an integer >= 2. It is implemented in the eoDetTournamentSelect class, a sub-class of eoSelectOne, as well as in the eoDetTournamentTruncate class that repeatidly removes from the population the "winner" of the inverse tournament.  These objects use the C++ function determinitic_tournament in  selectors.h.
• Stochastic Tournament of rate R first choses two individuals from the population, and selects the best one with probability R (the worse one with probability 1-R). Real parameter R should be in [0.5,1]. It is implemented in the eoStochTournamentSelect class, a sub-class of eoSelectOne, as well as in the eoStochTournamentTruncate class that repeatidly removes from the population the "winner" of the inverse tournament.  These objects use the C++ function determinitic_tournament in  selectors.h.

Note: A stochastic tournament with rate 1.0 is strictly identical to a deterministic tournament of size 2.
• EP Tournament of size T is a global tournament: it works by assigning a score to all individuals in the population the following way: starting with a score of 0, each individual I is "opposed" T times to a uniformly chosen individual. Everytime I wins, its score in incremented by 1 (and by 0.5 for every draw). The individuals are then selected deterministically based on their scores from that procedure. The EP Tournament is implemented in the  eoEPReduce truncation method used in the eoEPReplacement procedure.

Note: whereas both the determinitic and the stochastic tournament select one individual, the EP tournament is designed for batch selection. Of course it could be used to select a single individual, but at a rather high computational cost.

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.

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

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

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.

• eoTruncate, deterministically kills the worse individuals, keeping only the required number. It starts by sorting teh populations, and hence does modify its order.
• eoLinearTruncate, deterministically kills the worse individuals, keeping only the required number. It does so by repeatedly removing the worsr individual. Hence does not modify its order, but takes longer time than eoTruncate in case of many offspring.
• eoEPReduce, uses the EP stochastic tournament to reduce the population. It requires an additinal argument, the tournament size.
• eoDetTournamentTruncate uses inverse deterministic tournament to repeatidly kill one individual until the propoer size is reached. As eoLinearTruncate, it might take some time in the case of many offspring. It requires the size of the tournament (unsigned int) as parameter in the constructor (default is 2).
• eoStochTournamentruncate  uses inverse stochastic tournament to repeatidly kill individuals from the population. It requires the rate of the tournament (double) as parameter in the constructor (default is 0.75).

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:

• return a given rate of the argument population size
• return an absolute (unsigned) integer, whatever the argument population size
• return the argument population size minus a given number

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:

• eoHowMany(double _rate, bool _interpret_as_rate = true) where _rate is by default the fixed rate of behavior 1 above. However, if the boolean second argument is false, the rate is transformed into a positive integer, and is used for behavior 2 above
• eoHowMany(int _combien): if _combien is positive, it is the absolute number of behavior 2 above, and if _combien is negative, its absolute value is used to decrease the argument population in behavior 3 above
• eoHowMany(unsigned int _combien): _combien (positive!)  is the absolute number of behavior 2 above. Note that this constructor is mandatory to avoid ambiguity, as an unsigned int can be casted to either an int or a double.

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

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:

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.