/* File: SimulatedAnnealing.cpp * Author: Dan Gibson *         ECE 556 HW 3 * Contents: * The implementation of the functions required * for problem 1 of hw 3 * * Last modified: * Development platforms: Solaris 9, MS-DOS, WINNT * Intended platforms: Solaris 9 */#include "SA_floor.h"#include <stdio.h>				/* for fprintf */#include <math.h>				/* for floor and exp */#include <stdlib.h>				/* rand() and srand() */#include <time.h>				/* for time() */#include <string.h>				/* for strtok() */#ifndef NULL#define NULL 0x00000000#endif/********************************************************** * Function name: SimulatedAnnealing() * Author: Dan Gibson * * Parameters: * E0			A Floorplan object representing a starting *				solution. * lambda		The cooling rate parameter (0<lambda<1) *				Recommended = 0.85 * * Return value * * SimulatedAnnealing() returns the best solution found. * **********************************************************/void SimulatedAnnealing(Floorplan * E0,							   double lambda = 0.85,							   double T0 = 65536.0,							   double Tf = 10.0,							   unsigned int M1_prob = 4,							   unsigned int M2_prob = 2,							   unsigned int M3_prob = 1){	/* Variable declaration */	Floorplan * E;				 /* Current solution */	Floorplan * newE;			 /* Proposed next solution */	Floorplan * Best;			 /* Best solution so far */	double T;					 /* current temperature */	unsigned int uphill;		 /* Number of uphill moves									at a given temperature */	unsigned int MT;			 /* Total # moves at a given									temperature */	unsigned int prob_radix;	 /* Used to determine likelihood									of a given move type */	unsigned int reject;		 /* Number of rejections */	unsigned int N;				 /* An increasing function of									the number of modules */	unsigned int nModules;		 /* the number of modules in								    the floorplan */	unsigned int nOperators;	 /* the number of operators								    in the floorplan */	unsigned int best_cost;		 /* the cost of the best solution */	unsigned int current_cost;	 /* the cost of the current solution */	unsigned int new_cost;		 /* the cost of the new solution */	bool verbose;				 /* used to determine output */	int printed;				 /* used to format output */	unsigned int step;			 /* Keeps track of how many solutions									have been considered */	int delta_cost;		/* Parameter checking */	bool parameter_errors = false;	if(E0==NULL) {		fprintf(stderr,"SimulatedAnnealing: Parameter 1 (Floorplan * E0) is NULL\n");		parameter_errors = true;	}	if(lambda<=0||lambda>=1) {		fprintf(stderr,"SimulatedAnnealing: Parameter 2 (double lambda) is not 0<lambda<1\n");		parameter_errors = true;	}	if(parameter_errors) {		fprintf(stderr,"SimulatedAnnealing: Exited under abnormal conditions\n");		return;	}	/* Random number generator initialization (seed) */	srand(time(NULL));	/* Variable initialization */	E      = E0;	Best   = E0->Clone();	uphill = 0;	MT     = 0;	reject = 0;	step   = 0;		prob_radix = M1_prob+M2_prob+M3_prob;	nModules = E->getModuleCount();	nOperators = E->getOperatorCount();	if(nModules<15) N = nModules*nModules;
	else N = 2*nModules;	current_cost = E->getArea();	best_cost = current_cost;	verbose = nModules < 20;		// to define T:	T  = T0;	// print the initial solution	if(verbose) {		fprintf(stdout,"Initial Floorplan: ");		E->dumpList(); // dumpList faster than dumpTree	} else {		fprintf(stdout,"Initial");	}	fprintf(stdout," Cost: %i",current_cost);	fprintf(stdout,"\n\n***Start of Simulated Annealing***\n\n");	// outer REPEAT/UNTIL statement	// Note: ignores the OUT_OF_TIME concept	do{		// reset inner-loop variables		MT = uphill = reject = 0;		// inner REPEAT/UNTIL statement		do{			// Select a move to perform according			// to the probability parameters			unsigned int r = RandOnRange(1,prob_radix);			int M;			if(r<=M1_prob) M = 1;			else if(r<=M1_prob+M2_prob) M = 2;			else M = 3;			newE = E->Clone();			switch(M) {			case 1:				// do an M1-type move: swap two adjacent				// operators				// we want to swap a random pair of modules				while(!newE->M1( RandOnRange(1,nModules) )) {					//fprintf(stdout,"a");				}								break;			case 3:				// do an M3-type move: swap operand/operator				// if the floorplan is in a state to accept				// ANY M3-type move, then do it,				// otherwise do an inversion				if(newE->M3OK()) {					// want to swap Nth and (N+1)th operand/operator					while(newE->M3(RandOnRange(0,nModules+nOperators-1))!=0) {					//	fprintf(stdout,"c");					}					break;				}			case 2:
				// do an M2-type move: chain-invert operators

				// want to invert a random chain of operators
				while(newE->M2( RandOnRange(0,nOperators-1))==0) {
					//fprintf(stdout,"b");
				}

				break;			default:				// this can't happen, but it makes the compiler				// happy to have a default statement				return;			}			// considering another solution			step++;			// pretty-print the current step			printed = fprintf(stdout,"%i ",step);			for(int i=0;i<10-printed;i++) fprintf(stdout," ");			// pretty-print the polish expression if needed			if(verbose) newE->dumpList();			// something has been done to newE to make			// it different from E			new_cost = newE->getArea();			// print the cost			printed = fprintf(stdout,"  %i ",new_cost);			for(int j=0;j<10-printed;j++) fprintf(stdout," ");			// if verbose, print the temperature			if(verbose) fprintf(stdout,"%f ",T);			// increment # moves at current temerature			MT++;			// compute the difference in costs between current and			// new solutions			delta_cost = ((int) new_cost) - ((int) current_cost);			// if this happens to be the best solution so far,			// save it off!			if(new_cost<best_cost) {				// newE is better than Best!				best_cost = new_cost;				delete Best;				Best = newE->Clone();			}						if(delta_cost<0) {				// newE is better than E!, so				// automaticaly accept the solution				delete E;				E = newE;
				current_cost = new_cost;				// print acceptance				fprintf(stdout,"Y\n");			} else {				// newE is uphill from E				if(Rand01() < exp(((double)-delta_cost)/T)) {					// accept the new solution anyway,					// despite being and uphill move					uphill++;					delete E;					E = newE;					// print acceptance					fprintf(stdout,"Y\n");									} else {					// reject the move					reject++;					delete newE;					// print rejection					fprintf(stdout,"N\n");				}			}		} while(uphill<=N && MT <= 2*N);		// Temperature cools down		T = lambda * T;	}while(((double)reject) <= 0.99 * ((double) MT) &&		   (T>=Tf));	fprintf(stdout,"\n***End of Simulated Annealing***\n");	fprintf(stdout,"Final solution:\n");	Best->dumpList();	fprintf(stdout,"\n\nCost: %i\n",best_cost);

	// do the memory cleanup	delete E;	delete Best;
	return;	}unsigned int RandOnRange(unsigned int low, unsigned int high) {	return (rand()%(high-low+1))+low;};double Rand01() {	double retval;	retval = 0.001 * RandOnRange(0,999);	return retval;}Floorplan * ReadFloorplanFromFile(char * filename) {	Floorplan * f;	FILE * infile;	// open the file	infile = fopen(filename,"r");	if(infile==NULL) return NULL; // if file can't be opened, signal error	// file format is	// M<index> <height> <width>	int i1,h1,w1,i2,h2,w2;	char buff_in[1024];	char * token;	// read the first two lines separately from the	// rest, since the first two modules are 	// used in Floorplan's constructor	if(!fgets(buff_in,1024,infile)) return NULL;	// get the index of the first mod	token = strtok(buff_in,"M \t\n");	i1 = atoi(token);	// get the height of the first mod	token = strtok(NULL," \t\n");	if(token!=NULL) h1 = atoi(token);	else return NULL;	// get the width of the first mod	token = strtok(NULL," \t\n");	if(token!=NULL) w1 = atoi(token);	else return NULL;	// read in the second line	if(!fgets(buff_in,1024,infile)) return NULL;	// get the index of the second mod	token = strtok(buff_in,"M \t\n");	i2 = atoi(token);	// get the height of the second mod	token = strtok(NULL," \t\n");	if(token!=NULL) h2 = atoi(token);	else return NULL;	// get the width of the second mod	token = strtok(NULL," \t\n");	if(token!=NULL) w2 = atoi(token);	else return NULL;	// ready to call the constructor	f = new Floorplan(i1,w1,h1,i2,w2,h2);	// loop to read in the rest of the modules	while(fgets(buff_in,1024,infile)) {		token = strtok(buff_in,"M \t\n");		if(token!=NULL) i1 = atoi(token);		else continue; // ignore blank lines		token = strtok(NULL," \t\n");		if(token!=NULL) h1 = atoi(token);		else return f; // truncate file at incommplete specification		token = strtok(NULL," \t\n");		if(token!=NULL) w1 = atoi(token);		else return f;		f->AddModule(i1,w1,h1);	}	// close the file	fclose(infile);		return f;}