Creating a simple ParadisEO-PEO Evolutionary Algorithm

0.1

Introduction

One of the first steps in designing an evolutionary algorihtm using the ParadisEO-PEO framework consists in having a clear overview of the implemented algorithm. A brief pseudo-code description is offered bellow - the entire source code for the ParadisEO-PEO evolutionary algorithm is defined in the peoEA.h header file. The main elements to be considered when building an evolutionary algorithm are the transformation operators, i.e. crossover and mutation, the evaluation function, the continuation criterion and the selection and replacement strategy.

do {
select( population, offsprings );	// select the offsprings from the current population
transform( offsprings );	// crossover and mutation operators are applied on the selected offsprings
evaluate( offsprings );	// evaluation step of the resulting offsprings
replace( population, offsprings );	// replace the individuals in the current population whith individuals from the offspring population, according to a specified replacement strategy
} while ( eaCheckpointContinue( population ) );	// checkpoint operators are applied on the current population

The peoEA class offers an elementary evolutionary algorithm implementation. The peoEA class has the underlying structure for including parallel evaluation and parallel transformation operators, migration operators etc. Although there is no restriction on using the algorithms provided by the EO framework, no parallelism is provided - the EO implementation is exclusively sequential.

Requirements

You should have already installed the ParadisEO-PEO package - this requires several additional packages which should be already included in the provided archive. The installation script has to be launched in order to configure and compile all the required components. At the end of the installation phase you should end up having a directory tree resembling the following:
     ...
     paradiseo-mo
     paradiseo-moeo
     paradiseo-peo
            docs
            examples
                   lesson1
                   lesson2
                   ...
                   shared
                   ...
            src
            ...
     ...

The source-code for this tutorial may be found in the paradiseo-peo/examples/lesson1 directory, in the main.cpp file. For a complete reference on the TSP-related classes and definitions please refer to the files under the paradiseo-peo/examples/shared. After the installation phase you should end up having an tspExample executable file in the paradiseo-peo/examples/lesson1 directory. We will discuss testing and launching aspects later in the tutorial.

---

NOTE: All the presented examples have as case study the Traveling Salesman Problem (TSP). All the presented tutorials rely on a common shared source code defining transformation operators, evaluation functions, etc. for the TSP problem. For a complete understanding of the presented tutorials please take your time for consulting and for studying the additional underlying defined classes.

---

Problem Definition and Representation

As we are not directly concerned with the Traveling Salesman Problem, and to some extent out of scope, no in depth details are offered for the TSP. The problem requires finding the shortest path connecting a given set of cities, while visiting each of the specified cities only once and returning to the startpoint city. The problem is known to be NP-complete, i.e. no polynomial time algorithm exists for solving the problem in exact manner.

The construction of a ParadisEO-PEO evolutionary algorithm requires following a few simple steps - please take your time to study the signature of the peoEA constructor:

peoEA(             eoContinue< EOT >& __cont,             peoPopEval< EOT >& __pop_eval,             eoSelect< EOT >& __select,             peoTransform< EOT >& __trans,             eoReplacement< EOT >& __replace      );

A few remarks have to be made: while most of the parameters are passed as EO-specific types, the evaluation and the transformation objects have to be derived from the ParadisEO-PEO peoPopEval and peoTransform classes. Derived classes like the peoParaPopEval and peoParaSGATransform classes allow for parallel evaluation of the population and parallel transformation operators, respectively. Wrappers are provided thus allowing to make use of the EO classes.

In the followings, the main required elements for building an evolutionary algorithm are enumerated. For complete details regarding the implementation aspects of each of the components, please refer to the common shared source code. Each of the bellow refered header files may be found in the pardiseo-peo/examples/shared directory.

1. representation - the first decision to be taken concerns the representation of the individuals. You may create your own representation or you may use/derive one of the predefined classes of the EO framework.
   

   For our case study, the TSP, each city is defined as a Node in the node.h header file - in fact an unsigned value defined as typedef unsigned Node. Moreover, each individual (of the evolutionary algorithm) is represented as a Route object, a vector of Node objects, in the route.h header file - typedef eoVector< int, Node > Route. The definition of the Route object implies two elements: (1) a route is a vector of nodes, and (2) the fitness is an integer value (please refer to the eoVector definition in the EO framework).

   In addition you should also take a look in the route_init.h header file which includes the RouteInit class, defined for initializing in random manner Route objects.

