Variation Operators

• Variation operators involving two individuals are called crossover operators. They can either modify one of the parents according to the material of the other parent, or modify both parents. In EO, the former are called Binary operators and the latter Quadratic operators.
• Variation operators involving one single individual are called mutation operators.
• Straightforward extensions of these simple operators allow to combine them: in proportional combinations, one operator is chosen among a given set of operators of same arity according to some weights.
• In EO you can also define and use variation operators that generate any number of offspring from any number of parents (sometimes termed orgy operators). They are called general operators.
• However, the interface of such operators was designed for their use inside general combinations: you can use proportional combination, in which one operator is chosen among a given set of operators of same arity according to some weights, as for simple operators except that operators of different arities can be mixed, but you can also use sequential combinations, where different operators  are applied in turn with given probability. But you can also embed any of such combinations at any depth.
• The price to pay for that is that you must use an instermediate class to access the individuals, the eoPopulator class.
• Thanks to that class, it also become easy to design advanced operators, such as crossover operators where the mate is chosen according to sexual preference rather than fitness-based preferences.

The basic idea of EO variation operators is that they operate on genotypes only. Hence there should be generally no reference to anything related to the fitness within a variation operator. However, whenever the genotype of an individual has been modified, it will be necessary to recompute its fitness before any selection process. This is why all variation operator return a bool that indicates whether or not the genotype argument has been modified or not.

EO classes for variation operators:

• Base classes: all variation operators in EO derive from the base (pure abstract) class eoOp (as usual, click to see the inheritance diagram).  Four (also abstract) classes derive from eoOp, namely eoMonOp (for mutations), eoBinOp and eoQuadOp (for crossover) and eoGenOp for all other operators.
• Combined classes: those classes combine variation operators, and are variation operators by themselves: the simple variation operators can be combined into the corresponding eoProportionalCombinedMonOp, eoProportionalCombinedBinOp and eoProportionalCombinedQuadOp. The general operators eoGenOp can be combined into some eoOpContainer, abstract class with two implementations, eoProportionalOp and eoSequentialOp
• Related classes: General operators of class eoGenOp can only be used through the eoPopulator class.

The characteristic of crossover operators is that they involve two parents. However, there are crossover operators that generate two parents, and some that generate one parent only, and both types are available in EO. The former type (2 --> 2) is termed quadratic crossover operator, and is implemanted in the eoQuadOp class; the latter type (2 --> 1) is termed binary operator and is implemanted in class eoBinOp. Both classes are, as usual, templatized by the type of individual they can handle (see documentation for eoBinOp and eoQuadOp).

Note: Whereas it is straightforward to create a binary crossover operator from a quadratic one (by discarding the changes on the second parent), the reverse might prove impossible (imagine a binary crossover that simply merges the parents material: there is no way to generate two new parents from that!).

Interfaces:
The general approach in EO about simple variation operators is to perform in-place modifications, i.e. modifying the arguments rather than generating new (modified) individuals. This results in the following interfaces for the functor objects eoBinOp and eoQuadOp:

bool operator()(EOT & , const EOT &)         for eoBinOp (note the const)
bool operator()(EOT & , EOT & )                       for eoQuadOp

which you could have guessed from the inheritance diagrams up to the eoBF abstract class. You can also guess that only the first argument will be modified by an oeBin object, while both arguments will be modified by an eoQuad object.

Using crossover operators:
Directly applying crossover operators is straightforward from the interface above:
eoBinOpDerivedClass<Indi> myBinOp(parameters); //  use constructor to pass
eoQuadOpDerivedClass<Indi> myQuadOp(parameters); //  any useful argument
Indi eo1= ..., eo2= ...;   // the candidates to crossover
if (myBinOp(eo1, eo2))
   { ...               // eo1 has been modified, not eo2
   }
else ...               // none has been modified
if (myQuadOp(eo1, eo2))
   { ...               // both eo1 and eo2 have been modified
   }
else ...               // none has been modified

However, you will hardly have to actually apply operators to individuals, as operators are used within other classes, and are applied systematically to whole sets of individuals (e.g. that have already been selected, in standard generation-based evolutionary algorithms).
Hence the way to use such operators will more likely ressemble this if you are using for instance an SGA. See also the different ways that are described below, encapsulating the operators into combined operators objects.

Writing a crossover operator:
There are three things to modify in the template class definitions provided in the Templates directory for both binary crossover and quadratic crossovers (apart from the name of the class you are creating!)

• The constructor, where you pass to the object any useful parameter (see the private data at end of class definition).
• The operator() method, which performs the actual crossover.
• The return value, that should be true as soon as at least one genotype has actually been modified. Otherwise, the lazy fitness evaluation procedure in EO might not know it should compute the fitness again and will keep the old value.

