刘　锴　游晓明*　刘　升

1(上海工程技术大学电子电气工程学院　上海 201620)

2(上海工程技术大学管理学院　上海 201620)



基于分层搜索的蚁群算法及收敛性分析

刘锴1游晓明1*刘升2

1(上海工程技术大学电子电气工程学院上海 201620)

2(上海工程技术大学管理学院上海 201620)

摘要针对蚁群算法容易陷入局部最优的问题，提出一种新的解决连续空间优化的蚁群分层搜索算法。该算法将蚁群搜索空间逐层分割，用信息素分布函数给出了基于分层结点的信息素分布方法。定义了适用于连续域的信息素局部更新、全局更新、状态转移规则，其中局部更新算子能够通过选取合适的参数来增加解的多样性。实验结果表明，相比传统算法，该算法全局搜索能力强，求解精度更高。该算法能达到连续域问题的理论最优值，通过下鞅的停时理论证明了算法以概率1收敛。

关键词蚁群算法连续空间优化分层搜索下鞅

ANT COLONY ALGORITHM BASED ON HIERARCHICAL SEARCH AND ITS CONVERGENCE ANALYSIS

Liu Kai1You Xiaoming1*Liu Sheng2

1(College of Electronic and Electrical Engineering,Shanghai University of Engineering Science,Shanghai 201620,China)2(School of Management,Shanghai University of Engineering Science,Shanghai 201620,China)

AbstractFor ant colony algorithm easily falling into local optimum, we proposed a novel ant colony hierarchical search algorithm for solving continuous space optimisation. The algorithm partitions the ant colony search space hierarchically, and presents a hierarchical nodes-based pheromone distribution approach with pheromone distribution function. We defined the rules of pheromone local update, global update and state transition suitable for continuous domains, in which the local update operator could increase the diversity of solutions by selecting the appropriate parameters. Experimental results showed that comparing with traditional ant colony algorithms, the ant colony hierarchical search algorithm had stronger global search capability and higher solution accuracy. It could achieve the theoretical optimum of continuous domains problem. Moreover, by using the stopping theory of submartingale, it was concluded that the algorithm converges with probability 1.

KeywordsAnt colony algorithmContinuous space optimisationHierarchical searchSubmartingale

0引言

意大利学者M.Dorigo等人从蚂蚁觅食行为中受到启发，于1991年首次提出了蚁群算法。常见的蚁群算法模型有AS(ant system)模型、ACS(ant colony system)模型、MMAS(max-min ant system)模型等[1]。目前蚁群算法已成功应用于多种优化问题，如车辆路径[2]、资源调配[3]、机器人路径规划[4,5]等。

虽然这种自适应人工智能技术在组合优化中应用较广泛，求解连续空间优化问题的蚁群算法尚缺乏理论基础，它将搜索周期模拟成个体的进化或觅食过程，将个体对环境的适应能力作为目标函数，总体上将个体的觅食过程或优胜劣汰过程抽象成用较好可行解取代较差可行解的迭代过程。目前主要有两种途径：一是将连续空间离散化[6]，从而使连续问题转化为离散问题，但该方法能否适用于高维优化问题还有待研究；二是与其他算法融合[7-9]，引入进化机制或某种算子弥补在连续域的适用缺陷，但收敛速度较慢。尤其应用于连续函数优化的蚁群算法其收敛性问题还需要探讨。因此，如何应用蚁群算法高效率实现连续空间优化问题求解将是一个很有意义的研究课题。

许多学者提出了用于求解连续空间优化问题的蚁群算法。文献[10]提出了一种基于密集非递阶的连续交互式蚁群算法，该算法通过信息素交流和直接通信的融合来指导蚂蚁寻优，却带来了收敛速度慢、评价代价高等缺点；文献[11]提出TCACS并比较了多组测试函数的解精度，但仅仅引入了动态调整禁忌表；文献[12]提出了MTACO(Modified Touring Ant Colony Optimization)算法。以上这些研究取得了一定的成果，但如何提高全局搜索能力，提高收敛速度仍是有待解决的问题。在国内，大多是从仿真角度进行分析，没有对算法的收敛性进行分析。文献[13]将量子计算与蚁群算法相融合，提出一种连续量子蚁群算法。文献[14]提出了一种全新的由侦察蚁和觅食蚁协作搜索的快速连续蚁群算法。本文针对函数优化问题中的信息素分布方法、解的表示进行了研究，提出了一种蚁群分层搜索算法，相比传统算法中的信息素区间分布，本文基于分层结点的分布更合理。给出了算法的收敛性分析，仿真实验说明了本文算法全局搜索能力强，解的精度高且求解速度快。

1基于分层搜索的蚁群算法求解连续空间问题

