蚂蚁算法在行商问题中的应用.doc

《蚂蚁算法在行商问题中的应用.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、蚂蚁算法在旅行商问题中的应用薛军涛蚂蚁是大家司空见惯的一种昆虫，而他们的群体合作的精神令人钦佩。他们的寻食、御敌、筑巢（蚂蚁的筑窝，蜜蜂建巢）之精巧令人惊叹。若我们是能从他们身上学习到一些什么的话，也将是一件非常有益之事。据研究当蚂蚁找到食物并将它搬回来时，就会在其经过的路径上留下一种“外激素”，其他蚂蚁嗅到这个激素的“味道”，就沿该路奋勇向前，觅食而去。不但如此而且还会沿着最短的路径奔向食物。20世纪90年代初意大利学者Dorigo，Maniezzo提出的第一个“蚂蚁算法（antcolonyalgorithm）”。就是依照蚂蚁觅食原理，设计的一个群体智能的算法。如前所述，蚂蚁

2、能很快地找到通向食物的最短路径，下面我们较仔细地分析一下蚂蚁是如何找到到食物地点的最短程的。设一群蚂蚁（随机地）向四面八方去觅食，当某只蚂蚁觅到食物时，一般就沿原路回巢，同时在归途上留下外激素，外激素随着向四周散发其浓度会不断下降。若有两只蚂蚁都找到食物，且沿原路返回（见图一）设OA比OBA短，当第一只蚂蚁回到O点时，第二只蚂蚁（沿OBA的蚂蚁）才回到C点。于是OA路上有两次外激素的遗留物（去一次、回来一次），而在OC路是只有去一次的外激素遗留物，故OA的外激素浓度比OC上大，据研究蚂蚁一般会沿外激素浓度大的路径上前行。于是后面的蚂蚁会渐渐地沿由O到A的最短程到达A点（指所有已

3、求到的路径中的最短者）。以上就是蚂蚁能以最短和找到食物的原因。我们下面简单介绍，人们是如何根据这个原理设计出求最短程的“蚂蚁算法”的。下面以求通过n个城市的最短回路为例。设有n个，设在t时刻在第i个城市上有蚂蚁ai(t)个,令共有m个蚂蚁.设在t时刻在连接第i,j两城市间的道路留下的外激素量为bij(t)规定每个蚂蚁,在未完成一个回路时,不重复走已走过的城市.第k个蚂蚁从i城市到j城市的概率其中外激素量bij(t)有许多不同的定义,如可定义为:b(t)=e-ct,c>0;或定义为:bij(t+n)=dbij(t)+dij,其中d、e是一正常量.(1)这样每只蚂蚁经过n次迁移后就

4、得到一条回路,其长度记为Lk.若满足要求,则停止.不然,利用(1)式重新计算各边的外激素浓度,进行第二轮的搜索…。蚂蚁算法的原理：其原理是一种正反馈机制或称增强型学习系统，它通过信息素的不断更新达到最终收敛于最优路径上以下利用蚂蚁算法解决旅行商（TSP）问题，简而言之就是利用蚂蚁算法求解若干个城市的最短回路问题，求得的解同其它方法求到得解一样精确，这说明蚂蚁算法不但是求解组合优化问题的可行方法，而且是一种很有竞争力的算法。本验示程序是采用VC++6.0设计，验示程序求解70个城市之间的最短路径，也就是最短哈密而顿环。程序设计思路：蚂蚁从起点城市开始跑，对跑过的城市不再访问，在两

5、个城市之间留下信息素。两个城市之间的信息素总和影响别的蚂蚁进行路径的选择。本程序的特点：1．验示程序中蚂蚁的个数可以用户指定，根据程序的大量试验发现，蚂蚁的个数越少收敛的越慢，同样蚂蚁的数量越多理论上收敛的速度是越快，可是这样程序用来运算消耗的时间也就越来越多，经大量试验表明蚂蚁的数量和城市的个数相等的时候收敛的速度和结果都比较优化。2．程序的采用可视化，便于用户操作而且结果同步显示便于用户比较。3．蚂蚁根据信息素的多少选择下一路径，在这个过程中随即函数对算法收敛速度的影响也是非常严重的。因此用户要选择适当的随即函数。关于程序的设计按照蚂蚁算法的思路，具体见附录程序源代码。下图

6、为70个蚂蚁运行产生的最优路径解：验示程序存在的问题：1．程序只是对蚂蚁算法进行了验示，对于蚂蚁算法中α、β等参数的变化对程序收敛速度的影响只是由用户感觉所得，没有进行比较分析。2．程序实现了蚂蚁算法在TSP问题中的应用，虽较好的求解了问题，但没有对原蚂蚁算法在具体问题方面进行改进。