蚁群算法解决TSP问题实验报告--

一、实验题目

TSP问题的蚁群算法实现

二、实验目的

1 熟悉和掌握蚁群算法的基本概念和基本思想；

2 加深对蚁群算法的理解，理解和掌握蚁群算法的各个操作； 3 理解和掌握利用遗传算法进行问题求解的基本技能。

三、实验原理

1、算法来源

蚁群算法的基本原理来源于自然界蚂蚁觅食的最短路径原理，根据昆虫学家的观察，发现自然界的蚂蚁虽然视觉不发达，但它可以在没有任何提示的情况下找到从食物源到巢穴的最短路径，并且能在环境发生变化（如原有路径上有了障碍物）后，自适应地搜索新的最佳路径。

2、单个蚂蚁寻找路径 正反馈：

单个的蚂蚁为了避免自己迷路，它在爬行时，同时也会释放一种特殊的分泌物——信息素（Pheromone），而且它也能觉察到一定范围内的其它蚂蚁所分泌的信息素，并由此影响它自己的行为。当一条路上的信息素越来越多（当然，随着时间的推移会逐渐减弱），后来的蚂蚁选择这条路径的概率也就越来越大，从而进一步增加了该路径的信息素浓度，这种选择过程称为蚂蚁的自催化过程。 多样性：

同时为了保证蚂蚁在觅食的时候不至走进死胡同而无限循环，蚂蚁在寻找路径的过程中，需要有一定的随机性，虽然在觅食的过程中会根据信息素的浓度去觅食，但是有时候也有判断不准，环境影响等其他很多种情况，还有最终要的一点就是当前信息素浓度大的路径并不一定是最短的路径，需要不断的去修正，多样性保证了系统的创新能力。 正是这两点小心翼翼的巧妙结合才使得蚁群的智能行为涌现出来。 3、具体实现需要解决的两个首要问题 （1）如何实现单个蚂蚁寻路的过程 （2）如何实现信息素浓度的更新

四、蚁群算法解决TSP问题

1、 相关变量的表示和计算

（1）n个城市相互之间的几何距离di,j

（2）it,j表示在t时刻在城市ｉ和ｊ路线上残留的信息量，初始值为一个常数C （3）参数表示信息量的保留度

（4）在t+1时刻路径i，j上的信息量更新公式如下所示

it,j1it,jit,j1t1i,jk1mki,j

ik,jQLk0第k只蚂蚁经过i,j时 当不经过时（5）i,j表示i和j之间路径长度的反比与信息素量相除得到信息素浓度

i,j1 di,j（6）每个蚂蚁在当前节点选择可走的下一个点的时候有一个转移概率概率，信息素浓度越高，概率越大

ia,ji,jaPi,kji,si,ssallowedk0

jallowedk 其他（7）,参数用来实现对信息素浓度的调节，以实现对算法的优化。

五、实验算法（详细代码见附件）

（1）单个蚂蚁搜索路径的算法，根据信息素浓度用轮盘赌算法选择下一个城市 struct Ant {

int Path[CITY_NUM]; //蚂蚁走的路径 double length; //路径总长度

int vis[CITY_NUM]; //走过城市标记 int cur_cityno; //当前城市 int moved_cnt; //已走的数量 //初始化 void Init() {

memset(vis, 0, sizeof(vis)); length = 0;

cur_cityno = rnd(0, CITY_NUM);//随机选择一个出发城市 Path[0] = cur_cityno; vis[cur_cityno] = 1; moved_cnt = 1;

//printf(\"Init %d \\n\ }

//选择下一个城市 //返回值 为城市编号 int chooseNextCity() {

int nSelectedCity=-1; //返回结果，先暂时把其设置为-1 //计算当前城市和没去过的城市之间的信息素总和 double dbTotal=0.0;

double prob[CITY_NUM]; //保存各个城市被选中的概率 for(int i = 0; i < CITY_NUM; i++) {

if (!vis[i]) {

prob[i]=pow(info[cur_cityno][i],ALPHA) *pow(1.0/dis[cur_cityno][i], BETA); dbTotal += prob[i]; } else {

prob[i] = 0; } }

//进行轮盘选择 double dbTemp=0.0;

if (dbTotal > 0.0) //总的信息素值大于0 {

dbTemp = rnd(0.0, dbTotal); for (int i = 0; i < CITY_NUM; i++) {

if (!vis[i]) {

dbTemp -= prob[i]; if (dbTemp < 0.0) {

nSelectedCity = i; break; } } } }

//如果城市间的信息素非常小 ( 小到比double能够表示的最小的数字还要小 ) //出现这种情况，就把第一个没去过的城市作为返回结果

if (nSelectedCity == -1) {

for (int i=0; iif (!vis[i]) //城市没去过 {

nSelectedCity=i; break; } } }

return nSelectedCity; }

