src/algorithm.h

   1 #ifndef __ALGORITHM_H
   2 #define __ALGORITHM_H
   3
   4 #include <iostream>
   5
   6 #include "chromosome.h"
   7 #include "generation.h"
   8 #include "fitness/fitness.h"
   9 #include "generator/generator.h"
  10 #include "selection/selection.h"
  11 #include "crossover/crossover.h"
  12 #include "mutation/mutation.h"
  13
  14 #include "condition/condition.h"
  15
  16 using namespace std;
  17
  18 namespace genetic {
  19     /**
  20      * Genetic Algorithm itself
  21      */
  22     template < typename _Chromosome, typename _Selection, typename _Crossover, typename _Mutation, typename _Fitness = Fitness<_Chromosome, typename _Selection::FitnessValueType > >
  23     class Algorithm {
  24     public:
  25         /**
  26          * Type representing Fitness value
  27          */
  28         typedef typename _Selection::FitnessValueType FitnessValueType;
  29     protected:
  30         /**
  31          * Generator which draws initial population
  32          */
  33         generator::Generator<_Chromosome>& generator;
  34
  35         /**
  36          * Fitness function used in selection
  37          *
  38          * It is a reference, because Fitness is purely virtual class and we
  39          * can't have instance of it. It must be one of derived classes.
  40          */
  41         _Fitness& fitness;
  42
  43         /**
  44          * Crossover function
  45          */
  46         _Crossover crossover;
  47
  48         /**
  49          * Mutation function
  50          */
  51         _Mutation mutation;
  52
  53         /**
  54          * Current population
  55          */
  56         Generation<_Chromosome> generation;
  57
  58         /**
  59          * Method invoked in each iteration of algorithm.
  60          *
  61          * Applies selection, crossover and mutation on each of the chromosomes
  62          * in generation.
  63          */
  64         void do_search() {
  65             _Selection selection(this->generation, fitness);
  66             this->generation = selection.draw();
  67             this->generation = crossover.cross(this->generation);
  68             this->generation = mutation.mutate(this->generation);
  69         }
  70     public:
  71         /**
  72          * Class constructor. Initializes class with values and breeds initial
  73          * population using passed generator::Generation.
  74          *
  75          * @param _generator Generator used to generate initial population
  76          * @param _fitness Fitness class used to check fitness of the chromosome
  77          * @param crossoverChance probability of crossover (0 = 0%, 1 = 100%)
  78          * @param mutationChance probability of fitness (0 = 0%, 1 = 100%)
  79          */
  80         Algorithm(
  81             generator::Generator<_Chromosome>& _generator,
  82            _Fitness& _fitness,
  83             double crossoverChance,
  84             double mutationChance) :
  85                 generator(_generator),
  86                 fitness(_fitness),
  87                 crossover(crossoverChance),
  88                 mutation(mutationChance) {
  89
  90             this->generation = this->generator.breed();
  91         }
  92
  93         /**
  94          * Starts Algorithm in search for result.
  95          * For each generation but initial, condition is checked, if algorithm
  96          * should stop.
  97          *
  98          * Displays separated by space: generation number, generation average
  99          * fitness and best chromosome fitness.
 100          *
 101          * @param condition Condition used to check after breeding new generation
 102          */
 103         void searchForResult(Condition<_Chromosome>& condition) {
 104             unsigned int i = 0;
 105             cout << "generation avg best\n";
 106             do {
 107                 cout << i;
 108                 do_search();
 109
 110 //                 cout << "New Generation:\n";
 111 //                 this->showGeneration();
 112                 this->showAvgFitness();
 113                 this->showBestFitness();
 114             } while(condition.check(this->generation) && ++i);
 115         }
 116
 117         /**
 118          * Displays entire generation.
 119          * \attention Method is currently not in use.
 120          */
 121         void showGeneration() {
 122             unsigned int generationSize = this->generation.size();
 123             unsigned int chromosomeSize = this->generation[0].size();
 124
 125             for (unsigned int i = 0; i < generationSize; i++) {
 126                 cout << "# " << i << ") ";
 127                 for (unsigned int j = 0; j < chromosomeSize; j++) {
 128                     cout << this->generation[i][j].get();
 129                 }
 130                 cout << "\n";
 131             }
 132         }
 133
 134         /**
 135          * Displays average fitness value of the entire generation.
 136          */
 137         void showAvgFitness() {
 138             double avg = 0;
 139             unsigned int generationSize = this->generation.size();
 140
 141             for (unsigned int i = 0; i < generationSize; i++) {
 142                 _Fitness fit(this->generation[i]);
 143                 fit.parseArguments(fitness.getArguments());
 144                 avg += fit.calculate();
 145             }
 146             cout << " " << avg / generationSize;
 147         }
 148
 149         /**
 150          * Displays best fitness value of the entire generation.
 151          */
 152         void showBestFitness() {
 153             double best = -100000;
 154             unsigned int generationSize = this->generation.size();
 155
 156             for (unsigned int i = 0; i < generationSize; i++) {
 157                 _Fitness fit(this->generation[i]);
 158                 fit.parseArguments(fitness.getArguments());
 159
 160                 double tmp = fit.calculate();
 161                 if (tmp > best) {
 162                     best = tmp;
 163                 }
 164             }
 165             cout << " " << best << endl;
 166         }
 167     };
 168 }
 169
 170 #endif /* __ALGORITHM_H */