Paradiseo-MOEO Lesson 1 : Implement NSGA, NSGA-II and IBEA for the SCH1 problem

First, be sure that the ParadisEO-MOEO module has been compiled correctly and that the documentation has been generated (see the README file in the ParadisEO root directory to know how to compile the package and to generate the documentation).

We describe here a complete methodology to design and implement some easy-to-use evolutionary algorithms using ParadisEO-MOEO, namely NSGA, NSGA-II and IBEA . As an example, we will apply these search methods to the SCH1 academic problem (Schaffer's bi-objective poblem 1). All the source and program files required for this lesson are provided in the ParadisEO-MOEO package. The source files are located in the moeo/tutorial/Lesson1 directory. The program files are located in the moeo/build/tutorial/Lesson1 directory. The main file explained here is named Sch1.cpp.

Browse source code

Objective functions

The goal of the SCH1 problem is to minimize the following objective functions:

  • f1(x)=x^2
  • f2(x)=(x-2)^2

We have one decision variable x, and two objective functions f1 and f2.
As a first step, we have to define a class (here called Sch1ObjectiveVectorTraits) to define the number of objective functions and if they have to be minimized or maximized:

class Sch1ObjectiveVectorTraits : public moeoObjectiveVectorTraits
{
public:
static bool minimizing (int i) { return true; }
static bool maximizing (int i) { return false; }
static unsigned int nObjectives () { return 2; }
};

Note that Sch1ObjectiveVectorTraits must extend the ParadisEO-MOEO class moeoObjectiveVectorTraits.

Then, we can define the representation of an objective vector. For the problem under consideration, we need a real-coded objective vector representation. Then, we will use the moeoRealObjectiveVector class (that need to be templatized >>black font-size=8pt bgcolor=#ffffcc<<

typedef moeoRealObjectiveVector<Sch1ObjectiveVectorTraits> sch1ObjectiveVector;

The next step consists in defining the representation of a solution. Assuming that our individuals are encoded using a real-coded genotype with a single decision variable, such a representation can be defined as follows:

class Sch1 : public moeoRealVector<Sch1ObjectiveVector, double, double>
{
public:
Sch1() : moeoRealVector<Sch1ObjectiveVector, double, double> (1) {}
};

Then, we have to define the class that allows to evaluate a solution in the objective space. This class gives the content of the objective functions. Note that it extends the moeoEvalFunc class and that it is templatized with Sch1:

class Sch1Eval : public moeoEvalFunc<Sch1>
{
public:
void operator () (Sch1 & _sch1)
{
if (_sch1.invalidObjectiveVector())
{
Sch1ObjectiveVector objVec;
double x = _sch1[0];
objVec[0] = x * x; // first objective
objVec[1] = (x - 2.0) * (x - 2.0); // second objective
_sch1.objectiveVector(objVec);
}
}
};

Crossover and mutation operators

Many variation operators are available within ParadisEO-EO for this kind of representation. We choose here a eoUniformMutation (with a 0.01 range) as the mutation operator and a eoQuadCloneOp as the crossover operator. Furthermore, we also define the crossover and mutation rates.

double M_EPSILON = 0.01;
eoUniformMutation<Sch1> mutation (M_EPSILON);
double P_MUT = 0.35; // mutation probability
eoQuadCloneOp<Sch1> xover;
double P_CROSS = 0.25; // crossover probability

For more information about these operators, see the ParadisEO-EO API documentation.

Initial Population

The eoPop class is used to represent a population of individuals. Many initializers are available within ParadisEO-EO when using a real-coded representation. Here, we use a eoRealInitBounded, that generates real-coded individual genotypes randomly between specified bounds.

unsigned int POP_SIZE = 100; // population size
eoRealVectorBounds bounds (1, 0.0, 2.0); // [0,2]
eoRealInitBounded<Sch1> init (bounds); // initializer
eoPop<Sch1> pop (POP_SIZE, init);

For more information about these operators, see the ParadisEO-EO API documentation.

Evaluation

To evaluate an individual in the objective space, we have to create an evaluation object by using the Sch1Eval we previously defined.

Sch1Eval eval; // evaluation object

Stopping criteria

By default, the easy-to-use algorithms proposed within ParadisEO-MOEO use a maximum number of generations as a stopping criteria. Then, all you have to do is to define this number:

unsigned int MAX_GEN = 100; // number of generations before stopping

To use or to define another stopping criteria for your algorithm, please refer to the API documentation.

NSGA-II declaration and execution

The algorithm that is defined in the main file of the current lesson is NSGA-II. The declaration of the algorithm is done as follows:

moeoNSGAII<Sch1> nsgaII (MAX_GEN, eval, xover, P_CROSS, mutation, P_MUT);

Now we are ready to apply our algorithm on the initial population:

nsgaII (pop);

NSGA declaration and execution

The algorithm used by default in this lesson is NSGA-II. In order to use NSGA instead of NSGA-II, all you have to do is to replace the declaration of the algorithm by the following:

moeoNSGA<Sch1> nsga (MAX_GEN, eval, xover, P_CROSS, mutation, P_MUT);
nsga (pop);

IBEA declaration and execution

The algorithm used by default in this lesson is NSGA-II. To use IBEA instead of NSGA-II, you first have to define the indicator to be used within IBEA. As an example, we will use the moeoAdditiveEpsilonBinaryMetric. Then, the declaration of IBEA can be done by using this indicator.

moeoAdditiveEpsilonBinaryMetric<Sch1ObjectiveVector> indicator;
moeoIBEA<Sch1> ibea (MAX_GEN, eval, xover, P_CROSS, mutation, P_MUT, indicator);
ibea (pop);

Extract the (approximated) Pareto set from the final population

At the end of the search process, the population "pop" contains both the non-dominated solutions found by our algorithm, but maybe some dominated individuals too. So we have to extract the best solutions from it. This can be done by using a moeoArchive object as follows:

moeoArchive<Sch1> arch;
arch.update(pop);

Now, the approximated efficient set we have found (the output of our algorithm) is contained in the "arch" object.

Compilation and execution

In order to test your program, you first need to build the Sch1 and the install targets thanks to your own generator?. Then, you will be able to launch the obtained executable file using the Sch1.param parameter file.
Then, you can modify the parameter file Sch1.param in order to study the influence of parameters on the output of the algorithm.

Refer to INSTALL file or installation guide for further information about how to (re)build tutorial and lessons.

Conclusion

To design an evolutionary algorithm for a multi-objective combinatorial problem, go to Lesson 2.
For any question or further information, please contact paradiseo-help [at] lists.gforge.inria.fr.