src/GeneticReplication.cpp

Go to the documentation of this file.

/*
This file is part of Teapot Colony Wars.

Teapot Colony Wars is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 2 of the License, or
(at your option) any later version.

Teapot Colony Wars is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with Teapot Colony Wars.  If not, see <http://www.gnu.org/licenses/>.
*/

#include "GeneticReplication.h"

#include <map>
#include <list>

#include "Worshiper.h"
#include "Random.h"
#include "Constants.h"
#include "GeneticBehaviour.h"
#include "GeneticCode.h"

using namespace std;


GeneticReplication::GeneticReplication() : Replication() {}


unsigned int GeneticReplication::evaluation(Worshiper * w){
  return w->getFood();
}


GeneticReplication::~GeneticReplication() {}


list<Worshiper*>* GeneticReplication::getNewWorshipers(){
  //Clear the list
  _new_worshipers->clear();

  Worshiper * w = NULL;

  //The information sources : the survivors and the number of created worshipers
  unsigned int colonyFood = getFood();
  unsigned int nbWorshipers = _survivors.size();

  //If nobody (or not enough worshipers) has came back,
  //we create as many worshipers as we can
  if(nbWorshipers < 2){

    //While we have food, we spend it by creating randomized behaviours
    do {
      w = createWorshiper(new GeneticBehaviour); //NULL when not enough food
      if(w) {
        _new_worshipers->push_back(w);
      }
    } while (w && _new_worshipers->size() <= (MAX_WORSHIPER_PER_CELL * getNbCells()));

    //(Food may remain because the food quantity is randomized, but we save it)

  } else { //There are some survivors who came back

    //We select two survivors, and we cross them

    //Copy the map into a temp one
    map<GeneticCode*,unsigned int> temp(_survivors);

    //We iterate over the map and we add a random delta to each value,which can
    //be positive or negative (in [GENETIC_RANDOM_I, GENETIC_RANDOM_I[)
    unsigned int delta;
    map<GeneticCode*,unsigned int>::iterator it, end = temp.end();
    for(it = temp.begin(); it != end; ++it){
      delta = (Random::value() % GENETIC_RANDOM_I);
      if(Random::value() %2 == 0) it->second += delta;
      else {
        if(it->second > delta) it->second -= delta;
        else it->second = 0;
      }
    }

    //We select the two maximal individuals
    map<GeneticCode*,unsigned int>::iterator it_max1, it_max2;
    unsigned int max1 = 0, max2 = 0;
    for(it = temp.begin(); it != end; ++it){
      if(it->second >= max1){
        it_max1 = it;
        max1 = it->second;
      }
    }

    for(it = temp.begin(); it != end; ++it){
      if(it != it_max1 && it->second >= max2){
        it_max2 = it;
        max2 = it->second;
      }
    }

    //Crossover operation between the two best
    GeneticCode * c = it_max1->first->crossover(it_max2->first);

    //If the randomized number divisible by GENETIC_MUTATE_PROBA, a mutation occurs
    if((Random::value() % GENETIC_MUTATE_PROBA) == 0){
      c->mutate();
    }

    //The new worshiper is created and put into the _new_worshipers list
    Worshiper * w = createWorshiper(new GeneticBehaviour(c));
    if(w){
      _new_worshipers->push_back(w);
    }

    //We remove some individuals whose score are minimal
    //It ensures the population won't grow infinitly, and that we keep the best
    map<GeneticCode*,unsigned int>::iterator it_min;
    unsigned int min;
    while(_survivors.size() > GENETIC_MAX_SURVIVORS){
      min = max1;
      end = temp.end();
      for(it = temp.begin(); it != end; ++it){
        if(it->second <= min){
          it_min = it;
          min = it->second;
        }
      }

      //The individual is deleted...
      delete it_min->first;

      //...then removed in both the temp map and the survivors one
      _survivors.erase(it_min->first);
      temp.erase(it_min);
    }
  }

  return _new_worshipers;
}


Worshiper* GeneticReplication::createWorshiper(GeneticBehaviour * b){
  //Extract the information from the genetic code
  GeneticCode * code = b->getGeneticCode();
  return Replication::createWorshiper(code->getSize(),
                                      Random::value() % MAX_FOOD_CAPACITY,
                                      b);
}


void GeneticReplication::addSurvivor(Worshiper * w){
  //Copy the genetic code (so that the worshiper can be destroyed)
  GeneticBehaviour * b = (GeneticBehaviour *) w->getBehaviour();
  GeneticCode * gc = new GeneticCode(b->getGeneticCode());

  //Calculate the evaluation value and add the code to the survivors
   _survivors[gc] = evaluation(w);

  //Delete the worshiper
  delete w;
}

---