一种改进的小窗口蚁群算法

陈立　谢富强　李兰君

摘要：针对现有小窗口蚁群算法对优化问题规模的适应性较差、对设定可选城市范围的参数依赖大、易于陷入局部最优等缺点，提出了一种随机小窗口蚁群算法，将问题规模与随机性同时引入小窗口蚁群算法，增强了算法的鲁棒性，而且可以避免算法早熟，陷入局部最优。通过对200个城市的仿真结果表明，该算法效果良好。

关键词关键词：蚁群算法；小窗口蚁群算法；路径优化；商旅问题

DOIDOI：10.11907/rjdk.143829

中图分类号：TP312

文献标识码：A文章编号

文章编号：16727800（2015）002004803

基金项目基金项目：湖南省科技厅项目（2013FJ3154）；航天支撑基金项目（2013ZGDZDX）

作者简介作者简介：陈立（1990—），男，湖北黄石人，南华大学电气工程学院硕士研究生，研究方向为最优控制、智能控制理论及应用；谢富强（1971-），男，湖南衡山人，博士，南华大学电气工程学院讲师、硕士生导师，研究方向为最优控制、智能控制理论及应用、导航与制导；李兰君（1965-），女，湖南衡阳人，南华大学电气工程学院教授、硕士生导师，研究方向为智能控制、嵌入式系统应用。

0引言

蚁群算法是20世纪90年代初期由意大利学者Colorni等人＼[1＼]提出的一种仿生算法，通过模拟自然界中蚂蚁寻找食物时利用其留下的信息素强弱来寻找最优路径。本文就是在基本蚁群算法基础上，通过改进小窗口蚁群算法，增加随机小窗口这一环节避免算法过早收敛，增强寻优能力。

1基本蚁群算法

1.1算法原理

蚁群算法是源于蚂蚁的觅食行为，蚂蚁在寻找食物时会在经过的路径上留下信息素，当某条路径是从蚁穴到食物的较短路径时，通过该条路径的蚂蚁就会较多，该条路径上面的信息素浓度就会较高，以此吸引更多的蚂蚁经过这条路径。通过多次往返，某条最短路径上面的信息素浓度会非常高，蚁群就会都从这条最优路径上经过，使得整个种群在寻找食物上的时间变短，提高了效率。

1.2算法实现

1.2.1禁忌表规则

蚁群算法中的蚂蚁具有记忆功能，这与实际的蚂蚁群有区别。记录蚂蚁k当前走过的元素，将其坐标记录下来并放入禁忌表tabu＼[k＼]中，蚂蚁在一次循环过程中不能再次经过已存在禁忌表上的坐标，当一次循环结束后，禁忌表被清零，蚂蚁又可以进行自由选择。

1.2.2状态转移规则

每只蚂蚁在运动过程中，根据各条路径上信息素的浓度以及启发信息来计算状态转移概率。表达式如式（1）所示。

Pkij（t）=[τij（t）]α·[ηk（t）]β∑sallowedk[τis（t）]α·[ηis（t）]β若j∈allowedk0，否则 （1）

其中，allowedk表示蚂蚁k下一次允许移动到的元素，α为信息启发式因子，表示轨迹的相对重要性；β为期望启发式因子，表示能见度的相对重要性[23]，ηij（t）为启发函数。

1.2.3信息素更新规则 蚁群算法中只有那些属于最短路径上的边信息素才被得到增强[4]。这种规则使得算法在寻找最优路径时更具有目的性：对于最优路径的寻找始终是在当前最短路径的周围进行。在k个蚂蚁遍历完n个元素后，按照式（2）进行全局更新。

τij（t+n）=（1-ρ）τij（t）+ρΔτij（t）（2）Δτij（t）=∑mk=1Δτkij（t）（3）

其中ρ为挥发系数，ρ[0，1]；Δτij（t）表示本次循环中路径ij上的信息素增量；Δτkij（t）表示第k只蚂蚁在本次循环中留在路径ij上的信息量。

