蚁群算法浅析
摘要：介绍了什么是蚁群算法，蚁群算法的种类，对四种不同的蚁群算法进行了分析对比。详细阐述了蚁群算法的基本原理，将其应用于旅行商问题，有效地解决了问题。通过对旅行商问题C++模拟仿真程序的详细分析，更加深刻地理解与掌握了蚁群算法。 关键词：蚁群算法；旅行商问题；信息素；轮盘选择
一、引言
蚁群算法（Ant Colony Optimization, ACO），是一种用来在图中寻找优化路径的算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。 蚁群算法成功解决了旅行商问题（Traveling Salesman Problem, TSP）：一个商人要到若干城市推销物品，从一个城市出发要到达其他各城市一次而且最多一次最后又回到第一个城市。寻找一条最短路径，使他从起点的城市到达所有城市一遍，最后回到起点的总路程最短。若把每个城市看成是图上的节点，那么旅行商问题就是在N个节点的完全图上寻找一条花费最少的回路。
最基本的蚁群算法见第二节。目前典型的蚁群算法有随机蚁群算法、排序蚁群算法和最大最小蚁群算法，其中后两种蚁群算法是对前一种的优化。本文将终点介绍随机蚁群算法。
二、基本蚁群算法
（一）算法思想
各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种信息素，信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多（或者较长的路上蚂蚁多，这也无关紧要）。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素。因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就找到了。 蚁群算法的基本思想如下图表示：
图1 等概率选择 图2 最优路径 图3 最优比重
（二）算法描述
基本蚁群算法的算法简单描述如下：
1．所有蚂蚁遇到障碍物时按照等概率选择路径，并留下信息素；
2．随着时间的推移，较短路径的信息素浓度升高；
3．蚂蚁再次遇到障碍物时，会选择信息素浓度高的路径；
4．较短路径的信息素浓度继续升高，最终最优路径被选择出来。
三、随机蚁群算法
（一）算法思想
在基本蚁群算法中，蚂蚁会在多条可选择的路径中，自动选择出最短的一条路径。但是，一旦蚁群选择了一条比之前短的路径，就会认为这条路径是最好的，在这条路径上一直走下去。这样的算法存在问题：蚂蚁可能只是找到了局部的最短路径，而忽略了全局最优解。
因此，在基本蚁群算法的基础上，需要对蚂蚁选路的方案加以改善：有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另辟蹊径，也就是它会按照一定的概率不往信息素高的地方。如果令开辟的道路比原来的其他道路更短，那么，渐渐地，更多的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复
为了实现蚂蚁的“随机”选路，我们需要做以下假设：
1．范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径，如果半径等于2，那么它能观察到的范围就是2*2个方格世界，并且能移动的距离也在这个范围之内。
2．环境：环境以一定的速率让信息素消失。
3．觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，那么它朝哪个方向走的概率就大。这就意味着每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。
4．避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。
5．播撒信息素规则：每只蚂蚁在找到食物后撒发的信息素。
自然想到一个问题：开始时环境没有信息素，蚂蚁为什么会相对有效的找到食物呢？ 这个问题用蚂蚁的移动规则同样可以解释。首先，它要能尽量保持某种惯性，这样使得蚂蚁尽量向前方移动（开始，这个前方是随机固定的一个方向），而不是原地无谓的打转或者震动；其次，蚂蚁要有一定的随机性，虽然有了固定的方向，但它也不能像粒子一样直线运动下去，而是有一个随机的干扰。这样就使得蚂蚁运动起来具有了一定的目的性，尽量保持原来的方向，但又有新的试探，这就解释了为什么单个蚂蚁在复杂的诸如迷宫的地图中仍然能找到隐蔽得很好的食物。
（二）算法描述
随机蚁群算法的算法描述如下：
算法输入：城市数量N，两两城市间的距离，所有路径的信息素浓度
算法输出：蚂蚁走过的路径长度 1．设置全部城市都没有去过，走过的路径长度为0； 2．随机选择一个出发的城市； 3．i = 1 4．while(i
用随机蚁群算法解决旅行商问题，实际上是多次使用蚁群算法，不断更新最短路径的过
程。由此，我们容易得到旅行商问题的算法描述：
四、改进的随机蚁群算法
（一）排序蚁群算法
与随机蚁群算法不同的是，当蚂蚁遇到障碍物选择路径时，根据不同路径上信息素的浓度，通过计算可能达到最优解的概率算法，将路径进行排序，选择最好的路径作为下一个通往的城市。
（二）最大最小蚁群算法
与随机蚁群算法和排序蚁群算法都不同的是，当蚂蚁遇到障碍物选择路径时，使用贪心算法输入：所有城市的X、Y坐标，蚂蚁数量n，迭代次数K 算法输出：旅行商的最短路径 1．计算两两城市间的距离，初始化所有路径信息素为0； 2．for i = 1 : K 3． for j = 1 : n 4． 第j只蚂蚁搜索一遍； 5． if 走过的路径小于最短路径 6． 更新最短路径； 7． 更新走过路径的信息素； 8． end 9．end 策略，优先选择达到下一个城市最短的城市，即得到局部最优解。这样以来，更多的信息素将在较短的路径聚集，使算法更快地得到全局最短路径。
五、算法比较
本文介绍了四种蚁群算法，其中第一种比较简单，描述了最基本的蚁群算法思想。但是，它忽略了更优路径存在的可能性，没有考虑到更普遍的情况。因此，该算法只适用于小规模，无特殊情况的问题。
后三种蚁群算法属于实际中典型的蚁群算法，对不同情况的考虑比较全面，因此应用比较广泛。三者的差别主要在于蚂蚁对不同路径的选择上，其中，随机蚁群算法首先根据不同路径上信息素的浓度，计算出选择各条路径的概率，而后使用轮盘算法选择一条路径，适用
择最好的路径作为下一个通往的城市，这样做增加了空间复杂度，有效改善了时间复杂度，适用于规模较大的场合；最大最小蚁群算法则是采用贪心策略，优先选择达到下一个城市最短的城市，先得到局部最优解，再通过聚类效应得到全局最短路径，适合对时间和空间要求都较高的场合。
参考文献：
1. 丁洋. 蚁群优化算法分析. 论文期刊. 2012.5.
2. 蚁群优化算法. http://www.pudn.com/.
附录：
1．预编译所需头文件 Stdafx.h
#pragma once
// Stdafx.h : 标准系统包含文件的包含文件，
// 或是常用但不常更改的项目特定的包含文件
#include
#include
#include
#include
2．算法参数头文件 Common.h
#pragma once
const int N_CITY_COUNT=51; //城市数量
const int N_ANT_COUNT=34; //蚂蚁数量
const int N_IT_COUNT=50; //迭代次数
//蚁群算法参数
const double ALPHA=1.0;
const double BETA=2.0;
const double ROU=0.5; //信息素传递参数
const double DBQ=100.0; //总的信息素
const double DB_MAX=10e9; //最大标志数
extern double g_Trial[N_CITY_COUNT][N_CITY_COUNT]; //两两城市间信息素
extern double g_Distance[N_CITY_COUNT][N_CITY_COUNT]; //两两城市间距离
extern int rnd(int nLow,int nUpper); //返回随机整数
extern double rnd(double dbLow,double dbUpper);//返回随机浮点数
extern double ROUND(double dbA);//浮点数四舍五入
extern double x_Ary[N_CITY_COUNT];
extern double y_Ary[N_CITY_COUNT];
3．蚂蚁类头文件 Ant.h
#pragma once
#include
//蚂蚁类
class CAnt
public:
CAnt();
~CAnt();
int m_nPath[N_CITY_COUNT]; //蚂蚁走的路径
double m_dbPathLength; //蚂蚁走过的路径长度
int m_nAllowedCity[N_CITY_COUNT]; //没去过的城市
int m_nCurCityNo; //当前所在城市编号
int m_nMovedCityCount; //已经去过的城市数量
int ChooseNextCity(); //选择下一个城市
void Init(); //初始化
void Move(); //蚂蚁在城市间移动
void Search(); //搜索路径
void CalPathLength(); //计算蚂蚁走过的路径长度
};
4．旅行商类头文件 Stdafx.h
#pragma once
#include
#include
//旅行商类
class CTsp
{
public:
CTsp();
~CTsp();
CAnt m_cAntAry[N_ANT_COUNT];
CAnt m_cBestAnt; //保存结果
void InitData(); //初始化数据
void Search(); //开始搜索
void UpdateTrial();//更新环境信息素
};
5．预编译所需文件 Stdafx.cpp
// stdafx.cpp : 只包括标准包含文件的源文件
// City.pch 将成为预编译头
// stdafx.obj 将包含预编译类型信息
#include
6．数据及全局函数文件Common.cpp
#include
#include
double g_Trial[N_CITY_COUNT][N_CITY_COUNT]; //两两城市间信息素
double g_Distance[N_CITY_COUNT][N_CITY_COUNT]; //两两城市间距离
//城市坐标数据
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,
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,
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);
}
//返回指定范围内的随机浮点数
double rnd(double dbLow,double dbUpper)
{
double dbTemp=rand()/((double)RAND_MAX+1.0);
return dbLow+dbTemp*(dbUpper-dbLow);
}
//返回浮点数四舍五入取整后的浮点数
double ROUND(double dbA)
{
return (double)((int)(dbA+0.5));
7．蚂蚁类定义文件Ant.cpp
#include
#include
CAnt::CAnt()
{
}
CAnt::~CAnt()
{
}
//搜索一次
void CAnt::Search()
{
//初始出发点
Init();
//所有城市走一遍
while(m_nMovedCityCount
{
Move();
}
//计算走过路径长度
CalPathLength();
}
void CAnt::Init()
{
for (int i=0;i
{
m_nAllowedCity[i]=1; //设置全部城市为没有去过
m_nPath[i]=0; //蚂蚁走的路径全部设置为0
}
//蚂蚁走过的路径长度设置为0
m_dbPathLength=0.0;
//随机选择一个出发城市
m_nCurCityNo=rnd(0,N_CITY_COUNT);
//设置出发城市
m_nPath[0]=m_nCurCityNo;
//标识出发城市为已经去过了
m_nAllowedCity[m_nCurCityNo]=0;
//已经去过的城市数量设置为1
m_nMovedCityCount=1;
}
//选择下一个城市，返回值为城市编号
int CAnt::ChooseNextCity()
{
int nSelectedCity=-1; //返回结果，先暂时把其设置为-1
//计算当前城市和没去过的城市之间的信息素总和
double dbTotal=0.0;
double prob[N_CITY_COUNT]; //保存城市被选中的概率
for (int i=0;i
{
if (m_nAllowedCity[i] == 1) //城市没去过
{
//该城市被选中的概率=该城市和当前城市间的信息素总量*(1/距离)^2
prob[i]=pow(g_Trial[m_nCurCityNo][i],ALPHA)*pow(1.0/g_Distance[m_nCurCityNo][i],BETA); dbTotal=dbTotal+prob[i]; //累加信息素，得到总和
}
else
{
prob[i]=0.0;
}
}
//轮盘选择
double dbTemp=0.0;
if (dbTotal > 0.0) //总的信息素值大于0
{
dbTemp=rnd(0.0,dbTotal); //取一个随机数
for (int i=0;i
{
if (m_nAllowedCity[i] == 1) //城市没去过
{
dbTemp=dbTemp-prob[i]; //转动轮盘
if (dbTemp
{
nSelectedCity=i;
}
}
}
}
//如果城市间的信息素非常小，由于浮点运算的误差原因，可能没有城市被选择出来
//出现这种情况，就把第一个没去过的城市作为返回结果
if (nSelectedCity == -1)
{
for (int i=0;i
{
if (m_nAllowedCity[i] == 1) //城市没去过
{
nSelectedCity=i;
break;
}
}
}
//返回结果
return nSelectedCity;
}
void CAnt::Move()
{
int nCityNo=ChooseNextCity(); //选择下一个城市
m_nPath[m_nMovedCityCount]=nCityNo; //记录蚂蚁走的路径
m_nAllowedCity[nCityNo]=0;//标记城市已经去过
m_nCurCityNo=nCityNo; //记录当前所在城市编号
m_nMovedCityCount++; //去过的城市数量加一
}
//计算蚂蚁走过的路径长度
void CAnt::CalPathLength()
{
m_dbPathLength=0.0;
int m=0;
int n=0;
//计算走过路径的长度和
for (int i=1;i
{
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];
}
8．旅行商类定义文件Tsp.cpp
#include
#include
CTsp::CTsp()
{
m_cBestAnt.m_dbPathLength=DB_MAX;
}
CTsp::~CTsp()
{
}
//初始化数据
void CTsp::InitData()
{
//先把最佳结果的路径设置成最大
m_cBestAnt.m_dbPathLength=DB_MAX;
//计算两两城市间距离
double dbTemp=0.0;
for (int i=0;i
{
for (int j=0;j
{
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);
}
}
//初始化环境信息素为0
for (int i=0;i
{
for (int j=0;j
{
g_Trial[i][j]=0.0;
}
//更新环境信息素
void CTsp::UpdateTrial()
{
//临时保存信息素
double dbTempAry[N_CITY_COUNT][N_CITY_COUNT];
memset(dbTempAry,0,sizeof(dbTempAry)); //先全部设置为0
//计算新增加的信息素,保存到临时数组里
int m=0;
int n=0;
for (int i=0;i
{
for (int j=1;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;
dbTempAry[m][n]=dbTempAry[n][m];
}
//最后城市和开始城市之间的信息素
n=m_cAntAry[i].m_nPath[0];
dbTempAry[n][m]=dbTempAry[n][m]+DBQ/m_cAntAry[i].m_dbPathLength;
dbTempAry[m][n]=dbTempAry[n][m];
}
//更新环境信息素
for (int i=0;i
{
for (int j=0;j
{
g_Trial[i][j]=g_Trial[i][j]*ROU+dbTempAry[i][j]; //最新的环境信息素 = 留存的信息素 + 新留下的信息素
}
}
}
void CTsp::Search()
{
//输出缓冲区
char cBuf[256];
//每次迭代出动一群蚂蚁，尝试得到更短路径
}
for (int j=0;j
9．main函数主文件City.cpp
#include
#include
int main()
{
//初始化随机种子
time_t tm;
time(&tm);
unsigned int nSeed=(unsigned int)tm; srand(nSeed);
//旅行商开始搜索
CTsp tsp;
tsp.InitData();
tsp.Search();
//输出结果
printf(
} sprintf_s(cBuf,
蚁群算法浅析
摘要：介绍了什么是蚁群算法，蚁群算法的种类，对四种不同的蚁群算法进行了分析对比。详细阐述了蚁群算法的基本原理，将其应用于旅行商问题，有效地解决了问题。通过对旅行商问题C++模拟仿真程序的详细分析，更加深刻地理解与掌握了蚁群算法。 关键词：蚁群算法；旅行商问题；信息素；轮盘选择
一、引言
蚁群算法（Ant Colony Optimization, ACO），是一种用来在图中寻找优化路径的算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。 蚁群算法成功解决了旅行商问题（Traveling Salesman Problem, TSP）：一个商人要到若干城市推销物品，从一个城市出发要到达其他各城市一次而且最多一次最后又回到第一个城市。寻找一条最短路径，使他从起点的城市到达所有城市一遍，最后回到起点的总路程最短。若把每个城市看成是图上的节点，那么旅行商问题就是在N个节点的完全图上寻找一条花费最少的回路。
最基本的蚁群算法见第二节。目前典型的蚁群算法有随机蚁群算法、排序蚁群算法和最大最小蚁群算法，其中后两种蚁群算法是对前一种的优化。本文将终点介绍随机蚁群算法。
二、基本蚁群算法
（一）算法思想
各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种信息素，信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多（或者较长的路上蚂蚁多，这也无关紧要）。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素。因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就找到了。 蚁群算法的基本思想如下图表示：
图1 等概率选择 图2 最优路径 图3 最优比重
（二）算法描述
基本蚁群算法的算法简单描述如下：
1．所有蚂蚁遇到障碍物时按照等概率选择路径，并留下信息素；
2．随着时间的推移，较短路径的信息素浓度升高；
3．蚂蚁再次遇到障碍物时，会选择信息素浓度高的路径；
4．较短路径的信息素浓度继续升高，最终最优路径被选择出来。
三、随机蚁群算法
（一）算法思想
在基本蚁群算法中，蚂蚁会在多条可选择的路径中，自动选择出最短的一条路径。但是，一旦蚁群选择了一条比之前短的路径，就会认为这条路径是最好的，在这条路径上一直走下去。这样的算法存在问题：蚂蚁可能只是找到了局部的最短路径，而忽略了全局最优解。
因此，在基本蚁群算法的基础上，需要对蚂蚁选路的方案加以改善：有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另辟蹊径，也就是它会按照一定的概率不往信息素高的地方。如果令开辟的道路比原来的其他道路更短，那么，渐渐地，更多的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复
为了实现蚂蚁的“随机”选路，我们需要做以下假设：
1．范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径，如果半径等于2，那么它能观察到的范围就是2*2个方格世界，并且能移动的距离也在这个范围之内。
2．环境：环境以一定的速率让信息素消失。
3．觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，那么它朝哪个方向走的概率就大。这就意味着每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。
4．避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。
5．播撒信息素规则：每只蚂蚁在找到食物后撒发的信息素。
自然想到一个问题：开始时环境没有信息素，蚂蚁为什么会相对有效的找到食物呢？ 这个问题用蚂蚁的移动规则同样可以解释。首先，它要能尽量保持某种惯性，这样使得蚂蚁尽量向前方移动（开始，这个前方是随机固定的一个方向），而不是原地无谓的打转或者震动；其次，蚂蚁要有一定的随机性，虽然有了固定的方向，但它也不能像粒子一样直线运动下去，而是有一个随机的干扰。这样就使得蚂蚁运动起来具有了一定的目的性，尽量保持原来的方向，但又有新的试探，这就解释了为什么单个蚂蚁在复杂的诸如迷宫的地图中仍然能找到隐蔽得很好的食物。
（二）算法描述
随机蚁群算法的算法描述如下：
算法输入：城市数量N，两两城市间的距离，所有路径的信息素浓度
算法输出：蚂蚁走过的路径长度 1．设置全部城市都没有去过，走过的路径长度为0； 2．随机选择一个出发的城市； 3．i = 1 4．while(i
用随机蚁群算法解决旅行商问题，实际上是多次使用蚁群算法，不断更新最短路径的过
程。由此，我们容易得到旅行商问题的算法描述：
四、改进的随机蚁群算法
（一）排序蚁群算法
与随机蚁群算法不同的是，当蚂蚁遇到障碍物选择路径时，根据不同路径上信息素的浓度，通过计算可能达到最优解的概率算法，将路径进行排序，选择最好的路径作为下一个通往的城市。
（二）最大最小蚁群算法
与随机蚁群算法和排序蚁群算法都不同的是，当蚂蚁遇到障碍物选择路径时，使用贪心算法输入：所有城市的X、Y坐标，蚂蚁数量n，迭代次数K 算法输出：旅行商的最短路径 1．计算两两城市间的距离，初始化所有路径信息素为0； 2．for i = 1 : K 3． for j = 1 : n 4． 第j只蚂蚁搜索一遍； 5． if 走过的路径小于最短路径 6． 更新最短路径； 7． 更新走过路径的信息素； 8． end 9．end 策略，优先选择达到下一个城市最短的城市，即得到局部最优解。这样以来，更多的信息素将在较短的路径聚集，使算法更快地得到全局最短路径。
五、算法比较
本文介绍了四种蚁群算法，其中第一种比较简单，描述了最基本的蚁群算法思想。但是，它忽略了更优路径存在的可能性，没有考虑到更普遍的情况。因此，该算法只适用于小规模，无特殊情况的问题。
后三种蚁群算法属于实际中典型的蚁群算法，对不同情况的考虑比较全面，因此应用比较广泛。三者的差别主要在于蚂蚁对不同路径的选择上，其中，随机蚁群算法首先根据不同路径上信息素的浓度，计算出选择各条路径的概率，而后使用轮盘算法选择一条路径，适用
择最好的路径作为下一个通往的城市，这样做增加了空间复杂度，有效改善了时间复杂度，适用于规模较大的场合；最大最小蚁群算法则是采用贪心策略，优先选择达到下一个城市最短的城市，先得到局部最优解，再通过聚类效应得到全局最短路径，适合对时间和空间要求都较高的场合。
参考文献：
1. 丁洋. 蚁群优化算法分析. 论文期刊. 2012.5.
2. 蚁群优化算法. http://www.pudn.com/.
附录：
1．预编译所需头文件 Stdafx.h
#pragma once
// Stdafx.h : 标准系统包含文件的包含文件，
// 或是常用但不常更改的项目特定的包含文件
#include
#include
#include
#include
2．算法参数头文件 Common.h
#pragma once
const int N_CITY_COUNT=51; //城市数量
const int N_ANT_COUNT=34; //蚂蚁数量
const int N_IT_COUNT=50; //迭代次数
//蚁群算法参数
const double ALPHA=1.0;
const double BETA=2.0;
const double ROU=0.5; //信息素传递参数
const double DBQ=100.0; //总的信息素
const double DB_MAX=10e9; //最大标志数
extern double g_Trial[N_CITY_COUNT][N_CITY_COUNT]; //两两城市间信息素
extern double g_Distance[N_CITY_COUNT][N_CITY_COUNT]; //两两城市间距离
extern int rnd(int nLow,int nUpper); //返回随机整数
extern double rnd(double dbLow,double dbUpper);//返回随机浮点数
extern double ROUND(double dbA);//浮点数四舍五入
extern double x_Ary[N_CITY_COUNT];
extern double y_Ary[N_CITY_COUNT];
3．蚂蚁类头文件 Ant.h
#pragma once
#include
//蚂蚁类
class CAnt
public:
CAnt();
~CAnt();
int m_nPath[N_CITY_COUNT]; //蚂蚁走的路径
double m_dbPathLength; //蚂蚁走过的路径长度
int m_nAllowedCity[N_CITY_COUNT]; //没去过的城市
int m_nCurCityNo; //当前所在城市编号
int m_nMovedCityCount; //已经去过的城市数量
int ChooseNextCity(); //选择下一个城市
void Init(); //初始化
void Move(); //蚂蚁在城市间移动
void Search(); //搜索路径
void CalPathLength(); //计算蚂蚁走过的路径长度
};
4．旅行商类头文件 Stdafx.h
#pragma once
#include
#include
//旅行商类
class CTsp
{
public:
CTsp();
~CTsp();
CAnt m_cAntAry[N_ANT_COUNT];
CAnt m_cBestAnt; //保存结果
void InitData(); //初始化数据
void Search(); //开始搜索
void UpdateTrial();//更新环境信息素
};
5．预编译所需文件 Stdafx.cpp
// stdafx.cpp : 只包括标准包含文件的源文件
// City.pch 将成为预编译头
// stdafx.obj 将包含预编译类型信息
#include
6．数据及全局函数文件Common.cpp
#include
#include
double g_Trial[N_CITY_COUNT][N_CITY_COUNT]; //两两城市间信息素
double g_Distance[N_CITY_COUNT][N_CITY_COUNT]; //两两城市间距离
//城市坐标数据
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,
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,
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);
}
//返回指定范围内的随机浮点数
double rnd(double dbLow,double dbUpper)
{
double dbTemp=rand()/((double)RAND_MAX+1.0);
return dbLow+dbTemp*(dbUpper-dbLow);
}
//返回浮点数四舍五入取整后的浮点数
double ROUND(double dbA)
{
return (double)((int)(dbA+0.5));
7．蚂蚁类定义文件Ant.cpp
#include
#include
CAnt::CAnt()
{
}
CAnt::~CAnt()
{
}
//搜索一次
void CAnt::Search()
{
//初始出发点
Init();
//所有城市走一遍
while(m_nMovedCityCount
{
Move();
}
//计算走过路径长度
CalPathLength();
}
void CAnt::Init()
{
for (int i=0;i
{
m_nAllowedCity[i]=1; //设置全部城市为没有去过
m_nPath[i]=0; //蚂蚁走的路径全部设置为0
}
//蚂蚁走过的路径长度设置为0
m_dbPathLength=0.0;
//随机选择一个出发城市
m_nCurCityNo=rnd(0,N_CITY_COUNT);
//设置出发城市
m_nPath[0]=m_nCurCityNo;
//标识出发城市为已经去过了
m_nAllowedCity[m_nCurCityNo]=0;
//已经去过的城市数量设置为1
m_nMovedCityCount=1;
}
//选择下一个城市，返回值为城市编号
int CAnt::ChooseNextCity()
{
int nSelectedCity=-1; //返回结果，先暂时把其设置为-1
//计算当前城市和没去过的城市之间的信息素总和
double dbTotal=0.0;
double prob[N_CITY_COUNT]; //保存城市被选中的概率
for (int i=0;i
{
if (m_nAllowedCity[i] == 1) //城市没去过
{
//该城市被选中的概率=该城市和当前城市间的信息素总量*(1/距离)^2
prob[i]=pow(g_Trial[m_nCurCityNo][i],ALPHA)*pow(1.0/g_Distance[m_nCurCityNo][i],BETA); dbTotal=dbTotal+prob[i]; //累加信息素，得到总和
}
else
{
prob[i]=0.0;
}
}
//轮盘选择
double dbTemp=0.0;
if (dbTotal > 0.0) //总的信息素值大于0
{
dbTemp=rnd(0.0,dbTotal); //取一个随机数
for (int i=0;i
{
if (m_nAllowedCity[i] == 1) //城市没去过
{
dbTemp=dbTemp-prob[i]; //转动轮盘
if (dbTemp
{
nSelectedCity=i;
}
}
}
}
//如果城市间的信息素非常小，由于浮点运算的误差原因，可能没有城市被选择出来
//出现这种情况，就把第一个没去过的城市作为返回结果
if (nSelectedCity == -1)
{
for (int i=0;i
{
if (m_nAllowedCity[i] == 1) //城市没去过
{
nSelectedCity=i;
break;
}
}
}
//返回结果
return nSelectedCity;
}
void CAnt::Move()
{
int nCityNo=ChooseNextCity(); //选择下一个城市
m_nPath[m_nMovedCityCount]=nCityNo; //记录蚂蚁走的路径
m_nAllowedCity[nCityNo]=0;//标记城市已经去过
m_nCurCityNo=nCityNo; //记录当前所在城市编号
m_nMovedCityCount++; //去过的城市数量加一
}
//计算蚂蚁走过的路径长度
void CAnt::CalPathLength()
{
m_dbPathLength=0.0;
int m=0;
int n=0;
//计算走过路径的长度和
for (int i=1;i
{
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];
}
8．旅行商类定义文件Tsp.cpp
#include
#include
CTsp::CTsp()
{
m_cBestAnt.m_dbPathLength=DB_MAX;
}
CTsp::~CTsp()
{
}
//初始化数据
void CTsp::InitData()
{
//先把最佳结果的路径设置成最大
m_cBestAnt.m_dbPathLength=DB_MAX;
//计算两两城市间距离
double dbTemp=0.0;
for (int i=0;i
{
for (int j=0;j
{
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);
}
}
//初始化环境信息素为0
for (int i=0;i
{
for (int j=0;j
{
g_Trial[i][j]=0.0;
}
//更新环境信息素
void CTsp::UpdateTrial()
{
//临时保存信息素
double dbTempAry[N_CITY_COUNT][N_CITY_COUNT];
memset(dbTempAry,0,sizeof(dbTempAry)); //先全部设置为0
//计算新增加的信息素,保存到临时数组里
int m=0;
int n=0;
for (int i=0;i
{
for (int j=1;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;
dbTempAry[m][n]=dbTempAry[n][m];
}
//最后城市和开始城市之间的信息素
n=m_cAntAry[i].m_nPath[0];
dbTempAry[n][m]=dbTempAry[n][m]+DBQ/m_cAntAry[i].m_dbPathLength;
dbTempAry[m][n]=dbTempAry[n][m];
}
//更新环境信息素
for (int i=0;i
{
for (int j=0;j
{
g_Trial[i][j]=g_Trial[i][j]*ROU+dbTempAry[i][j]; //最新的环境信息素 = 留存的信息素 + 新留下的信息素
}
}
}
void CTsp::Search()
{
//输出缓冲区
char cBuf[256];
//每次迭代出动一群蚂蚁，尝试得到更短路径
}
for (int j=0;j
9．main函数主文件City.cpp
#include
#include
int main()
{
//初始化随机种子
time_t tm;
time(&tm);
unsigned int nSeed=(unsigned int)tm; srand(nSeed);
//旅行商开始搜索
CTsp tsp;
tsp.InitData();
tsp.Search();
//输出结果
printf(
} sprintf_s(cBuf,