蚂蚁算法商旅问题

《蚂蚁算法商旅问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、用蚂蚁算法求解商旅问题1研究背景1.1商旅问题（Travelingsalesmanproblem）也被称作邮递员路径问题。这个问题字面的描述是：一个商人，要到n个城市兜售商品，他要从一个城市出发，走一条经过且仅经过所有每个城市一次的最短路径。这个问题由来已久，是一个经典的NP完全问题，由于应用范围广泛，在世界上受到很高度的重视。商旅问题最直接的解法就是穷举法，找出所有可能的路径比较长短。但是显而易见，随着城市数的增多，路径的数量将成指数级增长，很快这个数字就会增长到用穷举法无法计算的地步。因此，目前已经出现了多种有效的降低计算量而求解商旅问题的方法。求解TSP问题的方法有

2、很多，比如经典的遗传算法，贪心算法等。由于TSP问题的重要性，近几年来它依然是很热的问题，从2007年到2009年也出现了很多研究TSP问题的重要文献，相继提出了优化遗传算法，多路遗传算法，蚁群算法，模拟退火算法等一些更高效更实用的求解方法。可见对TSP问题的求解还在进行当中，我们也期待更高效的求解方法的出现。本文将使用之前老师们提出的混合蚂蚁算法来对小规模城市数的TSP问题进行验证求解，以求得到学习的目的。1.2蚁群算法(antcolonyoptimization,ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。它由MarcoDorigo于1992年在

3、他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚂蚁在运动觅食过程中，分泌一种信息素，蚂蚁走过的路径就会残留一定浓度的信息素，当后来的蚂蚁再走过这段路径的时候，它们会以较大的概率选择信息素浓度大的路径行走，同时再放出信息素。这就形成了一个正反馈，最优路径上的信息素浓度越来越大，最终可以找到最优路径。2总体设计本文将对小规模TSP问题进行求解，城市数N将设定为10。该TSP问题的实质是在一个顶点数为10的带权完全无向图中，找到一个权值最小的Hamilton回路。其精确描述为：G=（V,E）是一个带权图，V={1,2,……10}为顶点集，E={eij=(i

4、,j)／i,j∈V,i≠j}为边集。dij(i,j∈V,i≠j)为顶点i到j的距离，其中dij﹥0且dij≠∞，同时dij=dji（i，j∈V）。任务目标则是在顶点集V中找到一个完全序列（从i点出发，经过所有点一次），使其形成的回路中∑dij最小。。在求解过程中，文中将使用一种改进的混合蚂蚁算法。次进化蚂蚁算法是相对基本蚂蚁算法而言的，基本蚂蚁算法存在着一些缺陷，为了使算法更加准确，更加有效率，针对基本蚂蚁算法的缺陷我们做了相应的改进。具体有：初始化时每条边上信息素浓度的设置；蚂蚁的转移策略设置；信息素的更新方法；引入局部优化策略，优化蚂蚁所走路径等。3详细设计3.1初始

5、化本文的混合蚂蚁算法中，有几个重要的参数如下：最大的循环次数NcMax；城市的数目N；蚂蚁的总数M；信息素总量Q；程序开始的时候，令时间t=0；循环次数NcMax=0；信息素总量Q设置为1000；并且令M=8只蚂蚁随机的分布在N=10座城市中。并且每条城市之间的路径有一定的初始信息素浓度。同时，为了保证一只蚂蚁从一个城市转移到另一个城市的时候，只在一定数量的相对较近的城市中选择，定义了以下两个数据结构：集合ptabu存放城市i的最近的前K个城市的编号。数据Sumtabu[i]存放距城市i到与其最近的前K个城市的距离之和。通过对每个城市i的相邻城市按距离排序，选择前K个城市

6、置于ptabu中，并且根据其距离计算Sumtabu[i]。10座城市的之间的距离由一个二维数组intdistance[N][N]保存。具体距离由下边给出（是一对称矩阵，并且同城之间的距离设置为Max）：表一城市编号123456789101Max5876152116982Max17614113021963Max319242019774Max213171222105Max921188136Max152316117Max2212308Max21279Max1510Max3.2初始边上的信息素量的设置在基本的蚂蚁算法中，一般在开始的时候，每条边上的信息素的量是相等的，以便使蚂蚁可

7、以初始时可以完全随机的选择下一次要移动的城市。但是在优化的蚂蚁算法中，为了使蚂蚁相对的倾向选择较近的城市，本文中算法在初始化时对每个顶点的相邻顶点按路径长短不同设置了不同量的信息素，公式如下：signaltab=d*Q／Sumtabu[i]*K／N。3.3信息素的更新基本蚂蚁算法采用的信息素更新方法，或者只考虑路径长度而不考虑每条边对减小路径长度所做的贡献，或者不考虑路径长度，另外，对所有蚂蚁所走过的路径均更新信息素，这些更新方法均不利于信息素向最优路径上集中。本算法中，只对部分较短路径更新信息素。更新方法为:对所有蚂蚁走过的