EO Programming guide

Most EO code is written using templates. This allows to write generic code, i.e. involving a class which doesn't have to be known when writing the code -- but only when compiling it. In some sense this is similar to naming variables in algebra: you can write a lot of equations involving some variable $x$ without knowing even it if will be an integer or a float (or a matrix or ...). The main basic type that is templatized in EO is the fitness: an EO object is some object which has a fitness of some type F that can be anything. The definition for that is (see EO.h)

template<class F> class EO

The idea is that, later in your code, you can define a class as follows (see for instance  eoOneMax.h - or check Lesson 5 for more details).

template<class F> class eoOneMax : public EO<F>
{ ... code for eoOneMax  };

and then use it in your application as

eoOneMax<double> myeoBit;

declares an object of type eoOneMax which has as fitness a double.

Whereas the advantages are obvious (writing generic reusable code instead of having to rewrite the same pieces of code for different types), there are some drawbacks: namely, it makes some of the compiler error messages hard to understand; and it forbids the compilation of most parts of EO into an object library file, as the actual types are not known in advance.

Though EO is a library, it contains almost no functions per se!
EO mainly contains functors, that are objects which have a method called operator(). Such objects are used  as if they were functions, but the big differences are that

• functors are functions with private data
• you can have different functors objects of the same class, i.e. you can use at the same time the same functionality with different parameters
• you can have a hierarchy of functors objects, which means that you have a hierarchy of functions with defaults behaviors and specialized sub-functions
• ...

Functors: Example:

The following is a basic example of how to program and use a functor object: First code the class:

class MyFunctor
{ ...
    void operator()(ArgType arg)
       {
            // do what you have to do
       }
}; // end of class declaration

Then use it  later in the code :

ArgType myArgument;
MyFunctor myFunctorInstance;    // myFunctorInstance is an object of class MyFUnctor ...
myFunctorInstance(myArgument);  // calls operator() of myFunctorInstance acting on myArgument ...
 

Functors: The three basic classes:

Direct sub-classes of the root class , three classes are defined to differentiate functors by the number of argument required by their operator(). These classes are templatized by the types of its arguments, and by its return type. Hence,
from the inheritance diagram of any functor class in EO, you can immediately deduce the interface of their operator() method.
 

• eoF is for arity-zero functors, i.e.  their operator() method does not require any argument. It has a single template parameter, the return type of the operator() method. For instance,  eoMonitor  are eoF's that return an eoMonitor &.
• eoUF is for unary functors, i.e.  their operator() method requires one argument. It has two template parameters, the type of the argument and the return type of the operator() method. For instance,  eoMonOp's are eoUF's that take as argument an EOT & and return void .
• eoBF is for binary functors, i.e.  their operator() method requires two arguments. It has three template parameters, the types of the arguments and the return type of the operator() method. For instance,  eoBinOp's are eoBF's that take as arguments a const EOT & and an EOT &, and return void .

Note: for obvious simplicity reasons, we very often omit the reference to the operator(), e.g. when we say above:

• eoMonOp's are eoUF's that take as argument an EOT & and return void

• eoMonOp's are eoUF's, their operator() method takes as argument an EOT & and returns void.

All EO heavily relies on STL, the Standard Template Library.
But you don't have to know more than a few words of STL to use EO (like with "hello", "please" and "goodbye" you can survive in a foreign country :-) and even to contribute to new EO features. Moreover, while browsing through EO code, you will gradually learn how to use STL, especially if you check at the SGI STL Web site from time to time, where you can not only download STL, but also browse in the Programmer's guide  for isntance from the Table of Content.

Anyway, you will only find here, in EO tutorial, the basics of STL that you will need to understand most of EO code - and to guess what the parts you don't understand are actually doing. Don't worry, I don't understand everything :-)

STL provides the user with containers, iterators and algorithms. And you can access (almost) all containers content using (almost) all iterators, or apply (almost) all algorithms on (almost) all containers (of course the tricky part is to instanciate the "almost" in the previous sentence :-)

STL: Containers
Containers are high level data types used to hold simpler data - the most widely used example of a container is the vector construct.
The use of STL containers relieve the user from memory management.

• vector The most widely used container is a one-dimensional array of items.

Data manipulation: suppose v is an STL vector<AtomType>. Then
v[i] is the ith element of v, as in standard C arrays
v.size() is the number of elements of v
v.push_back(atom) appends the atom at end of v, provided of course that atom is of type AtomType, the size is automatically increased...
blabla insert, erase, ...
• list STL provides different types of list. The one used in EO is the simple linked list named ... list. As far as the user is concerned, simple lists are very similar to vectors, and the data manipulation listed above for vectors can be applied to list.
• pair

This simple container allows you to hold two data types together. It is very handy for temporary data handling. Assuming p is a pair<AtomType1, AtomType2>, p.first and p.second  refer to the encapsulated data, of respective types AtomType1 and AtomType2
• Blabla

STL: Iterators
Iterators are accessors to the containers contents that provide unified access to different containers. They are very similar to pointers, i.e. you can increment them, compare them with one another, etc

Some very useful iterators for vectors and lists are begin() and end(), that refer to the first and after-last items of a container. They allow loops to sweep all items contained in a container as follows:
STLcontainer myContain;
STLcontainer::iterator it;
for (it=myContain.begin(); it!=myContain.end(); it++)
{
// do what you have to do to (*it) the current item in the container
}

STL: Algorithms
Algorithms are functions acting on containers - the most widely used example of a STL algorithm are the different sorting algorithms.

• sort, nth_element, are sorting algorithms used in EO
• copy is used to copy a range of data designated by iterators
• apply is used to perform the same operation to many items designated by a range of iterators
• Blabla - help wanted thanks...