Interfaces:
The general approach in EO about simple variation operators is to perform in-place modifications, i.e. modifying the arguments rather than generating new (modified) individuals. This results in the following interface for the functor objects eoMonOp:

bool operator()(EOT & )

which you could have guessed from the inheritance diagrams up to the eoUF abstract class.

Using mutation operators:
Directly applying mutation operators is straightforward from the interface above:
eoMonOpDerivedClass<Indi> myMutation(parameters); //pass parameters in constructor
Indi eo = ...;           // eo is candidate to mutation
if (myMutation(eo))
   { ...    // eo has been modified
   }
else      // eo has not been modified

However, you will hardly have to actually apply operators to individuals, as operators are used within other classes, and are applied systematically to whole sets of individuals (e.g. that have already been selected, in standard generational evolutionary algorithms).
Hence the way to use such operators will more likely ressemble this if you are using for instance an SGA. See also the different ways that are described below, encapsulating the operators into combined operators objects.

Writing a mutation operator:
There are only two things to modify in the template class definitions provided in the Templates directory (apart from the name of the class you are creating!)

• The constructor, where you pass to the object any useful parameter (see the private data at end of class definition).
• The operator() method, which performs the actual crossover.
• The return value, that should be true as soon as the genotype has actually been modified.  Otherwise, the lazy fitness evaluation procedure in EO might not know it should compute the fitness again and will keep the old value.

The best thing to do is to go to the Lesson2 of the tutorial, where everything is explained. You will find out how you can use
several mutations (respectiveley quadratic crossovers) as a single operator: every time the operator is called, one of the available operators is chosen by some roulette wheel selection using realtive weights.

General operators in EO are variation operators that are neither simple mutations nor simple crossovers. They can involve any number of parents, and create any number of offspring. Moreover, they can make use of different ways to get the parents they will involve, e.g. they can use a different selector for each of the parents they need to select.

The corresponding EO class is called eoGenOp. and it is as usual templatized by the type of individual it can handle (see documentation for eoGenOp :-)

Interface:
All the work a general operator is done within the apply() method. WHy not in the usual operator() method? Because some memory management are needed, that are performed in the base class itself - which then calls the virtual apply() method. The interface for a eoGenOp thus is not deducible from its inheritance diagram, and actually is

    void apply(eoPopulator<EOT>& _plop)

As you can see,the interface for eoGenOp is based on that of another class, called eoPopulator. An eoPopulator is a population, but also behaves like an iterator over a population (hence the name, Population-Iterator).  However, please note that you should probably never use an eoGenOp alone, but rather through objects of type eoOpContainer.

This results in the following general interface for an eoGenOp: It receives as argument an eoPopulator, gets the individuals it needs using the operator*, and must handle the positinning of the  using the ++operator method (Warning: the operator++ method is not defined, as recommended by many good-programming-style books).

bool apply()(eoPopulator& _pop)
{
   EOT& parent1 = *_pop; // select the first parent
   ++_plop;   // advance once for each selected parents
   ...
   EOT& parentN = *_pop; // select the last parent
       // don't advance after the last one: _plop always
            // points to the last that has already been treated

// do whatever the operator is supposed to do
}

Warning: as said above, an eoPopulator should always point to the last individual that has already been treated. This is because it is intended to be used within a loop that looks like (see e.g. eoBreeder class):

      eoSelectivePopulator<EOT> popit(_parents, _offspring, select);    // eoSelect is an eoSelectOne
      while (_offspring.size() < target)
          {
               op(popit);
              ++it;
          }

What happens next? Well, it all depends on how many parents and how many offspring your general op needs:

• If the number of generated offspring is equal to the number of parents, the operator simply needs to modify them (they are passed by reference, no useless copy takes place).
• If the operator produces more offspring than there were parents, it needs to insert them into the list using the insert method of the class eoPopulator as in the following:

 

 

void apply()(eoPopulator& _pop)
{
  // get the necessary number of parents (see above)
  ...
  // Now create any supplementary offspring
  EOT ofs1 = create_individual(...);
  ...
  EOT ofsK = create_individual(...);
  // advance and inserts offspring in _pop after parentN
  ++_pop;
  _pop.insert(ofs1);
  ...

  // invalidate the parents that have been modified
  parent1.invalidate();
  ...
  parentN.invalidate();
}   // over

Of course the size of the resulting population will grow - and you should have a replacement procedure that takes care of that.
 

• The case where more parents are needed than offspring will be created is a little more delicate: think about eoBinOp, and try to imagine the reasons why no crossover of that class are used in the first lessons of the tutorial, within the SGA framework.

There are two possibilities:
• If you think "generational", the first idea is to get the parents from outside the curent list, so the total number of (intermediate) offspring is always equal to the initial population size. By chance, the eoPopulatorhas a handle on the initial population that was used to start the process, and you can access it from inside the GenOp method. For instance

 

 

