tspnew.cpp

蚂蚁算法的VC++源程序代码

// TspNew.cpp: implementation of the CTspNew class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "acs.h"
#include "acsDoc.h"
#include "TspNew.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
///////////////////////////////////////////////////
// 构造函数，对城市距离初始化为0，默认蚂蚁数目为10
///////////////////////////////////////////////////
CTspNew::CTspNew()
{
	m_bestTourLength = 0.0;
	m_AntNumber = 10;
	for(int i=0;i<MAX_SIZE;i++)
	{
		for(int j=0;j<MAX_SIZE;j++)
		{
			m_CityDistance[i][j] = 0.0;
		}
	}
}
////////////////////////
//析构函数，不做任何事
////////////////////////
CTspNew::~CTspNew()
{

}

/////////////////////////////////////////////////////////////
//函数GetCityNumber()从输入的数据文件(*.txt)中确定城市的个数，
/////////////////////////////////////////////////////////////
void CTspNew::GetCityNumber()
{
	CFileDialog tspfile(TRUE,_T("*.txt"),NULL,
					   OFN_HIDEREADONLY|OFN_PATHMUSTEXIST,
					   "输入文件(*.txt)|*.txt|AllFile(*.*)|*.*",NULL);	
	CString str,filename;
	CStdioFile file;
	if(tspfile.DoModal() == IDCANCEL)
	{
		//若选择取消按钮，则退出程序
		exit (0);
   	}
	else
	{
		//取得输入文件的完整路径及名称
		filename = tspfile.GetPathName();
		filepath = filename;
	}
	//若打开文件出现错误，则返回错误信息
	if(!file.Open(filename,CFile::modeRead| CFile::typeText ))
	{
		str = "打开输入数据文件"+filename+"失败!";
		AfxMessageBox(str);
		return;
	}
	//读文件数据，每次读一行
	char buf[100];
	file.ReadString(buf, 99 ); 
	//分离每行的元素，确定个数
	int i;
	int count=0;
	char ch;
	char xbuf[100];
	//将xbuf[100]用100个0填充
	memset(xbuf,0,100);
	int j = 0;
	for( i = 0; i<strlen(buf); i ++ ) 
	{
		ch = buf[j++];
		xbuf[i]=ch;
		//若读到一个空格，则说明一个数已经读完，计数器加1
		if( ch == ' ' )
		{
		count++;
		memset(xbuf,0,100);
		j=0;
		}
	}
	//将城市数目赋值给	m_CityNumber
	m_CityNumber = count;
    file.Close(); 
}
/////////////////////////////////////////////////////////////
//*该函数从文件中读取城市间距离值，赋给m_CityDistance[][]数组
/////////////////////////////////////////////////////////////
void CTspNew::GetDataFromFile()
{
 // m_Outputfile为输出文件对象 
 CString str;
 m_Outputfile = fopen("output.txt","w");
 fprintf(m_Outputfile,"------------------------------------------------\n");
 fprintf(m_Outputfile,"***蚂蚁群落系统(Ant Colony System)运行结果如下***：\n");
 fprintf(m_Outputfile,"------------------------------------------------\n");
 FILE *fp;
 //重新打开刚才的输入文件，获取距离信息并捕获异常
 	try
	{
		fp=fopen(filepath,"r");
		if (!fp)
			throw "您要读取的数据文件不存在!";		
	}catch(char *exception)
	{
		AfxMessageBox(exception);
		return ;
	}
	//用循环控制读文件数据，每次读取一行
	for(int loop=0;loop<m_CityNumber;loop++)
	{
		for(int i=0;i<m_CityNumber;i++)
		{
			double tmp=0.0;
			fscanf(fp,"%lf",&tmp);
			m_CityDistance[loop][i] = tmp;
		}
	}
	fclose(fp);
}

