ParadisEO - PEO Lesson 1: Multistart over a MO, Packing and Unpacking

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

This lesson will teach you how to start several MO metaheuristics from different initial solutions. Thanks to PEO, these algorithms are run on differents processes leading to a drastic gain of computation time. That is what we refer to as a multistart MO.

Requirements

Now you are supposed to have implemented a sequential MO program that you want to run on parallel. It is usefull to stress on that your programs should have been tested thouroughly and memory leak freed. Otherwise, you might encounter many problems in executing your MPI program.

Implementation

Before giving an example of use, we will show you the skeleton of an MPI program under ParadisEO-PEO.

#include <peo>
    .
    .  Common part to all processes
    .

    peo :: init (__argc, __argv); initialisation of the MPI environment

    .
    .  Specific part treated by each process
    .

    peo :: run( ); Run the MPI program
    peo :: finalize( ); Terminate the MPI program

Let us recall what has been done in the QAP-MO lesson?. This bit of the program is exactly the same as in that lesson.

Initialization of the local search

  MoveInit move_init;
  ProblemEval problem_eval;  
  MoveNext move_next;
  MoveIncrEval move_incr_eval;
  moBestImprSelect<Move> move_select;
  moSimpleMoveTabuList <Move> tabulist (param.tabuListSize);
  moImprBestFitAspirCrit <Move> aspiration_criterion;
  moGenSolContinue <Problem> continu (param.TSmaxIter);
  moTS <Move> tabu_search (move_init, move_next, move_incr_eval, 
			   tabulist, aspiration_criterion, continu, problem_eval );

Since a multistart is a simple run of different initial solutions on different processes, it is needed then to create a population of initial solutions. Consequently, we must add the definitions of creating and initializing a population.

Initialization of the Population

  ProblemInit chromInit;
  eoPop <Problem> pop (POP_SIZE, chromInit);

Definition of ProblemInit can be found at QAP-EO lesson?. Now we are almost ready to launch the execution of our program. We need to add the simple few lines

Launching the parallel local search

    peo :: init (__argc, __argv);

    peoMultiStart <Problem> initParallelTS (tabu_search);
    peoWrapper parallelTS (initParallelTS, pop);
    initParallelTS.setOwner(parallelTS);

    peo :: run( );
    peo :: finalize( );

Please refer to the API documentation for more details on every component. We are now one step from running our program. Indeed, if you try to compile your code at this step, your compiler would probably complain about not knowing how to pack and unpack the problem in hand. That is because, the ParadisEO framework offers the pack and unpack operations on the basic types. Indeed, ParadisEO does not know your class and would not know how to pack and unpack it. This is then left to the programer who knows on what consists his class. In our case, we have to pack and unpack a QAP class. This latter contains only an array of integers. The corresponding pack and unpack methods can be written this way:

void pack( const Problem& _problem ) {

  if ( _problem.invalid() ) 
    pack( (unsigned int)0 );
  else
    {
      pack( (unsigned int)1 );
      pack(_problem.fitness());
    }

  for (int i = 0; i < n; i++ )
    {
      pack( _problem.solution[i] );
    }

}

void unpack( Problem& _problem ) {

  unsigned int validFitness;

  unpack( validFitness );
  if ( validFitness )
    {
      double fitnessValue;
      unpack( fitnessValue );
      _problem.fitness( fitnessValue );    
    }
  else
    {
      _problem.invalidate();
    }

  for (int i = 0; i < n; i++ )
    {
      unpack(_problem[i]);
    }

}

It is quite straightforward to understand this packing and unpacking methods. When packing, we first pack 1 or 0 depending whether the solution is valid or not, and then, pack the elements of the array. Unpacking is merely the inverse operation. We unpack the first element that indicates if the solution is valid or not and then proceed with unpacking the array.

Launching the program

At this point of this tutorial, you are ready to compile your program. You can use the already distributed makefile or generate one for yourself. Once this is done, to run your program please refer to the technical introduction.