- Main Page
- Classes
- Files

- File List

# OptFrame/Heuristic/EvolutionaryAlgorithms/GeneticAlgorithm.hpp

    00001 #ifndef OPTFRAME_GENETICALGORITHM_HPP_
    00002 #define OPTFRAME_GENETICALGORITHM_HPP_
    00003
    00004 #include <algorithm>
    00005
    00006 #include "../../Heuristic.hpp"
    00007
    00008 #include "../../Population.hpp"
    00009
    00010 #include "../../InitialPopulation.h"
    00011
    00012 #include "Crossover.hpp"
    00013
    00014 #include "Mutation.hpp"
    00015
    00016 #include "Selection.hpp"
    00017
    00018 #include "Elitism.hpp"
    00019
    00020 //#define DBG_GA
    00021
    00022 /*
    00023  * TODO
    00024  *
    00025  * Terminar de implementar as mensagens padrão que, no caso de estarem ativadas, devem ser impressas.
    00026  * Ex. Qdo melhora-se a melhor solução, deve-se imprimir uma mensagem.
    00027  *
    00028  */
    00029
    00030 /*
    00031  * TODO
    00032  *
    00033  * Criar um outro algoritmo genético que retorne apenas a melhor solução.
    00034  *
    00035  */
    00036
    00037 /*
    00038  * ToDo : Analisar critérios parada do algoritmo dado um tempo máximo de execução.
    00039  */
    00040
    00041 template<class R, class M>
    00042 class GeneticAlgorithm: public Heuristic<R, M>
    00043 {
    00044 protected:
    00045
    00046    typedef Solution<R> chromossome;
    00047
    00048    typedef vector<Evaluation<M>*> FitnessValues;
    00049
    00050    Evaluator<R, M>& evaluator;
    00051
    00052 private:
    00053
    00054    unsigned pSize;
    00055
    00056    double crossoverRate, mutationRate, elitismRate;
    00057
    00058    unsigned numGenerations;
    00059
    00060    InitialPopulation<R>& initPop;
    00061
    00062    Selection<R, M> *selection;
    00063
    00064    Crossover<R, M> *cross;
    00065
    00066    Mutation<R, M> *mut;
    00067
    00068    Elitism<R, M> *elt;
    00069
    00070 public:
    00071
    00072    GeneticAlgorithm(Evaluator<R, M>& _evaluator, InitialPopulation<R>& _initPop,
    00073          double crossoverRate, double mutationRate, double elitismRate, unsigned populationSize,
    00074          unsigned numGenerations, Selection<R, M>& _selection, Crossover<R, M>& _cross, Mutation<R,
    00075                M>& _mut, Elitism<R, M>& _elt) :
    00076       evaluator(_evaluator), initPop(_initPop), selection(&_selection), cross(&_cross), mut(&_mut),
    00077             elt(&_elt)
    00078    {
    00079 #ifdef DBG_GA
    00080       cout << "Genetic Algorithm constructor started .. .\n";
    00081 #endif
    00082
    00083       this->crossoverRate = crossoverRate;
    00084       this->mutationRate = mutationRate;
    00085       this->elitismRate = elitismRate;
    00086       pSize = populationSize;
    00087       this->numGenerations = numGenerations;
    00088
    00089 #ifdef DBG_GA
    00090       cout << "Genetic Algorithm was correctly initialized.. .\n";
    00091 #endif
    00092
    00093    }
    00094
    00095    virtual void evaluateFitness(const Population<R> &p, FitnessValues &fv) const
    00096    {
    00097       /*
    00098        * In the canonical genetic algorithm, fitness is defined by:
    00099        *
    00100        * fi/f
    00101        *
    00102        * where:
    00103        *
    00104        *    fi: is the evaluation associated with the i-th chromossome.
    00105        *    f: is the average population evaluation.
    00106        *
    00107        */
    00108
    00109       double sumEvals = 0;
    00110
    00111       for (int i = 0; i < p.size(); i++)
    00112       {
    00113          fv.push_back(&evaluator.evaluate(p.at(i)));
    00114          sumEvals += fv.at(i)->evaluation();
    00115       }
    00116
    00117       double avgEvalsPop = sumEvals / p.size();
    00118
    00119       for (int i = 0; i < p.size(); i++)
    00120       {
    00121          fv.at(i)->setObjFunction(fv.at(i)->evaluation() / avgEvalsPop);
    00122       }
    00123    }
    00124
    00125    // Means Sufficient OffSprings Created
    00126    virtual const unsigned suffOffCreated(const Population<R> &p) const
    00127    {
    00128       return p.size() / 2;
    00129    }
    00130
    00131    virtual pair<const chromossome&, const chromossome&>& selectParents(const Population<R> &p) const
    00132    {
    00133       unsigned p1 = rand() % (p.size());
    00134       unsigned p2 = p1;
    00135
    00136       while (p1 == p2)
    00137       {
    00138          p2 = rand() % (p.size());
    00139       }
    00140
    00141       return *new pair<const chromossome&, const chromossome&> (p.at(p1), p.at(p2));
    00142    }
    00143
    00144    void exec(Population<R> &p, double timelimit, double target_f)
    00145    {
    00146 #ifdef DBG_GA
    00147       cout << "GA exec(" << target_f << "," << timelimit << ")" << endl;
    00148 #endif
    00149
    00150       //long tini = time(NULL);
    00151
    00152       //long tnow = time(NULL);
    00153
    00154 #ifdef DBG_GA
    00155       cout << "Executing Genetic Algorithm with specified parameters:\n" << "Crossover Rate: "
    00156             << crossoverRate << endl << "Mutation Rate: " << mutationRate << endl
    00157             << "Elitism Rate: " << elitismRate << endl << "Population Size: " << p.size() << endl
    00158             << "Total of Generations: " << numGenerations << endl;
    00159
    00160       cout << "Generating the Initial Population .. .\n";
    00161 #endif
    00162
    00163       p = initPop.generatePopulation(pSize);
    00164
    00165 #ifdef DBG_GA
    00166       cout << "Initial Population successfully generated.\n";
    00167
    00168       cout << "Calculating the fitness of each chromossome from Initial Population.. .\n";
    00169 #endif
    00170
    00171       FitnessValues fv;
    00172       evaluateFitness(p, fv);
    00173
    00174 #ifdef DBG_GA
    00175       cout << "Fitness values calculated.\n";
    00176 #endif
    00177
    00178       chromossome* cStar = new chromossome(p.at(0));
    00179
    00180       unsigned g = 0;
    00181
    00182       unsigned suffIters = suffOffCreated(p);
    00183
    00184       //while (g < numGenerations && ((tnow - tini) < timelimit))
    00185       while (g < numGenerations)
    00186       {
    00187 #ifdef DBG_GA
    00188          cout << "GA generation: " << g << endl;
    00189 #endif
    00190
    00191 #ifdef DBG_GA
    00192          /*
    00193           cout << "Population in generation " << g << endl;
    00194
    00195           for (unsigned i = 0; i < p.size(); i++)
    00196           {
    00197           p.at(i).print();
    00198           cout << "Evaluation: " << (evaluator.evaluate((p.at(i)))).evaluation() << endl;
    00199           }
    00200
    00201           cout << endl;
    00202
    00203           */
    00204
    00205          /*
    00206           for (unsigned i = 0; i < populationSize; i++)
    00207           cout << (evaluator.evaluate(*(p.at(i)))).evaluation() << endl;
    00208           */
    00209 #endif
    00210
    00211          // ---
    00212
    00213          // Finding the best chromossome in the initial population.
    00214
    00215          unsigned pos_cStar = 0;
    00216          cStar = new chromossome(p.at(pos_cStar));
    00217
    00218          bool improved = false;
    00219
    00220          for (int i = 1; i < fv.size(); i++)
    00221          {
    00222             if (evaluator.betterThan(*fv.at(i), *fv.at(pos_cStar)))
    00223             {
    00224                pos_cStar = i;
    00225                improved = true;
    00226             }
    00227          }
    00228
    00229          if (improved)
    00230          {
    00231             delete cStar;
    00232             cStar = new chromossome(p.at(pos_cStar));
    00233          }
    00234
    00235          // ---
    00236          Population<R> p_elitist;
    00237          // ---
    00238
    00239          // Recalculating the number of best individuals (chromossomes) to carried to the next generation.
    00240          unsigned best_chromossomes_this_generation = elitismRate / 100 * p.size();
    00241
    00242          if (best_chromossomes_this_generation >= 1)
    00243          {
    00244 #ifdef DBG_GA
    00245             cout << "ELITISM\n";
    00246 #endif
    00247             p_elitist = elt->doElitism(p, fv, best_chromossomes_this_generation);
    00248          }
    00249
    00250          Population<R> intermediatePop;
    00251
    00252          unsigned iter = 0;
    00253
    00254          /*
    00255           *
    00256           *  ToDo : Corrigir a implementação do laço abaixo. Do jeito que está, sempre vão ser gerados
    00257           *  todos os individuos especificados pelo <suffIters>. Passando uma taxa de cross baixa, o que
    00258           *  vai acontecer é que o laço vai demorar mais para finalizar. Isso esta errado. Talvez seja necessário
    00259           *  criar versões específicas para as possibilidades de se realizar as operações de cross e mutação.
    00260           *
    00261           */
    00262          do
    00263          {
    00264             pair<const chromossome&, const chromossome&>& parents = selectParents(p);
    00265
    00266             pair<chromossome&, chromossome*>* offspring = NULL;
    00267
    00268             unsigned doCross = rand() % 101; // numbers 0 to 100
    00269
    00270             // Crossover condition
    00271             if (doCross < crossoverRate)
    00272             {
    00273 #ifdef DBG_GA
    00274                cout << " >> CROSSOVER";
    00275 #endif
    00276                offspring = &cross->offspring(parents);
    00277             }
    00278             else
    00279             {
    00280                continue;
    00281             }
    00282
    00283             // Mutation condition
    00284             unsigned doMut = rand() % 101; // numbers 0 to 100
    00285
    00286             if (doMut < mutationRate)
    00287             {
    00288 #ifdef DBG_GA
    00289                cout << ", MUTATION";
    00290 #endif
    00291                mut->mutate(offspring->first);
    00292
    00293                if (offspring->second)
    00294                {
    00295                   mut->mutate(*offspring->second);
    00296                }
    00297             }
    00298
    00299 #ifdef DBG_GA
    00300             cout << endl;
    00301 #endif
    00302
    00303             intermediatePop.push_back(offspring->first);
    00304
    00305             if (offspring->second)
    00306             {
    00307                intermediatePop.push_back(*offspring->second);
    00308                iter++;
    00309             }
    00310
    00311             iter++;
    00312
    00313          } while (iter < suffIters); // Suffient Offsprings created
    00314
    00315 #ifdef DBG_GA
    00316          cout << "Sufficient Offsprings created in generation " << g << endl;
    00317 #endif
    00318
    00319          FitnessValues fv_intPop;
    00320          evaluateFitness(intermediatePop, fv_intPop);
    00321
    00322 #ifdef DBG_GA
    00323          cout << "Intermediate Population Evaluated. " << endl;
    00324
    00325          cout << "SELECTION\n";
    00326 #endif
    00327
    00328          // The selection specified by the user can return a new population with different size (nb. of chromossomes).
    00329          Population<R> next_p = selection->select(p, fv, intermediatePop, fv_intPop,
    00330                best_chromossomes_this_generation);
    00331
    00332          if (!p_elitist.empty())
    00333          {
    00334             for (unsigned i = 0; i < p_elitist.size(); i++)
    00335             {
    00336                next_p.push_back(p_elitist.at(i));
    00337             }
    00338          }
    00339
    00340 #ifdef DBG_GA
    00341          cout << "Next Population Chosen and Evaluated." << endl;
    00342 #endif
    00343
    00344          // ---
    00345
    00346          // Checking the new population size.
    00347
    00348          bool break_it = false;
    00349
    00350          if (p.size() < next_p.size())
    00351          {
    00352             cout << "WARNNING: Population's size is increasing.\n";
    00353          }
    00354          else if (p.size() > next_p.size())
    00355          {
    00356             cout << "WARNNING: Population's size is decreasing.\n";
    00357
    00358             /*
    00359              *
    00360              *  When the population's size is decreasing, verify at each generation if the size reached size one.
    00361              *
    00362              *  If yes, break the two main loops.
    00363              *
    00364              */
    00365
    00366             if (next_p.size() == 1)
    00367             {
    00368                cout << "THIS EXECUTION WILL GO BREAK" << endl;
    00369                break_it = true;
    00370             }
    00371
    00372          }
    00373
    00374          // ---
    00375
    00376          for (int i = 0; i < fv.size(); i++)
    00377          {
    00378             delete fv.at(i);
    00379          }
    00380
    00381          fv.clear();
    00382
    00383          for (int i = 0; i < fv_intPop.size(); i++)
    00384          {
    00385             delete &intermediatePop.at(i);
    00386             delete fv_intPop.at(i);
    00387          }
    00388
    00389          intermediatePop.clear();
    00390          fv_intPop.clear();
    00391
    00392          p = next_p;
    00393
    00394          // Here, we have already past the unique solution to p. Then we stop the algorithm execution.
    00395          if (break_it)
    00396          {
    00397             break;
    00398          }
    00399
    00400          evaluateFitness(p, fv);
    00401
    00402          // ---
    00403
    00404          g++;
    00405
    00406          //tnow = time(NULL);
    00407
    00408       }
    00409
    00410       // Adding the best chromossome found in GA execution.
    00411       p.push_back(*cStar);
    00412
    00413 #ifdef DBG_GA
    00414       cout << "Best chromossome's evaluation found: " << (evaluator.evaluate(*(cStar))).evaluation() << endl;
    00415 #endif
    00416
    00417    }
    00418
    00419    void exec(Population<R> &p, FitnessValues &ev, double timelimit, double target_f)
    00420    {
    00421       exec(p, timelimit, target_f);
    00422    }
    00423
    00424 };
    00425
    00426 #endif /*OPTFRAME_GENETICALGORITHM_HPP_*/

All Classes Functions