CPopulation.cpp 16.2 KB
Newer Older
kruger's avatar
kruger committed
1
2
3
4
5
6
7
8
/*
 * CPopulation.cpp
 *
 *  Created on: 22 juin 2009
 *      Author: maitre
 */

#include "include/CPopulation.h"
kruger's avatar
kruger committed
9
10
#include <iostream>
#include <fstream>
kruger's avatar
kruger committed
11
12
13
14
#include <string.h>
#include "include/CRandomGenerator.h"
#include "include/CIndividual.h"
#include "include/Parameters.h"
15
#include "include/CStats.h"
kruger's avatar
kruger committed
16

kruger's avatar
kruger committed
17
18
using namespace std;

kruger's avatar
kruger committed
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
CSelectionOperator* CPopulation::selectionOperator;
CSelectionOperator* CPopulation::replacementOperator;
CSelectionOperator* CPopulation::parentReductionOperator;
CSelectionOperator* CPopulation::offspringReductionOperator;


float CPopulation::selectionPressure;
float CPopulation::replacementPressure;
float CPopulation::parentReductionPressure;
float CPopulation::offspringReductionPressure;


extern float* pEZ_MUT_PROB;
extern float* pEZ_XOVER_PROB;
extern CIndividual** pPopulation;
maitre's avatar
maitre committed
34
extern CIndividual* bBest;
kruger's avatar
kruger committed
35
36
37
38

CPopulation::CPopulation(){
}

Ogier Maitre's avatar
Ogier Maitre committed
39
CPopulation::CPopulation(unsigned parentPopulationSize, unsigned offspringPopulationSize,
kruger's avatar
kruger committed
40
		       float pCrossover, float pMutation, float pMutationPerGene,
41
		       CRandomGenerator* rg, Parameters* params, CStats* cstats){
kruger's avatar
kruger committed
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

  this->parents     = new CIndividual*[parentPopulationSize];
  this->offsprings  = new CIndividual*[offspringPopulationSize];

  this->parentPopulationSize     = parentPopulationSize;
  this->offspringPopulationSize  = offspringPopulationSize;

  this->actualParentPopulationSize    = 0;
  this->actualOffspringPopulationSize = 0;

  this->pCrossover       = pCrossover;
  this->pMutation        = pMutation;
  pEZ_MUT_PROB = &this->pMutation;
  pEZ_XOVER_PROB = &this->pCrossover;
  this->pMutationPerGene = pMutationPerGene;
  pPopulation = parents;
maitre's avatar
maitre committed
58
  bBest = Best;
kruger's avatar
kruger committed
59
60
61
62
63

  this->rg = rg;

  this->currentEvaluationNb = 0;
  this->params = params;
64
  this->cstats = cstats;
kruger's avatar
kruger committed
65
66
67
}

void CPopulation::syncInVector(){
Ogier Maitre's avatar
Ogier Maitre committed
68
  for( unsigned i = 0 ; i<actualParentPopulationSize ; i++ ){
kruger's avatar
kruger committed
69
70
71
72
73
74
    parents[i] = pop_vect.at(i);
  }
}

void CPopulation::syncOutVector(){
  pop_vect.clear();
Ogier Maitre's avatar
Ogier Maitre committed
75
  for( unsigned i = 0 ; i<actualParentPopulationSize ; i++ ){
kruger's avatar
kruger committed
76
77
78
79
80
81
82
83
    pop_vect.push_back(parents[i]);
  }
#ifndef WIN32
  DEBUG_PRT("Size of outVector",pop_vect.size());
#endif
}

CPopulation::~CPopulation(){
Ogier Maitre's avatar
Ogier Maitre committed
84
85
  for( unsigned i=0 ; i<actualOffspringPopulationSize ; i++ ) delete(offsprings[i]);
  for( unsigned i=0 ; i<actualParentPopulationSize ; i++ )    delete(parents[i]);
kruger's avatar
kruger committed
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

  delete[](this->parents);
  delete[](this->offsprings);
}

