vrp遗传算法25个点的3.cpp

该算法经运行

		for(a=0;a<aa;a++)
			sum_r[a]=distance[0][road[i][a][0]]+distance[road[i][a][kt[a]-1]][0];
		for(a=0;a<aa;a++)
			for(j=1;j<kt[a];j++)
				sum_r[a]+=distance[road[i][a][j-1]][road[i][a][j]];
			for(a=0;a<aa;a++)
			    sum_s+=sum_r[a];
			return sum_s;			
}


void objfunc()                   //计算目标函数值     应该OK的
{
	int i,j;	
	for(i=0;i<M;i++)
	{		
		population[i].value=roads(i);
		population[i].fitness=CONST-roads(i);
	}
	for(i=0;i<M;i++)
	{
		sum_f=0.0;sum_f+=population[i].fitness;
	}
	for(i=0;i<M;i++)
	{
		p[i]=population[i].fitness/sum_f;
	}
	for(i=0;i<M;i++)
	{
		q[i]=0.0;
		for(j=0;j<=i;j++)
			q[i]+=p[j];
	}
}

void cross()              //交叉        这下差不多了 
{
	int a,b,t=0,r=0,k=0;
	srand((unsigned)time(NULL));
	do
	{
		m=rand()%M;
		n=rand()%M;
	}while(m==n);
	do
	{
		a=rand()%(car_client_num-1)+1;
	    b=rand()%(car_client_num-1);
	}while(a>=b);
	double p1=rand()%1000/1000.0;
//	e=b;
	if(p1<pc)
	{
		for(i=0;i<car_client_num;i++)
		{
			k=0;
			for(j=a;j<=b;j++)
			    temp[j]=popinitialize[m][j];
		    for(j=0;j<b-a+1;j++)
			    if(temp[j]!=popinitialize[n][i])
				    k++;
			    if(k==b-a+1)
				{
					if(t<a)
					{
						temp[t]=popinitialize[n][i];
			            t++;
					}
					else 
					{
						temp[t+b-a+1]=popinitialize[n][i];
						t++;
					}
				}
		}
	    for(i=0;i<car_client_num;i++)
		    popinitialize[m][i]=temp[i];
	}
}
int ak,am,an;
void mutation()             //变异  这下也差不多了
{
	int ak,am,an;
	srand((unsigned)time(NULL)); 
	for(i=0;i<M;i++)
	{
		double p=rand()%1000/1000.0;
		if(p<pm)
		{
			do
			{
				am=rand()%car_client_num;
			    an=rand()%car_client_num;
			}while(am==an);
			ak=popinitialize[i][am];
			popinitialize[i][am]=popinitialize[i][an];
			popinitialize[i][an]=ak;
		}
	}
}

void selects() //轮盘赌选择算法
{
	int m,n;double N;
//	initialize();
//	objfunc();
	srand((unsigned)time(NULL));
	for(i=0;i<M;i++)
	{
		double r=rand()%1000/1000.0;
		for(int k=0;k<M;k++)
		{
			if(k==0)
			{
			    if(r<=q[k])
				    for(j=0;j<car_client_num;j++)
					    popnew[i][j]=popinitialize[k][j];
					break;
			}
		    else if(q[k-1]<r&&r<q[k])
			{
			    for(j=0;j<car_client_num;j++)
					popnew[i][j]=popinitialize[k][j];
				break;
			}
		}
	}
	for(i=0;i<M;i++)
		for(j=0;j<car_client_num;j++)
		popinitialize[i][j]=popnew[i][j];
		for(i=0;i<M;i++)
		for(j=0;j<car_client_num;j++)
		popinitialize[i][j]=popnew[i][j];
			for(i=1;i<M;i++)
	{
		N=max(population[i-1].fitness,population[i].fitness); 
		population[i].fitness=N;
	}
    for(i=0;i<M;i++)
		if(population[i].fitness==N)
		{
			m=i;
			break;
		}
	for(i=1;i<M;i++)
	{
		N=min(population[i-1].fitness,population[i].fitness); 
		population[i].fitness=N;
	}
    for(i=0;i<M;i++)
		if(population[i].fitness==N)
		{
			n=i;
			break;
		}
		for(j=0;j<car_client_num;j++)
		{
			popinitialize[n][j]=popinitialize[m][j];
			best[y][j]=popinitialize[m][j];
		}
		best_f[y]=population[m].value;
	    y++;
	
}

void main()
{
	int i,j,m;
	double N;
//	cout<<" 显示窗口 "<<endl;
    initialize();
	//for(i=0;i<M;i++)
//	{for(j=0;j<car_client_num;j++)
//	cout<<popinitialize[i][j]<<"  ";cout<<endl;}
//    cout<<" 显示窗口1 "<<endl;
    int K=0;
    while(K<GEN)
    {
		for(i=0;i<M;i++)       //cout<<roads(i)<<endl;//此处不运行了,why????若不要此句后边均可运行
		roads(i);		
		objfunc();
		selects();		  
		cross();	
		mutation();
		K++;
	}
    for(i=1;i<GEN;i++)
	{
		N=min(best_f[i-1],best_f[i]);
		best_f[i]=N;
	}//cout<<N<<endl;
    for(i=0;i<M;i++)
		if(best_f[i]==N)
		{
			m=i;
			break;
		}
		for(j=0;j<car_client_num;j++)
			popinitialize[m][j]=best[m][j];
    roads(m);
	//objfunc();
	for(i=0;i<aa;i++)
	{
    cout<<"第"<<car[i]<<"辆车的路线为："<<endl;
    for(j=0;j<kt[i];j++)
		cout<<road[m][car[i]-1][j]<<"  ";
	cout<<endl;
	}
    cout<<"优化后的距离为："<<roads(m)<<endl;          	
}