Tutorial Lesson 2: more encapsulations

• minimizing (and not only maximize) the fitness
• combining several operators of the same type
• combining several stopping criteria
• use alternate selection/replacement engines, deviating from the pure generational GA

Again, two basic algorithms are provided, namely FirstBitEA and FirstRealEA.
To compile and run them, go to the Lesson2 sub-directory of the tutorial dir and simply type make. Both examples should get compiled, and you can then run them by calling their name from the system prompt.

Note the slim difference in names, from GA to EA: the behavior of these  EAs is almost identical to that of their GA counterpart, at least with the default settings that are provided. But their potentialities for easy modifications are much larger, both in terms of variation operators and of evolution engine (i.e. selection/replacement mechanism). 

Browse through the code, and discover them one after the other:

• The fitness function now lies in a separate file (Bit - Real). But, more important, its argument is a vector<bool> or a vector<double>, and not an unknown type. This will allow to use the same file for any EO object that is a sub-class of the corresponding STL vector class.

 

 

Note: Also, a non-templatized fitness can be compiled separately (not done here) into an object file once and for all (remember that templates forbid that).
 

• The encapsulation of the fitness (Bit - Real) looks more complicated: you have to declare 3 template arguments: the type of EO object it will be applied to, the return type and the type of argument the function actually requires.

 

 

Note: In the previous files (Bit - Real) , the last 2 types were deduced from the first (2nd argument = fitness type of EO object, third = first).
 

• Both the above modifications makes it very easy to minimize rather than maximize a fitness function (see Exercise 1).

 
• The initialization of the population is now encapsulatedinto a separate initializer (based on a boolean generator or a double-number generator -see random_generators.h) that is then used in the constructor of the population to build the individuals. You can also use different initializers and call them in turn through the call to pop.append() function (see Exercise 2).

 

 

Note: Don't forget to evaluate the population: the eoPop has no idea of the eval function, so it has to be done from outside!!!
 

• You can now use different crossover and mutation operatorsin the same algorithm, choosing among them according to relative weights. The class eoPropCombinedxxxOp, where xxx is either Mon (for mutations, of class eoMonOp) or Quad (for crossovers, of class eoQuadOp), is derived from the corresponding eoxxxOp class. When applying the eoPropCombinedxxxOp, one of the eoxxxOp it contains is chosen by a roulette wheel, according to their respective rates, and is applied to the arguments. For more details on these classes, go to the algorithm-based corresponding pages, or to their respective documentation pages.
• Bit

Three crossover operators are available: the one-point crossover is still there (class ), but now you also have the N-point crossover eoBinNxOver (the  number of points is 2 by default, but as always you can change that in the constructor), and the Uniform crossover eoBinUxOver (where you can eventually twidle the choice from one parent to the other by providing a probability in the constructore - defaulted to 0.5, which amounts to symmetrical choice).
As for mutation operators, apart from the eoBinMutation (standard bitstring mutation flipping one bit with a given probability) you can also use the eoDetBitFlip that always filps the same number of bits (1 by default, but you can change that in the constructor), randomly chosen in the bitstring. Even though the average number of bits flipped is the same if the eoBinMutation is used with a rate of 1/N (N is the bitstring length) the behavior of these mutation can be very different on many problems.
• Real

Two crossover operators are available: the eoSegmentCrossover chooses one point uniformly on the segment joining the parents, while the eoHypercubeCrossover performs a linear combination on each coordinate independently, which amount to choosing the offspring uniformly in the hypercube whose diagonal is the segment joining the parents.
As for mutation operators, apart from the eoBinMutation (standard bitstring mutation flipping one bit with a given probability) you can also use the eoDetBitFlip that always filps the same number of bits (1 by default, but you can change that in the constructor), randomly chosen in the bitstring. And last but not least, the normal mutation eoNormMutation modifies all coordinates with a Gaussian noise, with standard deviation passed in the constructor.
Note: A third optional argument in method add is a boolean (defaulted to false). When true, the actual rates for all operators are displayed on the screen as percentages: you don't have to input rates that sum up to 1, all rates are scaled anyway.

Note: The operators have to be encapsulated into an eoTransform object (Bit - Real) to be passed to the eoEasyEA algorithm. The eoSGATransform is a simple eoTransform that does exactly the same thing than eoSGA: each pair from the selected parents undergoes the crossover operator with given probability, and all individuals (after crossover eventually) undergo mutation with given probability. The arguments to the eoSGATransform are an eoQuadOp with its probability and an eoMonOp with the associated probability.
 

• You can use combinations of several stopping criteria by using an object of the class eoCombinedContinue (Bit - Real). Initialize it with an object of class eoContinue, and add as many of other such objects as you wish. And as an eoCombinedContinue is an eoContinue, simply pass it to the algorithm (Bit - Real). To find out more, and to get the list and syntax of existing eoContinue subclasses, check out the corresponding component-based page.

 
• The full selection/replacement mechanism is now in place through the eoEasyEA algorithm.

This means that you can use different selectors. which was already true in Lesson 1, but also different replacement strategies (see Exercise 3) whereas generational replacement was hard-coded in the algorithm eoSGA used in Lesson1.

Beware that we have to encapsulate  (Bit - Real) the eoDetTournament, which is of class eoSelectOne (i.e. allows to select one individual from a population, its operator() returning a single individual) into an object of the eoSelectPerc (perc stands for percentage) which allows to select a ... percentage of a population (his operator()  returns a population). This was done internally in the  constructor of eoSGA  - see lesson1.

• For the bitstring case, you only have to modify the declaration of the representation, using eoMinimizingFitness instead of double. But is that really all? Give it a try, look at the output, and do it right the second time!!!
• For the real-valued problem, you also need to modify the file real_value.h so that it returns the sum of squares instead of its inverse. And again there is something else to modify...

Exercise 3:  full selection/replacement
You can now twiddle the number of offspring that will be generated from the parents. But of course you need to adjust the replacement to keep a constant population size.

• To modify the number of offspring, use the second argument of the encapsulator (Bit - Real) of the selector of class eoSelectOne into an eoSelectPerc object. For instance, try

                eoSelectPerc<Indi> select(selectOne,2.0)
to generate twice as many offspring as there are parents.
You can also use the other encapsulator that takes as second argument an absolute number (e.g. if you want to generate 2 offspring whatever the population size):
                eoSelectNumber<Indi> select(selectOne,2)
Or you can use the HowMany paradigm and the eoSelectMany to do either one depending on some command-line input (advanced).
• To keep a constant population size, you can use either the eoCommaReplacement class, or the eoPlusReplacement. The former selects the best offspring to replace the parents, the latter selects the best among parents+offspring. Of course you cannot use eoCommaReplacement if you have less offspring than parents!

Now if you use eoSelectRandom as selector with a rate of lambda, you end up with exactly the (mu+lambda) or (mu,lambda) strategies from Evolution Strategies.
• Question: what do you get if you select 1 offspring only, and an eoPlusReplacement strategy? Yes, you get almost the replace_worst Steady-State GA, though rather inefficient, as you sort the population at every generation.
• Hint: there are a few Steady-State replacement strategies already there in EO. See the Replacement page.

• How to write a fitness function that only needs a genotype, not a full individual. Moreover you can compile it separately.

How to initialize the population using random generators
• How to use other evolution engine than the simple generational GA.
• How to combine different objects of the same kind into a single object that you can use like a simple basic object (operators and stopping criteria here).