一种多粒度模式蚁群算法及其在路径规划中的应用-有色金属在线

敛速度慢以及易陷入局部极值的特点，提出一种多粒度模式蚁群算法，对每个蚂蚁设置不同的窗口宽度，增加蚂蚁搜索的灵活性和多样性，给出一种寻找蚁群高阶模式的方法，提高算法进化效率。提出蚁群规模的自适应变化方法，对所提算法在不同约束条件下进行收敛性分析，给出算法收敛时间的估计方法和首达时间分布的表达形式。对提出的算法利用几个典型的TSP问题与基本蚁群算法和几种改进蚁群算法进行对比分析。将提出的多粒度模式蚁群算法应用于无人机(UAV)路径规划中。研究结果表明：所提出的算法均优于基本蚁群算法，并且大部分问题均比其他几种改进蚁群算法的优。所提出的算法提高了路径规划的效率，并可以有效地规避动态威胁。

关键词：

多粒度；模式；蚁群算法；收敛性；路径规划；

中图分类号：E955 文献标志码：A 文章编号：1672-7207(2013)09-3713-10

Multi-granularity pattern ant colony optimization algorithm and its application in path planning

LIU Zhen^{1, 2}, HU Yunan³

(1. Department of Graduate Students’ Brigade, Naval Aeronautical and Astronautical University, Yantai 264001, China;

2. Training Brigade of Equipment Acceptance and Modification, Naval Aeronautical and Astronautical University, Yantai 264001, China;

3. Department of Control Engineering, Naval Aeronautical and Astronautical University, Yantai 264001, China)

Abstract: Aiming at the problem that ant colony algorithm takes a long time to converge and is easy to converge to local optimum, the multi-granularity pattern ant colony algorithm was proposed. The ants had different window sizes in the proposed algorithm to enhance the diversity of the ants, and a new pattern was also proposed in order to enhance the efficiency. The ant number could also vary according to the evolution condition. The convergence of the proposed algorithm was also analyzed in different conditions, and the convergence time and the first hitting time were given. The proposed algorithm was used for UAV path planning problem. The results show that the proposed algorithm performs better than the basic ant colony optimization (ACO) in the TSP problem and performs better in most of TSP problem compared with the reference article. The proposed algorithm is feasible and can promote the efficiency of path planning, and can also avoid moving threat efficiently.

Key words: multi-granularity; pattern; ant colony algorithm; convergence; path planning

蚁群算法(ant colony optimization，ACO)是一种仿生智能进化算法，Dorigo等^[1]较系统地总结了蚁群算法的思想。经过近20年的研究发展，对蚁群算法的研究可以大致概括分为以下几个方面：

(1) 对算法收敛性的研究。对蚁群算法收敛性分析较早的有Stutzle等^[2-3]。Guitar^[3]提出一种基于图形的蚁群系统的收敛分析方法，Stutzle等^[2]较早提出了最大最小的蚁群系统并对其进行了收敛性分析分析。国内学者中对这一方面研究较早的有黄翰等^[4-5]。黄翰等^[4]研究了基于吸收态Markov过程的数学模型，对蚁群算法的收敛速度进行了分析。Yu等^[5]给出了期望收敛时间的估计方法。

(2) 对蚁群算法的模型、参数和结构的研究。龙文等^[6]利用最小二乘支持向量机获取的参数引导蚂蚁搜索的方向。黄明等^[7]提出了一种动态的窗口蚁群算法，增强算法的全局寻优性，在一定程度上克服了陷入局部极值问题。Wong等^[8]提出一种新的最大最小的信息素阈值方法，以克服原有的缺陷。

(3) 研究蚁群算法与其他方法的混合，提出新型蚁群算法。对这方面的文献主要有蚁群算法与演化算法的结合^[9]、蚁群算法与遗传算法的结合^[10]等。

