📄 tspnew.cpp
字号:
// 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 );
//分离每行的元素，确定个数
unsigned 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[]记录每只蚂蚁走过的路径的顺序
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);
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
///////////////////////////////////////////////////////////////////⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -