#include<math.h>
#include<iostream.h>
#include<utlab.h>

#define popsize 30
#define node 11
#define vehicle 4
#define S 15.

int x[popsize][node+1];     //染色體 popsize個
int y[popsize][vehicle+1];  //染色體 popsize個
double t[popsize][vehicle+1];  //染色體 popsize個

int x_tmp[popsize][node+1];         //染色體 popsize個,轉輪臨時放置
int y_tmp[popsize][vehicle+1];      //染色體 popsize個,轉輪臨時放置
double t_tmp[popsize][vehicle+1];   //染色體 popsize個,轉輪臨時放置



int d[node+1][node+1]=
{ 0, 18, 14, 14, 21, 21, 15, 22, 21, 18, 24, 14,
  18, 0, 20, 34, 49, 55, 49, 65, 57, 49, 50, 22,
  14, 20, 0, 15, 31, 41, 43, 56, 55, 52, 56, 35,
  14, 34, 15, 0, 16, 28, 36, 46, 51, 51, 58, 44,
  21, 49, 31, 16, 0, 16, 32, 37, 48, 52, 62, 54,
  21, 55, 41, 28, 16, 0, 21, 21, 36, 43, 54, 55,
  17, 49, 43, 36, 32, 21, 0, 15, 16, 22, 34, 41,
  22, 65, 56, 46, 37, 21, 15, 0, 21, 33, 44, 56,
  21, 57, 55, 51, 48, 36, 16, 21, 0, 13, 24, 43,
  18, 49, 52, 51, 52, 43, 22, 33, 13, 0, 11, 32,
  24, 50, 56, 58, 62, 54, 34, 44, 24, 11, 0, 36,
  14, 22, 35, 44, 54, 55, 41, 56, 43, 32, 36, 0,
};

int tw[node+1][2]=
{0,  0,
 90, 370,
 80, 180,
 100, 190,
 130, 360,
 80, 300,
 70, 440,
 100, 320,
 20, 120,
 100, 250,
 50, 260,
 80, 120,
};

int tt[node+1][node+1][3]=
{
	0,0,0,  25,50,75,  5,10,15,  25,50,75,  7,15,23,  25,50,75,  25,50,75,  12,25,38,  7,15,23,  25,50,75,  10,20,30,  25,50,75,  
	25,50,75,  0,0,0,  20,40,60,  5,10,15,  25,50,75,  17,35,53,  7,15,23,  20,40,60,  20,40,60, 7,15,23,  22,45,68,   5,10,15,
	5,10,15,  20,40,60,  0,0,0,   20,40,60, 7,15,23,   17,35,53,  20,40,60,  15,30,45, 5,10,15,  22,45,68, 12,25,38,   17,35,53,
	25,50,75,  5,10,15,  20,40,60, 0,0,0,   22,45,68,  15,30,45,  2,5,8,   17,35,53,  22,45,68,  5,10,15,  22,45,68,   15,30,45,
	7,15,23,  25,50,75,  7,15,23,  22,45,68, 0,0,0,    17,35,53,  22,45,68,  7,15,23,  10,20,30,  22,45,68,  7,15,23,  17,35,53,
	25,50,75,  17,35,53, 17,35,53, 15,30,45,  17,35,53, 0,0,0,    15,30,45,  12,25,38, 17,35,53,  15,30,45,  15,30,45,  5,10,15,
	25,50,75,  7,15,23,  20,40,60,  2,5,8,  22,45,68,  15,30,45,  0,0,0,  17,35,53,  20,40,60,  5,10,15,  20,40,60,  15,30,45,
	12,25,38,  20,40,60,  15,30,45, 17,35,53, 7,15,23,  12,25,38,  17,35,53,  0,0,0,  17,35,53,  20,40,60, 5,10,15,   5,10,15,
	7,15,23,  20,40,60,  5,10,15,  22,45,68,  10,20,30,  17,35,53,  20,40,60,  17,35,53, 0,0,0,  20,40,60,  12,25,38,  17,35,53,
	25,50,75,  7,15,23,  22,45,68,  5,10,15,  22,45,68, 15,30,45,  5,10,15,  20,40,60,  20,40,60,  0,0,0,  22,45,68,  17,35,53,
	10,20,30,  22,45,68, 12,25,38,  22,45,68, 7,15,23,  15,30,45,  20,40,60, 5,10,15,  12,25,38,  22,45,68,  0,0,0,   15,30,45,
	25,50,75,  5,10,15,  17,35,53,  15,30,45,  17,35,53, 5,10,15,  15,30,45, 5,10,15,  17,35,53,  17,35,53,  15,30,45, 0,0,0,
};
int rdint(int l,int r)//生成l-r的隨機整數
{
	double x;
	int a;
	x=myu(l,r+0.99);
	a=int(floor(x));
	return(a);
}


