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