void CPopulation::initPopulation(CSelectionOperator* selectionOperator,
				CSelectionOperator* replacementOperator,
				CSelectionOperator* parentReductionOperator,
				CSelectionOperator* offspringReductionOperator,
				float selectionPressure, float replacementPressure,
				float parentReductionPressure, float offspringReductionPressure){
  CPopulation::selectionOperator   = selectionOperator;
  CPopulation::replacementOperator = replacementOperator;
  CPopulation::parentReductionOperator = parentReductionOperator;
  CPopulation::offspringReductionOperator = offspringReductionOperator;

  CPopulation::selectionPressure   = selectionPressure;
  CPopulation::replacementPressure = replacementPressure;
  CPopulation::parentReductionPressure = parentReductionPressure;
  CPopulation::offspringReductionPressure = offspringReductionPressure;

}




Ogier Maitre's avatar
Ogier Maitre committed
112
113
void CPopulation::evaluatePopulation(CIndividual** population, unsigned populationSize){
  for( unsigned i=0 ; i < populationSize ; i++ )
kruger's avatar
kruger committed
114
115
116
    population[i]->evaluate();
}

Ogier Maitre's avatar
Ogier Maitre committed
117
void CPopulation::optimisePopulation(CIndividual** population, unsigned populationSize){
kruger's avatar
kruger committed
118
}
kruger's avatar
kruger committed
119
120
121
122
123

void CPopulation::evaluateParentPopulation(){
  evaluatePopulation(parents,parentPopulationSize);
}

kruger's avatar
kruger committed
124
125
126
void CPopulation::optimiseParentPopulation(){
  optimisePopulation(parents,parentPopulationSize);
}
kruger's avatar
kruger committed
127
128
129

void CPopulation::evaluateOffspringPopulation(){
  evaluatePopulation(offsprings,offspringPopulationSize);
kruger's avatar
kruger committed
130
131
132
133
}

void CPopulation::optimiseOffspringPopulation(){
  optimisePopulation(offsprings,offspringPopulationSize);
kruger's avatar
kruger committed
134
135
136
137
138
139
140
141
142
143
144
145
}


/**
   Reduit la population population de taille populationSize
   a une population reducedPopulation de taille obSize.
   reducedPopulation doit etre alloue a obSize.

   Ici on pourrait avoir le best fitness de la prochaine population de parents.


 */
Ogier Maitre's avatar
Ogier Maitre committed
146
147
void CPopulation::reducePopulation(CIndividual** population, unsigned populationSize,
					  CIndividual** reducedPopulation, unsigned obSize,
kruger's avatar
kruger committed
148
149
150
151
152
					  CSelectionOperator* replacementOperator){


  replacementOperator->initialize(population,replacementPressure,populationSize);

Ogier Maitre's avatar
Ogier Maitre committed
153
  for( unsigned i=0 ; i<obSize ; i++ ){
kruger's avatar
kruger committed
154
155

    // select an CIndividual and add it to the reduced population
Ogier Maitre's avatar
Ogier Maitre committed
156
    unsigned selectedIndex = replacementOperator->selectNext(populationSize - i);
kruger's avatar
kruger committed
157
158
159
    // std::cout << "Selected " << selectedIndex << "/" << populationSize
    // 	      << " replaced by : " << populationSize-(i+1)<< std::endl;
    reducedPopulation[i] = population[selectedIndex];
maitre's avatar
maitre committed
160
    //printf("TEST REMPLACEMENT %d %d %f %f\n", i, selectedIndex, reducedPopulation[i]->fitness, population[selectedIndex]->fitness);
kruger's avatar
kruger committed
161
162
163
164
165
166
167
168
169
170

    // erase it to the std population by swapping last CIndividual end current
    population[selectedIndex] = population[populationSize-(i+1)];
    //population[populationSize-(i+1)] = NULL;
  }

  //return reducedPopulation;
}