void init(double cr0)//初始化數據
{
	int i,j,k,w,nm;
	double counter=0.;
	double cr_tmp;
	int ct;
	
	double cr(int m);
	int distance(int m);

	double cro;

	int tt[node+1];
	int te;
	int judge;
	for(i=1;i<=node;i++)
		tt[i]=0;
		
	for(i=0;i<popsize;i++)	
	{
		nm=0;
		cro=0.;
		cr_tmp=0.;



		while(cro<(cr0))
		{
			for(k=1;k<=node;k++)
				tt[k]=0;
			j=1;
			while(j<=node)
			{
				te=rdint(1,node);
				judge=1;
				for(k=1;k<=node;k++)
					if(tt[k]==te)
						judge=judge*0;
				if(judge==1)
				{
					x[i][j]=te;
					tt[j]=te;
					j++;
				}
				else
					continue;
			}

			//以上初始化x.

	
			for(k=1;k<vehicle;k++)
			{
				y[i][k]=rdint(0,node);
			}

			//sort
			for(j=1; j<vehicle; j++)
				for(k=j+1; k<vehicle; k++) 
					if(y[i][j] > y[i][k]) 
					{
						w = y[i][k];
						y[i][k] = y[i][j];
						y[i][j] = w;
					}
	
	
				y[i][0]=0;
				y[i][vehicle]=node;
	
   
				//以上初始化y

	
			for(k=1;k<=vehicle;k++)
			{
				t[i][k]=double(rdint(30.,120.));
			}

			//以上初始化t
			cro=cr(i);
		}
		system("cls");
		counter=double(i)/popsize*100;
		ct=floor(counter);
		cout<<"Initializing..."<<ct<<"%"<<endl;
	}

	system("cls");
	cout<<"Initializing...100%"<<endl;

}



void chrom(int a)
{
	int distance(int a);
	double cr(int a);
	int j;
	cout<<endl;
	cout<<"x["<<a<<"]= ";
	for(j=1;j<=node;j++)
		cout<<x[a][j]<<"  ";		
	   
	cout<<endl;
	cout<<"y["<<a<<"]= ";
	for(j=0;j<=vehicle;j++)
		cout<<y[a][j]<<"  ";		
	    
	cout<<endl;
	cout<<"t["<<a<<"]= ";
	for(j=0;j<=vehicle;j++)
		cout<<t[a][j]<<"  ";
	cout<<endl; 
	cout<<"  cr  "<<cr(a)<<"  dist  "<<distance(a)<<endl;
}