设计连续空间蚁群算法，需要定义信息素分布函数、状态转移规则以及信息素更新策略。搜索空间本质上的连续性使得分布于路径上的信息素被区间淹没，蚁群分层搜索算法ACHSA(Ant Colony Hierarchical Search Algorithm)是将连续域中的结点分成有等级的层，信息素也是依层结点进行分布，利用蚁群优化框架进行结点搜索。这些蚂蚁在其寄居点周围以分布函数的形式留存信息素，蚂蚁智能体根据这些结点上的信息素强度确定该结点的吸引力，从而选取其最终的转移结点。当蚁群搜索完各层后，根据当前解的函数值更新各层结点上的信息素强度。对于定义域E上的函数优化问题，要求解的精度为小数点后位，设计 层结点。把E上的全体整数作为 层结点，中间层 上结点依次代表解的十分位，百分位，…，各层有10个结点，依次编码为数字0~9。在一个搜索周期中，让蚂群往层数更大的结点上转移，而不能向层数减小的结点转移，随着层数的递增，蚁群的转移步长就会越来越小。这样通过 层后形成的通路就代表一个解，并且开始进入下一个搜索周期，蚂蚁智能体根据各结点周围的信息素强度及路径的启发信息选择下一层结点。

1.1信息素分布函数

(1)

其中：xr表示个体在解空间上的位置，f(xr)是目标函数值，kr是形状尺度系数。本文中Ar留存在某结点周围的信息素强度用定积分式表示：

(2)

此值应该与时间t无关的。

1.2状态转移规则

我们采用确定性计算和随机性选择相结合的策略，蚂蚁Ar(r=1,2,…,m)选择第i层结点j的概率为：

(3)

其中q是区间(0,1)上的随机数，参数q0用来调节蚁群的探索能力(exploration)和挖掘能力(exploitation)的相对强弱，q0越大，蚁群的挖掘能力越强，反之，探索能力越强。

(4)

1.3信息素更新策略

1.3.1局部更新

(5)

τi,j(t)=(1-ρ1)τi,j(t)+ρ1Δτi,j(t)

(6)

1.3.2全局更新

当所有蚂蚁完成一次循环之后，会自适应地调整各结点上的信息素分布，来启发蚁群探索解的改进方向。将路径记录表映射到优化问题的解空间，计算对应点的函数值并选取最优值。所有结点周围残留信息素强度以ρ2倍的速率蒸发掉，只有本次循环中最优路径的信息素得到补偿。

(7)

至此，蚁群返回L0层，根据上一周期中路径上信息素残留按照状态转移规则开始寻找下一层结点，如此循环，直到满足终止准则[16]：

(8)

参数取值ε1=ε2=10-4。

1.4算法描述

2) for i=1:m

3) for j=1:d

4) if j==1 按式(4)起始结点到下层的转移概率;

5) else 按式(4)中间层的转移概率; end

6) if q<=q0

7) if j==1 按式(3)选择下层结点;

8) tau1(idex)=(1-ρ1rho1)*tau1(idex)+ρ1*τ0;

9) else 根据list中上一结点选择下层结点;

10) tau(list,idex)=(1-ρ1rho1)*tau(list,idex)+ρ1*τ0;

11) else按式(4)选择下层结点;进行信息素局部更新;

12) for i=1:m

13) for k=1:d

14) x(i)=x(i)+list(i,k)×10-k;y(i)=f(x(i)); end

15) for k=1:d-1 按式(7)进行全局更新;

16) end [y_best,x_bestidex]=min(y_min);

2算法收敛性分析

本节在转移路径向量列的马氏性基础上证明函数最小值序列是非负下鞅，并从鞅过程的停止定理证明算法以概率1收敛。

引理1最优函数值序列{f(n),n=1,2,…}是非负下鞅。

证明蚂蚁Ar的本次转移与蚁群在前一个搜索周期到达的状态有关，由信息素局部更新规则，第t+1步转移概率由前一步结点周围残留的信息素强度决定，决定了蚁群在n+1个循环中各步转移后的状态，即f(n+1)只与Γ1(n),Γ2(n),…,Γm(n)有关。

(9)

式中Γ1(n),Γ2(n),…,Γm(n)是第n个周期中蚁群的搜索通路，υjk是蚂蚁Ar所在结点位置，为避免信息素不断蒸发，而算法在某几个循环中还未改进解，信息素强度设置一个下限τmin。

定理1最优函数值序列{f(n),n=1,2,…}以概率1收敛。

证明蚁群首次发现最优解时即满足算法终止准则，迭代次数T是最优路径Γ*(1),Γ*(2),…,Γ*(T)的函数，T是关于下鞅{f(n),n=1,2,…}的停时。

对于下鞅序列{f(n)}n≥1，有Ef(n)≤Ef(T)，n

=O(f(T))<+∞

3仿真实验

(10)

ming=5e-0.5xsin(30x)+e0.2xsin(20x)+6x∈[0,8]

(11)

