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

#define popsize 40
#define node 8
#define vehicle 3
#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, 15, 21, 18, 14,
  18, 0, 20, 34, 55, 49, 57, 49, 22,
  14, 20, 0, 15, 41, 43, 55, 52, 35,
  14, 34, 15, 0, 28, 36, 51, 51, 44,
  21, 55, 41, 28, 0, 21, 36, 43, 55,
  17, 49, 43, 36, 21, 0, 16, 22, 41,
  21, 57, 55, 51, 36, 16, 0, 13, 43,
  18, 49, 52, 51, 43, 22, 13, 0, 32,  
  14, 22, 35, 44, 55, 41, 43, 32, 0,
};

int tw[node+1][2]=
{0,  0,
 90, 380,
 80, 190,
 100, 200,
 80, 310,
 70, 450,
 20, 130,
 100, 260,
 80, 130,
};

int tt[node+1][node+1][2]=
{
	0,0,  50,25,  10,5,  50,25,    50,25,  50,25,    15,7,  50,25,   50,25,  
	50,25,  0,0,  40,20,  10,5,    35,17,  15,7,    40,20, 15,7,    10,5,
	10,5,  40,20,  0,0,   40,20,    35,17,  40,20,   10,5,  45,22,   35,17,
	50,25,  10,5,  40,20, 0,0,     30,15,  5,2,     45,22,  10,5,    30,15,
	50,25,  35,17, 35,17, 30,15,   0,0,    30,15,   35,17,  30,15,    10,5,
	50,25,  15,7,  40,20,  5,2,    30,15,  0,0,    40,20,  10,5,    30,15,
	15,7,  40,20,  10,5,  45,22,    35,17,  40,20,   0,0,  40,20,   35,17,
	50,25,  15,7,  45,22,  10,5,   30,15,  10,5,    40,20,  0,0,   35,17,
	50,25,  10,5,  35,17,  30,15,   10,5,  30,15,  35,17,  35,17,   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(int dis0)//初始化数据
{
	int i,j,k,w,nm;
	double counter=0.;
	double pr_tmp;
	int ct;
	
	double pr(int m);
	int distance(int m);

	double dist;
//	cout<<"A="<<endl;
//	for(i=0;i<10;i++)
//	{	for(j=0;j<10;j++)			cout<<a[i][j]<<"  ";		cout<<endl; 	}


	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;
		dist=1000.;
		pr_tmp=0.;
		while((dist>dis0))//||(pr_tmp<0.05))//(nm<500)&&
		{
		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
		dist=distance(i);
	//	pr_tmp=pr(i);
		nm++;
		}
		system("cls");
		counter=double(i)/popsize*100;
		ct=floor(counter);
		cout<<"Initializing..."<<ct<<"%"<<endl;


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

}





void chrom(int a)
{
	int distance(int a);
	double pr(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<<"  pr  "<<pr(a)<<"  dist  "<<distance(a)<<endl;
}


void crossover(int a, int b)
{
	int i;
	double c;
	c=myu(0,1);
	double tp;
	int yp;
	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.

}//crossover tested.

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;
}


/*
void mutation(int a, int dis0)
{
	int i,j,k, n1, n2, nn, xx, w;
	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

	double dt[vehicle+1];
	for(i=1;i<=vehicle;i++)
	{
		dt[i]=double(floor(myu(-30.,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]);
	}
	//mutate t;

}//mutation tested.
*/

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

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

	int distance(int);
	double pr(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(distance(a)<=dis0)
		;
	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][node]][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;
	
}//distance tested.

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 pr(int m)//Pr{ai<fi<bi, i=1,2,...,n} for the m-th chrom.
{
	int N=3000;
	int i,j,k,l;
	int jg=1;
		
	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;
//	for(i=1;i<=node;i++)
//		cout<<"  "<<v[i];
	

	x[m][0]=0;

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

		//for(k=1;k<=node;k++)
		//cout<<"k="<<k<<" fk="<<f[k]<<endl;

		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
		
		counter=counter+jg;	
		//	cout<<"ct="<<counter<<endl;
		//getchar();

	}
	double pro;
	//cout<<"ct="<<counter<<endl;
	pro=double(counter)/N;
	
	return (pro);
	

}

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

	best=0;
	bestob=0.;
	N=700;
	
	for(i=0;i<popsize;i++)
		fit[i]=0.;
	for(times=0;times<N;times++)
	{
		//crossover
		for(i=0;i<popsize;i++)
		{
			r=myu(0.,1.);
			//pk=1;
			if(r<pc)
			{
				cross[c]=i;
				c++;
			}
			if(c==2)
			{
				map(cross[0],cross[0]);
				map(cross[1],cross[1]);
				crossover(cross[0],cross[1]);
				
				if(distance(cross[0])>dis0)
				{
					bmap(cross[0],cross[0]);
				//	pk=0;
				}
				if(distance(cross[1])>dis0)
				{
					bmap(cross[1],cross[1]);
					//pk=0;
				}
				//if(pk==1)
				//	cout<<"crossed"<<endl;
				c=0;
			}
		}
		//mutation
		for(i=0;i<popsize;i++)
		{
			r=myu(0.,1.);
			//pk=1;
			if(r<pm)
			{
				map(i,i);
				mutation(i,dis0);
			}
		}

		//objective value
		for(i=0;i<popsize;i++)
		{
			ob[i]=pr(i);			
		}
	
				
		sumob=0.;
		for(i=0;i<popsize;i++)
		{
			sumob=sumob+ob[i];
		}

		//fitness
		fit[0]=ob[0]/sumob;
		for(i=1;i<popsize;i++)
		{
			fit[i]=fit[i-1]+(ob[i]/sumob);
		}

		
		//roulette wheel
		for(i=0;i<popsize;i++)
		{
			r=myu(0., fit[popsize-1]);
			for(k=0;k<popsize-1;k++)
			{
				if(r<=fit[0])
				{
					map(0,i);
				}
				else if((r>fit[k])&&(r<=fit[k+1]))
				{
					map(k+1,i);   //duplicate to temp
				}
				else 
					;								
			}
			//getchar();

		}
		
		for(i=0;i<popsize;i++)
		{
			bmap(i,i);  //duplicate back
		}
		


		k=0;r=0.;		
		
		for(i=0;i<popsize;i++)
		{
			if(r<pr(i))
			{
				r=pr(i);
				k=i;
			}			
		}
/*		if(r>bestob)
			cout<<"evaluated!"<<endl;
		else cout<<"not evaluated"<<endl;
*/		

		if(r>bestob)
		{
			best=k;
			bestob=r;
		}
			cout<<"generate: "<<times<<endl;
			cout<<"maxob= "<<bestob<<endl;
			chrom(best);
			//cout<<best<<"  "<<pr(best)<<endl;
				
		//getchar();

	}
/*	cout<<"generate: "<<times<<endl;
	cout<<"maxob= "<<bestob<<endl;
	chrom(best);
	cout<<best<<"  "<<pr(best)<<endl;
*/
}


/*
void test()
{
    chrom(3);
	chrom(5);
	cout<<"crossover"<<endl;
	getchar();
	crossover(3,5);

	chrom(3);
	chrom(4);
	chrom(5);
	
	cout<<"mutation"<<endl;
	getchar();
	mutation(3);
	mutation(4);
	mutation(5);
    chrom(3);
	chrom(4);
	chrom(5);
}
*/


void main()
{
	double pc,pm;
	int dis0=240;
	
	cout<<"enter pc ";
	cin>>pc;
	cout<<"enter pm ";
	cin>>pm;
	cout<<"enter dis0 ";
	cin>>dis0;

	int i;
	
	cout<<"press Enter to start: "<<endl;
	getchar();
	
	init(dis0);
	
	GAforpr(dis0,pc,pm);
	cout<<" GAforpr(dis0,pc,pm) "<<endl;

	
	getchar();
	init(dis0);
	GAforpr(dis0,0.3,0.1);
	cout<<" GAforpr(dis0,0.3,0.1) "<<endl;


}