main.cpp

遗传算法是一类借鉴生物界自然选择和自然遗传机制的 随机化搜索算法。 它是模拟达尔文的遗传选择和自然淘汰的生 物进化过程的计算模型。

#include<iostream.h>
#include<fstream.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>

struct city{
	double x;
	double y;
};
double random(double a,double b)
{
	srand((unsigned)time(NULL));
	double k=rand()%1000;
	double r=(b-a)*(double)(k/1000);
	return a+r;

}
void crossover(int*p1,int *p2,int j1,int j2,int count)
{
  int *tu1=new int[count+2];
   int *tu2=new int[count+2];
   for(int i=1;i<=count+1;i++)
   {
	   tu1[i]=p1[i];
	   tu2[i]=p2[i];
   }
   int temp;
   for(i=j1;i<=j2;i++)
   { 
	   temp=tu2[i];
	   for(int j=1;j<=count;j++)
            if(temp==p1[j])
			{
				for(int k=j;k>=2;k--)
					p1[k]=p1[k-1];
			}

   }
   temp=j1;
   for(i=1;i<=j2-j1+1;i++)
   {
	 p1[i]=tu2[temp++];
   }
   p1[count+1]=p1[1];
 
   for(i=j1;i<=j2;i++)
   { 
	   temp=tu1[i];
	   for(int j=1;j<=count;j++)
            if(temp==p2[j])
			{
				for(int k=j;k>=2;k--)
					p2[k]=p2[k-1];
			}

   }
   temp=j1;
   for(i=1;i<=j2-j1+1;i++)
		p2[i]=tu1[temp++];

   p2[count+1]=p2[1];

   
   delete []tu1;
   delete []tu2;
}
sort(double *leng,int *p,int count)
{
	bool *allow=new bool[count];
	for(int i=0;i<count;i++)
		allow[i]=true;
	for(i=0;i<count;i++)
	{
		int k;
		double temp=1000000;
		for(int j=0;j<count;j++)
		{
			if(allow[j])
			{
				if(leng[j]<temp)
				{
					k=j;
					temp=leng[j];
				 
				}
			}
		}
   p[i]=k;
   allow[k]=false;
 
  }
  delete []allow;
}
void swapp(int&a,int&b)
{
	int temp=a;
	a=b;
	b=temp;
}

