genetic.cpp

uploading the file , the system will delete the file when time expires

#include "rand32.h"
#include "genetic.h"
Placement *
      Genetic(Netlist * nl, /* Constraints */
			 double Rc, /* Crossover Rate*/ 
			 double Rm, /* Mutation Rate */
			 double Ri, /* Inversion Rate */
			 int Np, /* Population Size */
			 int Ng, /* Number of Generatios */
			 FILE * outfile, /* Where to dump */
			 int verbosity /* How much to dump */) {

	if(verbosity>=9) {
		fprintf(outfile,"Entering Genetic:\n");
		fprintf(outfile,"  Rc = %f",Rc);
		fprintf(outfile,"  Rm = %f",Rm);
		fprintf(outfile,"  Ri = %f\n",Ri);
		fprintf(outfile,"  Np = %i  Ng = %i\n",Np,Ng);
	}

	// the best solution we have found will be:
	Placement * kwisatch_haderach;

	// KH is a reference to Frank Herbert's DUNE:
	// many of the variables and comments herein
	// contain such references

	// allocate room for the entire population
	// maximum population size is Np + Ns
	// Ns = Np * Rc...so max pop size is:
	// PSize = (1+Rc)*Np

	int psize = (int) ((1.0+Rc)*Np);
	int nkids = psize - Np;
	int nparents = Np;
	Placement ** population = new Placement*[psize];

//	int nliving;

	if(verbosity>=9) {
		fprintf(stdout,"  Psize = %i\tNKids = %i\n",psize,nkids);
	}
	
	double sum; // sum of the fitnesses of the population
	double max_fitness;
	int    max_i;
	double fitness;
	double min_fitness;
	int    min_i;

	// loop counter
	int i;

	// mutation/inversion/crossover variables
	int a, b, kid;
	Placement * parentA,*parentB;
	parentA = parentB = NULL;
	int tries;

	// allocate the population members themselves
	for(i=0;i<psize;i++) {
		population[i] = new Placement(nl);
		// if this is an initial parent, randomize it
		if(i<nparents) {
			// this is a member of the first generation
			population[i]->Randomize();
			population[i]->alive = true;
		} else {
			// this is just a placeholder for future children
			population[i]->alive = false;
		}
	}

	// evaluate the initial population
	max_fitness = 0.0;
	sum = 0.0;
	max_i = -1;
	for(i=0;i<psize;i++) {
		if(!population[i]->alive) continue;
		fitness = population[i]->Fitness();
		population[i]->myFitness = fitness;
		sum += fitness;
		if(fitness>max_fitness) {
			max_fitness = fitness;
			max_i = i;
		}
		
	}

	// assign the kwisatch haderach to the most fit
	kwisatch_haderach = population[max_i]->Clone();

	// now normalize all the fitnesses st sum of all
	// fitnesses = 1
	for(i=0;i<psize;i++) {
		if(!population[i]->alive) continue;
		population[i]->myFitness = population[i]->myFitness / sum;
	}

	// start the outer genetic loop
	for(int current_generation=0;current_generation<Ng;current_generation++) {
		if(verbosity>=7) {
			fprintf(outfile,"GENETIC: Starting generation %i\n",current_generation);
		}
		// firstly, do inversions on living members of the population
		// with probablity Ri

		// this is the GENOTYPE MUTATION PHASE
		for(i=0;i<psize;i++) {
			if(!population[i]->alive) continue;

			if(randNorm()>Ri) continue; // don't invert this member

			// invert some portion of this member of the population

			do {
				a = randOnRange(0,nl->nCells-2);
				b = randOnRange(a,nl->nCells-1);
//				fprintf(outfile,"a");
			} while(!population[i]->Invert(a,b));
			// keep trying inversions until one is OK

			if(verbosity>=9)
				fprintf(outfile,"MuTaNt: Inverting member %i\n",i);

		}

		// next, breed offspring according the the crossover rate,
		// aka generate nkids children, and add them to the population

		// this is the BENE GESSERIT BREEDING PROGRAM
		for(i=0;i<nkids;i++) {
			// generate a kid
			
			// in most cases, two parents are not allowed to breed
			// if they are genetically identical, but in the event 
			// that all members of the population are clones, the
			// breeding must be allowed.  However, this is too
			// costly to check for, so a simple retry limit is implemented

			tries = 0;

//			if(verbosity==10) {
//				fprintf(outfile,"Preparing to generate a kid\n");
//			}

			do {
				tries++;

				// select parent A according to fitness
				fitness = randNorm();
//				fprintf(outfile,"fitness = %f\n",fitness);
				sum = 0.0;
				for(a=0;a<psize;a++) {
					// skip non-living members of the population
					if(!population[a]->alive) continue;
					sum += population[a]->myFitness;

//					fprintf(outfile,"sum = %f\n",sum);

					if(sum>=fitness) break;
				}
				
				parentA = population[a];

//				if(verbosity==10) {
//				fprintf(outfile,"Got A: %i\n",a);
//				}
				// select parent B according to fitness
				fitness = randNorm();
//				fprintf(outfile,"fitness = %f\n",fitness);
				sum = 0.0;
				for(b=0;b<psize;b++) {
					// skip non-living members of the population
					if(!(population[b]->alive)) continue;
					sum += population[b]->myFitness;
//					fprintf(outfile,"sum = %f\n",sum);
					if(sum>=fitness) break;
				}

				parentB = population[b];

//				if(verbosity==10) {
//				fprintf(outfile,"Got B: %i\n",b);
//				}

//				fprintf(outfile,"a=%i  b=%i  psize=%i\n",a,b,psize);

			} while(a==psize || b==psize || ((parentA==parentB || parentA->IsCloneOf(parentB)) &&
				    tries<psize*2));

//			if(verbosity==10) {
//				fprintf(outfile,"Selected parents\n");
//			}
				    
			// the two parents have been selected: parentA and parentB
			// find a spot for the child
			for(kid=0;kid<psize;kid++) {
				// skip all living members of the population
				if(population[kid]->alive) continue;
				break;
			}

			if(kid==psize) {
				// this should never happen
				fprintf(stderr,"Danger, Will Robinson!\n");
				fprintf(stderr,"No room in population for children!\n");
				return NULL;
			}

//			if(verbosity==10) {
//				fprintf(outfile,"Found a spot\n");
//			}

			// spawn the child--no need to check return value--
			// crossover cannot fail!! mwa ha ha
			population[kid]->Crossover(parentA,parentB);
			population[kid]->myFitness = 0.0;

			// mark this child as alive!!
			population[kid]->alive = true;

//			if(verbosity==10) {
//				fprintf(outfile,"Considering mutation\n");
//			}

			// now that the child has been generated, there
			// is a chance that a mutation will occur
			// this is the PHENOTYPE MUTATION PHASE
			if(randNorm()<Rm) {
				
				if(verbosity>=9) {
					fprintf(outfile,"MuTaNt: Mutating member %i\n",kid);
				}
				// this child is a MuTaNt mUtAnT MuTaNt
				// so mutate it!!
				if(nl->nCells!=1)
				do {
					a = randOnRange(0,nl->nCells-1);
					b = randOnRange(0,nl->nCells-1);
//					fprintf(outfile,"c");
				} while(!population[kid]->Mutate(a,b));

//				if(verbosity==10) fprintf(outfile,"Mutation complete\n");

			}

			
		} // end of BENE GESSERIT BREEDING PROGRAM
/*
		// count living kids
		nliving = 0;
		for(i=0;i<psize;i++) {
			if(population[i]->alive) nliving++;
		}

		printf("After BG Breeding, nliving = %i\n",nliving);
*/
		// now, we've bred our next generation, lets evaluate
		// the whole population
		sum = 0.0;
		if(verbosity>=7) {
			fprintf(outfile,"Population members:\n");
		}
		for(i=0;i<psize;i++) {

			// at this point, everyone is alive, so no need
			// to check for a pulse
			fitness = population[i]->Fitness();
			population[i]->myFitness = fitness;
			sum += fitness;
			
			if(verbosity>=7) {
				fprintf(outfile,"Member %i: Fitness = %f\n",i,fitness);
			}
			if(fitness>max_fitness) {
				// this is the best placement seen so far
				if(verbosity>=6)
					fprintf(outfile,"New Genetic Best Solution! Member %i: Fitness = %f\n",i,fitness);
				delete kwisatch_haderach;
				max_fitness = fitness;
				kwisatch_haderach = population[i]->Clone();
			}
			if(verbosity>=8) {
				population[i]->dump(outfile);
			}
		}

		// now renormalize the fitnesses st sum of all fitness[i]=1
		for(i=0;i<psize;i++) {
			population[i]->myFitness = population[i]->myFitness / sum;
		}

		// we now know the fitnesses of our children relative 
		// to our parents--time for 

		// SURVIVAL OF THE FITTEST

		// to keep the population size constant, we must kill off the
		// same number that are bred, namely nkids
		for(i=0;i<nkids;i++) {
			// in each iteration, kill off the least fit of the surviving
			// population
			min_i = -1;
			min_fitness = 1.0; // can't get better than perfect

			for(a=0;a<psize;a++) {
				// consider only live members for termination
				if(!population[a]->alive) continue;
				
				fitness = population[a]->myFitness;
				if(fitness<min_fitness) {
					min_i = a;
					min_fitness = fitness;
				}
			}

			// so the least fit of the surviving memebers of the
			// population is at location min_i--kill it

			population[min_i]->alive = false;
		} // end of SURVIVAL OF THE FITTEST loop
/*
		// count living kids
		nliving = 0;
		for(i=0;i<psize;i++) {
			if(population[i]->alive) nliving++;
		}

		printf("After Survival of the Fittest, nliving = %i\n",nliving);
*/
		// we must re-normalize the fitnesses of the remaining,
		// living members of the population
		sum = 0.0;
		for(i=0;i<psize;i++) {
			if(!population[i]->alive) continue;
			fitness = population[i]->Fitness();
			population[i]->myFitness = fitness;
			sum += fitness;
		}

		for(i=0;i<psize;i++) {
			population[i]->myFitness = population[i]->myFitness / sum;
		}

		// the next generation can begin now
		
	} // end of generation

	// deallocate the entire population (except KH)
	for(i=0;i<psize;i++) {
		delete population[i];
	}
	
	delete population;

	if(verbosity>=5) {
		fprintf(outfile,"Genetic returning best fitness = %f\n",max_fitness);
		kwisatch_haderach->dump(outfile);
	}

	return kwisatch_haderach;
}