void crossover(int a, int b, double cr0)
{
	int i,tm;
	double c;
	
	double tp,cro1,cro2;
	int yp;
	
	bool feasible(int a,double cr0);
	void map(int a, int b);
	void bmap(int a, int b);
	double max(double a, double b);
	double cr(int m);

	tm=0;
	cro1=0.;
	cro2=0.;

	map(a,a);
	map(b,b);

	while((tm<5)&&(max(cro1,cro2)<cr0))
	{
		c=myu(0,1);
		for(i=1;i<=vehicle;i++)
		{
			tp =c*t[a][i]+(1-c)*t[b][i];
			t[b][i]=t[a][i]*(1-c)+t[b][i]*c;
			t[a][i]=tp;
		}//crossover  t[a], t[b]
		for(i=1;i<=vehicle;i++)
		{
			yp=y[a][i];
			y[a][i]=y[b][i];
			y[b][i]=yp;
		}//crossover y.

		cro1=cr(a);
		cro2=cr(b);

		if(cro1<cr0)
			bmap(a,a);
		
		if(cro2<cr0)
			bmap(b,b);
	
		tm++;
		
	}
		
	map(a,a);
	map(b,b);
	

}

double min(double a, double b)
{
	if (a>b)
		return b;
	else return a;
}
double max(double a, double b)
{
	if (a<b)
		return b;
	else return a;
}

bool feasible(int a,double cr0)
{
	double cr(int );
	if(cr(a)>=cr0)
		return true;
	else 
		return false;
}



void mutation(int a, double cr0)
{
	int i,j,k, n1, n2, nn, xx, w, tm;
	double M;

	void map(int a, int b);
	void bmap(int a, int b);

	
	double cr(int m);
	double dt[vehicle+1];
	tm=0;
	M=1.;
	
	map(a,a);

mutatet: n1=rdint(1,node);
	n2=rdint(1,node);
	if(n1>n2)
	{
		nn=n1;
		n1=n2;
		n2=nn;
	}
	
	for(i=n1;i<=n2;i++)
	{
		nn=rdint(i,n2);
		xx=x[a][i];
		x[a][i]=x[a][nn];
		x[a][nn]=xx;
	}
	//mutate x

	n1=rdint(1,vehicle-1);
	n2=rdint(1,vehicle-1);

	if(n1>n2)
	{
		nn=n1;
		n1=n2;
		n2=nn;
	}
	
	for(i=n1;i<=n2;i++)
	{
		y[a][i]=rdint(0,node);
	}

	for(j=1; j<vehicle; j++)
		for(k=j+1; k<vehicle; k++) 
			if(y[a][j] > y[a][k]) 
			{
				w = y[a][k];
				y[a][k] = y[a][j];
				y[a][j] = w;
			}	

	//mutate y
	 
	dt[0]=0.;
	for(i=1;i<=vehicle;i++)
	{
		dt[i]=myu(0.,60.) - 30.;
	}
	for(i=1;i<=vehicle;i++)
	{
		if(dt[i]>=0.)
			t[a][i]=min(460., t[a][i] + dt[i]);
		else
			t[a][i]=max(10., t[a][i] + dt[i]);
	}
	
	
	if(cr(a)>=cr0)
		;
	else if(tm<6)
	{	
		bmap(a,a);
		
		M=myu(0.,M);
		tm++;
		goto mutatet;
	}
	else bmap(a,a);
	
	//mutate t;

}

int distance(int m)//the m-th chrom's distance
{
	int dis=0;
	int i,j;



	for(i=0;i<node;i++)
		dis+=d[x[m][i]][x[m][i+1]];

	dis+=d[x[m][11]][0];

	
	for(j=1;j<vehicle;j++)
	{
		if(y[m][j]!=y[m][j-1])
		{
			dis+=d[x[m][y[m][j]]][0];
			dis+=d[x[m][y[m][j]+1]][0];
			dis-=d[x[m][y[m][j]]][x[m][y[m][j]+1]];
		}

	}	
	return dis;
	
}

void map(int a, int b)  // original a-->temp b duplicate chrom.
{
	int i;
	for(i=0;i<=node;i++) 
		x_tmp[b][i]=x[a][i];
	for(i=0;i<=vehicle;i++)
	{
		y_tmp[b][i]=y[a][i];
		t_tmp[b][i]=t[a][i];
	}
}

