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


Local: Introduction - Crossover - Mutation - Combinations - General Operators - Populators - General combinations- Advanced operators

Variation Operators

Variation Operators
Variation operators modify the gnotype of individuals, or, equivalently, move them in the search space. In Evolutionary Algorithms, varitaion operators are almost always stochastic, i.e. they are based on random numbers, or equivalently, perform random modifications of their arguments. Variation operators are classified depending on the number of arguments they use and/or modify. Implementation

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:


Simple operators: Crossover

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


Simple operators: Mutation
Mutation operators modify one single individual. The corresponding EO class is called eoMonOp. and it si as usual templatized by the type of individual it can handle (see documentation for eoMonOp).

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


Combining simple operators: proportional combinations

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

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:

Warning: if you use operators that have different number of parents than offspring, you are deviating from the simple generational approach. Be careful to have the proper replacement procedure to take care of the population size: in most instances of algorithms that come within EO, this is enforced (an exception is thrown if population size varies from one genertaion to the other) but this might not be true for all forthcoming EO algorithms.

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.


The populators:
As has been said above, an eoPopulator mainly behaves like an iterator over a population (hence the name, Population-Iterator).

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

Moreover, a public method termed select,  is used inside the object to get new parents for the following operator*, and its implementation distinguishes two types of eoPopulator: An immediate consequence is that if you are not sure of the number of  parents you will need in some operators (e.g. because of some stochastic proportional selection ebtween operators that don't need the same number of parents, then you must use an eoSelectivePopulator to apply the variation operators to the population, and thus get exactly the number of offspring you want.

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.


General Operator Containers:
General operators in EO are meant to be used withing eoOpContainer objects, that allow to combine them in a hierarchical and flexible way. There are two ways to do that: the proportional combination, similar to what has been described for simple operators above, and the sequential combination, which amounts to apply all operators in turn to a bunch of individuals, each operator being applied with a specific probability.

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

Sequential combinations
When it is called upon a list of pending candidates, an eoSequentialOpContainer enters the following loop:

mark the current position
for all operators it contains,

Warning: the way rate will be used is highly dependent on the type of eoOpContainer your are creating there: Remark:The eoSGATransform presented in Lesson2 can be viewed as a particular type of eoSequentialOpContainer. It was not coded that way in order to provide a gradual introduction to all concepts.
Exercise: write the code to perform an eoSGA using the eoOpContainer constructs.

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:


Advanced general operators:

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


Local: Introduction - Crossover - Mutation - Combinations - General Operators - Populators - General combinations- Advanced operators
General: Algorithm-Based - Component-Based - Programming hints -EO documentation

Marc Schoenauer

Last modified: Sat. Feb. 17 2002