void main()
{
	int la,lb,n,NC,ncount;//n 坐标个数 NC迭代次数 nant 蚂蚁个数
	double C,Q,P;
	la = 1;
	lb = 1;
	C = 20;//初始信息素
	Q = 100000;
	NC = 2000;//迭代次数
	ncount = 40;//蚂蚁个数
	P = 0.6;//信息素衰减系数
    double lla = 0.1;//变异概率
	double llb = 0.85;//交叉概率

	ifstream in("input.txt",ios::in);
	in>>n;

	city *pNo=new city[n+1];
	for(int i=1;i<=n;i++)
		in>>pNo[i].x>>pNo[i].y;
	in.close();
    
	double **dist,**disad,**dis,**distem,**a;//zeng jia
    a=new double*[n+1];
	dist=new double*[n+1];
	disad=new double*[n+1];
	dis=new double*[n+1];
	distem=new double*[n+1];
	dist[0]=NULL;
	disad[0]=NULL;
	dis[0]=NULL;
	distem[0]=NULL;
	a[0]=NULL;

	clock_t start=clock();

	for(i=1;i<=n;i++)
	{
		a[i]=new double[n+1];
		dist[i]=new double[n+1];
		disad[i]=new double[n+1];
		dis[i]=new double[n+1];
		distem[i]=new double[n+1];
	}

	for(i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dis[i][j]=C;
		

	for(i=1;i<=n;i++)
	{   a[i][i]=0;
		dist[i][i]=0;
		double temp1,mtem;
		for(int j=i+1;j<=n;j++)
		{    
			mtem=1;
		    a[i][j]=sqrt((pNo[i].x-pNo[j].x)*(pNo[i].x-pNo[j].x)+(pNo[i].y-pNo[j].y)*(pNo[i].y-pNo[j].y));
			a[j][i]=a[i][j];
		
			temp1=1/a[i][j];
			for(int k=0;k<lb;k++)
				mtem=mtem*temp1;
			
			dist[i][j]=mtem;
			dist[j][i]=mtem;			
		}
	}

	int **tabu,**allowed,*turn;
	double *Length;
	allowed=new int*[ncount];
	tabu=new int*[ncount];
	turn=new int[ncount];
	Length=new double[ncount];
	for(i=0;i<ncount;i++)
	{
		tabu[i]=new int[n+2];
		allowed[i]=new int[n+1];
	}

    srand(time(0));
	int nc=1;
	double upbest;
    int *bex=new int[n+2];

	float *stop=new float[NC+1];
	for(i=1;i<=NC;i++)
		stop[i]=0;
	int realcount;
	int** sortemp;
	sortemp=new int*[4*ncount];
	for(i=0;i<4*ncount;i++)
		sortemp[i]=new int[n+2];
	double *reLth=new double[4*ncount];
	int *sor=new int[4*ncount];

	while(nc<=NC)
	{   
		for(i=0;i<ncount;i++)
		{
			for(int j=1;j<=n;j++)
			{
				tabu[i][j]=0;
				allowed[i][j]=1;
			}
			 tabu[i][n+1]=0;
		}
		for(i=0;i<ncount;i++)
			Length[i]=0;

		int t=1;
		 
		for(i=0;i<ncount;i++)
		{  
			tabu[i][1]=t;
			tabu[i][n+1]=t;
			allowed[i][t]=0;
			
			turn[i]=t;
		}
	

		for(i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			{    
				double temp1=dis[i][j],mtem;
				mtem=1;
				for(int lk=0;lk<la;lk++)
				mtem*=temp1;
					
				distem[i][j]=mtem;	
			}
		
		int cho,cur;
		double sum;
		for(i=1;i<n;i++)
		{
			double  r;
			double gtem;
			for(int j=0;j<ncount;j++)
			{
				cur=turn[j];
                sum=0;
				for(int lk=1;lk<=n;lk++)
				   if(allowed[j][lk])
						sum+=distem[turn[j]][lk]*dist[turn[j]][lk];
				 
				r=random(0,1);
				 //  cout<<"r="<<r<<endl;
				   gtem=0;
				  
				for(lk=1;lk<=n;lk++)
					if(allowed[j][lk])
					{
						gtem+=(distem[turn[j]][lk]*dist[turn[j]][lk])/sum;
						if(r<=gtem)
							break;
					}
					
				   	cho=lk;
				    allowed[j][cho]=0;
					tabu[j][i+1]=cho;
				
					Length[j]=Length[j]+a[cur][cho];
                  	turn[j]=cho;
			}
		}
	
		for(i=0;i<ncount;i++)
		Length[i]+=a[turn[i]][n+1];
      
		for(i=0;i<ncount;i++)
		{
			for(int j=1;j<=n+1;j++)
				sortemp[i][j]=tabu[i][j];
			reLth[i]=Length[i];
			
		}
	
		realcount=ncount;
		int r;
		for(i=0;i<ncount;i++)
		{
			r=random(0,1);
			if(r<lla)
			{
				for(int j=1;j<=n+1;j++)
				sortemp[realcount][j]=tabu[i][j];
            	realcount++;

			}
		}
	
		if((realcount-ncount)%2==1)
			realcount--;
		//ncount realcount-1 进行交叉
		for(i=ncount;i<realcount;i+=2)
		{
			int j1=rand()%n+1;
			int j2=rand()%n+1;
			if(j1==j2)
				break;
			if(j1>j2)
				swapp(j1,j2);
			crossover(sortemp[i],sortemp[i+1],j1,j2,n);
			

		}
	
		int ck=realcount;
		for(i=0;i<ck;i++)
		{
	     	r=random(0,1);
			if(r<llb)
			{
				for(int j=1;j<=n+1;j++)
			     sortemp[realcount][j]=sortemp[i][j];
				 realcount++;
			}
		}
	
		int j1,j2;
		for(i=ck;i<realcount;i++)
		{   srand(time(0));
			j1=rand()%n+1;
			j2=rand()%n+1;
			if(j1>j2)
				swapp(j1,j2);
			for(int jleft=j1,jright=j2;jleft<jright;jleft++,jright--)
			
			   swapp(sortemp[i][jleft],sortemp[i][jright]);	
               sortemp[i][n+1]=sortemp[i][1];
		}
		
		// 进行变异：变异方法
		for(i=1;i<n;i++)
			for(int j=i;j<=n;j++)
			{
				disad[i][j]=0;
				disad[j][i]=0;
			}
	   for(i=ncount;i<realcount;i++)
	   {
		   reLth[i]=0;
		   for(int j=1;j<n+1;j++)
			   reLth[i]+=a[sortemp[i][j]][sortemp[i][j+1]];
		  
	   }
	   
	   sort(reLth,sor,realcount);
	 
		for(i=0;i<ncount;i++)
		{
		   for(int j=1;j<=n+1;j++)
			   tabu[i][j]=sortemp[sor[i]][j];
		   Length[i]=reLth[sor[i]];  
		}
	
		realcount=0;
		for(i=1;i<=n;i++)
		   for(int j=0;j<ncount;j++)
			disad[tabu[j][i]][tabu[j][i+1]]+=Q/Length[j];

		for(i=1;i<=n;i++)
	      for(int j=1;j<=n;j++)
			  dis[i][j]=P*dis[i][j]+disad[i][j];
		 
		int besin;
		bool update=false;
		 
		if(1==nc)
		{
			upbest=Length[0];
			besin=0;

		}
	
		for(i=0;i<ncount;i++)
		{
			if(Length[i]<upbest)
			{
				besin=i;
				upbest=Length[i];
				update=true;
			}
			
		}
		
		if(update)
			for(i=1;i<=n+1;i++)
				bex[i]=tabu[besin][i];

		stop[nc]=upbest;
		nc++;

	}
	 clock_t end=clock();
	 cout<<"所用时间:"<<(end-start)<<endl;
	 cout<<"最优值："<<upbest<<endl;
	 ofstream out("output.txt",ios::out||ios::app);
	 out<<"所用时间:"<<(end-start)<<'\n';
	 out<<"最优值："<<upbest<<'\n';
 
	 for(i=1;i<nc;i++)
		 out<<i<<' '<<stop[i]<<'\n';
 
	 out.close();
	 delete []sor;
	 delete []reLth;
	 delete []bex;
	 delete []pNo;
	 delete []stop;
	 delete []turn;
	 delete []Length;
	for(i=0;i<ncount;i++)
	{
		delete []tabu[i];
		delete []allowed[i];
	}

	for(i=1;i<=n;i++)
	{
		delete []a[i];
		delete []dist[i];
		delete []disad[i];
		delete []dis[i];
		delete []distem[i];
	}
	for(i=0;i<4*ncount;i++)
	delete []sortemp[i];

}