void bmap(int a, int b) // temp a--> original b duplicate chrom.
{
	int i;
	for(i=0;i<=node;i++) 
		x[b][i]=x_tmp[a][i];
	for(i=0;i<=vehicle;i++)
	{
		y[b][i]=y_tmp[a][i];
		t[b][i]=t_tmp[a][i];
	}

}


double cr(int m)  //Cr{ai<fi<bi, i=1,2,...,n} for the m-th chrom.
{
	int N=3000;
	int i,j,k;
	int jg=1;
	double eps=0.2;
	double tf=0.;
	double mu[node+1]; //membership functions
	double miu;
	double mu1=0.;   
	double mu2=0.;	   //membership function for right and wrong
	int v[node+1];

	double f[node+1];

	int counter=0;

	//為xi編號，表示到達的vehicle。

	k=0;
	for(i=1;i<=vehicle;i++)
	{
		
		if(y[m][i]!=y[m][i-1])
		{
			for(j=k+1;j<=y[m][i];j++)
				v[j]=i;
			k=j-1;
		}
		else ;
	}

	

	v[0]=0;
	

	x[m][0]=0;

	for(i=0;i<(N-20);i++)
	{
		//generate rd number
		for(j=1;j<=node;j++)
		{
			if(v[j]!=v[j-1])
			{
				tf=myu(tt[0][x[m][j]][0],tt[0][x[m][j]][2]);
				mu[j]=triangle(tf,tt[0][x[m][j]][0],tt[0][x[m][j]][1],tt[0][x[m][j]][2]);
				f[j]=t[m][v[j]]+tf;
			}
			else
			{
				tf=myu(tt[x[m][j-1]][x[m][j]][0],tt[x[m][j-1]][x[m][j]][2]);
				mu[j]=triangle(tf,tt[x[m][j-1]][x[m][j]][0],tt[x[m][j-1]][x[m][j]][1],tt[x[m][j-1]][x[m][j]][2]);
				f[j]=max(f[j-1],tw[x[m][j-1]][0])+S+tf;
			}
		}

		mu[0]=1.;
		miu=1.;
		for(j=1;j<=node;j++)
			miu=min(miu,mu[j]);

		jg=1;
		for(j=1;j<=node;j++)
			if((f[j]<tw[x[m][j]][0])||(f[j]>tw[x[m][j]][1]))
				jg=0;
			else ;
		//judge

			
		if(jg==1)
			mu1=max(mu1,miu);
		else
			mu2=max(mu2,miu);		

	}
	for(;i<N;i++)
	{
		//generate rd number
		for(j=1;j<=node;j++)
		{
			if(v[j]!=v[j-1])
			{
				tf=myu(tt[0][x[m][j]][1]-eps,tt[0][x[m][j]][1]+eps);
				mu[j]=triangle(tf,tt[0][x[m][j]][0],tt[0][x[m][j]][1],tt[0][x[m][j]][2]);
				f[j]=t[m][v[j]]+tf;
			}
			else
			{
				tf=myu(tt[x[m][j-1]][x[m][j]][1]-eps,tt[x[m][j-1]][x[m][j]][1]+eps);
				mu[j]=triangle(tf,tt[x[m][j-1]][x[m][j]][0],tt[x[m][j-1]][x[m][j]][1],tt[x[m][j-1]][x[m][j]][2]);
				f[j]=max(f[j-1],tw[x[m][j-1]][0])+S+tf;
			}
		}

		mu[0]=1.;
		miu=1.;
		for(j=1;j<=node;j++)
			miu=min(miu,mu[j]);

		jg=1;
		for(j=1;j<=node;j++)
			if((f[j]<tw[x[m][j]][0])||(f[j]>tw[x[m][j]][1]))
				jg=0;
			else ;
		//judge

			
		if(jg==1)
			mu1=max(mu1,miu);
		else
			mu2=max(mu2,miu);
		

	}
	double cre;


	cre=0.5*(1.+mu1-mu2);
	
	return (cre);
	

}