单个蚂蚁在搜寻最优路径时使用信息素局部更新规则对其经过路径上的信息素按照式（4）进行更新。

τij（t+h）=（1-ζ）τij（t）+ζτ0（4）τ0=1/（nlmin）（5）

其中ζ[0，1]，lmin表示所有元素集合中两个最近元素之间的距离。

2小窗口蚁群算法

蚁群算法最早是应用于商旅问题（TSP）。TSP问题的求解是典型的NP问题，当城市规模n大到一定程度后便会面临“组合爆炸”问题[5]，此时，传统的搜索算法便会陷入困境。随着人工智能算法的兴起，这一问题才被逐渐解决。蚁群算法就是其中之一。然而，蚁群算法同样也存在不足，容易陷入局部最优解。目前，对于蚁群算法的改进大多数都是通过增加变异环节的方法，如文献[6]中引入非均匀变异算子，对已完成搜索的蚁群进行变异处理，以及调节信息素的方法，如文献[7]中提出对挥发因子的取值进行改进。

以上这些改进，对于小规模问题的改善较为明显，但是当TSP问题中城市的数量大于50时，优化结果就难以令人满意。文献[8]提出了小窗口蚁群算法，其核心思想就是在蚂蚁从一个城市向下一个城市移动时，不需要对剩下所有城市（不在禁忌表上）进行考虑，而只需要在出发城市邻近的若干个城市中进行选择，因为最终的最优解是保证总路径最短，因此不可能出现两个城市距离很远的情况。

2.1固定小窗口蚁群算法

固定小窗口蚁群算法就是设定一个相邻城市的范围city[p]，每次蚂蚁选择下一个城市时，都是在city[p]与禁忌表tabu[k]的交集中选择，然后再按照式（1）的规则进行移动。在仿真中，p的取值为6。

2.2动态小窗口蚁群算法

固定小窗口蚁群算法是将可选择城市的规模，也即数量固定下来，但是这样存在一个缺点：不能更好地适应问题规模，当城市数量为100个左右时，可选城市数量为p，当城市数量为200个左右，可选城市数量还是为p，在这种情况下，就没有将问题规模的变化考虑进来，无法得到一个适合不同规模的优化算法。文献[9]提出将可选城市的数量用一个分段函数表示，将其与问题规模联系起来，如式（6）所示，当问题规模n处于不同范围时，可选城市的数量MAXYC也相应地取不同数值。

MAXYC=8，n≤50；10，50

3随机小窗口蚁群算法

3.1算法原理

动态小窗口蚁群算法虽然使用分段函数的形式将可选城市的数量与问题规模联系起来，但是在一定城市规模的范围内，可选城市的数量仍然是个定值，这与固定小窗口蚁群算法一样，同样会使算法早熟，在解决问题时陷入局部最优。在综合考虑固定小窗口蚁群算法和动态小窗口蚁群算法的缺点与不足后，本文提出了随机小窗口蚁群算法，通过数学处理，将问题规模与随机性同时引入小窗口蚁群算法，增强了算法的鲁棒性，而且可以避免算法早熟，陷入局部最优。

3.2算法实现

在确定可选城市数量时，确定一个基准值r，其值与问题规模正相关，表达式见式（7）；一个随机值ε，其值为[0，1]之间的随机数，则可以得到可选城市的数量，表达式见式（8）。

r=n10，（7）citynum=[1+rε]，（8）

式（7）的作用就是将问题规模的参数引入确定小窗口范围的数学表达式中，当n为50时，r为5，当n为200时，r为20，这样随着问题规模n的变化，参数r也会随之变化，并且将该变化传递到式（8）中。式（8）的作用则是引入一个随机值，将r的值做适当缩小，并且限定其变化范围，为了避免当问题规模小于10时程序运行出现问题，特意在式（8）中加上1作为小窗口可选城市的最小值。

