void runNgenerations(int nbGenerations){
        int size = int(population.size());

        int itmp = 0;
        for (int i = 0; i<nbGenerations; i++){
            // sélection des meilleurs éléments
            std::set<individual> toMutate;
            selectIndividuals( int(size /1.5), toMutate);

            // croisements / mutations
            std::set<individual> mutated;
            mutate(toMutate, .4, mutated);

            std::set<individual> toCross;
            selectIndividuals( size /2, toCross);

            std::set<individual> crossed;
            cross(toCross, .8, crossed);

            // insertion dans population
            injectIntoPopulation(mutated);
            injectIntoPopulation(crossed);

            troncatePopulation(size);

            individual &tmp = *population.begin();
            std::cout << i << " " << tmp.fitness << " " << tmp.display() << std::endl;               
        }
    }
        

void injectIntoPopulation(std::set<individual>& l){
        for (std::set<individual>::iterator i = l.begin(); i != l.end(); i++)
                population.insert(*i);
       
    }

    void troncatePopulation(int n){
        int nbFound = 0;
        std::set<individual>::iterator i = population.begin();
        while (i != population.end() && nbFound < n){
            i++;
            nbFound++;
        }
        
        if (i != population.end())
            population.erase(i, population.end());
    }

    void selectIndividuals(int nbToSelect, std::set<individual>& selected){       
        int globalSum = 0;

        std::set<individual>::iterator it = population.end(); it--;
        int maxFitness = it->fitness;

        for (std::set<individual>::iterator i = population.begin(); i!=population.end(); i++)
            globalSum += maxFitness  - i->fitness;    // inversion du sens des fitness

        std::set<individual>::iterator ii = population.begin();
        // conservation des 5 meilleurs individus
        for (int i=0; i<5; i++, ii++)
            selected.insert(*ii);   

		// roulettes de sélection
        for (int i = 0; i<nbToSelect ; i++){
            int found = rand()%globalSum;
            int a=0;
            std::set<individual>::iterator ite = population.begin();
            a += maxFitness  - ite->fitness;
           
            while (a<found){
                ite++;
                a += maxFitness  - ite->fitness;
            }

            if (selected.find(*ite) == selected.end())
                selected.insert(*ite);
        }
    }

        std::set<individual>::iterator ii = population.begin();
        for (int i=0; i<nbToSelect; i++){
            ii++;
            selected.insert(*ii);      
        }

   
void individual::createRandomly(){
    int nbValues = int(data.distances.size());

    // on commence à la position 0
    solution.push_back(0);
    std::vector<int> remainingPossibilities;
    for (int i=1; i<nbValues; i++)
        remainingPossibilities.push_back(i);

    int a=1;

	// on recherche les villes suivantes
    while (a < nbValues){
        solution.push_back(data.selectNearCity(a));
        a++;
    }

	// on rend la solution cohérente avec le problème
    makeCoherent();

    calculateQuality();
}

class problem{
public:  
    problem(int);
    int selectNearCity(int);

    std::vector<std::vector<int> > distances;

protected:
    std::vector< std::map<int, int> > dual;
    std::vector< int > maxDistances;
    std::vector<int > globalSums;
};

int problem::selectNearCity(int from){
    int f = rand()%globalSums[from];
    int i = 0;
    std::map<int, int>::iterator it = dual[from].begin();
    i += maxDistances[from] - it->first;
    
    // roulette de sélection
	while (i<f && it!=dual[from].end()){
        i += maxDistances[from] - it->first;
        it++;
    }

	if (it == dual[from].end())
		return dual[from][ int(dual[from].size()-1) ];

    return it->second;
}

class individual{
public:
    individual(problem &);    // constructeur à partir du jeu de données
    individual(const individual&);
    individual& operator =(const individual&);
    ~individual();

    void createRandomly();    // création aléatoire
    void mutate();                // mutation
    individual operator*(individual&);    // croisement

    std::vector<int> solution;        // chemin retenu dans le graphe
    int fitness;                            // qualité de la solution
    problem &data;        // référence sur les données du problème

    std::string display();
    void makeCoherent();    // vérifier que this répond bien au problème

protected:
    void calculateQuality(); 
};

void individual::mutate(){
    // intervertir 2 villes
    int l = int(solution.size());

	// on détermine le nombre de couples à intervertir
    int nb = rand()%5;
    for (int i=0; i<nb; i++){
        int a = rand()%l;
        int b = rand()%l;

        int tmp = solution[a];
        solution[a] = solution[b];
        solution[b] = tmp;
    }
  
  	// on détermine la fitness de la solution créée
    calculateQuality();
}

individual individual::operator*(individual& i){

    int l = int(i.solution.size());

    // croisement multipoints
    int a = rand()%l;
    int b = rand()%l;
    int min1, min2;
  
    min1 = (a<b)?a:b;
    min2 = (a<b)?b:a;
  
  	// pour la première inversion de composantes
    for (int ii=0; ii<min1; ii++){
        int tmp =  solution[ii];
        solution[ii] = i.solution[ii];
        i.solution[ii] = tmp;
    }

	// pour la seconde inversion de composantes
    for (int ii=min1; ii<min2; ii++){
        int tmp =  i.solution[ii];
        i.solution[ii] = solution[ii];
        solution[ii] = tmp;
    }

	// pour la troisième inversion de composantes (2 points de croisement = 3 composantes)
    for (int ii=min2; ii<l; ii++){
        int tmp =  solution[ii];
        solution[ii] = i.solution[ii];
        i.solution[ii] = tmp;
    }
	
	// on rend les individus cohérents
    makeCoherent();
    i.makeCoherent();

    calculateQuality();
    i.calculateQuality();

    return *this;
}

bool operator<(individu& i1, individu& i2){
    return i1.fitness< i2.fitness;
}