void apply()(eoPopulator& _pop)
{
  // get as many parents as you will have offspring (see above)
  ...
  // get extra parents - use private selector
  const EOT& parentN+1 = select(_pop.source());
  ...
  const EOT& parentM = select(_pop.source());
  // do whatever needs to be done
  ...
  // and of course invalidate fitnesses of remaining modified parents
  parent1.invalidate();
  ...
  parentN.invalidate();
}
where select is any selector you like. Note the const: you are not allowed to modify an element of the original population (but you could of course have copied it!). As usual, the select selector was passed to the operator at construct time. This typically allows one to use a different selector for one parent and the others, as demonstrated here.
 

• If you don't care about the size of the offspring population (that is, if that size os controlled elsewhere, e.g. in some external loop), you can use the inbedded select method of the class eoPopulator. For instance

 

 

void apply()(eoPopulator& _pop)
{
  // get as many parents as you will have offspring (see above)
  ...
  // get extra parents - use populator selector
  const EOT& parentN+1 = _pop.select();
  ...
  const EOT& parentM = _pop.select();
  // do whatever needs to be done
  ...
  // and of course invalidate fitnesses of remaining modified parents
  parent1.invalidate();
  ...
  parentN.invalidate();
}

Using general operators:
Directly applying general operators to given individuals is impossible in EO, due to its interface. You need the help of an individual dispenser of class eoPopulator. But anyway general operators were thought to be used putely in eoOpContainer, as described below.

Writing a general operator:
There are many things to do to write a general operator - but the Templates directory contains some sample tempaltes files to help you. It all depends on whether you want more or less offspring than parents, and whetehr you want the same selector for every parent or more specialized selectors.