void GAfordis(double cr0, double pc, double pm)
{
	int r;
	double r1;
	int c=0;
	int i,j,k,N,times;
	int cross[2];
	double ob[popsize],obp[popsize];
	double fit[popsize];
	double sumob;
	int best;
	int bestob;

	best=0;
	
	N=1000;
	
	int xb[node+1];
	int yb[vehicle+1];
	double tb[vehicle+1];  //save the best

	for(i=0;i<=node;i++)
		xb[i]=x[0][i];
	for(i=0;i<=vehicle;i++)
	{
		yb[i]=y[0][i];
		tb[i]=t[0][i];
	}
	bestob=distance(0);

	for(i=0;i<popsize;i++)
		fit[i]=0.;
	for(times=0;times<N;times++)
	{


		if(((times%1500)==0)&&(times>1))
			getchar();
	
		
		//crossover
		for(i=0;i<popsize;i++)
		{
			r=myu(0.,1.);
			if(r<pc)
			{
				cross[c]=i;
				c++;
			}
			if(c==2)
			{
				crossover(cross[0],cross[1],cr0);
	
				c=0;
			}
		}

		//mutation
		for(i=0;i<popsize;i++)
		{
			r=myu(0.,1.);
			
			if(r<pm)
			{
				map(i,i);
				mutation(i,cr0);
				if(cr(i)<cr0)
				{
					bmap(i,i);
				
				}			
			}
		}

		//objective value
		for(i=0;i<popsize;i++)
		{
			ob[i]=double(distance(i));
			obp[i]=100./(ob[i]-220.);
		}

		
				
		sumob=0.;
		for(i=0;i<popsize;i++)
		{
			sumob=sumob+obp[i];
		}

		//fitness
		fit[0]=obp[0]/sumob;
		for(i=1;i<popsize;i++)
		{
			fit[i]=fit[i-1]+(obp[i]/sumob);
		}
		
		//roulette wheel
		for(i=0;i<popsize;i++)
		{
			r1=myu(0., fit[popsize-1]);
			if(r1<=fit[0])
			{
				map(0,i);
			}
			else 
			{
				for(k=0;k<popsize-1;k++)
				{
					if((r1>fit[k])&&(r1<=fit[k+1]))
					{
						map(k+1,i);   //duplicate to temp
					}	
				}
			}
		}
		
		for(i=0;i<popsize;i++)
		{
			bmap(i,i);  //duplicate back
		}
				
		k=0;r=1000;		
		
		for(i=0;i<popsize;i++)
		{
			if(r>distance(i))
			{
				r=distance(i);
				k=i;
			}			
		}

		if(r<bestob)
		{
			best=k;
			for(j=0;j<=node;j++)
				xb[j]=x[k][j];
			for(j=0;j<=vehicle;j++)
			{
				yb[j]=y[k][j];
				tb[j]=t[k][j];
			}
			bestob=r;
			for(j=0;j<=node;j++)
			x[0][j]=xb[j];
			for(j=0;j<=vehicle;j++)
			{
				y[0][j]=yb[j];
				t[0][j]=tb[j];
			}
		}
		else
		{
			for(j=0;j<=node;j++)
				x[0][j]=xb[j];
			for(j=0;j<=vehicle;j++)
				{
					y[0][j]=yb[j];
					t[0][j]=tb[j];
				}
		}
		cout<<"generate: "<<times<<endl;
		cout<<"bestob= "<<bestob<<endl;
		chrom(0);
	

	}

}




void main()
{
	
	double cr0,pc,pm;


	cout<<"enter cr0(0.75) ";
	cin>>cr0;
	cout<<"enter pc ";
	cin>>pc;
	cout<<"enter pm ";
	cin>>pm;


	cout<<"press Enter to start: "<<endl;
	getchar();
	

	init(cr0);
	

	GAfordis(cr0,pc,pm);
	cout<<" GAfordis(cr0,pc,pm) "<<endl;


}