Doc.TutoPEOLesson5 History

Hide minor edits - Show changes to markup

August 19, 2010, at 03:31 PM by 193.49.212.125 -

Added lines 1-2:

Restore

June 24, 2010, at 03:14 PM by ::1 -

Deleted lines 114-122:

Other lessons

Technical introduction ?
PEO Lesson 1 ?
PEO Lesson 2 ?
PEO Lesson 3 ?
PEO Lesson 4 ?
PEO Lesson 5
PEO Lesson 6 ?\\

Restore

May 28, 2010, at 04:46 PM by ::1 -

Added lines 1-123:

ParadisEO - PEO Lesson 5: Island model

Note: All the components are not presented in this lesson (binary, topology, asynchronous or synchronous... ). To know the completeness of components refer to API documentation of ParadisEO-EO and ParadisEO-PEO.

Introduction

The need to speed up the runtime of evolutionary algorithms (EA) drove towards a model of parallelism called island model. This means that we are running several EAs on different machines. It could be viewed like a multi start on an EA, however there is a fundamental change.

In a multi start model we merely run our EA on different populations and then wait for the results hoping that one of the EAs would get better results. No exchange of useful information is considered.

The island model steps in by modifying this behaviour. With the island model, we need to specify a topology linking between the different "islands", a number of individual to exchange and a policy of exchange.

This model is of particular interest as the computation on grids are more common nowadays. We can imagine a hundred of nodes on a grid on which we run an individual EA. Then, useful information could be exchanged to get better results but also fast convergence.

Explanations

A schematic representation of an arbitrary topological model with migrations between the islands is offered bellow:

http://paradiseo.gforge.inria.fr/img/islands.png%%

Let's consider the following scenario emigrations/immigrations should occur at every ten generations. In addition we would like to have control on selecting the individuals to emigrate as well as on the replacement process of the current individuals with the immigrant ones. In other words, constructing an insular migration model consists in (1) having a ring topological model including several evolutionary algorithms (2) defining the migration frequency as well as the size of the migration (i.e. the number of individuals that emigrate) and (3) the selection and replacement strategies or the velocity strategy.

Requirements

Before to start this lesson 5, you should read and execute Lesson4 ?. Of course, to execute the lesson 5, you should be in the directory of this lesson.

Implementation

Let us assume we have three islands. Here is an example of an asynchronous migration with an EA.

Define the topology of your island model

  RingTopology topology;

Main algorithm

  Common part to all islands

  ProblemEvalFunc plainEval;
  eoEvalFuncCounter<Problem> eval(plainEval);
  ProblemInit chromInit;  
  eoDetTournamentSelect<Problem> selectOne(param.tSize);
  eoSelectPerc<Problem> select(selectOne);
  ProblemXover Xover;
  ProblemSwapMutation  mutationSwap;
  eoSGATransform<Problem> transform(Xover, param.pCross, mutationSwap, param.pMut);
  eoPlusReplacement<Problem> replace;
  eoGenContinue<Problem> genCont(param.maxGen);

  Island 1

  eoPop<Problem> pop_1(param.popSize, chromInit);
  eoCheckPoint< Problem > checkpoint_1( genCont );
  eoEasyEA<Problem> gga_1(checkpoint_1, plainEval, select, transform, replace);

  Island 2

  eoPop<Problem> pop_2(param.popSize, chromInit);
  eoCheckPoint< Problem > checkpoint_2( genCont );
  eoEasyEA<Problem> gga_2(checkpoint_2, plainEval, select, transform, replace);

  Island 3

  eoPop<Problem> pop_3(param.popSize, chromInit);
  eoCheckPoint< Problem > checkpoint_3( genCont );
  eoEasyEA<Problem> gga_3(checkpoint_3, plainEval, select, transform, replace);

  Start MPI environment
  peo :: init (argc, argv);

  (*)Define an asynchronous island

    Continuation
     eoPeriodicContinue< Problem > mig_conti_1(  param.manGeneration );
     eoContinuator<Problem> mig_cont_1(mig_conti_1,pop_1);

    Selection
     eoRandomSelect<Problem> mig_select_one_1;
     eoSelector <Problem, eoPop<Problem> > mig_select_1 (mig_select_one_1,param.nbMigrants,pop_1);

    Replacement
     eoPlusReplacement<Problem> replace_one_1;
     eoReplace <Problem, eoPop<Problem> > mig_replace_1 (replace_one_1,pop_1);

    Island
     peoAsyncIslandMig< eoPop< Problem >, eoPop< Problem > > mig_1(mig_cont_1,mig_select_1,
                                                mig_replace_1,topology);
     checkpoint_1.add( mig_1 );

  Repeat the step (*) for each island meaning that, in our case, we are going to do it three times

  Wrap the EA
  peoWrapper parallelEA_1( gga_1, pop_1);
  mig_1.setOwner(parallelEA_1);
  peoWrapper parallelEA_2( gga_2, pop_2);
  mig_2.setOwner(parallelEA_2);
  peoWrapper parallelEA_3( gga_3, pop_3);
  mig_3.setOwner(parallelEA_3);

  Run the EAs
  peo :: run( );
  End MPI environment
  peo :: finalize( );

Launching the program

You can now go ahead and run the program included on island model.

Other lessons

Technical introduction ?
PEO Lesson 1 ?
PEO Lesson 2 ?
PEO Lesson 3 ?
PEO Lesson 4 ?
PEO Lesson 5
PEO Lesson 6 ?\\

Restore