/////////////////////////////////////////////////////////////
//蚂蚁按照蚂蚁算法开始寻找最优路径，每只蚂蚁遍历每个城市一次
/////////////////////////////////////////////////////////////
void CTspNew::BeginTour()
{
	//局部变量q用来比较随机数q0决定采用公式(1)或(3)
	double q;
	int firstcity,nextcity,secondcity,bijiaocity;
	//*上面四个变量记录城市序列中城市在数组中的位置
	//*程序最外层循环m_AntNumber次；每只蚂蚁遍历m_CityNumber个
	//*城市结点，并用order[]记录每只蚂蚁走过的路径的顺序
	//每一只蚂蚁开始旅行。
	/*
	void printResultToFile();//输出结果到文件
	void UpdateTourGlobal();//用全局更新规则更新路径
	void GetBestTour();//取得最优路径函数
	void CalculateAveragelength();//计算平均路径
	void CalculateTourLength();//计算每只蚂蚁走过的路径
	void Initialization();//初始化参数序列
	void BeginTour();//开始优化过程
	void GetDataFromFile();//从文件得到城市距离信息
	void GetCityNumber();//从文件得到城市个数

	int m_CityNumber;//城市数目
	int m_AntNumber;//蚂蚁数目
	int loopnumber;//循环变量
	int	bestTourPos;//取得最优路径的蚂蚁
	int index;//产生的随机数
	int rk,rk1,sk;//存放城市结点
	int r,u;//取得城市的位置信息
	double m_BValue;//信息素与距离相对参数β
	double m_T0Value;//初始状态下信息素水平τ0
	double	m_Q0Value;//蚂蚁寻路随机变量q0
	double	m_AValue;//信息素腐化参数α
	double	m_PValue;//局部更新规则的参数ρ
	double exploitation[MAX_SIZE];//用公式(1)时的概率数组
	double exploration[MAX_SIZE];//用公式(3)时的概率数组
	double tourbyant[MAX_SIZE];//ant k visited tour length

	CArray <int,int> city;//城市序列
	CArray <int,int> citySet[MAX_SIZE];//存放未被访问过的城市序列
	CArray <int,int> order[MAX_SIZE];//存放每只蚂蚁走过路径顺序的链表
	CArray <int,int> bestOrder;//存放最优路径顺序的链表
	int freshcity[MAX_SIZE];//城市数组
	double m_bestTourLength;//最优路径长度
	double averagelength;//平均路径长度
	CString filepath;//文件完整路径
    double m_CityDistance[MAX_SIZE][MAX_SIZE];//城市距离信息
	double m_xinxisu[MAX_SIZE][MAX_SIZE];//信息素值
	FILE *m_Outputfile; //输出文件
	CArray <int,int> city;//城市序列
	CArray <int,int> citySet[MAX_SIZE];//存放未被访问过的城市序列
	CArray <int,int> order[MAX_SIZE];//存放每只蚂蚁走过路径顺序的链表
	CArray <int,int> bestOrder;//存放最优路径顺序的链表.*/

	for(loopnumber=0;loopnumber<m_AntNumber;loopnumber++)
	{
		//初始化种子，产生随机数
		srand( (unsigned)time( NULL )*(loopnumber+1) );
		index = rand()%m_CityNumber;//index介于0~m_CityNum-1之间;
		rk1 = city.GetAt(index);//返回给定下标处元素的值。
		int rk2;	
		//citySet[loopnumber].RemoveAt(index);//删除指定下标处元素的值。
		order[loopnumber].Add(rk1);//将一元素添加至数组尾。
		rk = rk1;
		//蚂蚁循环m_CityNumber-1次，遍历城市
		 for(int k=1;k<m_CityNumber;k++)
		 {
		
			if(k<m_CityNumber)
			{
				srand( (unsigned)time( NULL )*m_CityNumber);
				q=(rand()%10)/10.0;	//蚂蚁寻路随机变量。
			    //根据q值选择 Eq(3)或者Eq(1);
				if(q <= m_Q0Value)//use Eq(3)
				{
					for(int m=0;m<citySet[loopnumber].GetSize()
						//获取数组中元素的个数。
						;m++)
					{		
						r=0;
						u=0;
						//确定点在CITY中的位置,以便更新信息素值;
						for(int c=0;c<m_CityNumber;c++)
						{
							if(rk == city.GetAt(c))//返回给定下标处
								//的数组元素。
							{	
								r=c;
								firstcity = c;
								//当前结点在城市中的位置firstcity
							}
							else 
								{
									r=0;
								}
						}
			
				for(int nextdot=0;nextdot<m_CityNumber;nextdot++)
				{
				 if(citySet[loopnumber].GetAt(m) == city.GetAt(nextdot))
					 {
						u = nextdot;
						secondcity = nextdot;
						//下一个结点在城市中的位置secondcity 
					 }
						else
							{
								u=0;
							}
				}
			exploitation[m]=m_xinxisu[firstcity][secondcity]*pow(1/m_CityDistance[firstcity][secondcity],m_BValue);
			}
			//找出数组中最大的，该点即为下一个被访问的结点 nextcity 
			double max = exploitation[0];
			nextcity = 0;
			for(int p=1;p<citySet[loopnumber].GetSize()-1;p++)
			{
			if(max<exploitation[p])
			{
		     max=exploitation[p];
	         nextcity = p;
			}
			else nextcity = 0;
			}
			sk = citySet[loopnumber].GetAt(nextcity);
		  //将刚访问的点从citySet[num]中删除,并作为下一步的初始位置;
		    for(int ab=0;ab<citySet[loopnumber].GetSize();ab++)
			{
			 if(sk == citySet[loopnumber].GetAt(ab))
				citySet[loopnumber].RemoveAt(ab);
			}	
			order[loopnumber].Add(sk);
			}
		else //search sk use Eq(1)
		{
		for(int m=0;m<citySet[loopnumber].GetSize() ;m++)  
		{
		int t=0;
		double totalparam = 0.0;
		//确定点在City中的位置;以便更新信息素值;
		for(int d=0;d<m_CityNumber;d++)
		{
	      if(rk == city.GetAt(d))
			{
			 r=d;
			 firstcity = r;
			}
		  else 
			 r=0;
		}
		//firstcity中记录当前城市在原来城市中的位置
		for(int nextdot=0;nextdot<m_CityNumber;nextdot++)
		{
		 if(citySet[loopnumber].GetAt(m) == city.GetAt(nextdot))
		 {
			 u = nextdot;
			 secondcity = u;
		 }
			 else
			 {
				 u = 0;
			 }
		}
		//secondcity记录下一个城市在原城市中的位置
		for(int i=0;i<citySet[loopnumber].GetSize();i++ )
			{
				for(int l=0;l<m_CityNumber;l++)
				{
					if(citySet[loopnumber].GetAt(i) == city.GetAt(l))
						t = l;
					bijiaocity = t;
				}
			 totalparam +=m_xinxisu[firstcity][bijiaocity]*pow(1/m_CityDistance[firstcity][bijiaocity],m_BValue );
			}
		exploration[m]=m_xinxisu[firstcity][secondcity]*pow(1/m_CityDistance[firstcity][secondcity],m_BValue )/totalparam;
		}
		//找到数组中最大的，该位置即为下一步访问的结点
    	double max = exploration[0];
		for(int n=0;n<citySet[loopnumber].GetSize()-1;n++)
		 {
			
		  if(max<exploration[n])
		   {
		   max=exploration[n];
	       nextcity = n;
			}
			else 
			 {
			  nextcity=0;//用nextcity记录最佳位置;
			 }
		 }
		 sk = citySet[loopnumber].GetAt(nextcity);
	  //在citySet[]中找到当前访问的结点，并删除该点
	  for(int ab=0;ab<citySet[loopnumber].GetSize();ab++)
	   {
	    if(sk == citySet[loopnumber].GetAt(ab))
			citySet[loopnumber].RemoveAt(ab);
	   }	
		  order[loopnumber].Add(sk);
	 	}
	//用局部更新规则更新信息素信息
	m_xinxisu[firstcity][nextcity]=(1-m_PValue)*m_xinxisu[firstcity][nextcity]+m_PValue *m_T0Value;
    m_xinxisu[nextcity][firstcity] = m_xinxisu[firstcity][nextcity];
	rk=sk ;//刚访问过的点作为下一步的初始结点
	}
	else//all ants go back to initial city rk1
	  {
	   sk = rk1;
	   order[loopnumber].RemoveAll();
	   order[loopnumber].Add(sk);
	   rk = sk;
	  }
	 }
	} 
}