• It you want more (or as many) offspring than parents, you should use the moreOffspringGenOp.tmpl template - if you want to use the same selector for all parents, the one embedded in the argument eoPopulator. Otherwise, you'll have to write your own operator based on an external selector, as described in lessOffspringExternalSelectorGenOp.tmpl.
• If you decide to have more parents than offspring, you can decide either to get the extra parents using the eoPopulator  own selector (see lessOffspringSameSelectorGenOp.tmpl, or to use an external selector (passed at construct-time) as described in lessOffspringExternalSelectorGenOp.tmpl.
• Now you can modify the constructor, where you pass to the object any useful parameter (see private data at end of class definition). In case you need an external selector, you have to choose it (or write it!) - it should be an eoSelectOne object.
• Finally, write the core of the operator in method apply(). Remember you must use the argument eoPopulator to access the members of the population in turn (method operator*), you may use the initial population (method source()), as well as the insert methods.

Warning: in general operators, you must not forget to invalidate the fitness of any individual that has actually been modified. this implicitely implies that general operators can only be applied to EO object (i.e. objects with a fitness), and not to any type of structure.
It you don't invalidate the individual, the lazy fitness evaluation procedure in EO will not know it should compute the fitness again and will keep the old obsolete value.

The basic interface of an eoPopulator (see also the documentation, of course) is the following:

• Individuals are accessed through the operator*;
• Basic iterator operations are available, like (pre)incrementation through operator++, position management through seekp (returns the current position) and tellp (go to a given position);
• Individuals can also be inserted at current position using the corresponding methods;
• last but not least, as the individuals are returned by reference, it is mandatory to ensure that they will not be moved around later: the memory management  routine reserve is called whenever there is a chance to add some individuals in the population - i.e. in the eoGenOp base class operator() method.

• The eoSeqPopulator gets new parents from its source (the initial population). When the source is exhausted, an exception if thrown. The idea of such pooulator is to start from a population of already selected individuals.

The programmer should hence be very careful that the number of available parents matches the requirements of the operators when using an eoSeqPopulator object.
• The eoSelectivePopulator , on the opposite, always gets new parents using its private eoSelectOne object (passed at construct time). Hence it can handle any number of parents at will. The idea of such populator is to handle the whole breeding process, i.e. selection and variation operators.

Example: An eoSelectivePopulator is the main ingredient of the eoGeneralBreeder operator() method - a class that creates a population of offspring from the parents applying an eoGenOp (usually an eoOpContainer) to all selected parents in turn.

Proportional combinations
When called upon a population (through an eoPopulator object), an eoProportionalOpContainer enters the following loop:

while there are individuals left in the list

• choose one of the included operators according to their relative rates (by some roulette wheel random choice)
• applies the chosen operator. The parents are dispensed to the operator from the list on demand.
• What happens next exactly depends on the type of operator, but basically, some of the parents get modified, some might get removed from the list and some new individual might get inserted on the list.
• updates the list pointer (if needed) to the individual following the ones that just have been modified/inserted/deleted.

mark the current position
for all operators it contains,

• go to marked position
• until current end of population is reached do
• flip a coin according to the operator rate.
• If true, apply the operator to the parents. The current parents can be modified, or some can be deleted from the list, or some offspring can be inserted in the list.
• If false, move the pointer over the required number of parents (i.e. don't modify thoses parents)
• Next pending parent
• Next operator

• The rates for eoProportionalOpContainer will be used in a roulette wheel choice among all operators. They can take any value, the only important thing is their relative values.
• The "rates" for eoSequentialOpContainer actually are probabilities, i.e. they will be used in a coin-flipping to determine whether that particuler operator will be applied to the next candidates at hand. They should be in [0,1] (no error will happen if they are not, but the operator will be applied systematically - this is equivalent of a rate equal to 1).

Adding operators to a container:
The way to add an operator to an eoOpContainer is the method add. It is similar to all other add methods in other Combined things in eo (as the simple eoProportionalCombinedXXXop described above, but also the eoCombinedContinue class or the eoCheckPoint class).
The syntax is straightforward, and it works with any of the operator classes eoXXXOp, where XXX stands for Mon, Bin, Quad or Gen:

someOperatorType<Indi> myOperator;
eoYYYOpContainer<Indi> myOpContainer;
myOpContainer.add(myOperator, rate); // rate: double whose meaning depends on YYY

where YYY can be one of Proportional and Sequential. Note that before being added to the container, all simple operators are wrapped into the corresponding eoGenOp (see e.g. how an eoMonOpis wrapped into an eoMonGenOp- or how any operator is handled by calling the appropriate wrapper). In particular, the wrapper ensures that individuals who have been modified are invalidated.

Containers, Selectors and Populators
The way the eoOpContainer are applied on a population using an eoPopulator object. But, whereas the behavior of eoProportionalOpContainer does not depend on the type of eoPopulator,(one operator is chosen by roulette_wheel, and applied once before control is given back to the caller), the main loop in method operator() of class eoSequentialOpContainer iterates while (!_pop.exhausted()) which is interpreted differently depending on the type of eoPopulator:

• if the argument is an eoSelectivePopulator, the default position of the eoPopulator, considered as a population iterator, is at end of population. Individuals are added upon demand of an operator, and in most cases all operators are applied once. This also depends, however, on the arities of all operators:
• Consider an eoSequentialOpContainer containing an eoQuadOp and an eoMonOp. The eoQuadOp first asks for two parents and modifies them. The eoMonOp is then called starting from the forst of thoses two modified individuals, and is hence applied twice, once on each parent.
• But consider now an eoSequentialOpContainer containing an eoGenOp that takes one parent and generates three offspring, followed by an eoQuadOp. The eoGenOp will call the selector to get the parent its need and will modify it and put 2 additional offspring at end of the population. The eoQuadOp will then be called on the first of the three outputs of the eoGenOp, and hence will act upon the frist two of them. But at that point, the populator iterator will point to the third of the individuals resulting from the eoGenOp, and the test _pop.exhausted() will return false, so the eoQuadOp will again be called. The second parent it needs will be given by a new call to the embedded eoSelectOne of the  and everything will go on smoothly, except that a total of 4 offspring will have been generated by application of this particular eoSequentialOpContainer.
• if the argument is an eoSeqPopulator, the position of the iterator starts from the beginning of an existing population (the source populations), and hence when an  an eoSequentialOpContainer is called, it goes through the whole remaining of the population (the test _pop.exhausted() only returns true at end of the source population).
• From the above it is easy to see that passing an eoSeqPopulator to an eoProportionalOpContainer that contains an eoSequentialOpContainer, though not technically forbiddden, will most produce something  totally unpredictable, and hence should probably not be used without great care.

It is sometimes useful to be able to use a selector from inside an operator (a typical example is when you want to implement sexual preferences, i.e. choose a mate for a first parent according to some characteritics of that first parent).
This is made possible in EO because the general operators have a handle on the initial population through the method source() of the argument eoPopulator they work on. Their apply() method shoudl look like

void apply()(eoPopulator& _pop)
{
  EOT & eo1 = *_pop; // get (select if necessary) the first guy
  EOT maBlonde = findBlonde(_pop.source()); // select mate
  // do whatever the operator is supposed to do, e.g
  cross(eo1, maBonde);       // cross is some embedded crossover
  ...
  // if you don't want to put maBlonde into the offspring,
  // stop here (and use a reference to maBlonde above). Otherwise
  maBonde.invalidate();
 ++_pop;    // advance
  _pop.insert(maBlonde);    // and insert it
}

Where does that findBlonde selector comes from? As usual, you have to attach it to the operator,  in its constructor for instance, which should give something like:

sexualSelectorType<Indi>  findBlonde;
sexualOperatorType<Indi> yourBrainAndMyBeauty(cross, findBlonde);