ant.cpp

c语言编写的蚁群算法源程序

/*
说明：对于论文中给出的算法 存在这样一个问题：如果c和a只有一条路径，而ab之间没有路径，
      那么当蚂蚁从从c到a后该如何处理呢，因为蚂蚁不能重复原路（文中假设），估计要出问题了，
	  不妨我们假设无路径时 路径为一个很大的值，但多大是一个合适的值呢，又不好确定。
	  此处取自身到自身为-1，无路径为某个很大的值32767，要求对输入的个路径进行合理缩放
缺陷：1.当无法求解时会求得一个很大的值。2.在这里城市数量要在程序里修改，但这点不影响体现算法的的实质。
*/
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>

#define Infinite 32767//路经无穷大

const int m=1000;//count of ant
const int n=6;//城市数
const double To=0.2;//初始信息素

const double alfa=0.8;//参数
const double beta=1;//参数
const double row=0.2;//信息遗失参数

double edge[n][n];//初始时各城市之间的距离
double ph[n][n];//各边的信息素值
int Just[m][n];//蚂蚁未访问的城市，此处我们这样处理 当可访问第i个城市时我们计Just[m][i]=1
                   //否则即为0
int start[m];//蚂蚁的初始位置
int Locate[m];//记录蚂蚁的当前位置

int Tour[m][n];//蚂蚁的路径
double g[n][n];//启发函数此处在初始时设为1/distict
double Len[m];//蚂蚁的路径长度

double q;//公式3中的参数
double q0=0.8;
int sk[m];//下一个待选择的城市

/*初始化城市和路经以及各个蚂蚁的初始位置 */
void IntiNode()
{
	//输入各城市之间的路径
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			edge[i][j]=Infinite;
	printf("共%d城市请输入各城市之间的距离\n",n);
	for(i=0;i<n-1;i++)
		for(int j=i+1;j<n;j++)
		{
			printf("%d-->%d:",i,j);
			scanf("%lf",&edge[i][j]);
			printf("\n");
		}
   
	for(i=0;i<n;i++)
		for(int j=0;j<n;j++)
			if(i>j)
				edge[i][j]=edge[j][i];	
  
	//输入蚂蚁的初始位置
    for(i=0;i<m;i++)
		start[i]=i%n;
	
	//设置启发函数g	
	for(i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			if(i!=j)
			{
				g[i][j]=(double)1/edge[i][j];				
			}
		}	
}
/*初始化信息素*/
void IntiPh()
{
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			if(i!=j)
			{
				ph[i][j]=To;
			}
		}
}
/*初始化蚂蚁*/
void IntiAnt()
{
	//设置Just
	for(int i=0;i<m;i++)
		for(int j=0;j<n;j++)
			Just[i][j]=1;

   for(i=0;i<m;i++)
	   Len[i]=0;

	for(int k=0;k<m;k++)
	{		
		Just[k][start[k]]=0;//开始位置设置为不可访问
		Locate[k]=start[k];
	}
}
/*根据T获得sk*/
int getsk(int k)//k已在数组范围内
{
	double temp=0.0;
	int sk=0;
	int lk=Locate[k];//当前位置
	for(int i=0;i<n;i++)
	{
		//if(Just[k][i]==1 && lk!=i && edge[lk][i]!=Infinite && temp < pow(ph[lk][i],alfa)*pow(g[lk][i],beta))
		if(Just[k][i]==1 && lk!=i && temp < pow(ph[lk][i],alfa)*pow(g[lk][i],beta))
		{
			temp=pow(ph[lk][i],alfa)*pow(g[lk][i],beta);
			sk=i;
		}
	}
	return sk;
}
/*产生0-1之间的一个随机数*/
double drand()
{	
	return ((double)rand())/(double)Infinite;
}
/*根据p获得sk 可以这样来实现根据概率确定sk 对0-1按概率进行划分成若干段，
 产生一个0-1之间的随机数，根据该数值所在的范围来确定sk 这样既体现了概率又唯一确定一个值 */
int getSK(int k)
{
	double sum=0;
	int lk=Locate[k];	
	int count=0;
	double r=drand();
	
	for(int i=0;i<n;i++)//计算总量
	{
		//if(Just[k][i]==1&&edge[lk][i]!=Infinite)
		if(Just[k][i]==1&&lk!=i)//未访问且有路径
		{
			sum=sum+pow(ph[lk][i],alfa)*pow(g[lk][i],beta);
			count++;
		}
	}	
	double x=0;
	double y=0;
	for(i=0;i<n;i++)
	{
		//if(Just[k][i]==1&&edge[lk][i]!=Infinite)
		if(Just[k][i]==1&&lk!=i)//判断随机时的路径
		{		
			y=y+pow(ph[lk][i],alfa)*pow(g[lk][i],beta);		
			if(r>=x/sum &&r<y/sum)
				break;
			else
				x=y;
		}
	}
	return i;
}
void main()
{	
	int b=0;//记录最佳蚂蚁
	srand((unsigned)time(NULL));//设置随机数种子
	double Lbest=100000000;
	double Lbest0=100000000;//此处只是一个无穷大的值
	/*初始化城市和路经*/
	IntiNode();
    IntiPh();
label:
	/*建立每只蚂蚁的路径存入tourk*/
	IntiAnt();
	for(int i=0;i<n;i++)
	{
		if(i<n-1)
		{
			for(int k=0;k<m;k++)
			{
				q=drand();
				//确定下一个城市sk			
				if(q<=q0)
				{			
					sk[k]=getsk(k);
				}
				else
				{			
					sk[k]=getSK(k);
				}
				Just[k][sk[k]]=0;
				Tour[k][i]=sk[k];			
				Len[k]=Len[k]+edge[Locate[k]][sk[k]];			
			}
		}
		else
		{
			for(int k=0;k<m;k++)
			{
				sk[k]=start[k];				
				Tour[k][i]=sk[k];
				Len[k]=Len[k]+edge[Locate[k]][sk[k]];			
			}
		}
		//利用公式5更新局部信息素
		for(int k=0;k<m;k++)
		{
			int x,y;
			x=Locate[k];
			y=sk[k];
			ph[x][y]=(1-row)*ph[x][y]+row*To;
			Locate[k]=sk[k];			
		}
	}
	//更新全局信息素
	for(int k=0;k<m;k++)
	{
		if(Lbest>=Len[k])
		{
			Lbest=Len[k];
			b=k;
		}
	}
	for(i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			if(edge[i][j]!=Infinite)
			{
				ph[i][j]=(1-row)*ph[i][j]+row/(double)Lbest;			
			}
		}
	
	if(Lbest0>Lbest)//判断是否还可优化,  此处这样处理如果下一次的比上一次的小则认为还可优化
	{
		Lbest0=Lbest;
		goto label;
	}
	if(Lbest<Infinite)
	{
		for(i=0;i<n;i++)
			printf("%d->",Tour[b][i]);
		printf("\n%f\n",Lbest);
	}
	else
	{
		printf("no solution\n");
	}
	
}