在不确定的战场环境下对无人机(unmanned aerial vehicles，UAV)进行路径规划，对提高UAV的生存概率具有重要意义。战场中的威胁分为静态威胁以及动态威胁，在更复杂的战场环境中还存在突发威胁，因此，在出现突发威胁下如何有效地进行路径规划，具有重要的现实意义。标准蚁群算法在求解路径规划问题时存在收敛速度慢及容易陷入局部最优解的问题。在基本蚁群算法中，蚂蚁运动的路径总是趋向于信息量最强的路径，信息素都积累在这条局部最优的路径上，使该条路径上的信息素浓度远远大于其他路径上的信息素浓度，导致所有的蚂蚁都集中到这条局部最优的路径上，出现停滞现象。要提高蚁群算法的优化效率，可以从2方面着手：(1) 为提高收敛速度和进化效率，对蚂蚁的窗口进行调整并自适应地更改种群规模；(2) 为了提高全局收敛性能，使其尽快收敛到最优解附近，进行局部精细搜索，利用局部搜索方法，寻找优良模式，跳出局部极值，探索全局最优解。

基于以上的思想，本文作者从蚂蚁窗口的设定方法、局部搜索策略和蚂蚁种群的规模进行改进，提出一种多粒度模式蚁群算法，并对算法进行收敛性分析以及TSP问题的仿真验证分析。将算法应用于UAV路径规划问题。

1 多粒度模式蚁群算法实现过程

1.1 多粒度蚂蚁窗口的实现

在蚁群算法搜索的过程中，为提高搜索效率，并减少搜索的盲目性，通常可将蚂蚁下一步要选择的节点固定在一个窗口范围内。在蚁群算法迭代运行过程中，通过自适应调整的非均匀窗口限制蚂蚁的移动范围，在缩短蚂蚁搜索周期的同时能够及时开辟新的解空间，从而能够赋予蚁群算法良好的跳出局部极小的能力。虽然在种群进化过程中，每一代蚂蚁群体的窗口宽度能够自适应的进行调整，但在某一次迭代过程中，所有蚂蚁仍然使用同一个窗口宽度，因而，窗口宽度只能反映当前最优解的进化情况，并不一定反映整体蚁群解的质量，具有一定的片面性，限制了寻优能力较强的蚂蚁的全局寻优能力。为提高蚂蚁在寻优过程中的灵活性，可以考虑采用多粒度机制，每一只蚂蚁根据当前迭代后的进化情况，拥有自己的窗口宽度，因此，在第t+1次迭代过程中，第i(i=1, 2, …, m)个蚂蚁的窗口范围设置为

(1)

其中：为第t次迭代过程中第i个蚂蚁窗口外的节点数目；为第t次迭代中第i个蚂蚁寻找的最优解值；为截止到第t代第i个蚂蚁所寻找到的最优解值；表示向上取整；和分别表示第t次迭代和第t+1次迭代时的窗口宽度。

1.2 高阶优良模式的获取方法

蚁群算法在进化过程中寻找种群的优良模式，通过优良模式指导进化方向，可以有效地提高进化效率。设模式矩阵为：(i=1, 2, …, n, j=1, 2, …, n)，n为问题规模，表示第t迭代后路径(i, j)出现的频率。在蚁群完成一次迭代后，假定第k只蚂蚁在第t次迭代得到的解为，则模式更新矩阵可以表示为

(2)

其中：i=1, 2, …, n, j=1, 2, …, n；μ为模式更新率；

(3)

何小娟等^[11]提出一种利用PBIL算法寻找整个群体的优良模式，并利用优良模式产生新个体进行进化，但所采用的模式停留在二阶模式的阶段，属于低阶模式的范围，难免会出现一些错误。

对于一个路径寻优问题，假定此时的路径片段满足＜，＜，即模式e_ik和e_jh为优良模式，但当＞时，＞，因此，由优良模式构成的解并不一定是最优模式。

图1 模式示意图

Fig.1 Sketch map of pattern

寻求高阶的优良模式，会显著提高算法的效率和性能。考虑过多维数的模式，会增加算法的复杂性，通过仿真分析，对于低阶TSP问题一般可取三至四阶模式即可，对于高阶TSP问题，可取6~7阶模式。

