裴振兵
河南安彩高科股份有限公司 河南省 安阳市455000
摘 要：本文提出了一种在蚁群搜索路径过程中,通过建立α(信息素启发式因子), β(期望启发式因子)的互锁关系,动态自适应调整α、β的改进蚁群算法;并进行静态已知环境建模,通过仿真实验,验证了该方法的可行性和有效性,同时将其应用到TSP问题,并取得了较好实验效果.
关键词：改进蚁群算法；TSP问题；互锁关系
中图分类号：（TP） 文献标志码：A
1 蚁群算法基本原理及数学模型
根据蚂蚁“寻找食物”的群体行为，意大利学者Dorigo M等于1991年在法国巴黎召开的第一届欧洲人工生命会议(European Conference on Artificial Lif, ECAL)上最早提出了一种新型的仿生算法——蚁群算法[1],蚁群算法是科学家受到自然界中真实蚁群觅食行为的启发,经过长期研究发现:单个蚂蚁虽没有视觉，也无法掌握附近地理信息，但运动时会通过在路径上释放出一种特殊的分泌物——信息素来寻找路径[2]。当蚁群在运动路径上突然出现障碍物时，蚂蚁也可以通过信息素相互传递最终找到一条躲避障碍物的最优路径[3]。蚁群算法具有分布式并行计算机制，易于与其他方法结合，实现简单的优点。这也正是其最早成功应用解决著名TSP问题的原因。
蚂蚁k(k=1，2,…，m)在运动过程中，根据各条路径上的信息量决定其转移方向。用禁忌tabuk(k=1，2，…，m)来记录k当前所走过的节点，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。Pkij(t)表示t时刻蚂蚁k由节点i转移到节点j的状态转移概率[4]：
.png)
式中,τij(t)表示t时刻在路径(i, j)上的信息素量;allowedk={C—tabuk}表示蚂蚁k下一步允许选择的节点;α为信息启发因子(α反映信息素积累量在指导蚁群搜索中的相对重要)，β为期望启发式因子(β反映了下个目标点的距离在指导蚁群搜索过程中的相对重要)其值越大，则该状态转移概率越接近于贪心规则;ηij(t)为启发函数，其表达式如下：
.png)
(2)
式中，dij表示相邻节点之间的距离。对蚂蚁k而言，dij越小，则ηij(t)越大，Pkij(t)也就越大。显然，该启发函数表示蚂蚁从节点i转移到节点j的期望程度。对蚂蚁k而言，在每只蚂蚁走完一步或者完成对所有n个节点的遍历后，要对残留信息进行更新处理。这种更新策略模仿了人类大脑记忆的特点，在新信息不断存入大脑的同时，存储在大脑中的旧信息随着时间的推移逐渐淡化，甚至忘记。由此，t+n时刻在路径(i, j)上的信息量按如下规则进行调整[5]:
.png)
式,表示信息素挥发系数,则1-ρ表示信息素残留因子，为了防止信息素无限积累, ρ的取值范围为:ρ∈[0,1);Δτij(t)表示本次循环中路径(i, j)上的信息素增量，初始时刻Δτij(t)=0, Δτkij(t)表示第k只蚂蚁在本次循环中留在路径(i, j)上的信息量[6]。
其中Δτkij(t)按下式进行
.png)
2 改进蚁群算法
与基本蚁群算法相比，本文提出的改进算法的特点是：改进算法用动态自适应调整α、β的值，代替基本蚁群算法中固定值α、β从而提高算法收敛速度，跳离局部最优。
2.1 改进算法描述
定义1(α、β的动态自适应调整) 是指通过建立α(信息素启发式因子),β(期望启发式因子)的互锁关系，即对不同的迭代次数NC，α、β会对应取得不同的值，进而在整个过程中扩大搜索空间，使蚁群算法跳离局部最优。
根据蚁群算法搜索情况来自适应动态调整信息启发因子α，期望启发式因子β采用关于迭代次数NC的阶梯函数α(NC)，β(NC)来代替常数项α、β，按下式进行调整：
.png)
在搜索过程中为了达到一定平衡,式中信息启发因子α,期望启发式因子β是互锁的关系,即αi+βi=M(其中M为一定值)。由于α、β值过大或过小,都易使蚁群的搜索过早陷入局部最优[7]。结合其他改进算法中α、β的取值经验与分析,同时通过仿真实验分析,确定当1≤α≤9,1≤β≤9更有利于整个改进算法动态调整。刚开始信息素浓度差别不大，以各个节点之间的距离为主要调整因素,这样有利于提高路径搜索速度,即信息启发因子α(1≤α1<5)先取值较小,相对应的期望启发式因子β(5<β1≤9)取值较大 [8];随着迭代次数增加,各条路径的信息素也得到了积累,此时选择信息素浓度为主要调整因素进行全局搜索,即信息启发因子α(5<α2≤9)先取较大值,相对应的期望启发式因子β(1≤β2<5)取值较小;随着迭代次数的继续增加,为了防止由于信息素积累的正反馈机制作用,陷入局部最优,进而改为各个节点距离为主要调整因素,即信息启发因子α(1<α3≤5)先取值较小,相对应的期望启发式因子β(5≤β3<9)取值较大。
2.3 改进算法实现步骤
Step1：初始化
初始化改进蚁群算法的最大迭代次数NCmax，蚁群的蚂蚁数m，以及ρ，Q等参数进行初始化。
Step2：根据转移概率公式选择下一个节点
蚂蚁按照转移概率公式(1)进行选择，其中α、β的值按式(6)、(7)进行动态自适应调整，每转移一次记录已走过的路径，并将已访问节点加入禁忌表。
Step3：记录每一代每一只蚂蚁的觅食路线和路线长度
将蚁群中迭代一次的蚂蚁路径及路径长度进行记录，并写入细胞存储结构CELL
Step4：更新信息素
判断点i与j连接后的线路上信息素量Q，若Q≤q，则转Step3，否则修改禁忌表tabuk，删除已选节点jl且转到Step5。
Step5：终止条件判断
当算法迭代次数大于设定最大迭代次数NCmax，以及算法给出的最优解满足条件时，退出程序，输出最优解。
3 仿真实验及其分析
3.1算例验证改进算法的可行性
为了验证本文所提改进算法的可行性，基于TSP仿真算例进行试验分析，并与一般蚁群算法进行仿真对比。实验中重要参数设置如表1所示：
表1 参数设置说明
Tab.1 Parameters setup instructions
.png)
仿真实验：将改进算法与一般蚁群算法进行仿真对比，具体实验结果如下图所示：
.png)
图1平均距离与最短距离
Fig.1 Average distance and the shortest distance
.png)
图2最优路径
Fig.2 The optimal path
图1中实线代表本文所提的改进蚁群算法，图中点划线代表一般蚁群算法 (其中图1的上半部为本文所提的改进蚁群算法与一般蚁群算法在平均距离上的仿真对比；下半部为其在最短路径距离上的仿真对比)。图2为采用本文改进蚁群算法所搜索到的最优路径(其中1为起始目标点32为终止目标点)。
具体仿真数据分析如表2所示：
表2仿真数据
.png)
由表2我们可以得出如下结论：本文改进的蚁群算法，所获得的最短距离与平均距离明显优于一般蚁群算法，且整个运行时间也少于一般蚁群算法。通过该仿真实验，验证了本文所提出的改进算法的可行性和有效性。
4 结束语
本文在原有蚁群算法的基础上，主要针对蚁群算法在构造解的过程中,收敛速度慢且容易陷入局部最优, 提出了动态自适应调整α、β策略。基于TSP仿真实验将改进蚁群算法与一般蚁群算法进行对比分析，仿真结果显示了该改进算法在一定程度上提高了搜索速度，有效的弥补了传统蚁群算法容易陷入局部最优的劣势。
参考文献:
[1] Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies. Processings of the 1st Europea-n Conference on Artificial Life[C], 1991, 134-142.
[2] 王颖,谢剑英.一种自适应蚁群算法及其仿真研究[J].系统仿真学报,2002,14(1):31-33.
[3] 覃刚力,杨家本.自适应调整信息素的蚁群算法[J].信息与控制,2001,31(3):198-201.
[4] 段海滨.蚁群算法原理及其应用[M]. 北京:科学出版社,2005,12.
[5] 周明秀,程科,王正霞.动态路径规划中的改进蚁群算法[J].计算机科学,2012,40(1):314-316.
[6] 王越,叶秋冬.蚁群算法在求解最短路径问题上的改进策略[J].计算机工程与应用,2012,48(13):35-38.
[7] 赵凯,李声晋,孙娟,赵锋.改进蚁群算法在移动机器人路径规划中的研究[J].微型机与应用,2013,32(4):67-70.
[8] 温如春,汤青波,杨国亮.基于改进蚁群算法的移动机器人路径规划[J].兵工自动化,2010,29(8):