proj2.cpp

Simulated Annealing SA Hill Climbing HC Local Beam Search LBS Genetic Algorithm GA

// By Youhanna Parvizinejad 83405169  + Keyvan Nakhaiee + mehdi farahmandfar

#include<iostream.h>
#include<math.h>
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include"func.cpp"

//-------------------------------------------------------------
class node{
	public:
		double x,y,z,h;
		int p;
		node();
		void setval(double ,double ,double ,double );
		void setmax();
};


//-------------------- Initializing a node ---------------------------
node::node(){
	x=y=z=h=0;
}


//--------------------- Set Values for a node ------------------
void node::setval(double x1,double y1,double z1,double h1)
{
	x=x1;
	y=y1;
	z=z1;
	h=h1;
}

//-------------------------------------------------------------
void node::setmax(){
	h=10000000;
}


//-------------------------------------------------------------
inline int putneighb(char *);
int calculat();
int calculat2();
void calc3(int);
int beam(int);
int genet(int);


//-------------------------------------------------------------
const int ky=2;
double d,dnu[ky],dnu2[ky],dnt,*dnum=dnu,*dnum2=dnu2,*dnum3;
int worse=0,best=0,sf;
node point1,loc,neighb,nod1[ky],nod2[ky],*node1=nod1,*node2=nod2,*node3;


//-------------------------------------------------------------

inline void fixit(){ 
	int cf1=1,cf2=1;
	if(loc.h<0)
		cf2=-1;
	if(point1.h<0)
		cf1=-1;
	if((cf2*loc.h)<(cf1*point1.h)){
		point1.setval(loc.x,loc.y,loc.z,loc.h);
	}
}


//-------------------------------------------------------------

inline long int getn(){
	long int n;
	cout<<"Enter Number Of Try"<<endl;
	cin>>n;
	cout<<endl;
	return n;
}


//-------------------------------------------------------------
inline void prt(){
	cout<<"-----------------------------------------------"<<endl;
}

//-------------------------------------------------------------


inline void swapn(){
	node3=node1;
	node1=node2;
	node2=node3;
}


//-------------------------------------------------------------

inline void swapd(){
	dnum3=dnum;
	dnum=dnum2;
	dnum2=dnum3;
}
//-------------------------------------------------------------

inline void reset(){
	loc.setval(((double)(1000-rand()%2000))/10,((double)(1000-rand()%2000))/10,((double)(1000-rand()%2000))/10,0);
	loc.h=funcVal(loc.x,loc.y,loc.z);
}


//-------------------------------------------------------------

inline void analys(){
	for (int i=0;i<ky;i++){
		if((node2[i].h)>(node2[worse].h)){
			worse=i;
		}
		if((node2[i].h)<(node2[best].h)){
			best=i;
		}
	}
}


//-------------------------------------------------------------


inline int analys1(){
	for (int i=0;i<ky;i++){
		if(node1[i].h>(node1[worse].h)){
			worse=i;
		}
		if((node1[i].h)<(node1[best].h)){
			best=i;
		}
	}
	return best;
}


//-------------------------------------------------------------

inline void restart(int i){
	node1[i].setval(((double)(1000-rand()%2000))/10,((double)(1000-rand()%2000))/10,((double)(1000-rand()%2000))/10,0);
	node1[i].h=funcVal(node1[i].x,node1[i].y,node1[i].z);
	if ((node1[i].h)<0)
		node1[i].h*=-1;
}

//-------------------------------------------------------------


void main(int argc,char *argv[]){
	long int  n=0,m=0;
	if(argc!=2){
		cout<<"Invalid Number of Line Command "<<endl;
		getch();
		exit(1);
	}   
	if((*argv[1]>'0')&&(*argv[1]<'5')){
		n=getn();
	}
	else{
		cout<<"Entered Parameter is not valid "<<endl;
		cout<<endl<<"Press any key to Exit"<<endl;
		getch();
		exit(1);
	}

	prt();
	cout<<"Used Algorithm :";
	switch(*argv[1]){
		case '1':
		case '2':
			if(*argv[1]=='1'){
				cout<<"Hill Climbing + Random Restart"<<endl;
			}
			else {
				cout<<"Simulated Annealing"<<endl;
			}
			reset();
			point1.setval(loc.x,loc.y,loc.z,loc.h);
			if (loc.h>1){
				d=pow(loc.h,0.5);
			}
			else
				d=0.5;
			m=n;

			while ((n>0)&&(((loc.h)>0.00000001)||(loc.h<-0.00000001))){
				n--;
				if(putneighb(argv[1])==1){
					if(loc.h>1){
						d=pow(loc.h,0.5);
					}
					else
						d=2*d/3;
				}
				else {
					if (d-0.00000001<0){
						fixit();
						reset();
						}
					else
						d=2*d/3;
				}
			}
			fixit();
			m-=n;
			break;

		case '3':
			cout<<"Local Beam Search"<<endl;
			m=n-beam(n);
			break;
		case '4':
			cout<<"Genetic"<<endl;
			m=n-genet(n);
			break;
		default :
			cout<<"S is Not in range !" <<endl;
			getch();
			exit(1);
	}
	prt();
	cout<<endl<<"Results are : X="<<point1.x<<" Y="<<point1.y<<" Z="<<point1.z<<" Result="<<point1.h<<endl<<"Number of try :"<<m<<endl;
	cout<<endl<<"Press any key to continue"<<endl;
	getch();
}