2. evaluation function - having a representation model, an evaluation object has to be defined, implementing a specific fitness function. The designed class has to be derived (directly or indirectly) from the peoPopEval class - you have the choice of using peoSeqPopEval or peoParaPopEval for sequential and parallel evaluation, respectively. These classes act as wrappers requiring the specification of an EO evaluation object derived from the eoEvalFunc class - please refer to their respective documentation.
   

   The fitness function for our TSP case study is implemented in the route_eval.h header file. The class is derived from the eoEvalFunc EO class, being defined as class RouteEval : public eoEvalFunc< Route >.

3. transformation operators - in order to assure the evolution of the initial population, transformation operators have to be defined. Depending on your prolem, you may specify quadruple operators (two input individuals, two output resulting individuals), i.e. crossover operators, binary operators (one input individual and one output resulting individual), i.e. mutation operators, or combination of both types. As for the evaluation function, the signature of the peoEA constructor requires specifying a peoTransform derived object as transformation operator.

   The transform operators, crossover and mutation, for the herein presended example are defined in the order_xover.h and the city_swap.h header files, respectively.

4. continuation criterion - the evolutionary algorithm evolves in an iterative manner; a continuation criterion has to be specified. One of the most common and simplest options considers a maximum number of generations. It is your choice whether to use a predefined EO class for specifying the continuation criterion or using a custom defined class. In the later case you have to make sure that your class derives the eoContinue class.
   
5. selection strategy - at each iteration a set of individuals are selected for applying the transform operators, in order to obtain the offspring population. As the specified parameter has to be derived from the eoSelect it is your option of whehter using the EO provided selection strategies or implementing your own, as long as it inherits the eoSelect class.

   For our example we chose to use the eoRankingSelect strategy, provided in the EO framework.

6. replacement strategy - once the offspring population is obtained, the offsprings have to be integrated back into the initial population, according to a given strategy. For custom defined strategies you have to inherit the eoReplacement EO class. We chose to use an eoPlusReplacement as strategy (please review the EO documentation for details on the different strategies available).

A simple example for constructing a peoEA object

...
eoPop< EOT > population( POP_SIZE, popInitializer );	// creation of a population with POP_SIZE individuals - the popInitializer is a functor to be called for each individual
eoGenContinue< EOT > eaCont( NUM_GEN );	// number of generations for the evolutionary algorithm
eoCheckPoint< EOT > eaCheckpointContinue( eaCont );	// checkpoint incorporating the continuation criterion - startpoint for adding other checkpoint objects
peoSeqPopEval< EOT > eaPopEval( evalFunction );	// sequential evaluation functor wrapper - evalFunction represents the actual evaluation functor
eoRankingSelect< EOT > selectionStrategy;	// selection strategy for creating the offspring population - a simple ranking selection in this case
eoSelectNumber< EOT > eaSelect( selectionStrategy, POP_SIZE );	// the number of individuals to be selected for creating the offspring population
eoRankingSelect< EOT > selectionStrategy;	// selection strategy for creating the offspring population - a simple ranking selection in this case
eoSGATransform< EOT > transform( crossover, CROSS_RATE, mutation, MUT_RATE );	// transformation operator - crossover and mutation operators with their associated probabilities
peoSeqTransform< EOT > eaTransform( transform );	// ParadisEO specific sequential operator - a parallel version may be specified in the same manner
eoPlusReplacement< EOT > eaReplace;	// replacement strategy - for integrating the offspring resulting individuals in the initial population
peoEA< EOT > eaAlg( eaCheckpointContinue, eaPopEval, eaSelect, eaTransform, eaReplace );	// ParadisEO evolutionary algorithm integrating the above defined objects
eaAlg( population );	// specifying the initial population for the algorithm
...

---