CPopulation.cpp 15.7 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
15
#include <string.h>
#include "include/CRandomGenerator.h"
#include "include/CIndividual.h"
#include "include/Parameters.h"

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

kruger's avatar
kruger committed
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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
33
extern CIndividual* bBest;
kruger's avatar
kruger committed
34
35
36
37

CPopulation::CPopulation(){
}

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

  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
57
  bBest = Best;
kruger's avatar
kruger committed
58
59
60
61
62
63
64
65

  this->rg = rg;

  this->currentEvaluationNb = 0;
  this->params = params;
}

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

void CPopulation::syncOutVector(){
  pop_vect.clear();
Ogier Maitre's avatar
Ogier Maitre committed
73
  for( unsigned i = 0 ; i<actualParentPopulationSize ; i++ ){
kruger's avatar
kruger committed
74
75
76
77
78
79
80
81
    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
82
83
  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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

  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
110
111
void CPopulation::evaluatePopulation(CIndividual** population, unsigned populationSize){
  for( unsigned i=0 ; i < populationSize ; i++ )
kruger's avatar
kruger committed
112
113
114
    population[i]->evaluate();
}

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

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

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

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

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


/**
   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
144
145
void CPopulation::reducePopulation(CIndividual** population, unsigned populationSize,
					  CIndividual** reducedPopulation, unsigned obSize,
kruger's avatar
kruger committed
146
147
148
149
150
					  CSelectionOperator* replacementOperator){


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

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

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

    // 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
169
CIndividual** CPopulation::reduceParentPopulation(unsigned obSize){
maitre's avatar
maitre committed
170
171
172
173
174
175
  CIndividual** nextGeneration;
  if(obSize==0){
  	nextGeneration = new CIndividual*[1];
  }
  else
  	nextGeneration = new CIndividual*[obSize];
kruger's avatar
kruger committed
176
177

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

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

  this->actualParentPopulationSize = obSize;

maitre's avatar
maitre committed
187
  parents = nextGeneration;
kruger's avatar
kruger committed
188
189
190
191
192
193

  return nextGeneration;
}



Ogier Maitre's avatar
Ogier Maitre committed
194
CIndividual** CPopulation::reduceOffspringPopulation(unsigned obSize){
kruger's avatar
kruger committed
195
196
197
198
199
  // 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,
200
		   CPopulation::offspringReductionOperator);
kruger's avatar
kruger committed
201

maitre's avatar
maitre committed
202
  //printf("POPULATION SIZE %d\n",actualOffspringPopulationSize-obSize);
kruger's avatar
kruger committed
203
  // free no longer needed CIndividuals
Ogier Maitre's avatar
Ogier Maitre committed
204
  for( unsigned i=0 ; i<actualOffspringPopulationSize-obSize ; i++ )
kruger's avatar
kruger committed
205
206
    delete(offsprings[i]);
  delete[](offsprings);
maitre's avatar
maitre committed
207
208
209
210
  //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
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232

  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
233
void CPopulation::sortPopulation(CIndividual** population, unsigned populationSize){
kruger's avatar
kruger committed
234
235
236
  qsort(population,populationSize,sizeof(CIndividual*),CIndividualCompare);
}

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

kruger's avatar
kruger committed
241
242
243
244
245
246
247
248
249
250
251
252
253
/* 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();
}

254
255
256
257
258
259
260
261
262
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
263
264
265
266
267
268
269
270

/**
   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
271
void CPopulation::reduceTotalPopulation(CIndividual** elitPop){
kruger's avatar
kruger committed
272
273
274

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

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

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

maitre's avatar
maitre committed
282
283
284
285
286
287
288
289
290
  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
291
292
293
  }


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

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

maitre's avatar
maitre committed
299

kruger's avatar
kruger committed
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
  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
315
  unsigned crossoverArrity = CIndividual::getCrossoverArrity();
kruger's avatar
kruger committed
316
317
318
319
320
321
  CIndividual* p1;
  CIndividual** ps = new CIndividual*[crossoverArrity]();
  CIndividual* child;

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

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

    if( rg->tossCoin(pCrossover) ){
Ogier Maitre's avatar
Ogier Maitre committed
327
      for( unsigned j=0 ; j<crossoverArrity-1 ; j++ ){
kruger's avatar
kruger committed
328
329
330
331
332
333
334
335
336
337
338
	index = selectionOperator->selectNext(parentPopulationSize);
	ps[j] = parents[index];
      }
      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
339
340
    child->boundChecking();

kruger's avatar
kruger committed
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
    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
359
360
void CPopulation::strongElitism(unsigned elitismSize, CIndividual** population, unsigned populationSize,
			 CIndividual** outPopulation, unsigned outPopulationSize){
kruger's avatar
kruger committed
361
362

  float bestFitness = population[0]->getFitness();
Ogier Maitre's avatar
Ogier Maitre committed
363
  unsigned bestCIndividual = 0;
kruger's avatar
kruger committed
364
365
366
367
368

#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
369
  //printf("MINIMIZING ? %d\n",params->minimizing);
Ogier Maitre's avatar
Ogier Maitre committed
370
  for(unsigned i = 0 ; i<elitismSize ; i++ ){
maitre's avatar
maitre committed
371
372
    //bestFitness = replacementOperator->getExtremum();
    bestFitness = population[0]->getFitness();
kruger's avatar
kruger committed
373
    bestCIndividual = 0;
Ogier Maitre's avatar
Ogier Maitre committed
374
    for( unsigned j=0 ; j<populationSize-i ; j++ ){
kruger's avatar
kruger committed
375
376
377
378
379
380
381
382
383
384
385
386
387

    	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
388
void CPopulation::weakElitism(unsigned elitismSize, CIndividual** parentsPopulation, CIndividual** offspringPopulation, unsigned* parentPopSize, unsigned* offPopSize, CIndividual** outPopulation, unsigned outPopulationSize){
maitre's avatar
maitre committed
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411

  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
412
 	if(((!params->minimizing && bestParentFitness > bestOffspringFitness) || (params->minimizing && bestParentFitness<bestOffspringFitness) || (*offPopSize)==0) && (*parentPopSize)>0){
maitre's avatar
maitre committed
413
414
415
416
		outPopulation[i] = parentsPopulation[bestParentIndiv];
		parentsPopulation[bestParentIndiv] = parentsPopulation[(*parentPopSize)-1];
		parentsPopulation[(*parentPopSize)-1] = NULL;
		(*parentPopSize)-=1; 
kruger's avatar
kruger committed
417
418
419
420
421
422
423
424
425
426
427
		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
428
429
430
431
432
433
	}
	else{
		outPopulation[i] = offspringPopulation[bestOffspringIndiv];
		offspringPopulation[bestOffspringIndiv] = offspringPopulation[(*offPopSize)-1];
		offspringPopulation[(*offPopSize)-1] = NULL;
		(*offPopSize)-=1;
kruger's avatar
kruger committed
434
435
436
437
438
439
440
441
442
443
444
		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
445
446
447
	}
  }
}
kruger's avatar
kruger committed
448
449


Ogier Maitre's avatar
Ogier Maitre committed
450
void CPopulation::addIndividualParentPopulation(CIndividual* indiv, unsigned id){
451
	parents[id] = indiv;
kruger's avatar
kruger committed
452
}
453
454
455
void CPopulation::addIndividualParentPopulation(CIndividual* indiv){
	parents[actualParentPopulationSize++] = indiv;
}
kruger's avatar
kruger committed
456
457
458
459

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

Ogier Maitre's avatar
Ogier Maitre committed
460
461
  unsigned offspringPopulationSize = B.offspringPopulationSize;
  unsigned realOffspringPopulationSize = B.actualOffspringPopulationSize;
kruger's avatar
kruger committed
462

Ogier Maitre's avatar
Ogier Maitre committed
463
464
  unsigned parentPopulationSize = B.parentPopulationSize;
  unsigned realParentPopulationSize = B.actualParentPopulationSize;
kruger's avatar
kruger committed
465
466
467
468
469
470
471
472


  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
473
  for( unsigned i=0 ; i<realParentPopulationSize ; i++){
kruger's avatar
kruger committed
474
475
476
477
478
479
480
	B.parents[i]->printOn(O);
	 O << "\n";

  }
  return O;
}