算法分析
基于蚁群算法的TSP问题研究
温莹莹
(临沂大学山东临沂276000)
数字执本开与或用
摘要：双群优化算法是一种模拟进化算法，其灵感来源于妈双在寻找食物过程中发境路径的行为，它充分利用了生物效群能通过个体间简单的信息传递,截索从蚁累至食物间最超路径的集体寻优特征通过正反馈、分布式协作来寻找最优路径。本文崩速了数群算法的基本工作原理，建立了数学模型,并锋其应用于经典的TSP问题。通过仿真实例表明,数群算法在解决TSP同题时具有较好的鲁樟性,能快速地找到最优解。
关键词：蚁群算法TSP最优解
中图分类号：TP212 1引言
文献标识码：A
蚂蚊是地球上最常见、数量最多的昆虫种类之一，常常成群结队地出现在人类的日常生活环境中。意大利学者M.Dorigo，V， Maniezzo等人在观察蚂蚊的觅食习性时发现，蚂蚁总能找到巢穴与食物源之闻的最短路径。经研究发现，蚂数的这种群体协作功能是通过一种遗留在其来往路径上的叫做信息素的挥发性化学物质来进行通信和协调的。整个蚊群就是通过这种信息素进行相互协作，形成正反馈，从而使多个路径上的蚂蚊都逐渐聚集到最短的那条路径上。
这样，M.Dorigo等人于1991年首先提出了蚊群算法。其主要特点就是：通过正反馈、分布式协作来寻找最优路径。这是一种基于种群寻优的启发式搜索算法。它充分利用了生物蚁群能通过个体间简单的信息传递，搜索从蚁巢至食物间最短路径的集体寻优特征。该算法用来求解TSP间题（及其他组合优化间题，如VRP间题、Job-shop调度问题等),取得了一系列较好的实验结果。
旅行商问题又称为旅行推销员问题，货郎担问题，简称为TSP 问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本，
2蚊群算法的基本原理
蚂蚊在觅食过程时，是以信息素作为媒介而间接进行信息交流，当蚂蚁从食物源走到蚁穴，或者从蚊穴走到食物源时，都会在经过的路径上释放信息素，从而形成了一条含有信息素的路径，蚂数可以感觉出路径上信息素浓度的大小，某一条路径越短，路上经过的蚂数越多，其信息素遗留的也就越多，信息素的浓度就越高，蚂数选择这条路径的几率也就越高，
由此构成的正反馈过程，从面逐渐的逼近最优路径，找到最优路径。
3蚊群算法的基本模型
下面来建立敦群算法的模型，假设用N个节点来表示N个城市，
城市和城市之间的距离用d来表示，时刻从节点到节点这段路径上留下的信息量用↑。()来表示。开始每条路径上的信息量是相等的，蚂数k在运动过程中，根据每条路径上信息量的多少来决定应该走哪条路径。t时刻第k个蚂蚁从节点到节点的概率用p(t)表示。
文章编号:1007-9416(2016)03-0142-01
rg(t)mg(t)
p(t) =
vj eallowed
(t)(t)
(1)
0
orherwise
a，称为启发值，α参数控制信息量，β多数控制启发式, =
的值，这两个参数值越大，表明在转移中起的作用越大。公式1表明走过的蚂蚁越多，留下的信息素越多，下一个蚂蚊选择这个路径的概率越大。但是随着越来越多的蚂蚊走过此路径，之前的蚂蚁留下的信息会逐渐消失，此时用P参数表示信息消失的程度，经过n个时刻，所有的蚂蚁都走了一圈，相应的每个路径上留下的信息素需要做如下调整：
, (t + 1) = (1 p)r, (t) + r, (t) (t) =
4实验仿真
(2)(3)
将数群算法应用30个城市组成的旅行商间题，来进行仿真实验。假设Q=100,其中循环次数是整个程序运行时的总次数，达到最优解的运行次数是指找到最短路径需要循环的次数，最短路径即为旅行商问题的最优解，运行时闻是运行一次程序所需要的时闻，表1
是30个城市的仿真结果。 5结论
通过仿真结果，我们可以看出蚊群算法在解决TSP问题时，具有较好的鲁棒性，能迅速找到较好的解，避免过早地收效。但算法有很多参数(如α、β、P、q等)需要确定，当问题规模比较大时，全局搜索
能力差，需要在此基础上进一步改进。参考文献
[1]张宏达,郑全第.基于蚊群算法的TSP的仿真与研究[J].航空计算技术,2005年第4期
[2]胡小兵,黄席糖.基于蚊群算法的TSP间题求解[J].科技信惠,2010 年第25期
[3]汪镭.吴启迪.蚊群算法在连续空间寻优间题求解中的应用[J].控制与决策2003年第18卷第1期。
表1
α 0.8 1.0 0.8 1.0
β 5 3 5 5
p 0.8 0.7 80 0.5
循环次数 500 1000 10000 1000
达到最优解的运行次数
195 47 33 5910
收稿日期：20160118
作者篇介：温莹莹(1978一),女，山东临沂人,颈士研究生,讲师，研究方向是智能优化算法。 142
最短路径 424.633 556.110 408.752 149.8.38
遥行时间 51s 86s 4266 831s