随机小窗口蚁群算法如下：①初始化参数m、α、β、ρ、Nc_max；②将m只蚂蚁放在n个城市上；③一组蚂蚁开始循环；④蚂蚁从citynum与tabu[k]这两个列表中选择可以移动的城市，按照式（1）移动；⑤在蚂蚁遍历所有城市之前转至④；⑥记录一次搜索的最短路径，清空禁忌表tabu[k]；⑦更新信息素；⑧当迭代次数小于Nc_max时，转至②；⑨输出最终优化结果。

通过式（8）可以看出，此时可选城市的数量不仅与问题规模联系起来，而且由于引入了限定范围的随机变量ε，使得蚁群算法在搜索最优解时能够及时跳出局部最优，避免算法早熟，也没有过分增加系统消耗。对200个城市的实例仿真结果表明，该算法效果良好。

4仿真结果与分析

4.1实例仿真

仿真环境是MATLAB R2011b 64位，计算机系统为Windows7 64位，硬件配置为Intel（R） Core（TM） i3 M350双核主频2.27GHz，内存3GB。编写MATLAB程序进行实例仿真，蚁群的循环次数Nc_max=10，蚁群数量m=300，α=1，β=5，ρ=0.5。每个程序运行20次，对每次测得的数据进行记录，最后计算其平均值。

一个有200个城市的区域，城市位置随机分布，区域的横坐标范围是0～50，纵坐标范围是0～30，其坐标位置如图1所示。

4.2结果分析

由表1可知，固定小窗口蚁群算法和动态小窗口蚁群算法在最优路径的平均长度上比基本蚁群算法分别缩短了1.57%和1.79%，而随机小窗口蚁群算法在最优路径的平均长度上比基本蚁群算法缩短了4.25%，可以看出随机小窗口蚁群算法在寻找最优解上有较好的表现。同时，通过观察达到收敛所需要的循环次数，随机小窗口蚁群算法的数据比上面3种算法的要增加一倍，这也反映了随机小窗口蚁群算法可以避免算法早熟，能够跳出局部最优。

5结语

本文基于基本蚁群算法，通过改进动态小窗口蚁群算法的不足，提出了随机小窗口蚁群算法，该算法既可以适应问题规模的变化，又可以避免算法早熟，陷入局部最优解。但同时也存在收敛速度不够快的缺陷，这有待进一步研究改进。

参考文献参考文献：

＼[1＼]COLORNI A，DORIGO M，MANIEZZO V，et al.Distributed optimization by ant colonies＼[C＼].Paris：Proc of European Conf on Artificial Life，1991：134142.

＼[2＼]DORIGO M，CARO G D，GAMBARDELLA L M.Ant algorithms for discrete optimization＼[J＼]. Artificial Life，1999，5（2）：137172.

＼[3＼]JAMES M，MARCUS R.Antipheromone as a tool for better exploration of search space＼[C＼]. Brussels：Proc of 3rd Int Workshop on Ant Algorithms，2002：100110.

＼[4＼]倪庆剑，邢汉承，张志政，等.蚁群算法及其应用研究进展＼[J＼].计算机应用与软件，2008，25（8）：1215.

＼[5＼]冀俊忠，黄振，刘椿年，等.基于多粒度的旅行商问题描述及其蚁群优化算法＼[J＼].计算机研究与发展，2010，47（3）：434444.

＼[6＼]龚跃，吴航，赵飞.基于非均匀变异算子的改进蚁群优化算法＼[J＼].计算机工程，2013，39（10）：196199.

＼[7＼]叶仕通，万智萍.一种基于改进全局信息素更新效率的蚁群算法及仿真＼[J＼].计算机应用与软件，2014，31（1）：176179.

＼[8＼]萧蕴诗，李炳宇.小窗口蚁群算法＼[J＼].计算机工程，2003，29（20）：143145.

＼[9＼]赵娟平，高宪文，刘金刚，等.移动机器人路径规划的参数模糊自适应窗口蚁群优化算法＼[J＼].控制与决策，2011，26（7）：10961100.

责任编辑（责任编辑：孙娟）