以下用具体例子说明如何获取高阶的模式，假定模式矩阵如下所示：

令为模式合并概率，当时，e_ij为优良模式，若取得过大则模式连接关系难以满足，退化为在整个种群内搜索；太小则容易导致寻优方向的偏差，易陷入局部极值，一般取。

由模式矩阵可以看出e₂₁及e₃₄为优良模式，此时及为待定优良三阶模式，对于三阶模式，的取值范围为{3,4,5}，计算3条路径{2,1,3}，(2,1,4)及(2,1,5)的长度，将最优路径放入三阶优良模式集合G中。对于待定优良三阶模式也采用同样方法，依次可以计算4阶及其以上的模式。

1.3 种群规模的自适应衰减

种群规模随着进化过程的进行平稳地衰减将会有利于进化速度的加快，但Wu等^[12]给出的方法不便于根据实际的情形及时对种群进行调整，从而不利于进行全局和局部搜索。在前期设置较大的蚂蚁种群可以在全局范围内进行搜索，尽快找到最优解，并在最优解附近进行局部搜索，但是种群规模过大将严重影响算法的执行效率。因此，可以考虑种群自适应地跟随当前寻优情况进行变化，若当前寻优情况较好时，种群自适应的平稳减少，当蚁群陷入局部极值或者停滞时，适当减缓种群降低的速度，有利于更好地寻找到全局最优解。设定新的种群变化如式(4)和式(5)所示，其中T为最大迭代次数，m为初始种群数量。

(1) 当T＜m时，

(4)

其中：和D_t分别为第t-1次和t次迭代时种群的方差。

(2) 当T＞m时，

(5)

通过以上的几项关键技术的改进，所提出的多粒度模式蚁群算法的步骤可以描述如下。

步骤1：初始化信息素，设置蚂蚁规模m、信息素浓度τ和启发式信息η以及信息素浓度和启发式信息的权重和β、挥发系数ρ、最大循环次数T、模式阶数等参数信息。

步骤2：算法开始进行循环迭代，t ← t+1。

步骤3：每只蚂蚁根据式(1)调整窗口宽度，并设置第k只蚂蚁的禁忌表T_A(k)。

步骤4：第k只蚂蚁选择下一结点，选择概率为

步骤5：当蚂蚁行进一步后，进行信息素的局部更新：，，为初始信息素浓度。

步骤6：当蚂蚁完成一次周游后，对全局最优解进行信息素更新：。其中：

其中：L_k为第k只蚂蚁得到的路径长度，Q为常数。

步骤7：采取自适应挥发系数：

其中：；为信息素挥发系数下界。

步骤8：计算蚂蚁种群的进化情况，根据式(4)和(5)调整蚁群规模。

步骤9：更新模式矩阵，根据1.2节所提出的方法寻找高阶优良模式。

步骤10：判断是否满足收敛条件，收敛则结束，输出最优解，否则转步骤2。

本文提出的多粒度模式蚁群算法与基本蚁群算法的区别在于步骤3、步骤8和步骤9，通过多粒度窗口设置，使得每一个蚂蚁拥有自己窗口宽度，从而增加了寻优过程的多样性，有利于跳出局部极值，自适应地调整种群规模，从而能够根据进化情形，加快算法收敛速度，不断寻找优良模式矩阵，可以更高效地在优良解附近进行寻优，提高寻优效率和进化速度。

2 算法的收敛性分析及仿真验证

以下对多粒度模式蚁群算法的收敛性进行分析。根据文献[5]及[13]，可以得知为一个Markov过程。其中：；为当前最优解；为第t次迭代中所寻找到的最优解；T(t)为第t次迭代的信息素浓度。

定义1^[5]：给定吸收态Markov过程和最优状态空间，记，表示在t时刻到达最优状态的概率，若，则称收敛。对于离散空间，

(6)

2.1 收敛速度的估计方法

