Implement a binary PSO algorithm using ParadisEO-EO

Important: This tutorial is only compatible with ParadisEO-1.1 and later.
All the source code of this lesson is located in the paradiseo-eo/tutorial/Lesson6 directory and the executable files are located in the paradiseo-eo/build/tutorial/Lesson6 directory.

Introduction

This lesson is quite similar to the other PSO-dedicated tutorial. Only the changes required to get a binary algorithm are presented in this page. If you have already practiced with it please read the next sections, otherwise we would advise you to start with: Implement a real-coded PSO algorithm using ParadisEO-EO.

Our binary example behaves almost as the real-coded one. Each position of the particles is now a bit initially set by a binary-dedicated component. The velocities remain "real" as it's the flight that translate them to obtain binary positions. That's the common way to proceed when using the PSO to tackle combinatorial optimization problem.


Objective function: minimize the number of "1" in a bit-string

This objective function is now declared as follows:

double binary_value (const Particle & _particle)
{
double sum = 0;
for (unsigned i = 0; i < _particle.size(); i++)
sum +=_particle[i];
return (sum);
}

and is embedded into a templatized eoEvalFuncPtr:

eoEvalFuncPtr<Particle, double, const Particle& > eval( binary_value );

Each particle represents a bit-string whose size is 10:


Binary representation

We just need to specify that we want to minimize:

typedef eoMinimizingFitness FitT;

And then let's set the type for the individual itself using the ready-to-use eoBitParticle:

typedef eoBitParticle < FitT > Particle;

The size of the bit-string (<=> the number of positions for one particle <=> the dimension) is set to 10:

const unsigned int VEC_SIZE = 10;


Initialization

The initial positions are chosen at random in {0,1} :

eoUniformGenerator<bool> uGen;
eoInitFixedLength < Particle > random (VEC_SIZE, uGen);
pop.append (POP_SIZE, random);


Flight: translate real velocities to binary positions

The positions are set depending on the velocity values using a sigmoid transformation, see eoSigBinaryFlight:

eoSigBinaryFlight <Particle> flight;

That's the only one implemented at the moment into ParadisEO. Feel free to send us any proposal.


Results

The rest of the components are the same as those ones implemented for the real-coded example (stopping criteria, velocity initialization, algorithm, bounds, outputs ....). Here are the results you should get when launching the program:

./BinaryPSO
INITIAL POPULATION:

         best fit=2  10 0 0 0 0 0 0 1 1 0 0
         best fit=3  10 1 0 0 0 0 1 0 0 0 1
         best fit=3  10 1 0 0 0 0 0 1 0 1 0
         best fit=4  10 0 0 1 0 0 1 0 0 1 1
         best fit=5  10 1 1 0 0 1 0 0 1 0 1
         best fit=5  10 1 1 1 0 0 0 1 0 0 1
         best fit=5  10 1 1 1 1 0 0 0 0 0 1
         best fit=5  10 1 0 0 1 1 1 0 1 0 0
         best fit=5  10 0 0 0 1 0 1 1 0 1 1
         best fit=6  10 1 1 0 1 0 1 1 1 0 0
         best fit=6  10 0 1 1 0 0 0 1 1 1 1
         best fit=6  10 1 1 0 1 1 1 0 1 0 0
         best fit=6  10 0 1 0 1 0 1 1 1 1 0
         best fit=6  10 1 0 0 1 0 1 1 1 1 0
         best fit=6  10 0 1 1 1 0 0 1 1 1 0
         best fit=6  10 1 1 0 1 0 0 1 1 1 0
         best fit=6  10 1 1 0 1 0 1 0 1 1 0
         best fit=6  10 1 0 1 1 0 1 0 1 1 0
         best fit=8  10 1 1 0 1 1 1 1 1 1 0
         best fit=8  10 1 1 1 0 1 1 1 1 0 1

STOP in eoGenContinue: Reached maximum number of generations [500/500] FINAL POPULATION:

         best fit=0  10 0 0 0 0 0 0 0 0 0 0
         best fit=0  10 0 0 0 0 0 0 0 0 0 0
         best fit=0  10 0 0 0 0 0 0 0 0 0 0
         best fit=0  10 0 0 0 0 0 0 0 0 0 0
         best fit=0  10 0 0 0 0 0 0 0 0 0 0
         best fit=0  10 0 0 0 0 0 0 0 0 0 0
         best fit=0  10 0 0 0 0 0 0 0 0 0 0
         best fit=0  10 0 0 0 0 0 0 0 0 0 0
         best fit=0  10 0 0 0 0 0 0 0 0 0 0
         best fit=0  10 0 0 0 0 0 0 0 0 0 0
         best fit=0  10 0 0 0 0 0 0 0 0 0 0
         best fit=0  10 0 0 0 0 0 0 0 0 0 0
         best fit=0  10 0 0 0 0 0 0 0 0 0 0
         best fit=0  10 0 0 0 0 0 0 0 0 0 0
         best fit=0  10 0 0 0 0 0 0 0 0 0 0
         best fit=0  10 0 0 0 0 0 0 0 0 0 0
         best fit=0  10 0 0 0 0 0 0 0 0 0 0
         best fit=0  10 0 0 0 0 0 0 0 0 0 0
         best fit=0  10 0 0 0 0 0 0 0 0 0 0
         best fit=1  10 1 0 0 0 0 0 0 0 0 0

Conclusion

Now you can customize you own binary PSO algorithm. If you'd like to contribute to ParadisEO (add a new binary flight, design new topologies) or for help, feel free to contact us at: paradiseo-help@lists.gforge.inria.fr.