//蚂蚁在城市间移动 void Move() {

int nCityno = chooseNextCity();//选择下一个城市

Path[moved_cnt] = nCityno;//保存蚂蚁走的路径 vis[nCityno] = 1;//把这个城市设置成已经去过 cur_cityno = nCityno; //更新已走路径长度

length += dis[Path[moved_cnt-1]][Path[moved_cnt]]; moved_cnt++;

//puts(\"bigin move \"); }

//蚂蚁进行搜索一次 void Search() {

Init();

//如果蚂蚁去过的城市数量小于城市数量，就继续移动 while(moved_cnt < CITY_NUM) {

Move(); }

length += dis[Path[CITY_NUM-1]][Path[0]]; } };

（2）蚁群的定义，与不断迭代更新信息素和选择最优路径的过程 struct TSP {

Ant ants[ANT_NUM]; //定义一群蚂蚁 Ant ant_best; //保存最好结果的蚂蚁

void Init() {

//初始化为最大值 ant_best.length = mmax; puts(\"cal dis\"); //计算两两城市间距离

for (int i = 0; i < CITY_NUM; i++) {

for (int j = 0; j < CITY_NUM; j++) {

double temp1=CityPos[j][0]-CityPos[i][0]; double temp2=CityPos[j][1]-CityPos[i][1]; dis[i][j] = sqrt(temp1*temp1+temp2*temp2); } }

//初始化环境信息素 puts(\"init info\");

for (int i=0; ifor (int j=0; jinfo[i][j]=1.0; } } }

//更新信息素,当前每条路上的信息素等于过去保留的信息素 //加上每个蚂蚁这次走过去剩下的信息素 void Updateinfo() {

//puts(\"update info\");

double tmpinfo[CITY_NUM][CITY_NUM]; memset(tmpinfo, 0, sizeof(tmpinfo)); int m = 0; int n = 0; //遍历每只蚂蚁

for (int i = 0; i < ANT_NUM; i++) { //puts(\"****\");

// for (int j = 0; j < CITY_NUM; j++) { // printf(\"%d \// } //puts(\"\");

for (int j = 1; j < CITY_NUM; j++) {

m = ants[i].Path[j]; n = ants[i].Path[j-1]; //printf(\"%d %d\\n\

tmpinfo[n][m] = tmpinfo[n][m]+Q/ants[i].length;

tmpinfo[m][n] = tmpinfo[n][m]; }

//最后城市和开始城市之间的信息素 n = ants[i].Path[0];

tmpinfo[n][m] = tmpinfo[n][m]+Q/ants[i].length; tmpinfo[m][n] = tmpinfo[n][m]; }

//更新环境信息素

for (int i = 0; i < CITY_NUM; i++) {

for (int j = 0; j < CITY_NUM; j++) {

//最新的环境信息素 = 留存的信息素 + 新留下的信息素 info[i][j] = info[i][j]*ROU + tmpinfo[i][j];

} } }

//寻找路径，迭代TMAC次 void Search() {

for (int i = 0; i < TMAC; i++) {

printf(\"current iteration times %d\\n\ for (int j = 0; j < ANT_NUM; j++) { ants[j].Search(); }

//保存最佳结果

for (int j = 0; j < ANT_NUM; j++) { if (ant_best.length > ants[j].length) { ant_best = ants[j]; } }

//更新环境信息素 Updateinfo();

printf(\"current minimum length %lf\\n\ } } };

六、实验结果

（1）数据的读取，数据直接保存在数组中

（2）选择老师所给10个城市的数据，结果如下所示，经过50次迭代就能得到最优解，而且算法相当稳定，多次尝试都是50次就能得到最优解，相比于遗传算法的500次迭代在时间上有了很大的改进。

（3）选择老师所给的30个城市的数据，经过1000次迭代过程能得到一个非常较优的解，结果稳定在425左右，与最优解424.869292非常接近，并且偶尔会得到最优解，相比于遗传算法迭代10000次结果在700左右，最佳结果有了很大的飞跃。

七、实验总结及体会

（1）蚁群算法相比于遗传算法针对TSP问题的求解有了很大的改进，我觉得很大的原因是蚁群在寻找路径过程中的正反馈调节，正是根据信息素浓度的调整，才使得路径长度很容易收敛。同时由于用了轮盘赌算法，有保证了存在一定的多样性，受初始值的影响不大。 （2）蚁群算法也有一定的局限性，虽然相对于遗传算法有了很大的改进，但是有时候仍然找不到最优解，只能找到次优解。后续要具体优化的话，就要调节相关参数来不断进行改进。 （3）在本次求解TSP问题的实验过程中，我体会到了智能算法在求解NP问题中所起的巨大的作用，从30！的暴力求解，到遗传算法，再到蚁群算法，求解效率一步一步提高，结果让自己感到吃惊，对智能算法产生了极大的兴趣。