定理1：给定多粒度模式蚁群算法对应的吸收态Markov过程及最优状态空间，若满足

其中：为其期望收敛时间。则

其中：。

证明：令，则

同理可得：

由文献[5]得知：，又因为，故

同理可得：

，

证毕。

推论1：给定多粒度模式蚁算法对应的吸收态Markov过程及最优状态空间，若满足：

则

其中：；并且a和b均为常数；为其期望收敛时间。

证明：由定理1得知：

因为，等比数列收敛，。同理可得。故，证毕。

推论1实际是定理1的一种简化形式。上述方法利用吸收态马尔科夫的性质对速度进行了估计，以下从另一个角度给出多粒度模式蚁群算法收敛速度估计方法。

引理1^[13]：若，则期望收敛时间。其中：表示某只蚂蚁在第t次迭代中选择的第i个节点恰是最优路径的概率；表示最优路径；m为蚂蚁数目；n为问题规模。

推论2：令，，，，，，，，

和分别是当路径i和j属于最优路径时的信息素浓度及启发式信息，和分别为信息素浓度的最大和最小值，和分别为启发式信息的最大及最小值，则期望收敛时间为

(7)

证明：在1次循环中，某只蚂蚁发现最优解的概率为

其中：n_max为第i个节点所连接路径数目的最大值，同理可以得出，n_min为节点所连接路径数目的最小值。则由引理1得出期望收敛时间为

2.2 收敛性分析

定理2：多粒度模式蚁群算法首达时间满足：

(8)

证明：当算法第i次迭代首次到达最优解后，则t-1之前都未进入最优解，故

又因为：

分别对这2部分进行推导如下：

从而定理2得证，证毕。

定理3：给定多粒度模式蚁算法对应的吸收态Markov过程及最优状态空间，若

且，则，算法以概率1收敛。

证明：令，则可得到：

因为为吸收态Markov过程，从而得到：

故可以得到：

，算法收敛，证毕。

定理3说明当的转移概率满足约束条件时，算法将会以概率1收敛。h(t)表示当t-1时刻未到达全局最优解时t时刻仍未到达全局最优解的概率，令，表示算法在t-1时刻未到达全局最优解时t时刻到达全局最优解的概率，则，0＜g(t)≤1，0≤h(t)＜1。对于一个吸收态Markov过程来说，，否则，算法将无法达到全局最优解。同理，。因此，g(t)越大，越容易使收敛到最优解；同理，h(t)越小，则使得进化算法保持在非最优解的概率越低，即寻找到最优解的概率越大。

2.3 TSP仿真验证分析

为了验证算法，选用典型的TSP问题进行仿真分析，分别采用Gr24，Oliver30，Att48，Eil51，Berlin52和St70进行仿真分析，设定，，，，，种群规模和城市数目相同，模式阶数为3，初始时设定每个蚂蚁的窗口宽度为4，算法独立运行10次，统计结果如表1所示。

表1 TSP问题仿真结果对比

Table 1 Comparison of simulation results for TSP problems

从表1可以看出：本文算法在解的质量和稳定性都优于ACO算法，利用本文算法在Gr24和Att48这2个问题都能寻找到当前理论最优解，在其他几个问题上的偏差也都控制在1%以内，显示出本文算法的优越性。

为了进一步进行对比分析，以Oliver30和Eil51为例进行分析比较，给出这2个问题寻找到的最优路径以及收敛迭代结果，分别如图2和图3所示。

图2所示为Oliver30问题上本文算法与基本蚁群算法的对比结果，本文算法收敛效果优于基本的蚁群算法，主要是因为本文算法使得每个蚂蚁拥有自己的窗口宽度，增加了寻优的多样性，同时寻找进化过程中的高阶优良模式，提高了进化的效率。

图2 Oliver30问题仿真对比结果

Fig.2 Experimental results for Oliver30

图3 Eil51问题仿真对比结果

Fig.3 Experimental results for Eil51