两个算例中相同参数的设置如表1所示，形状系数kr在信息素局部更新中有利于增加解的多样性。主要结果如表2所示，两算例都可达到理论最优值，实验结果优于文献[18]中给出的最优值及鲁棒性，min g=1.3652，R=3.24%。

表1　ACHSA参数设置

表2　测试函数优化结果

本文算法求解式(10)的收敛曲线及找到的最优解位置分别如图1、图2所示，最优解位置用*号标识。算法的全局搜索性能较好，并且在150代以内收敛。求解式(11)的收敛曲线及找到的最优解位置分别如图3、图4所示，最优解位置用*号标识，对比文献[18]中的收敛曲线，本文算法求解精度更高，收敛性能稍好。

图1　测试函数f的ACHSA收敛曲线

图2　ACHSA得到的最优解位置

图3　测试函数g的ACHSA收敛曲线

图4　ACHSA得到的最优解位置

4结语

针对连续域优化问题，本文提出ACHSA，用分层结点模拟连续域中自变量的每位，以结点为对称中心的分布函数来表示信息素，并经过局部更新、全局更新合理地实现了迭代搜索过程，最终找到最优解。最后证明了最优函数值序列是非负下鞅并且算法以概率1收敛，给出了算法参数的取值，仿真对比说明了本文算法的有效性，并且改善了传统蚁群算法的全局搜索性能。

参考文献

[1] Neto T,Fernandes R,Filho G,et al.A software model to prototype ant colony optimization algorithms[J].Expert Systems with Applications,2011,38(1):249-259.

[2] 徐洪丽,钱旭,岳训,等.一种新的基于logistic混沌映像的自适应混沌蚁群优化算法求解动态车辆路径问题[J].计算机应用研究,2012,29(6):2058-2060.

[3] Zhang Na,Feng Zuren,Ke Liangjun.Guidance-solution based ant colony optimization for satellite control resource scheduling problem[J].Applied Intelligence,2011,35(3):436-444.

[4] 赵娟平,高宪文,符秀辉,等.移动机器人路径规划的改进蚁群优化算法[J].控制理论与应用,2011,28(4):457-461.

[5] 柳长安,鄢小虎,刘春阳,等.基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报,2011,39(5):1220-1224.

[6] 胡中华,赵敏,姚敏.引入侦查子群的二进制蚁群算法求解函数优化问题[J].小型微型计算机系统,2010,31(6):1175-1178.

[7] Chang L,Liao C,Lin W B,et al.A Hybrid method based on differential evolution and continuous ant colony optimization and its application on wideband antenna design[J].Progress In Electromagnetics Research,2012,122:105-118.

[8] 李擎,张超,陈鹏,等.一种基于粒子群参数优化的改进蚁群算法[J].控制与决策,2013,28(6):873-878.

[9] Ciornei I,Kyriakides E.Hybrid Ant Colony-Genetic Algorithm (GAAPI) for Global Continuous Optimization[J].IEEE Transactions on Systems,Man and Cybernetics-Part B:Cybernetics,2012,42(1):234-245.

[10] Dero J,Siarry P.Continuous interacting ant colony algorithm based on dense heterarchy[J].Future Generation Computer Systems,2004,5(20):841-856.

[11] Karimi A,Nobahari H,Siarry P.Continuous ant colony system and tabu search algorithms hybridized for global minimization of continuous multi-minima functions[J].Computational Optimization and Applications,2010,45(3):639-661.

[12] Karaboga N,Kalinli A,Karaboga D.Designing digital IIR filters using ant colony optimization algorithm[J].Engineering Application of Artificial Intelligence,2004,17(2):301-309.

[13] 李盼池,李士勇.求解连续空间优化问题的量子蚁群算法[J].控制理论与应用,2008,25(2):237-241.

[14] 马卫,朱庆保.求解函数优化问题的快速连续蚁群算法[J].电子学报,2008,36(11):2120-2124.

[15] 汪镭,吴启迪.蚁群算法在连续空间寻优问题求解中的应用[J].控制与决策,2003,18(1):45-48.

[16] Socha K,Dorigo M.Ant colony optimization for continuous domains[J].European Journal of Operational Research,2008,185(3):1155-1173.

[17] Liu Kai,You Xiaoming,Liu Sheng.The martingale process of ant colony optimization algorithms and its convergence analysis[J].ICIC Express Letters,Part B:Applications,2014,5(4):1105-1110.

[18] 段海滨,马冠军,王道波,等.一种求解连续空间优化问题的改进蚁群算法[J].系统仿真学报,2007,19(5):974-977.

中图分类号TP18

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.02.049

收稿日期：2014-06-21。国家自然科学基金项目(61075115)；上海市教委科研创新重点项目(12ZZ185)；上海市学科专业建设项目(XK CZ1212)。刘锴，硕士生，主研领域：嵌入式系统与智能信息处理。游晓明，教授。刘升，教授。