Ogier Maitre's avatar
Ogier Maitre committed
171
CIndividual** CPopulation::reduceParentPopulation(unsigned obSize){
maitre's avatar
maitre committed
172
173
174
175
176
177
  CIndividual** nextGeneration;
  if(obSize==0){
  	nextGeneration = new CIndividual*[1];
  }
  else
  	nextGeneration = new CIndividual*[obSize];
kruger's avatar
kruger committed
178
179

  reducePopulation(parents,actualParentPopulationSize,nextGeneration,obSize,
180
		   CPopulation::parentReductionOperator);
kruger's avatar
kruger committed
181
182

  // free no longer needed CIndividuals
Ogier Maitre's avatar
Ogier Maitre committed
183
  for( unsigned i=0 ; i<actualParentPopulationSize-obSize ; i++ )
kruger's avatar
kruger committed
184
185
186
187
188
    delete(parents[i]);
  delete[](parents);

  this->actualParentPopulationSize = obSize;

maitre's avatar
maitre committed
189
  parents = nextGeneration;
kruger's avatar
kruger committed
190
191
192
193
194
195

  return nextGeneration;
}



Ogier Maitre's avatar
Ogier Maitre committed
196
CIndividual** CPopulation::reduceOffspringPopulation(unsigned obSize){
kruger's avatar
kruger committed
197
198
199
200
201
  // this array has offspringPopulationSize because it will be used as offspring population in
  // the next generation
  CIndividual** nextGeneration = new CIndividual*[offspringPopulationSize];

  reducePopulation(offsprings,actualOffspringPopulationSize,nextGeneration,obSize,
202
		   CPopulation::offspringReductionOperator);
kruger's avatar
kruger committed
203

maitre's avatar
maitre committed
204
  //printf("POPULATION SIZE %d\n",actualOffspringPopulationSize-obSize);
kruger's avatar
kruger committed
205
  // free no longer needed CIndividuals
Ogier Maitre's avatar
Ogier Maitre committed
206
  for( unsigned i=0 ; i<actualOffspringPopulationSize-obSize ; i++ )
kruger's avatar
kruger committed
207
208
    delete(offsprings[i]);
  delete[](offsprings);
maitre's avatar
maitre committed
209
210
211
212
  //printf("DANS LA FONCTION DE REMPLACEMENT\n");
  /*for(int i=0; i<parentPopulationSize; i++)
	printf("Indiv %d %f | ",i, parents[i]->fitness);
  printf("\n");*/
kruger's avatar
kruger committed
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234

  this->actualOffspringPopulationSize = obSize;
  offsprings = nextGeneration;
  return nextGeneration;
}


static int CIndividualCompare(const void* p1, const void* p2){
  CIndividual** p1_i = (CIndividual**)p1;
  CIndividual** p2_i = (CIndividual**)p2;

  return p1_i[0]->getFitness() > p2_i[0]->getFitness();
}

static int CIndividualRCompare(const void* p1, const void* p2){
  CIndividual** p1_i = (CIndividual**)p1;
  CIndividual** p2_i = (CIndividual**)p2;

  return p1_i[0]->getFitness() < p2_i[0]->getFitness();
}


Ogier Maitre's avatar
Ogier Maitre committed
235
void CPopulation::sortPopulation(CIndividual** population, unsigned populationSize){
kruger's avatar
kruger committed
236
237
238
  qsort(population,populationSize,sizeof(CIndividual*),CIndividualCompare);
}

Ogier Maitre's avatar
Ogier Maitre committed
239
void CPopulation::sortRPopulation(CIndividual** population, unsigned populationSize){
kruger's avatar
kruger committed
240
241
242
  qsort(population,populationSize,sizeof(CIndividual*),CIndividualRCompare);
}

kruger's avatar
kruger committed
243
244
245
246
247
248
249
250
251
252
253
254
255
/* Fonction qui va serializer la population */
void CPopulation::serializePopulation(){
  ofstream EASEA_File;
  std::string fichier = params->outputFilename;
  fichier.append(".pop");
  EASEA_File.open(fichier.c_str(), ios::app); 
  for(int i=0; (unsigned)i<parentPopulationSize; i++){
	EASEA_File << parents[i]->serialize() << endl;
	
  }
  EASEA_File.close();
}

256
257
258
259
260
261
262
263
264
int CPopulation::getWorstIndividualIndex(CIndividual** population){
	int index=0;
	for(int i=1; i<(signed)this->parentPopulationSize; i++){
		if((params->minimizing && (population[i]->fitness > population[index]->fitness)) || (!params->minimizing && (population[i]->fitness < population[index]->fitness)))
			index=i;
	}	
	return index;
}