/////////////////////////////////////////////////////////
//初始化城市列表city，citySet[num]用于存放未被访问的城市
/////////////////////////////////////////////////////////
void CTspNew::Initialization()
{
	for(int j=0;j<m_CityNumber;j++)
	{
	 city.Add(j);
	}

	for(int num =0;num<m_AntNumber;num++)
	{
		for(int i=0;i<m_CityNumber;i++)
		{
			citySet[num].Add(i);
		}
	}

}
///////////////////////////////////////////////////////////
// 函数CalculateTourLength() 计算每只蚂蚁走过的路径的长度
///////////////////////////////////////////////////////////
void CTspNew::CalculateTourLength()
{
	int qqq;
	for(int number=0;number<m_AntNumber;number++)
	{
		tourbyant[number]=0.0;
		for(int num=0;num<m_CityNumber-1;num++)
		{
			qqq = num+1;
			tourbyant[number]+= m_CityDistance[order[number].GetAt(num)][order[number].GetAt(qqq)];
		}
	}
}

//////////////////////////////////////
// 计算所有蚂蚁走过的路径的平均长度
//////////////////////////////////////
void CTspNew::CalculateAveragelength()
{
	double totallength = 0.0;
	for(int i=0;i<m_AntNumber;i++)
	{
		totallength +=tourbyant[i];
	}
	averagelength = (double)totallength/m_AntNumber;
}

