# ParadisEO-MOEOMovingObjects: moeoIBMOLS.h Source File

# moeoIBMOLS.h

    00001 // -*- mode: c++; c-indent-level: 4; c++-member-init-indent: 8; comment-column: 35; -*-
    00002
    00003 //-----------------------------------------------------------------------------
    00004 // moeoIBMOLS.h
    00005 // (c) OPAC Team (LIFL), Dolphin Project (INRIA), 2007
    00006 /*
    00007     This library...
    00008
    00009     Contact: paradiseo-help@lists.gforge.inria.fr, http://paradiseo.gforge.inria.fr
    00010  */
    00011 //-----------------------------------------------------------------------------
    00012
    00013 #ifndef MOEOIBMOLS_H_
    00014 #define MOEOIBMOLS_H_
    00015
    00016 #include <math.h>
    00017 #include <eoContinue.h>
    00018 #include <eoEvalFunc.h>
    00019 #include <eoPop.h>
    00020 #include <moMove.h>
    00021 #include <moMoveInit.h>
    00022 #include <moNextMove.h>
    00023 #include <algo/moeoLS.h>
    00024 #include <archive/moeoArchive.h>
    00025 #include <fitness/moeoBinaryIndicatorBasedFitnessAssignment.h>
    00026 #include <move/moeoMoveIncrEval.h>
    00027
    00032 template < class MOEOT, class Move >
    00033 class moeoIBMOLS : public moeoLS < MOEOT, eoPop < MOEOT > & >
    00034 {
    00035 public:
    00036
    00038     typedef typename MOEOT::ObjectiveVector ObjectiveVector;
    00039
    00040
    00050     moeoIBMOLS(
    00051         moMoveInit < Move > & _moveInit,
    00052         moNextMove < Move > & _nextMove,
    00053         eoEvalFunc < MOEOT > & _eval,
    00054         moeoMoveIncrEval < Move > & _moveIncrEval,
    00055         moeoBinaryIndicatorBasedFitnessAssignment < MOEOT > & _fitnessAssignment,
    00056         eoContinue < MOEOT > & _continuator
    00057     ) :
    00058             moveInit(_moveInit),
    00059             nextMove(_nextMove),
    00060             eval(_eval),
    00061             moveIncrEval(_moveIncrEval),
    00062             fitnessAssignment (_fitnessAssignment),
    00063             continuator (_continuator)
    00064     {}
    00065
    00066
    00073     void operator() (eoPop < MOEOT > & _pop, moeoArchive < MOEOT > & _arch)
    00074     {
    00075         // evaluation of the objective values
    00076         /*
    00077                 for (unsigned int i=0; i<_pop.size(); i++)
    00078                 {
    00079                     eval(_pop[i]);
    00080                 }
    00081         */
    00082         // fitness assignment for the whole population
    00083         fitnessAssignment(_pop);
    00084         // creation of a local archive
    00085         moeoArchive < MOEOT > archive;
    00086         // creation of another local archive (for the stopping criteria)
    00087         moeoArchive < MOEOT > previousArchive;
    00088         // update the archive with the initial population
    00089         archive.update(_pop);
    00090         do
    00091         {
    00092             previousArchive.update(archive);
    00093             oneStep(_pop);
    00094             archive.update(_pop);
    00095         } while ( (! archive.equals(previousArchive)) && (continuator(_arch)) );
    00096         _arch.update(archive);
    00097     }
    00098
    00099
    00100 private:
    00101
    00103     moMoveInit < Move > & moveInit;
    00105     moNextMove < Move > & nextMove;
    00107     eoEvalFunc < MOEOT > & eval;
    00109     moeoMoveIncrEval < Move > & moveIncrEval;
    00111     moeoBinaryIndicatorBasedFitnessAssignment < MOEOT > & fitnessAssignment;
    00113     eoContinue < MOEOT > & continuator;
    00114
    00115
    00120     void oneStep (eoPop < MOEOT > & _pop)
    00121     {
    00122         // the move
    00123         Move move;
    00124         // the objective vector and the fitness of the current solution
    00125         ObjectiveVector x_objVec;
    00126         double x_fitness;
    00127         // the index, the objective vector and the fitness of the worst solution in the population (-1 implies that the worst is the newly created one)
    00128         int worst_idx;
    00129         ObjectiveVector worst_objVec;
    00130         double worst_fitness;
    00132         // the indexes and the objective vectors of the extreme non-dominated points
    00133         int ext_0_idx, ext_1_idx;
    00134         ObjectiveVector ext_0_objVec, ext_1_objVec;
    00135         unsigned int ind;
    00137         // the index of the current solution to be explored
    00138         unsigned int i=0;
    00139         // initilization of the move for the first individual
    00140         moveInit(move, _pop[i]);
    00141         while (i<_pop.size() && continuator(_pop))
    00142         {
    00143             // x = one neigbour of pop[i]
    00144             // evaluate x in the objective space
    00145             x_objVec = moveIncrEval(move, _pop[i]);
    00146             // update every fitness values to take x into account and compute the fitness of x
    00147             x_fitness = fitnessAssignment.updateByAdding(_pop, x_objVec);
    00148
    00152                         // extreme solutions (min only!)
    00153             ext_0_idx = -1;
    00154             ext_0_objVec = x_objVec;
    00155             ext_1_idx = -1;
    00156             ext_1_objVec = x_objVec;
    00157             for (unsigned int k=0; k<_pop.size(); k++)
    00158             {
    00159                 // ext_0
    00160                 if (_pop[k].objectiveVector()[0] < ext_0_objVec[0])
    00161                 {
    00162                     ext_0_idx = k;
    00163                     ext_0_objVec = _pop[k].objectiveVector();
    00164                 }
    00165                 else if ( (_pop[k].objectiveVector()[0] == ext_0_objVec[0]) && (_pop[k].objectiveVector()[1] < ext_0_objVec[1]) )
    00166                 {
    00167                     ext_0_idx = k;
    00168                     ext_0_objVec = _pop[k].objectiveVector();
    00169                 }
    00170                 // ext_1
    00171                 else if (_pop[k].objectiveVector()[1] < ext_1_objVec[1])
    00172                 {
    00173                     ext_1_idx = k;
    00174                     ext_1_objVec = _pop[k].objectiveVector();
    00175                 }
    00176                 else if ( (_pop[k].objectiveVector()[1] == ext_1_objVec[1]) && (_pop[k].objectiveVector()[0] < ext_1_objVec[0]) )
    00177                 {
    00178                     ext_1_idx = k;
    00179                     ext_1_objVec = _pop[k].objectiveVector();
    00180                 }
    00181             }
    00182                         // worst init
    00183             if (ext_0_idx == -1)
    00184             {
    00185                 ind = 0;
    00186                 while (ind == ext_1_idx)
    00187                 {
    00188                     ind++;
    00189                 }
    00190                 worst_idx = ind;
    00191                 worst_objVec = _pop[ind].objectiveVector();
    00192                 worst_fitness = _pop[ind].fitness();
    00193             }
    00194             else if (ext_1_idx == -1)
    00195             {
    00196                 ind = 0;
    00197                 while (ind == ext_0_idx)
    00198                 {
    00199                     ind++;
    00200                 }
    00201                 worst_idx = ind;
    00202                 worst_objVec = _pop[ind].objectiveVector();
    00203                 worst_fitness = _pop[ind].fitness();
    00204             }
    00205             else
    00206             {
    00207                 worst_idx = -1;
    00208                 worst_objVec = x_objVec;
    00209                 worst_fitness = x_fitness;
    00210             }
    00214
    00215             // who is the worst ?
    00216             for (unsigned int j=0; j<_pop.size(); j++)
    00217             {
    00218                 if ( (j!=ext_0_idx) && (j!=ext_1_idx) )
    00219                 {
    00220                     if (_pop[j].fitness() < worst_fitness)
    00221                     {
    00222                         worst_idx = j;
    00223                         worst_objVec = _pop[j].objectiveVector();
    00224                         worst_fitness = _pop[j].fitness();
    00225                     }
    00226                 }
    00227             }
    00228             // if the worst solution is the new one
    00229             if (worst_idx == -1)
    00230             {
    00231                 // if all its neighbours have been explored,
    00232                 // let's explore the neighborhoud of the next individual
    00233                 if (! nextMove(move, _pop[i]))
    00234                 {
    00235                     i++;
    00236                     if (i<_pop.size())
    00237                     {
    00238                         // initilization of the move for the next individual
    00239                         moveInit(move, _pop[i]);
    00240                     }
    00241                 }
    00242             }
    00243             // if the worst solution is located before _pop[i]
    00244             else if (worst_idx <= i)
    00245             {
    00246                 // the new solution takes place insteed of _pop[worst_idx]
    00247                 _pop[worst_idx] = _pop[i];
    00248                 move(_pop[worst_idx]);
    00249                 _pop[worst_idx].objectiveVector(x_objVec);
    00250                 _pop[worst_idx].fitness(x_fitness);
    00251                 // let's explore the neighborhoud of the next individual
    00252                 i++;
    00253                 if (i<_pop.size())
    00254                 {
    00255                     // initilization of the move for the next individual
    00256                     moveInit(move, _pop[i]);
    00257                 }
    00258             }
    00259             // if the worst solution is located after _pop[i]
    00260             else if (worst_idx > i)
    00261             {
    00262                 // the new solution takes place insteed of _pop[i+1] and _pop[worst_idx] is deleted
    00263                 _pop[worst_idx] = _pop[i+1];
    00264                 _pop[i+1] = _pop[i];
    00265                 move(_pop[i+1]);
    00266                 _pop[i+1].objectiveVector(x_objVec);
    00267                 _pop[i+1].fitness(x_fitness);
    00268                 // let's explore the neighborhoud of the individual _pop[i+2]
    00269                 i += 2;
    00270                 if (i<_pop.size())
    00271                 {
    00272                     // initilization of the move for the next individual
    00273                     moveInit(move, _pop[i]);
    00274                 }
    00275             }
    00276             // update fitness values
    00277             fitnessAssignment.updateByDeleting(_pop, worst_objVec);
    00278         }
    00279     }
    00280
    00281
    00282
    00283
    00284
    00285
    00286
    00287
    00288
    00289
    00290
    00291
    00292
    00293 // INUTILE !!!!
    00294
    00295
    00296
    00297
    00298
    00299
    00304     void new_oneStep (eoPop < MOEOT > & _pop)
    00305     {
    00306         // the move
    00307         Move move;
    00308         // the objective vector and the fitness of the current solution
    00309         ObjectiveVector x_objVec;
    00310         double x_fitness;
    00311         // the index, the objective vector and the fitness of the worst solution in the population (-1 implies that the worst is the newly created one)
    00312         int worst_idx;
    00313         ObjectiveVector worst_objVec;
    00314         double worst_fitness;
    00316         // the index of the extreme non-dominated points
    00317         int ext_0_idx, ext_1_idx;
    00318         unsigned int ind;
    00320         // the index current of the current solution to be explored
    00321         unsigned int i=0;
    00322         // initilization of the move for the first individual
    00323         moveInit(move, _pop[i]);
    00324         while (i<_pop.size() && continuator(_pop))
    00325         {
    00326             // x = one neigbour of pop[i]
    00327             // evaluate x in the objective space
    00328             x_objVec = moveIncrEval(move, _pop[i]);
    00329             // update every fitness values to take x into account and compute the fitness of x
    00330             x_fitness = fitnessAssignment.updateByAdding(_pop, x_objVec);
    00331
    00335                         // extremes solutions
    00336             OneObjectiveComparator comp0(0);
    00337             ext_0_idx = std::min_element(_pop.begin(), _pop.end(), comp0) - _pop.begin();
    00338             OneObjectiveComparator comp1(1);
    00339             ext_1_idx = std::min_element(_pop.begin(), _pop.end(), comp1) - _pop.begin();
    00340                         // new = extreme ?
    00341             if (x_objVec[0] < _pop[ext_0_idx].objectiveVector()[0])
    00342             {
    00343                 ext_0_idx = -1;
    00344             }
    00345             else if ( (x_objVec[0] == _pop[ext_0_idx].objectiveVector()[0]) && (x_objVec[1] < _pop[ext_0_idx].objectiveVector()[1]) )
    00346             {
    00347                 ext_0_idx = -1;
    00348             }
    00349             else if (x_objVec[1] < _pop[ext_1_idx].objectiveVector()[1])
    00350             {
    00351                 ext_1_idx = -1;
    00352             }
    00353             else if ( (x_objVec[1] == _pop[ext_1_idx].objectiveVector()[1]) && (x_objVec[0] < _pop[ext_1_idx].objectiveVector()[0]) )
    00354             {
    00355                 ext_1_idx = -1;
    00356             }
    00357             // worst init
    00358             if (ext_0_idx == -1)
    00359             {
    00360                 ind = 0;
    00361                 while (ind == ext_1_idx)
    00362                 {
    00363                     ind++;
    00364                 }
    00365                 worst_idx = ind;
    00366                 worst_objVec = _pop[ind].objectiveVector();
    00367                 worst_fitness = _pop[ind].fitness();
    00368             }
    00369             else if (ext_1_idx == -1)
    00370             {
    00371                 ind = 0;
    00372                 while (ind == ext_0_idx)
    00373                 {
    00374                     ind++;
    00375                 }
    00376                 worst_idx = ind;
    00377                 worst_objVec = _pop[ind].objectiveVector();
    00378                 worst_fitness = _pop[ind].fitness();
    00379             }
    00380             else
    00381             {
    00382                 worst_idx = -1;
    00383                 worst_objVec = x_objVec;
    00384                 worst_fitness = x_fitness;
    00385             }
    00389
    00390             // who is the worst ?
    00391             for (unsigned int j=0; j<_pop.size(); j++)
    00392             {
    00393                 if ( (j!=ext_0_idx) && (j!=ext_1_idx) )
    00394                 {
    00395                     if (_pop[j].fitness() < worst_fitness)
    00396                     {
    00397                         worst_idx = j;
    00398                         worst_objVec = _pop[j].objectiveVector();
    00399                         worst_fitness = _pop[j].fitness();
    00400                     }
    00401                 }
    00402             }
    00403             // if the worst solution is the new one
    00404             if (worst_idx == -1)
    00405             {
    00406                 // if all its neighbours have been explored,
    00407                 // let's explore the neighborhoud of the next individual
    00408                 if (! nextMove(move, _pop[i]))
    00409                 {
    00410                     i++;
    00411                     if (i<_pop.size())
    00412                     {
    00413                         // initilization of the move for the next individual
    00414                         moveInit(move, _pop[i]);
    00415                     }
    00416                 }
    00417             }
    00418             // if the worst solution is located before _pop[i]
    00419             else if (worst_idx <= i)
    00420             {
    00421                 // the new solution takes place insteed of _pop[worst_idx]
    00422                 _pop[worst_idx] = _pop[i];
    00423                 move(_pop[worst_idx]);
    00424                 _pop[worst_idx].objectiveVector(x_objVec);
    00425                 _pop[worst_idx].fitness(x_fitness);
    00426                 // let's explore the neighborhoud of the next individual
    00427                 i++;
    00428                 if (i<_pop.size())
    00429                 {
    00430                     // initilization of the move for the next individual
    00431                     moveInit(move, _pop[i]);
    00432                 }
    00433             }
    00434             // if the worst solution is located after _pop[i]
    00435             else if (worst_idx > i)
    00436             {
    00437                 // the new solution takes place insteed of _pop[i+1] and _pop[worst_idx] is deleted
    00438                 _pop[worst_idx] = _pop[i+1];
    00439                 _pop[i+1] = _pop[i];
    00440                 move(_pop[i+1]);
    00441                 _pop[i+1].objectiveVector(x_objVec);
    00442                 _pop[i+1].fitness(x_fitness);
    00443                 // let's explore the neighborhoud of the individual _pop[i+2]
    00444                 i += 2;
    00445                 if (i<_pop.size())
    00446                 {
    00447                     // initilization of the move for the next individual
    00448                     moveInit(move, _pop[i]);
    00449                 }
    00450             }
    00451             // update fitness values
    00452             fitnessAssignment.updateByDeleting(_pop, worst_objVec);
    00453         }
    00454     }
    00455
    00456
    00457
    00458
    00459
    00460
    00462 class OneObjectiveComparator : public moeoComparator < MOEOT >
    00463     {
    00464     public:
    00465         OneObjectiveComparator(unsigned int _obj) : obj(_obj)
    00466         {
    00467             if (obj > MOEOT::ObjectiveVector::nObjectives())
    00468             {
    00469                 throw std::runtime_error("Problem with the index of objective in OneObjectiveComparator");
    00470             }
    00471         }
    00472         const bool operator()(const MOEOT & _moeo1, const MOEOT & _moeo2)
    00473         {
    00474             if (_moeo1.objectiveVector()[obj] < _moeo2.objectiveVector()[obj])
    00475             {
    00476                 return true;
    00477             }
    00478             else
    00479             {
    00480                 return (_moeo1.objectiveVector()[obj] == _moeo2.objectiveVector()[obj]) && (_moeo1.objectiveVector()[(obj+1)%2] < _moeo2.objectiveVector()[(obj+1)%2]);
    00481             }
    00482         }
    00483     private:
    00484         unsigned int obj;
    00485     };
    00487
    00488
    00489
    00490
    00491 };
    00492
    00493 #endif /*MOEOIBMOLS_H_*/