Doc.TutoMOLesson7 History

Hide minor edits - Show changes to markup

August 19, 2010, at 03:18 PM by 193.49.212.125 -
Added line 2:
May 07, 2010, at 11:01 AM by ::1 -
Changed lines 2-5 from:

How to hybrid a evolutionary algorithm and a local search

In this lesson, a hybridization between an evolutionary algorithm(EA) and a local search is presented. It will illustrated by an example on the Queen problem. The mutation operator of the EA will be replace by a first improvement hill climber.

to:

How to hybrid an evolutionary algorithm and a local search

In this lesson, a hybridization between an evolutionary algorithm(EA) and a local search is presented. It will be illustrated by an example on the Queen problem. Here, the hybridization consists in replacing the mutation operator of the EA by a first improvement hill climber.

Changed line 10 from:

1. hybridization (example on the Queen problem)

to:

1. Hybridization (example on the Queen problem)

Changed line 13 from:

First you have to define the represenation of a Queen, how to initialize and eval a population of solutions:

to:

First, you have to define the represenation of a Queen, how to initialize and how to evaluate a population of solutions:

Changed line 28 from:

Like in previous lesson, a local search is declared (first improvement hill climber):

to:

As in previous lessons, a local search is declared (first improvement hill climber):

Changed line 37 from:

And to hybrid it with an EA, you just have to used it instead of a classical mutation:

to:

To hybrid this local search with an EA, you just have to use it instead of a classical mutation:

Changed lines 50-51 from:

Finally, the hybrid algorithm is declared:

to:

More details are available in EO lessons.

Finally, the hybrid algorithm is declared as:

Changed line 57 from:

Apply the algorithm on the population:

to:

and should be applied on the population with:

Changed line 62 from:

You can try it by changing problem size (use parameters file or the option --vecSize=X on command line to execute "hybridAlgo"). It prints the initial and final population.

to:

You can test this hybrid algorithm by changing problem size (use parameters file or the option --vecSize=X on command line to execute "hybridAlgo"). It prints the initial and final population.

May 07, 2010, at 10:25 AM by ::1 -
Added line 67:

Try to use a hybridization at the checkpointing step rather than at the mutation step. You have to implement an "eoUpdater" which applies a local search. This updater should be added in a "eoCheckpoint".

May 07, 2010, at 09:59 AM by ::1 -
Added lines 54-58:

Apply the algorithm on the population:

    hybridAlgo(pop);
May 06, 2010, at 05:57 PM by ::1 -
Changed line 40 from:
    eoSGATransform<Queen> transform(cross, 0.3, hc, 0.7); // cross and mutation probabilities are fixed
to:
    eoSGATransform<Queen> transform(cross, 0.3, hc, 0.7); // cross and mutation probabilities are fixed
Changed lines 45-47 from:
    eoGenContinue<Queen> EAcont(50); //nb generations is fixed to 50
    eoDetTournamentSelect<Queen> selectOne(2); //size of tournament is fixed to 2
    eoSelectMany<Queen> select(selectOne, 1); //rate of selection is fixed to 1
to:
    eoGenContinue<Queen> EAcont(50); //nb generations is fixed to 50
    eoDetTournamentSelect<Queen> selectOne(2); //size of tournament is fixed to 2
    eoSelectMany<Queen> select(selectOne, 1); //rate of selection is fixed to 1