kruger's avatar
kruger committed
265
266
267
268
269
270
271
272

/**
   Reduit les populations en faisant l'operation de remplacement.

   @TODO : on aurait voulu eviter la recopie des deux populations en une seule
   mais cela semble incompatible avec CSelectionOperator (notamment l'operation
   d'initialisation.
*/
maitre's avatar
maitre committed
273
void CPopulation::reduceTotalPopulation(CIndividual** elitPop){
kruger's avatar
kruger committed
274
275
276

  CIndividual** nextGeneration = new CIndividual*[parentPopulationSize];

maitre's avatar
maitre committed
277
278
  if(params->elitSize)
	memcpy(nextGeneration,elitPop, sizeof(CIndividual*)*params->elitSize);
kruger's avatar
kruger committed
279

Ogier Maitre's avatar
Ogier Maitre committed
280
  unsigned actualGlobalSize = actualParentPopulationSize+actualOffspringPopulationSize;
maitre's avatar
maitre committed
281
  
kruger's avatar
kruger committed
282
283
  CIndividual** globalPopulation = new CIndividual*[actualGlobalSize]();

maitre's avatar
maitre committed
284
285
286
287
288
289
290
291
292
  if(actualParentPopulationSize==0){
  	memcpy(globalPopulation,offsprings,sizeof(CIndividual*)*actualOffspringPopulationSize);
  }
  else if(actualOffspringPopulationSize==0){
  	memcpy(globalPopulation,parents,sizeof(CIndividual*)*actualParentPopulationSize);
  }
  else{
  	memcpy(globalPopulation,parents,sizeof(CIndividual*)*actualParentPopulationSize);
        memcpy(globalPopulation+actualParentPopulationSize,offsprings,sizeof(CIndividual*)*actualOffspringPopulationSize);
kruger's avatar
kruger committed
293
294
295
  }


maitre's avatar
maitre committed
296
297
  replacementOperator->initialize(globalPopulation, replacementPressure,actualGlobalSize);

kruger's avatar
kruger committed
298
299
300
  CPopulation::reducePopulation(globalPopulation,actualGlobalSize,params->elitSize+nextGeneration,
			       parentPopulationSize-params->elitSize,replacementOperator);

maitre's avatar
maitre committed
301

kruger's avatar
kruger committed
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
  for( unsigned int i=0 ; i<((int)actualGlobalSize+params->elitSize)-(int)parentPopulationSize ; i++ )
    delete(globalPopulation[i]);

  delete[](parents);
  delete[](globalPopulation);

  actualParentPopulationSize = parentPopulationSize;
  actualOffspringPopulationSize = 0;
  parents = nextGeneration;

}


void CPopulation::produceOffspringPopulation(){

Ogier Maitre's avatar
Ogier Maitre committed
317
  unsigned crossoverArrity = CIndividual::getCrossoverArrity();
kruger's avatar
kruger committed
318
319
320
321
322
323
  CIndividual* p1;
  CIndividual** ps = new CIndividual*[crossoverArrity]();
  CIndividual* child;

  selectionOperator->initialize(parents,selectionPressure,actualParentPopulationSize);

Ogier Maitre's avatar
Ogier Maitre committed
324
325
  for( unsigned i=0 ; i<offspringPopulationSize ; i++ ){
    unsigned index = selectionOperator->selectNext(parentPopulationSize);
kruger's avatar
kruger committed
326
327
    p1 = parents[index];

328
329
330
331
332
    //Check if Any Immigrants will reproduce
    if( this->params->remoteIslandModel && parents[index]->isImmigrant ){
        this->cstats->currentNumberOfImmigrantReproductions++;
    }

kruger's avatar
kruger committed
333
    if( rg->tossCoin(pCrossover) ){
Ogier Maitre's avatar
Ogier Maitre committed
334
      for( unsigned j=0 ; j<crossoverArrity-1 ; j++ ){
335
336
337
338
339
	    index = selectionOperator->selectNext(parentPopulationSize);
	    ps[j] = parents[index];
        if( this->params->remoteIslandModel && parents[index]->isImmigrant ){
            this->cstats->currentNumberOfImmigrantReproductions++;
        }
kruger's avatar
kruger committed
340
341
342
343
344
345
346
347
348
      }
      child = p1->crossover(ps);
    }
    else child = parents[index]->clone();//new CIndividual(*parents[index]);

    if( rg->tossCoin(pMutation) ){
      child->mutate(pMutationPerGene);
    }

Frederic Kruger's avatar
Frederic Kruger committed
349
350
    child->boundChecking();

kruger's avatar
kruger committed
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
    offsprings[actualOffspringPopulationSize++] = child;
  }
  delete[](ps);
  }




/**
   Here we save elit CIndividuals to the replacement

   @ARG elitismSize the number of CIndividuals save by elitism
   @ARG population the population where the CIndividuals are save
   @ARG populationSize the size of the population
   @ARG outPopulation the output population, this must be allocated with size greather than elitism
   @ARG outPopulationSize the size of the output population

*/
Ogier Maitre's avatar
Ogier Maitre committed
369
370
void CPopulation::strongElitism(unsigned elitismSize, CIndividual** population, unsigned populationSize,
			 CIndividual** outPopulation, unsigned outPopulationSize){
kruger's avatar
kruger committed
371
372

  float bestFitness = population[0]->getFitness();
Ogier Maitre's avatar
Ogier Maitre committed
373
  unsigned bestCIndividual = 0;
kruger's avatar
kruger committed
374
375
376
377
378

#ifndef WIN32
  if( elitismSize >= 5 )DEBUG_PRT("Warning, elitism has O(n) complexity, elitismSize is maybe too big (%d)",elitismSize);
#endif

maitre's avatar
maitre committed
379
  //printf("MINIMIZING ? %d\n",params->minimizing);
Ogier Maitre's avatar
Ogier Maitre committed
380
  for(unsigned i = 0 ; i<elitismSize ; i++ ){
maitre's avatar
maitre committed
381
382
    //bestFitness = replacementOperator->getExtremum();
    bestFitness = population[0]->getFitness();
kruger's avatar
kruger committed
383
    bestCIndividual = 0;
Ogier Maitre's avatar
Ogier Maitre committed
384
    for( unsigned j=0 ; j<populationSize-i ; j++ ){
kruger's avatar
kruger committed
385
386
387
388
389
390
391
392
393
394
395
396
397

    	if( (params->minimizing && bestFitness > population[j]->getFitness() ) ||
    			( !params->minimizing && bestFitness < population[j]->getFitness() )){
    		bestFitness = population[j]->getFitness();
    		bestCIndividual = j;
    	}
    }
    outPopulation[i] = population[bestCIndividual];
    population[bestCIndividual] = population[populationSize-(i+1)];
    population[populationSize-(i+1)] = NULL;
  }
}

Ogier Maitre's avatar
Ogier Maitre committed
398
void CPopulation::weakElitism(unsigned elitismSize, CIndividual** parentsPopulation, CIndividual** offspringPopulation, unsigned* parentPopSize, unsigned* offPopSize, CIndividual** outPopulation, unsigned outPopulationSize){
maitre's avatar
maitre committed
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421

  float bestParentFitness = parentsPopulation[0]->getFitness();
  float bestOffspringFitness = offspringPopulation[0]->getFitness();
  int bestParentIndiv = 0;
  int bestOffspringIndiv = 0;

  for(int i=1; (unsigned)i<(*parentPopSize); i++){
        if( (params->minimizing && bestParentFitness > parentsPopulation[i]->getFitness() ) ||
                        ( !params->minimizing && bestParentFitness < parentsPopulation[i]->getFitness() )){
                bestParentFitness = parentsPopulation[i]->getFitness();
                bestParentIndiv = i;
        }
  }
 
  for(int i=1; (unsigned)i<(*offPopSize); i++){
        if( (params->minimizing && bestOffspringFitness > offspringPopulation[i]->getFitness() ) ||
                        ( !params->minimizing && bestOffspringFitness < offspringPopulation[i]->getFitness() )){
                bestOffspringFitness = offspringPopulation[i]->getFitness();
                bestOffspringIndiv = i;
        }
  }
 
  for(int i = 0 ; (unsigned)i<elitismSize ; i++ ){
kruger's avatar
kruger committed
422
 	if(((!params->minimizing && bestParentFitness > bestOffspringFitness) || (params->minimizing && bestParentFitness<bestOffspringFitness) || (*offPopSize)==0) && (*parentPopSize)>0){
maitre's avatar
maitre committed
423
424
425
426
		outPopulation[i] = parentsPopulation[bestParentIndiv];
		parentsPopulation[bestParentIndiv] = parentsPopulation[(*parentPopSize)-1];
		parentsPopulation[(*parentPopSize)-1] = NULL;
		(*parentPopSize)-=1; 
kruger's avatar
kruger committed
427
428
429
430
431
432
433
434
435
436
437
		if((*parentPopSize)>0){
	  		bestParentFitness = parentsPopulation[0]->getFitness();
			bestParentIndiv=0;
			for(int j=1; (unsigned)j<(*parentPopSize); j++){
			        if( (params->minimizing && bestParentFitness > parentsPopulation[j]->getFitness() ) ||
	        	                ( !params->minimizing && bestParentFitness < parentsPopulation[j]->getFitness() )){
	        	        	bestParentFitness = parentsPopulation[j]->getFitness();
	        	        	bestParentIndiv = j;
	       			}
	  		}
		}
maitre's avatar
maitre committed
438
439
440
441
442
443
	}
	else{
		outPopulation[i] = offspringPopulation[bestOffspringIndiv];
		offspringPopulation[bestOffspringIndiv] = offspringPopulation[(*offPopSize)-1];
		offspringPopulation[(*offPopSize)-1] = NULL;
		(*offPopSize)-=1;
kruger's avatar
kruger committed
444
445
446
447
448
449
450
451
452
453
454
		if((*offPopSize)>0){
	  		bestOffspringFitness = offspringPopulation[0]->getFitness();
			bestOffspringIndiv = 0;	
			for(int j=1; (unsigned)j<(*offPopSize); j++){
			        if( (params->minimizing && bestOffspringFitness > offspringPopulation[j]->getFitness() ) ||
	        	                ( !params->minimizing && bestOffspringFitness < offspringPopulation[j]->getFitness() )){
	        	        	bestOffspringFitness = offspringPopulation[j]->getFitness();
	        	        	bestOffspringIndiv = j;
	       			}
	  		}
		}	
maitre's avatar
maitre committed
455
456
457
	}
  }
}
kruger's avatar
kruger committed
458
459


Ogier Maitre's avatar
Ogier Maitre committed
460
void CPopulation::addIndividualParentPopulation(CIndividual* indiv, unsigned id){
461
	parents[id] = indiv;
kruger's avatar
kruger committed
462
}
463
464
465
void CPopulation::addIndividualParentPopulation(CIndividual* indiv){
	parents[actualParentPopulationSize++] = indiv;
}
kruger's avatar
kruger committed
466
467
468
469

std::ostream& operator << (std::ostream& O, const CPopulation& B)
{

Ogier Maitre's avatar
Ogier Maitre committed
470
471
  unsigned offspringPopulationSize = B.offspringPopulationSize;
  unsigned realOffspringPopulationSize = B.actualOffspringPopulationSize;
kruger's avatar
kruger committed
472

Ogier Maitre's avatar
Ogier Maitre committed
473
474
  unsigned parentPopulationSize = B.parentPopulationSize;
  unsigned realParentPopulationSize = B.actualParentPopulationSize;
kruger's avatar
kruger committed
475
476
477
478
479
480
481
482


  O << "CPopulation : "<< std::endl;
  O << "\t Parents size : "<< realParentPopulationSize << "/" <<
    parentPopulationSize << std::endl;

  O << "\t Offspring size : "<< realOffspringPopulationSize << "/" <<
    offspringPopulationSize << std::endl;
Ogier Maitre's avatar
Ogier Maitre committed
483
  for( unsigned i=0 ; i<realParentPopulationSize ; i++){
kruger's avatar
kruger committed
484
485
486
487
488
489
490
	B.parents[i]->printOn(O);
	 O << "\n";

  }
  return O;
}