metagenetic.cpp

来自「uploading the file , the system will del」· C++ 代码 · 共 340 行

#include "metagenetic.h"
#include "rand32.h"

void MetaGenetic(Netlist * nl, /*Constraints*/
				 double Rc, /* Crossover Rate */
				 double Rm, /* Mutation Rate */
				 int    Np, /* Population size */
				 int    Ng, /* Number of Meta-generations */
				 int    Np_gen, /* Pop size of Genetic() calls */
				 int    Ng_gen, /* Number of generations to Genetic() */
				 FILE * outfile, /* Where to dump */
				 int verbosity /*How much to dump*/) {
	if(verbosity >= 5) {
		fprintf(outfile,"Entering Meta-Genetic:\n");
		fprintf(outfile,"  Rc = %f",Rc);
		fprintf(outfile,"  Rm = %f",Rm);
		fprintf(outfile,"  Np = %i  Ng = %i\n",Np,Ng);

	}

	// this is the best solution so far
	Placement * kwisatch_haderach = NULL;
	Placement * p;

	// 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 i;

	GenParamSet ** population = new GenParamSet*[psize];

	if(verbosity>=5) {
		fprintf(outfile,"  PSize = %i  NKids = %i\n",psize,nkids);
		fprintf(outfile,"Using the following population parameters for Genetic():\n");
		fprintf(outfile,"  Np = %i  Ng = %i\n",Np_gen,Ng_gen);
	}

	double fitness;
	double Rc_pass, Ri_pass, Rm_pass;
	int a, b, kid;
	double min_fitness;
	int    min_i;
	bool mutant;

	GenParamSet best_params;

	// allocate the population members, and generate the first
	// generation randomly
	if(verbosity >=3 ) {
		fprintf(outfile,"META-GENETIC: Initial Population:\n");
	}

	for( i=0;i<psize;i++) {
		population[i] = new GenParamSet;

		if(i<psize-nkids) {
			// generate the member randomly,
			// set it as alive, and evaluate it
			population[i]->Rc_param = randOnRange(0,20);
			population[i]->Ri_param = randOnRange(0,20);
			population[i]->Rm_param = randOnRange(0,20);

			// it is ALIVE!!
			population[i]->alive = true;

			// convert to useful parameters
			Rc_pass = 0.04 * population[i]->Rc_param + 0.2;
			Ri_pass = 0.05 * population[i]->Ri_param;
			Rm_pass = 0.005 * population[i]->Rm_param;

			// evaluate this parameter set
			p = Genetic(nl, Rc_pass,Rm_pass,Ri_pass,
				Np_gen,Ng_gen,outfile,verbosity);

			fitness = p->myFitness;
			population[i]->fitness = fitness;

			if(verbosity>=3) {
				fprintf(outfile,"Member #%i: Fitness = %f\n",i,fitness);
			}
			
			if(kwisatch_haderach==NULL) {
				kwisatch_haderach = p->Clone();
				best_params.fitness = 0.0;
				best_params.Rc_param = population[i]->Rc_param;
				best_params.Ri_param = population[i]->Ri_param;
				best_params.Rm_param = population[i]->Rm_param;
			}

			if(verbosity>=4) {
				fprintf(outfile,"Rc = %f\tRi = %f\tRm = %f\n",
					Rc_pass,Ri_pass,Rm_pass);
			}

			if(fitness>kwisatch_haderach->myFitness) {
				// new best
				delete kwisatch_haderach;
				kwisatch_haderach = p->Clone();
				best_params.fitness = 0.0;
				best_params.Rc_param = population[i]->Rc_param;
				best_params.Ri_param = population[i]->Ri_param;
				best_params.Rm_param = population[i]->Rm_param;
			}

			delete p;
			
						
		} else {
			// just set the member as dead
			population[i]->alive = false;
			population[i]->fitness = 0.0;
		}
	}

	if(verbosity>=2) {
		fprintf(outfile,"META-GENETIC: Best solution from inital members has fitness %f\n",
			kwisatch_haderach->myFitness);
		if(verbosity>=4) {
			kwisatch_haderach->dump(outfile);
		}
	}

	// start the genetic loop
	for(int current_generation=0;current_generation<Ng;current_generation++) {
		if(verbosity>=4) {
			fprintf(outfile,"META-GENETIC: Starting generation %i\n",current_generation);
		}

		// BENE GESSERIT BREEDING PROGRAM -- generate nkids offspring
		for(i=0;i<nkids;i++) {
			// select two unique living parents randomly
			// "living" parents are both alive and have nonzero fitness
			do{
				do {
					a = randOnRange(0,psize-1);
				} while(!population[a]->alive||population[a]->fitness==0.0);

				do {
					b = randOnRange(0,psize-1);
				} while(!population[b]->alive||population[b]->fitness==0.0);
			} while(a!=b);

			// find a spot for their offspring
			for(kid=0;kid<psize;kid++) {
				if(population[kid]->alive) continue;
				break;
			}

			// should never happen
			if(kid==psize) {
				fprintf(outfile,"DANGER, Will Robinson!\n");
				fprintf(outfile,"No room for child in population (META)!\n");
			}

			// generate the kid
			population[kid]->alive = true;
			population[kid]->fitness = 0.0;
			population[kid]->Rc_param = 
				(rand()%2==0) ? population[a]->Rc_param : population[b]->Rc_param;
			population[kid]->Ri_param = 
				(rand()%2==0) ? population[a]->Ri_param : population[b]->Ri_param;
			population[kid]->Rm_param = 
				(rand()%2==0) ? population[a]->Rm_param : population[b]->Rm_param;

			mutant = false;

			// MUTATE this child with probability Rm
			if(randNorm()<Rm) {
				mutant = true;
				// decide which parameter to mutate
				switch(randOnRange(0,2)) {
				case 0:
					// mutate Rc
					population[kid]->Rc_param = population[kid]->Rc_param + randOnRange(-2,2);
					if(population[kid]->Rc_param<0) population[kid]->Rc_param = 0;
					if(population[kid]->Rc_param>20) population[kid]->Rc_param = 20;
					break;
				case 1:
					// mutate Ri
					population[kid]->Ri_param = population[kid]->Ri_param + randOnRange(-2,2);
					if(population[kid]->Ri_param<0) population[kid]->Ri_param = 0;
					if(population[kid]->Ri_param>20) population[kid]->Ri_param = 20;
					break;
				default:
					// mutate Rm
					population[kid]->Rm_param = population[kid]->Rm_param + randOnRange(-2,2);
					if(population[kid]->Rm_param<0) population[kid]->Rm_param = 0;
					if(population[kid]->Rm_param>20) population[kid]->Rm_param = 20;
					break;
				}
			}

			if(verbosity>=4) {
				Rc_pass = 0.04 * population[kid]->Rc_param + 0.2;
				Ri_pass = 0.05 * population[kid]->Ri_param;
				Rm_pass = 0.005 * population[kid]->Rm_param;
				if(mutant) {
					fprintf(outfile,"Child %i: Rc = %f  Ri = %f  Rm = %f  MuTaNt\n",
						i,Rc_pass,Ri_pass,Rm_pass);
				} else {
					fprintf(outfile,"Child %i: Rc = %f  Ri = %f  Rm = %f\n",
						i,Rc_pass,Ri_pass,Rm_pass);
				}
			}
		} // end of BENE GESSERIT BREEDING PROGRAM

		// EVALUATION

//		b = 0; a = 0;
		for(i=0;i<psize;i++) {
			if(population[i]->fitness!=0.0) {
//				a++;
//				fprintf(outfile,"Skipping member %i for nonzero fitness\n",i);
				continue; // no need to reevaluate known members
			}
//			b++;
			// convert to useful parameters
			Rc_pass = 0.04 * population[i]->Rc_param + 0.2;
			Ri_pass = 0.05 * population[i]->Ri_param;
			Rm_pass = 0.005 * population[i]->Rm_param;

			// evaluate this parameter set
			p = Genetic(nl, Rc_pass,Rm_pass,Ri_pass,
				Np_gen,Ng_gen,outfile,verbosity);

			fitness = p->myFitness;
			population[i]->fitness = fitness;

			if(fitness>kwisatch_haderach->myFitness) {
				// new best
				delete kwisatch_haderach;
				kwisatch_haderach = p->Clone();
				best_params.fitness = (double) current_generation;
				best_params.Rc_param = population[i]->Rc_param;
				best_params.Ri_param = population[i]->Ri_param;
				best_params.Rm_param = population[i]->Rm_param;
				if(verbosity>=2) {
					fprintf(outfile,"New best solution found. Fitness = %f\n",
						kwisatch_haderach->myFitness);

					if(verbosity>=4) {
						kwisatch_haderach->dump(outfile);
					}
				}
			}

			delete p;

		} // end of evaluation

//		fprintf(outfile,"EVALUATED %i\tSKIPPED %i\n",b,a);

		// SURVIVAL OF THE FITTEST
		// kill off nkids members of the population
		for(i=0;i<nkids;i++) {
			// find the minimum fitness of the living members
			min_i = -1;
			min_fitness = 1.9;
			for(b=0;b<psize;b++) {
				if(!population[b]->alive) continue; // ignore the dead

				fitness = population[b]->fitness;
				if(fitness<min_fitness) {
					// found a new local low
					min_i = b;
					min_fitness = fitness;
				}

			}

			// kill the worst parameter set
			population[min_i]->alive = false;
			population[min_i]->fitness = 0.0;

			if(verbosity>=4) {
				fprintf(outfile,"Killing member %i with fitness %f\n",min_i,min_fitness);
			}
		} // end of SURVIVAL OF THE FITTEST

	} // end of generation

	// clean up the population
	for(i=0;i<psize;i++)
		delete population[i];

	delete population;

	// Metagetic is over: print the final solution
	fprintf(outfile,"Meta-Genetic optimization complete.\n");
	fprintf(outfile,"Best parameters were:\n");
	Rc_pass = 0.04 * best_params.Rc_param + 0.2;
	Ri_pass = 0.05 * best_params.Ri_param;
	Rm_pass = 0.005 * best_params.Rm_param;
	fprintf(outfile,"Rc = %f\tRi = %f\tRm = %f\n",Rc_pass,Ri_pass,Rm_pass);
	fprintf(outfile,"Generation #%i produced the best solution.\n",(int)best_params.fitness);
	fprintf(outfile,"Most fit placement found: (Fitness = %f)\n",kwisatch_haderach->myFitness);
	kwisatch_haderach->dump(outfile);
	fprintf(outfile,"Wire length = %i\n",(int) (1 / (kwisatch_haderach->myFitness)));

	delete kwisatch_haderach;
}

Placement *
PseudoGenetic(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 */) {
	Placement * p = new Placement(nl);

	// "optimal" values
	// Rc = 0.30
	// Rm = 0.07
	// Ri = 0.30

	double x = 0.0;
	x += (0.30 - Rc) * (0.30 - Rc);
	x += (0.07 - Rm) * (0.07 - Rm);
	x += (0.30 - Ri) * (0.30 - Ri);

	x += 1.0;

	p->Randomize();
	p->myFitness = 1 / x;

	if(p->myFitness<0.01) p->myFitness = 0.01;

	return p;
}