May 06, 2010, at 05:56 PM by ::1 -
Changed line 21 from:
    for(unsigned int i=0; i<20; i++){ //population size is fixed to 20
to:
    for(unsigned int i=0; i<20; i++){ //population size is fixed to 20
May 06, 2010, at 05:56 PM by ::1 -
Changed line 21 from:
    for(unsigned int i=0; i<20; i++){ //population size is fixed to 20
to:
    for(unsigned int i=0; i<20; i++){ //population size is fixed to 20
May 06, 2010, at 05:56 PM by ::1 -
Changed line 21 from:
    for(unsigned int i=0; i<20; i++){ //population size is fixed to 20
to:
    for(unsigned int i=0; i<20; i++){ //population size is fixed to 20
May 06, 2010, at 05:55 PM by ::1 -
Changed line 21 from:
    for(unsigned int i=0; i<20; i++){ //population size is fixed to 20
to:
    for(unsigned int i=0; i<20; i++){ //population size is fixed to 20
May 06, 2010, at 05:55 PM by ::1 -
Changed line 21 from:
    for(unsigned int i=0; i<20; i++){
to:
    for(unsigned int i=0; i<20; i++){ //population size is fixed to 20
Changed line 40 from:
    eoSGATransform<Queen> transform(cross, 0.3, hc, 0.7);
to:
    eoSGATransform<Queen> transform(cross, 0.3, hc, 0.7); // cross and mutation probabilities are fixed
Changed lines 45-47 from:
    eoGenContinue<Queen> EAcont(50);
    eoDetTournamentSelect<Queen> selectOne(2);
    eoSelectMany<Queen> select(selectOne, 1);
to:
    eoGenContinue<Queen> EAcont(50); //nb generations is fixed to 50
    eoDetTournamentSelect<Queen> selectOne(2); //size of tournament is fixed to 2
    eoSelectMany<Queen> select(selectOne, 1); //rate of selection is fixed to 1
Deleted line 61:
  1. Try to implement and use a diversification strategy in 'testSimpleTS". You can also use a predifined strategy: moMonOpDiversification (in "memory" directory)
May 06, 2010, at 05:53 PM by ::1 -
Changed line 51 from:

Finally, the hyrid algorithm is declared:

to:

Finally, the hybrid algorithm is declared:

Added lines 55-56:

You can try it by changing problem size (use parameters file or the option --vecSize=X on command line to execute "hybridAlgo"). It prints the initial and final population.

May 06, 2010, at 05:47 PM by ::1 -
Changed line 53 from:
    eoEasyEA<Queen> hybridAlgo(EAcont, fullEval, select, transform, repl);
to:
    eoEasyEA<Queen> hybridAlgo(EAcont, fullEval, select, transform, repl);
May 06, 2010, at 05:46 PM by ::1 -
Changed line 40 from:
    eoSGATransform<Queen> transform(cross, 0.3, hc, 0.7);
to:
    eoSGATransform<Queen> transform(cross, 0.3, hc, 0.7);
May 06, 2010, at 05:45 PM by ::1 -
Deleted line 29:
Changed lines 34-35 from:
    moFirstImprHC<shiftNeighbor> hc(orderShiftNH, fullEval, shiftEval);
to:
    moFirstImprHC<shiftNeighbor> hc(orderShiftNH, fullEval, shiftEval);
Changed lines 37-43 from:

Let see the most simple constructor of a Tabu Search (in algo/moTS.h). You need five parameters:

  • a neighborhood
  • a full evaluation function (declared before)
  • a neighbor's evaluation function
  • a time limit for the search (in seconds)
  • a size for the tabu list
to:

And to hybrid it with an EA, you just have to used it instead of a classical mutation:

Changed lines 39-40 from:
    moFullEvalByCopy<shiftNeighbor> shiftEval(fullEval);
    orderShiftNeighborhood orderShiftNH(pow(vecSize-1, 2));
to:
    eoOrderXover<Queen> cross;
    eoSGATransform<Queen> transform(cross, 0.3, hc, 0.7);
Changed line 43 from:

You can now declare the Tabu Search:

to:

Others components of the "eoEasyEA" have to be declared:

Changed lines 45-48 from:
    moTS<shiftNeighbor> localSearch1(orderShiftNH, fullEval, shiftEval, 2, 7);
to:
    eoGenContinue<Queen> EAcont(50);
    eoDetTournamentSelect<Queen> selectOne(2);
    eoSelectMany<Queen> select(selectOne, 1);
    eoGenerationalReplacement<Queen> repl;
Changed lines 50-59 from:

This simple constructor uses by default seven components:

  • moTimeContinuator
  • moNeighborComparator
  • moSolNeighborComparator
  • moNeighborVectorTabuList
  • moDummyIntensification
  • moDummyDiversification
  • moBestImprAspiration

More flexible constructors exist in which you can change these components:

to:

Finally, the hyrid algorithm is declared:

Changed line 53 from:
    moTS<shiftNeighbor> localSearch2(orderShiftNH, fullEval, shiftEval, 3, tl);
to:
    eoEasyEA<Queen> hybridAlgo(EAcont, fullEval, select, transform, repl);
Deleted lines 54-65:

In this one, the tabuList has been specified.

    moTS<shiftNeighbor> localSearch3(orderShiftNH, fullEval, shiftEval,
        comparator, solComparator, continuator, tl, inten, div, asp);

And in this one, comparators, continuator, tabu list, intensification strategy, diversification strategy and aspiration criteria have been specified.

You can try the three algorithms by changing problem sizes, time limit and the size of tabu list (use parameter file or the option --vecSize=X, --timeLimit=Y and --sizeTabuList=Z on command line to execute "testSimpleTS"). It prints the initial and final solutions.

May 06, 2010, at 05:40 PM by ::1 -
Added line 30:
Added line 36:
May 06, 2010, at 05:39 PM by ::1 -
Changed line 28 from:

Then, you have to ramdomly intialize a solution:

to:

Like in previous lesson, a local search is declared (first improvement hill climber):

Changed lines 30-31 from:
    init(sol1);
    fullEval(sol1);
to:
    moFullEvalByCopy<shiftNeighbor> shiftEval(fullEval);

    orderShiftNeighborhood orderShiftNH(pow(vecSize-1, 2));

    moFirstImprHC<shiftNeighbor> hc(orderShiftNH, fullEval, shiftEval);
May 06, 2010, at 05:37 PM by ::1 -
Added lines 1-80: