General: Tutorial main page - Algorithm-Based - Component-Based - Programming hints - EO documentation

Local: Templates - Functors - STL Library - Random numbers - EO programming style  - Memory management

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 so intimately linked to EO that a base class (eoFunctorBase) has been designed to hold all functors. This base class is itself divided into three derived class. These classes tell you immediately what kind of arguments the operator() method requires and what kind of result it produces. See EO conventions, and the inheritance diagram of class eoFunctorBase Also note that if you create new functors, you should also derive from one of these classes, as it is mandatory if you later use the EO memory management mechanism.
For a more complete introduction to functors, with detailed discussion, go to the STL documentation - as STL also heavily relies on functors, and the eoFunctorBase paradigm is borrowed from there.

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.

Now go back to the inheritance diagram of class eoFunctorBase, and guess the interface for all functors!

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

it actually means

A very brief introduction to STL

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.

There are many other types of containers that are not used in EO and that we will not present here.

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.

STL: Advantages
The main and huge advantage of using STL is that it handles (almost all) memory mangement automatically. You can use any STL container the same way you would use a scalar basic C++ type. And it does it in a (supposededly) optimized way. Of course, the user is also responsible for performances: for instance, the insert() method will take more time for vectors than for linked lists, while on the opposite, the operator[] accessor will be faster for vectors. But both will work anyway.

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

Random numbers

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 RNGs produce, by definition, integers that are uniformly distributed between 0 and some maximal number, EO provides you with random numbers following different probability distribution (e.g. floating point following normal distribution). See the complete list of RNG primitives.

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.

EO conventions and naming style

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

EO memory management

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);
eoBreeder<EOT> *ptBreed = new eoBreeder<EOT>(*ptSelect);
eoEasyAlgo<EOT> *ptAlgo = new eoEasyAlgo<EOT>( ..., *ptBreed, ...);

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.

Local: Templates - Functors - STL Library - Random numbers - EO programming style  - Memory management

General: Tutorial main page - Algorithm-Based - Component-Based - Programming hints - EO documentation

Marc Schoenauer