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.
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.
A schematic representation of an arbitrary topological model with migrations between the islands is offered bellow:
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.
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
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.