STL: Drawbacks
The main drawback I see in using STL is that it makes it difficult to use a debugger normally: whereas access to data is made simple to the programmer, data structures are actually so complex, and debuggers so willing to display everything that you get lines of template instantiation when asking your debugger what is inside some container!
However, here is a trick (thanks to Arnaud Quirin!) to actually print what is inside an STL vector with gdb (but it doesn't really work with complex structures like EO genotypes :-( :
(gdb) print (*(&v))[i]
$1 = (const double &) @0x934cad0: 0.69543264131061733

Evolutionary Algorithms make intensive use of random numbers. Random numbers are simulated in computers by using pseudo-random number generators (RNGs for short), i.e. functions that return series of numbers who look random (w.r.t. some statistical criteria).

To make sure the random number generator is as good as possible, and to ensure reproducibility of the results across different platforms, EO has its own RNG, the ``Mersenne Twister'' random number generator MT19937 (thanks to Takuji Nishimura, see eoRNG.h comments).

Though you can define and use as many RNGs as you wish in EO, the library also provides you with a global RNG termed eo::rng. Using that single RNG in all calls to random numbers allows one to be able to reproduce a given run:

• as strange as it seems for a random algorithm, it is mandatory for debugging purposes
• random numbers are computed starting from a seed - starting from the same seed will lead to the same series of pseudo-random numbers, and hence to the same results of the algorithms. All examples in this tutorial will use the RNG seeding procedure, see e.g. in Lesson1.
• to simulate "true" random runs, you can just seed the RNG with a machine-clock related number, e.g. calling time(0), as done for instance in Lesson3 (and after).

EO also provides random_generators that can be used in STL call to generate series of random numbers, as in eoPop initializers.

Note: the eo:: prefix indicates that it is in a separate C++ namespace, to avoid collision with possible variables that would also be named rng in some other library. As early versions of EO (<= 9.1)  did not use a separate namespace for rng, the compiler directive using eo::rng in eoRNG.h allows you to use the name rng without the eo:: prefix. However, the notation eo::rng should be preferred and might become mandatory some day.

A few naming conventions should help you to navigate more easily through EO:

• The name of local variables should start with a lower case letter. Capital letters should be used rather than underscore to separate words in names (e.g. popSize rather than pop_size).
• The name of the arguments to a function should start with an underscore, e.g.

          void myfunction(unsigned _popSize){...}
• The initialization parameters of constructors should be named from the names of the variables they are used to initialize, e.g.

 

 
 
 

class eoMyClass
{
public:
  eoMyClass(unsigned _popSize):popSize(_popSize){...}
   ...
private:
   unsigned popSize;
};

• The names of classes should start with eo + an Uppercase letter (as eoMyClass above).
• The name of the EO template should be EOT. This allows quick understanding of the inheritance diagrams for functors. and immediate perception of the arguments and return types of the functors oeprator() method (as in eoMonOp or  eoBinOp).

 
• Blabla

Most of EO constructs are based on the encapsulation of objects into other objects, and the embedded objects are passed through the constructor of the embedding object.
For instance, the construction of an algorithm requires a breeder (plus many other things of course), the construction of a breeder usually requires a selector, and in turn the construction of a selector requires some parameters. This gives something resembling the following

eoTournamentSelection<EOT>  select(tSize);
eoBreeder<EOT> breed(select);
eoEasyAlgo<EOT> algo( ..., breed, ...);

Such a practice is no problem when doing everything in a (large!) main function: all objects are local to that function, but when the end of the function is also the end of the program. For instance, all programs in Lesson1, Lesson2 and Lesson3 of this tutorial are built that way.

It is however a big problem when you want to outsource some code in other functions: indeed, the above sequence create objects that dissapear when exiting the function, and thus cannot be used outside their defining function.

The solution is of course to use pointers, which gives something like

eoTournamentSelection<EOT>  *ptSelect = new eoTournamentSelection<EOT>(tSize);
eoBreeder<EOT> *ptBreed = new eoBreeder<EOT>(*ptSselect);
eoEasyAlgo<EOT> *ptAlgo = new eoEasyAlgo<EOT>( ..., *ptBreed, ...);

and you can then use the dynamically allocated objects anywhere. But the trouble with such a construct is that after exiting the function where such objects are defined, you will never be able to free this allocated memory, should you not need the objects any nore. Whereas this is not in general a big problem (except of being a very bad practice that will make you a very naughty programmer :-), it will prevent any re-entrance of the resulting code, and for instance you will not be able to use an evolutionary algorithm within another loop of some outside code.

The solution in EO us to use an eoFunctorStore object to store such nowhere-belonging pointers: whenever you allocate such a thing, store it into an eoState : deleting that state will delete all the stored pointers - one eoState is thus the only object you have to care of.

The above pointer allocation sequence thus become

eoTournamentSelection<EOT>  *ptSelect = new eoTournamentSelection<EOT>(tSize);
state.storeFunctor(ptSelect);
eoBreeder<EOT> *ptBreed = new eoBreeder<EOT>(*ptSelect);
state.storeFunctor(ptBreed);
eoEasyAlgo<EOT> *ptAlgo = new eoEasyAlgo<EOT>( ..., *ptBreed, ...);
state.storeFunctor(ptAlgo);

or, even more quickly (though less readably)

eoTournamentSelection<EOT>  *ptSelect =
               state.storeFunctor(new eoTournamentSelection<EOT>(tSize));
eoBreeder<EOT> *ptBreed =
               state.storeFunctor(new eoBreeder<EOT>(*ptSelect));
eoEasyAlgo<EOT> *ptAlgo =
               state.storeFunctor(new eoEasyAlgo<EOT>( ..., *ptBreed, ...));

In both the above code, state is an eoFunctorStore that is of course passed from outside the function - and it's called state because in most cases it will actually be an eoState. As its name says, an eoFunctorStore can store any object that is an (derives from) eoFunctorBase - hence all objects in EO that are used as functors should derive from either eoF, eoUF or eBF.

Examples of such constructs are shown in the make_xxx files described in Lesson4.