蚁群优化算法研究

长江大学学报(自然科学版) 2009年9月第6卷第3期: 理工Journal of Yangtze University (Nat Sci Edit) Sep. 2009，Vol.6 No.3: Sei & Eng，221●蚁群优化算法研究王同喜(长江大学计算机科学学院， 湖北荆州434023)[摘要] 由传统的蚁群优化算法入手， 介绍了蚁群优化算法的基本原理以及在TSP问题中的应用，分析并总结了蚁群算法在信息素更新、路径构造等方面的改进方法。[关键词]蚁群算法;组合优化; TSP[中圈分类号] TP301. 6.[文献标识码] A [文章编号] 1673- 1409 (2009) 03- N221 -02蚁群优化算法是一种源于大自然中生物世界的新的仿生类算法。它吸收了蚂蚁的行为特性，通过其内在的搜索机制，在一系列的组合优化问题求解中取得了成效。意大利学者Dorigo 在1991年至1992年间提出蚂蚁密度(ant-density)、 蚂蚁数量(ant-quantity)、 蚂蚁周期(ant-cycle) 3种算法模型1。其中前2个算法模型因为其低劣的性能已经淘汰，现在的蚁群优化算法由蚂蚁周期演变而来。蚁群优化算法的一般步骤如下:①将待解问题抽象成以成分和状态变换的集合形式，或者以带权图的形式，蚁群将利用这些形式建立问题的解;②定义信息素r的合适含义;③定义一个合理的启发信息素η; ④在条件允许的情况下，使用合适有效的局部搜索算法;⑤选择某种具体的蚁群优化算法;⑥调整算法参数，跳转到第4步直到满足某种结束条件,算法结束。1 TSP 中的蚁群优化算法以求解n个城市的对称TSP问题为例，建立基本蚂蚁算法模型。首先，对算法中的参数和变量进行说明。记M为蚁群中蚂蚁的数量,c。为城市ivj间的距离的权值,ty(I)为t时刻城市i、j间路径的轨迹强度,即残留的信息素浓度,物为城市i、j间路径的能见度，即启发信息素,在TSP问题中一般取值1/cg，a表示轨迹的相对重要性(a≥0),β表示能见度的相对重要性(β≥0),帕(t)为I时刻蚂蚁k选择j作为下一个访问城市的转移概率,定义为:。[r,]°[n卫如果j∈N;p()=ScxJ[P否则其中,Nt为位于城市i的蚂蚁k可以直接到达的相邻城市的集合。采用蚁群算法求解TSP问题的主要步骤如下:步1初始化:n.← 0;(n.为迭代次数),对各路径(i,j),置τ=划= m/c"(c"为最邻近启发算法构造的路径长度,一般为估计值),Org←0 ,将m只蚂蚁随机分布于城市的m个顶点上。步2将各蚂蚁的初始 出发点置于当前解集中,对每个蚂蚁k(k = 1,2..m)，按慨率p(t)移至下一顶点j,将顶点j置于当前解集中;重复n-1次该过程,完成一个解的构造。步3计算各蚂蚁的目标函数值T*(k= 1,2,.. ,m)。步4进行解的评 价,并由解决定反馈给环境的轨迹更新量。按更新方程修改最好解路径上的轨迹强度。步5对各路径(i,),置t←r+ 二0嗜,即:如果(i,j)在路径T*上;n.←ne +1到←q+中国煤化工[收稿日期] 2009 -05 -25CNMH G_[作者简介们]王同喜(1971-), 男，1994年大学毕业，硕士,讲师，现主要从事数据库、典法刀们刀通的我子=研究工作。，222●长江大学学报(自然科学版)2009年9月步6若n 小于预定的迭代次数，则转步2,否则结束。2几种改进的蚁群算法随着TSP问题规模n的扩大，相比其他的启发式算法，蚁群算法的性能将严重下降。目前，对蚁群算法的研究工作都集中在优化其参数配置，改进信息素更新规则，或者与其他启发式算法结合。1)精华蚂蚁系统 精华蚂蚁系统(elitist strategy for ant system, EAS)是Dorigol2]在 1992年提出，是对基本蚁群算法的首次改进。其改进思想是对m只蚂蚁从算法开始到目前为止找到的最优路径T"实施-种强化。信息素释放规则改进为的←q+ 2st +eO你(e为一常数)。适当的e不但可以得到更好的解,而且可以再更少迭代次数的情况下得到更好的解，即只有最优的蚂蚁可以向该路径T*.2)最大最小蚂蚁系统Stuzle & HoosC3] 在对蚁群算法进行深人研究后提出了4点改进，产生了最大最小蚂蚁系统(max -min ant system, MMAS)。首先,在m只蚂蚁的一次迭代过程中,获得当前迭代最优路径Then的蚂蚁释放信息素,即r←τ +Or5*。其次,将信息素的取值范围限制在区间[mn,Tma],这.样避免了某些边信息索增长过快,导致算法停滯。再次,信息素的初始值为Tmax.最后，当算法出现停滞或者在达到一定的迭代次数后，信息素值重新初始化。3)蚁群系统蚁群系统 . (ant colony system, ACS)4I与上述算法的不同主要表现在3个方面:首先，蚁群系统采用了一种更积极的行为来构建路径。在ACS中,位于城市i的蚂蚁k ,根据伪随机比例规则选择城市j作为下一个访问,即:(arg max(re[n]}如果q≤qo否则其中,q是在区间[0,1]中均匀分布的- -个随机变量,0≤qo≤1;J根据公式:(_ [ry]°[y]°如果j∈Nt帱(t) =.乙[tv]°[η]°IEN给出的概率分布产生。根据这个改进的路径产生规则,能更好的利用蚂蚁所积累的搜索经验.第二,信息索的挥发和释放只在至今最优的路径上执行。第三,对蚂蚁每次路径的边(i,j),算法主动去掉一定的信息素,这样增加了搜索其他路径的机会。信息素的更新表示τ + (1- p)t; + pQ谐,(p为信息素挥发速率)。3结语蚁群优化算法作为一种通用型随机优化算法，自问世以来表现出了强大的生命力，较以往的启发式算法在搜索效率和算法的时间复杂度方面都取得了令人满意的效果。现已陆续应用到组合优化、人工智能等多个领域。蚂蚁算法的正反馈性和协同性使其可用于分布式系统，隐含的并行性更使之具有极强的发展潜力。[参考文献][1] Colormi A, Dorigo M, Maniezo V. Distributed optimization by ant colonies [M] . Boston; PWS Publishing, 1991.[2] Dorigo M, Maniezzo V , Colorni A. Ant System: Optimization by a coloay of cooperationg agents [J] . IEEE Transactions on System,1992, 26 (1): 29~41.[3] Stutle T, Hoos H H. The MAX-MIN Ant System and local search for the traveling sales man problem [A] . Proceedings of the 1997IEEE International Conference on Evolutionary Computation (ICEC'97) [C1 : NI: IEEE Press, 1997. 309~314.[4] DorigoM. 蚁群优化[M].张军，胡晓敏,罗旭耀等译.北京:清华中国煤化工MHCNMHG辆] 洪云飞