{
Move();
}
//完成搜索后计算走过的路径长度
CalPathLength();
}
//计算蚂蚁走过的路径长度
void CAnt::CalPathLength()
{
m_dbPathLength=0.0; //先把路径长度置0
int m=0;
int n=0;
for (int i=1;i<N_CITY_COUNT;i++)
//这里设置成1.0，设置成多少对结果影响不是太大，对算法收敛速度有些影响
for (int i=0;i<N_CITY_COUNT;i++)
{
for (int j=0;j<N_CITY_COUNT;j++)
{
g_Trial[i][j]=1.0;
}
}
}
//更新环境信息素
void CTsp::UpdateTrial()
public:
//初始化数据
void InitData();
//开始搜索
void Search();
//更新环境信息素
void UpdateTrial();
};
//构造函数
CTsp::CTsp(void)
{
}
CTsp::~CTsp(void)
{
}
//初始化数据
void CTsp::InitData()
10,21,5,30,39,32,25,25,48,56,
30
};
double y_Ary[N_CITY_COUNT]=
{
52,49,64,26,30,47,63,62,33,21,
41,32,25,42,16,41,23,33,13,58,
42,57,57,52,38,68,48,67,48,27,
const double DB_MAX=10e9; //一个标志数，10的9次方
double g_Trial[N_CITY_COUNT][N_CITY_COUNT]; //两两城市间信息素，就是环境信息素
double g_Distance[N_CITY_COUNT][N_CITY_COUNT]; //两两城市间距离
if (nSelectedCity == -1)
{
for (int i=0;i<N_CITY_COUNT;i++)
{
if (m_nAllowedCity[i] == 1) //城市没去过
{
nSelectedCity=i;
break;
}
}
}
//==============================================================================
// AO.cpp :定义控制台应用程序的入口点。
#pragma once
#include <iostream>
#include <math.h>
#include <time.h>
const double ALPHA=1.0; //启发因子，信息素的重要程度
const double BETA=2.0; //期望因子，城市间距离的重要程度
void Move(); //蚂蚁在城市间移动
void Search(); //搜索路径
void CalPathLength(); //计算蚂蚁走过的路径长度
};
//构造函数
CAnt::CAnt(void)
{
}
//析构函数
CAnt::~CAnt(void)
{
}
//初始化函数，蚂蚁搜索前调用
void CAnt::nit()
//把出发城市保存入路径数组中
m_nPath[0]=m_nCurCityNo;
//标识出发城市为已经去过了
m_nAllowedCity[m_nCurCityNo]=0;
//已经去过的城市数量设置为1
m_nMovedCityCount=1;
}
//选择下一个城市
//返回值为城市编号
int CAnt::ChooseNextCity()
}
//返回指定范围内的随机浮点数
double rnd(double dbLow,double dbUpper)
{
double dbTemp=rand()/((double)RAND_MAX+1.0);
return dbLow+dbTemp*(dbUpper-dbLow);
}
//返回浮点数四舍五入取整后的浮点数
for (int i=0;i<N_ANT_COUNT;i++) //计算每只蚂蚁留下的信息素
{
for (int j=1;j<N_CITY_COUNT;j++)
{
m=m_cAntAry[i].m_nPath[j];
n=m_cAntAry[i].m_nPath[j-1];
dbTempAry[n][m]=dbTempAry[n][m]+DBQ/m_cAntAry[i].m_dbPathLength;
{
int nSelectedCity=-1; //返回结果，先暂时把其设置为-1
//==============================================================================
//计算当前城市和没去过的城市之间的信息素总和
double dbTotal=0.0;
69,46,10,33,63,69,22,35,15,6,
17,10,64,15,10,39,32,55,28,37,
40
};
//返回指定范围内的随机整数
int rnd(int nLow,int nUpper)
{
return nLow+(nUpper-nLow)*rand()/(RAND_MAX+1);
{
m=m_nPath[i];
n=m_nPath[i-1];
m_dbPathLength=m_dbPathLength+g_Distance[m][n];
}
//加上从最后城市返回出发城市的距离
n=m_nPath[0];
m_dbPathLength=m_dbPathLength+g_Distance[m][n];
//如果城市间的信息素非常小(小到比double能够表示的最小的数字还要小)
//那么由于浮点运算的误差原因，上面计算的概率总和可能为0
//会出现经过上述操作，没有城市被选择出来
//出现这种情况，就把第一个没去过的城市作为返回结果
//题外话：刚开始看的时候，下面这段代码困惑了我很长时间，想不通为何要有这段代码，后来才搞清楚。
{
//临时数组，保存各只蚂蚁在两两城市间新留下的信息素
double dbTempAry[N_CITY_COUNT][N_CITY_COUNT];
memset(dbTempAry,0,sizeof(dbTempAry)); //先全部设置为0
//计算新增加的信息素,保存到临时数组里
int m=0;
int n=0;
//eil51.tsp城市坐标数据
double x_Ary[N_CITY_COUNT]=
{
37,49,52,20,40,21,17,31,52,51,
42,31,5,12,36,52,27,17,13,57,
62,42,16,8,7,27,30,43,58,58,
37,38,46,61,62,63,32,45,59,5,
double ROUND(double dbA)
{
return (double)((int)(dbA+0.5));
}
//定义蚂蚁类
class CAnt
{
public:
CAnt(void);
~CAnt(void);
public:
int m_nPath[N_CITY_COUNT]; //蚂蚁走的路径
double m_dbPathLength; //蚂蚁走过的路径长度
{
dbTemp=dbTemp-prob[i]; //这个操作相当于转动轮盘，如果对轮盘选择不熟悉，仔细考虑一下
if (dbTemp < 0.0) //轮盘停止转动，记下城市编号，直接跳出循环
{
nSelectedCity=i;
break;
}
}
}
}
//==============================================================================
{
dbTemp=(x_Ary[i]-x_Ary[j])*(x_Ary[i]-x_Ary[j])+(y_Ary[i]-y_Ary[j])*(y_Ary[i]-y_Ary[j]);
dbTemp=pow(dbTemp,0.5);
g_Distance[i][j]=ROUND(dbTemp);
}
}
//初始化环境信息素，先把城市间的信息素设置成一样
double prob[N_CITY_COUNT]; //保存各个城市被选中的概率
for (int i=0;i<N_CITY_COUNT;i++)
{
if (m_nAllowedCity[i] == 1) //城市没去过
{
prob[i]=pow(g_Trial[m_nCurCityNo][i],ALPHA)*pow(1.0/g_Distance[m_nCurCityNo][i],BETA); //该城市和当前城市间的信息素