图3(a)所示为本文算法在EIl51问题上得到的最优结果，图3(b)所示为本文算法与ACO寻优迭代比较结果，从对比结果可以看出：本文算法收敛效果较好，寻优结果明显优于基本蚁群算法。

为了充分进行比较以验证本文算法的正确性，将本文算法与其他相关算法进行仿真对比分析，以Oliver30和Eil51这2个问题为例进行对比分析，结果见表2和表3。

表2 Oliver30问题对比表

Table 2 Comparison results for Oliver30

表3 Eil51问题对比表

Table 3 Comparison results for Eil51

从表2和表3可以看出：在Oliver30问题上，文献[14]中的方法所寻找到的最优值略优于本文提出的方法最优值，但算法稳定性劣于本文算法。在Eil51问题上，本文算法相比几种其他文献方法具有优越性，能得到更优的路径。

3 多粒度模式蚁群算法在路径规划中的应用

3.1 新的评价函数

首先给出一种新的UAV路径规划的评价函数，整个航迹代价函数由威胁代价C_T和航迹代价C_L组成，威胁代价C_T为

(9)

其中：

(10)

h_k为第k个威胁的威胁等级；为第k个威胁的最大作用范围；为第k个威胁的高危作用范围，N_T为威胁数目。

第i架UAV在某2个航迹片段间的航迹代价为(其中，为该段路径的长度)，则UAV在2个航迹段的评价函数可以表示为

(11)

其中：k₁和k₂分别为其重要程度影响因子，表征各个参数在评价函数中的重要性。所以，第i架UAV的评价函数为

(12)

其中：n_i表示第i架UAV的路径片段数目。

假定共有N架UAV进行协同航迹规划，多机协同后综合代价函数为

(13)

3.2 路径规划仿真分析

对UAV及战场环境等仿真参数进行如下设定：

(1) UAV初始位置为(0, 0) km，终点位置为(60, 60) km；

(2) 共有6个威胁体，威胁源的圆心分别为(43, 20)，(30, 10)，(10, 30)，(25, 48)，(20, 18)和(40, 30)，威胁半径分别为2，2，3，4，4和3，高危作用范围均设为1，威胁等级设定为与威胁半径相同。

3.2.1 单机路径规划仿真分析

利用多粒度模式蚁群算法进行单机路径规划，仿真结果如图4(a)所示。为了验证算法的鲁棒性，对威胁等级进行改变，以验证算法的正确性。当威胁体3和6的威胁等级增大到20时，规划结果分别如图4(b)和4(c)所示，可见UAV都能有效地规避威胁，规划出满意的路径。

以上是在静态环境下利用多粒度模式蚁群算法的仿真结果，在动态环境下，当出现突发威胁时，突发威胁的初始位置为(0, 40)，飞行方向沿X轴，威胁等级为4。在突发动态威胁后的路径规划结果如图5(a)所示。

图4 静态环境下的仿真结果

Fig.4 Path planning results in static environment

由图5(a)可以看出：本文算法可以有效地规避移动威胁。采用本文提出的算法与基本ACO以及Duan等^[18]提出的ACO-DE评价函数的比较结果如图5(b)所示。从图5(b)可以看出：利用本文算法和ACO-DE所得出的评价结果均优于基本ACO，显示出2种改进算法都具有较好的优越性；本文算法的评价效果优于ACO-DE，显示出本文算法在单机情形下的收敛效果优于ACO-DE。

图5 突发移动威胁下路径规划

Fig.5 Experimental results of path planning with pop-up threat

3.2.2 多机协同下的路径规划分析

在多机协同下，假定突发移动威胁在(60, 0)，威胁等级为2，3架UAV位置分别为(0, 20)，(0, 10)和(0, 5)，多机协同路径规划结果如图6(a)所示，改进前后的效能对比如图6(b)所示。

从图6(a)可以看出：利用本文提出的算法在多机协同情形并出现突发动态威胁，能够规划出有效的路径。从图6(b)可以看出：利用本文算法所得总的评价函数与利用基本ACO以及ACO-DE所规划出的航迹代价函数都有所下降，从而表明本文算法规划出的路径优于基本蚁群算法，充分验证了本文算法的有效性。

从图6(b)还可以看出：在开始迭代时，ACO-DE收敛效果优于本文提出的多粒度模式蚁群算法。这主要是因为在复杂的多机协同情形下，本文算法采用了多粒度的窗口，并且在寻优过程中寻找路径的高阶模式，从而增加了算法的复杂性，因而开始阶段的收敛结果并不理想。但在寻优迭代过程中，本文算法的优势得到充分体现，并且最终得到的收敛效果也优于ACO-DE。

图6 突发威胁下多机协同路径规划

Fig.6 Experimental results of cooperative path planning with pop-up threat

4 结论

(1) 根据寻优情况，不同的蚂蚁赋予不同的窗口宽度，增加了算法的寻优性能，使得优良蚂蚁可以较快地找到最优解，加快了算法的收敛性能。

(2) 提出了一种寻找高阶模式的方法，从而提高了算法的搜索性能，避免了低阶模式所导致的搜索方向偏差。

(3) 对算法的收敛性进行了理论分析，给出了其收敛时间的估计方法和首达时间的分布形式。以TSP问题进行了仿真分析，并与相关文献对比分析，证明了算法的优越性。

(4) 将提出的算法应用于UAV的路径规划中，经仿真结果证明该算法是一种进行路径规划的有效方法，能有效地规避移动威胁。

参考文献：

[1] Dorigo M, Gambardella L M. Ant colony system: A cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66.

[2] Stutzle T, Dorigo M. A short convergence proof for a class of ant colony optimization algorithms[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(4): 358-365.

[3] Guitar W J. A graph-based ant system and its convergence[J]. Future Generation Computing Systems, 2000, 16(9): 873-888.

[4] 黄翰, 郝志峰, 吴春国, 等. 蚁群算法的收敛速度分析[J]. 计算机学报, 2007, 30(8): 1345-1353.

HUANG Han, HAO Zhifeng, WU Chunguo, et al. The convergence speed of ant colony optimization[J]. Chinese Journal of Computers, 2007, 30(8): 1345-1353.

[5] YU Yang, ZHOU Zhi-hua. A new approach to estimating the expected first hitting time of evolutionary algorithms[J]. Artificial Intelligence, 2008, 172(15): 1809-1832.

[6] 龙文, 梁昔明, 龙祖强, 等. 基于改进蚁群算法优化参数的LSSVM短期负荷预测[J]. 中南大学学报: 自然科学版, 2011, 42(2): 3408-3414.

LONG Wen, LIANG Ximing, LONG Zuqiang, et al. Parameters selection for LSSVM based on modified ant colony optimization in short-term load forecasting[J]. Journal of Central South University: Science and Technology, 2011, 42(2): 3408-3414.

[7] 黄明, 刘鹏飞, 梁旭. 面向作业车间的自适应非均匀窗口蚁群算法[J]. 计算机集成制造系统, 2009, 15(10): 1973-1978.

HUANG Ming, LIU Pengfei, LIANG Xu. Ant colony algorithm oriented to Job Shop scheduling problem based on self-adaptive and uneven windows[J]. Computer Integrated Manufacturing Systems, 2009, 15(10): 1973-1978.

[8] Wong K Y, See P C. A new minimum pheromone threshold strategy (MPTS) for max–min ant system[J]. Applied Soft Computing, 2009, 9(8): 882-888.

[9] 李康顺, 徐福梅, 张文生, 等. 一种基于启发式演化算法的最优—最差蚂蚁系统[J]. 中南大学学报: 自然科学版, 2010, 41(2): 609-614.

LI Kangshun, XU Fumei, ZHANG Wensheng, et al. An improved best-worst ant system based on heuristic evolutionary algorithm[J]. Journal of Central South University: Science and Technology, 2010, 41(2): 609-614.

[10] 雷友诚, 涂祖耀, 桂卫华, 等. 基于遗传蚁群算法的树枝型铁路取送车问题优化[J]. 中南大学学报: 自然科学版, 2011, 42(8): 2356-2362.

LEI Youcheng, TU Zuyao, GUI Weihua, et al. Optimization of genetic and ant colony algorithm[J]. Journal of Central South University: Science and Technology, 2011, 42(8): 2356-2362.

[11] 何小娟, 曾建潮. 基于优良模式连接的分布估计算法求解TSP问题[J]. 模式识别与人工智能, 2011, 24(2): 185-193.

HE Xiaojuan, ZENG Jianchao. Solving TSP problems with estimation of distribution algorithm based on superiority pattern junction[J]. PR & AI, 2011, 24(2): 185-193.

[12] Wu Z L, Zhao N, Ren G H, et al. Population declining ant colony optimization algorithm and its applications[J]. Expert Systems With Applications, 2009, 36(3): 6276–6281.

[13] HUANG Han, WU Chun-guo. A pheromone-rate-based analysis on the convergence time of ACO algorithm[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2009, 39(4): 910-923.

[14] 夏鸿斌, 须文波, 刘渊. 自适应并行机制的改进蚁群算法[J]. 系统工程与电子技术, 2009, 31(12): 2973-2976.

XIA Hongbin, XU Wenbo, LIU Yuan. Ant colony algorithm with adaptive parallel mechanism[J]. Systems Engineering and Electronic, 2009, 31(12): 2973-2976.

[15] 何小娟, 曾建潮, 王丽芳. 一种基于信息传递的分布估计算法[J]. 电子学报, 2011, 39(4): 968-970.

HE Xiaojuan, ZENG Jianchao, WANG Lifang. An estimation of distribution algorithm based on information transmission[J]. Acta Electronica Sinica, 2011, 39(4): 968-970.

[16] 郑松, 侯迪波, 周泽魁. 动态调整选择策略的改进蚁群算法[J]. 控制与决策, 2008, 23(2): 225-228.

ZHENG Song, HOU Dibo, ZHOU Zekui. Ant colony algorithm with dynamic transition probability[J]. Control and Decision, 2008, 23(2): 225-228.

[17] 夏辉, 王华, 陈熙. 一种基于微粒群思想的蚁群参数自适应优化算法[J]. 山东大学学报: 工学版, 2010, 40(3): 26-30.

XIA Hui, WANG Hua, CHEN Xi. A kind of ant colony parameter adaptive optimization algorithm based on particle swarm optimization thought[J]. Journal of Shandong, University: Engineering Science, 2010, 40(3): 26-30.

[18] DUAN Haibin, YU Yaxiang, ZHANG Xiangyin, et al. Three- dimension path planning for UCAV using hybrid meta-heuristic ACO-DE algorithm[J]. Simulation Modelling Practice and Theory, 2010, 18(3): 1104-1115.

(编辑何运斌)

收稿日期：2012-08-19；修回日期：2012-10-11

基金项目：国家自然科学基金资助项目(61174031)

通信作者：刘振(1983-)，男，山东临沂人，博士研究生，从事智能控制理论及应用等研究；电话：13723988582；E-mail: hylz1008@126.com

摘要：针对蚁群算法收敛速度慢以及易陷入局部极值的特点，提出一种多粒度模式蚁群算法，对每个蚂蚁设置不同的窗口宽度，增加蚂蚁搜索的灵活性和多样性，给出一种寻找蚁群高阶模式的方法，提高算法进化效率。提出蚁群规模的自适应变化方法，对所提算法在不同约束条件下进行收敛性分析，给出算法收敛时间的估计方法和首达时间分布的表达形式。对提出的算法利用几个典型的TSP问题与基本蚁群算法和几种改进蚁群算法进行对比分析。将提出的多粒度模式蚁群算法应用于无人机(UAV)路径规划中。研究结果表明：所提出的算法均优于基本蚁群算法，并且大部分问题均比其他几种改进蚁群算法的优。所提出的算法提高了路径规划的效率，并可以有效地规避动态威胁。