//-------------------------------------------------------------------------------

int putneighb(char *s){
	int select;
	switch(*s){
		case '1':
			select=calculat();
			break;
		case '2':
			select=calculat2();
			break;
		default:
			cout<<"Error in Transfering Line Commands"<<endl;
			getch();
			exit(1);
		}
	if (select !=13){
		return 1;}
	else
		return 0;
}


//-------------------------------------------------------------------------------

int calculat2(){
	if (loc.h<0)
		d*=-1;
	int nextstp=13,ranv,counter=1,p=1;

	ranv=rand()%(1000+p*25);
	if (ranv<1000)
		nextstp=calculat();
	else {
		ranv-=1000;
		if(ranv>13){
			ranv++;
			cout<<"Ranv is :"<<ranv<<endl;
			}
		nextstp=ranv;
		if(nextstp!=13){
			for(int i=0;((i<3)&&(counter<=ranv));i++){
				for(int j=0;((j<3)&&(counter<=ranv));j++){
					for(int k=0;((k<3)&&(counter<=ranv));k++){
						if(counter==ranv){
							loc.x=loc.x+(k-1)*d;
							loc.y=loc.y+(j-1)*d;
							loc.z=loc.z+(i-1)*d;
							loc.h=funcVal(loc.x,loc.y,loc.z);
						}
					}
				}
			}
		}
	}
	return nextstp;
}


//------------------------------------------------------------------------------
int calculat(){
	if (loc.h<0)
		d*=-1;
	int nextstp=13;
	node n;
	n.setval(loc.x,loc.y,loc.z,loc.h);
	int counter=1;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			for(int k=0;k<3;k++){
				neighb.setval(loc.x+(k-1)*(d),loc.y+(j-1)*(d),loc.z+(i-1)*(d),0);
				neighb.h=funcVal(neighb.x,neighb.y,neighb.z);
				if(neighb.h<0){
					neighb.h*=-1;
				}
				if(neighb.h<n.h){
					nextstp=counter;
					n.setval(neighb.x,neighb.y,neighb.z,neighb.h);
				}
				counter++;
				}
			}
		}
	if(nextstp!=13)
		loc.setval(n.x,n.y,n.z,n.h);
	return nextstp;
}


//------------------------------------------------------------
void calc3(int ptnum){
	node temp;
	if((node1[ptnum].h)<1){
		d=dnum[ptnum];
		dnum[ptnum]*=.5;
	}
	else {
		dnum[ptnum]=pow((node1[ptnum].h),0.5);
		d=dnum[ptnum];
	}

	loc.setval(node1[ptnum].x,node1[ptnum].y,node1[ptnum].z,node1[ptnum].h);
	while(13==calculat()){
		if((d-0.00000001)<0){
			break;
		}
		dnum[ptnum]*=0.5;
		d=dnum[ptnum];
	}

	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			for(int k=0;k<3;k++){
					temp.setval(node1[ptnum].x+(k-1)*(d),node1[ptnum].y+(j-1)*(d),node1[ptnum].z+(i-1)*(d),0);
					temp.h=funcVal(temp.x,temp.y,temp.z);
					if ((temp.h)<0)
						temp.h*=-1;
					if((temp.h)<((node2[worse].h))){
						node2[worse].setval(temp.x,temp.y,temp.z,temp.h);
						dnum2[ptnum]=dnum[ptnum];
						analys();
					}
			}
		}
	}
}


//-------------------------------------------------------------
int beam(int n){
	int best_node1=0;
	for (int i=0;i<ky;i++){
		restart(i);
		node2[i].setmax();
		dnum[i]=.5;
	}
	analys();
	while ((n>0)&&((node1[best_node1].h)-(0.00000001)>0)){
		for(int i=0;i<ky;i++){
			calc3(i);
		}
		swapn();
		for(i=0;i<ky;i++)
				node2[i].setmax();
		swapd();
		n--;
		best_node1=analys1();
	}

	point1.setval(node1[best_node1].x,node1[best_node1].y,node1[best_node1].z,funcVal(node1[best_node1].x,node1[best_node1].y,node1[best_node1].z));
	return n;
}


//-------------------------------------------------------------
int genet(int n){
	int best_node1=0;

	for (int i=0;i<ky;i++){
		restart(i);
		node2[i].setval(node1[i].x,node1[i].y,node1[i].z,node1[i].h);
		dnum[i]=.5;
	}
	analys();
	while ((n>0)&&((node1[best_node1].h)-(0.00000001)>0)){
		for(int i=0;i<ky;i++){
			calc3(i);
		}
		swapn();
		for(i=0;i<ky;i++)
				node2[i].setmax();
		swapd();
		n--;
		best_node1=analys1();
	}

	point1.setval(node1[best_node1].x,node1[best_node1].y,node1[best_node1].z,funcVal(node1[best_node1].x,node1[best_node1].y,node1[best_node1].z));
	return n;
}