////////////////////////////////////////////////////////////////
//计算最优路径的长度以及该路径的城市序列和取得该路径的蚂蚁
////////////////////////////////////////////////////////////////
void CTspNew::GetBestTour()
{
	double bestTourLength=tourbyant[0];
	bestTourPos = 0; 
	for (int pos=0; pos<m_AntNumber ; pos++)
	 {
		 if(bestTourLength > tourbyant[pos])
		 {
		  bestTourLength = tourbyant[pos];		  
          bestTourPos = pos;
		 }
	 }
	m_bestTourLength = bestTourLength;
}

//////////////////////////////////////
// 用全局更新规则更新信息素信息
//////////////////////////////////////
void CTspNew::UpdateTourGlobal()
{
	int next;
	for(int cou=0;cou<order[bestTourPos].GetSize();cou++)
		{
		freshcity[cou] = order[bestTourPos].GetAt(cou);
		}
	int a = -1;
	int first = 0;
	int second = 0;
	//确定最优路径中各点在原城市序列中的位置;记录于first,second中;
   while (a < city.GetSize()-1)
   {
   	   a++;
	   for(int b=0;b<city.GetSize()-1;b++ )
	   {
	    if (freshcity[a] == city.GetAt(b))
			first = b;
	   }
	   next = a+1;
	   for(int c=0;c<city.GetSize()-1;c++)
	   {
	    if (freshcity[next] == city.GetAt(c))
			second = c;
	   }
	m_xinxisu[first][second]=(1-m_AValue) *m_xinxisu[first][second]+m_AValue*(1/m_bestTourLength);
   	m_xinxisu[second][first] = m_xinxisu[first][second];
	}
}

/////////////////////////////////////////
//将程序的运行结果输出到文件output.txt中
/////////////////////////////////////////
void CTspNew::printResultToFile()
{
	fprintf(m_Outputfile,"TSP问题中城市数目：%5d\n",m_CityNumber);
	fprintf(m_Outputfile,"作为代理的蚂蚁数目：%5d\n\n",m_AntNumber);
	fprintf(m_Outputfile,"* * * * * * * * * * * * * * * * * * * *\n\n");
	fprintf(m_Outputfile,"TSP问题的城市集合如下：\n");
	//输出城市的距离信息m_CityDistance[][]
	for(int i=0;i<m_CityNumber;i++)
	{
	 for(int j=0;j<m_CityNumber;j++)
	 {
		fprintf(m_Outputfile,"%6.1f",m_CityDistance[i][j]);
	 }
	 	fprintf(m_Outputfile,"\n\n");
	}
	fprintf(m_Outputfile,"\n\n");
	//输出各个参数信息
	fprintf(m_Outputfile,"TSP问题的各参数设置如下:\n");
	fprintf(m_Outputfile,"信息素与距离相对参数β:%6.2f\n",m_BValue);
	fprintf(m_Outputfile,"蚂蚁寻路随机变量q0:%6.2f\n",m_Q0Value);
	fprintf(m_Outputfile,"信息素腐化参数α:%6.2f\n",m_AValue);
	fprintf(m_Outputfile,"局部更新规则的参数ρ:%6.2f\n",m_PValue);
	fprintf(m_Outputfile,"初始状态下信息素水平τ0:%6.2f\n\n",m_T0Value);
	//输出最优路径的顺序，平均路径长度和最优路径长度；
	fprintf(m_Outputfile,"下面是优化后的结果\n\n");
	fprintf(m_Outputfile,"最优路径的城市顺序为:\n");
	for(int k=0;k<order[bestTourPos].GetSize();k++)
	{
		if(k== m_CityNumber-1)
		{
		fprintf(m_Outputfile,"%3d",order[bestTourPos].GetAt(k)+1);
		}
		else
		{
	    fprintf(m_Outputfile,"%3d--->",order[bestTourPos].GetAt(k)+1 );
		}
	}
	fprintf(m_Outputfile,"\n\n");
	fprintf(m_Outputfile,"平均路径的长度为: %15.4f\n",averagelength);
	fprintf(m_Outputfile,"最优路径的长度为: %15.4f\n",m_bestTourLength);

}
///////////////////////////////////////////////////////////////////
//the end of the TspView.cpp
///////////////////////////////////////////////////////////////////