蚁群算法的路径规划改进策略

施建礼，刘志浩，潘 爽

（海军潜艇学院，山东 青岛 266199）

0 引言

路径规划问题在军事作战平台的任务及攻击筹划中具有重要的影响作用。对于飞机、水面舰艇及潜艇等传统意义上的载运工具，乃至具有路径规划功能的导弹鱼雷等兵器而言，性能优良的路径，能够充分利用战场态势，通过规避探测，增大己方的防御能力，同时以增大搜索概率的方式强化己方攻击能力，进而增加整体的作战效能。由于战场态势瞬息万变，导致作战过程对时间极为敏感，进而使得作战平台路径规划算法的快速性成为衡量其性能优异的重要标准。目前路径规划问题常采用的方法主要有图论法、概率路线图法、A*算法、蚁群算法、粒子群算法、模拟退火法等。蚁群算法的基本思想是由意大利Dorigo 在1991 年提出的一种智能算法，该方法通过模拟蚁群的社会行为完成对最优解的动态筛选。在旅行商问题（TSP）和二次资源分析（QAP）问题等经典的优化问题求解中，蚁群算法均取得了较好的结果。随时代进步，在近年的互联网通信、网络优化、物流调度等多种应用领域中，蚁群算法都体现了其在求解复杂问题时的可行性和优越性。在军事领域中，蚁群算法也在机器人、无人机、飞机、水面舰艇、潜艇、鱼雷和导弹等多种军事平台及兵器的路径规划中取得了很大的成就。但在大规模的军事作战空间分析中，受限于自身固有的初始信息匮乏及早熟性等特点，使得蚁群算法在面对数据量大的任务空间时存在一定的缺陷［1］。

本文以潜艇路径规划为例，基于蚁群算法，引入遗传算法的变异策略，克服蚁群算法早熟及遗传算法局部最优的特点，提高搜索效率，对改进的蚁群算法在路径规划中的应用进行了仿真研究。

1 路径规划问题的描述

军事应用中路径规划的目的是使被规划目标能够安全可靠及时地抵达目的地，并根据任务空间的不同属性，在行进机动过程中选择性地执行作战任务。根据航行器功能和作战地理环境的不同，路径规划可分为二维空间路径规划和三维空间路径规划。本文以潜艇航渡目标海区为例进行分析，着重研究二维空间内的路径优化问题。

假设潜艇的航渡任务如图1 所示，任务海区为S，潜艇由A 点出发机动到B 点执行某项作战任务，AB 两点之间存在若干不同类型的碍航区域及敌方设定的防御威胁区域，则该种约束下，路径规划的主要任务就是根据某种优化需求，为潜艇选择一条满足优化指标的可行路径。

一般而言，潜艇的路径规划问题需要考虑多种平台动力性能指标，如航速、回旋半径、航程限制、导航性能、通信能力等，同时也需要考虑海区水文环境、敌方威胁兵力配置、己方战术需求等多种环境及战术指标需求或约束。但在实际的作战过程中，根据特定的战术需求及战场态势，路径规划通常采用的指标为航路安全指标和航行时间指标，其中，前者表示目标需要以一定的安全隐蔽性抵达指定区域，后者表示目标需在限定的时间内抵达指定区域［2］。

图2 栅格化后的任务空间

栅格化后路径规划问题就可简化为在MN下的搜索满足相应指标的最优路径，可用式（1）表示为：

其中，E 为最优路径，f 为代价评估函数，Ek为所有的可由初始点行动至终止点的栅格序列。

2 改进蚁群算法模型描述

本文为在不失作战使用背景的前提下简化问题，在模型构建中采取如下的假定：

1）潜艇导航定位准确，忽略导航定位问题引起的误差；

2）在单位步长内，潜艇机动变向不受约束，即潜艇可确保完成任意角度变向；

3）任务海区内碍航物及敌方防御威胁兵力配置固定，位置不随时间发生变化；

4）潜艇电量充沛，能量对航程不存在限制；

5）忽略海况对潜艇航行影响，即潜艇航行过程中受洋流等因素造成的航速变化及航向航迹偏移忽略不计。

2.1 任务空间栅格模型

为简化说明，假设潜艇路径规划的任务海区为长为X，宽为Y 的矩形区域，则任务空间划分为m×n 的栅格后，每个栅格MN表示的区域长度为X/n，宽度为Y/m。对所有栅格MN按列由上至下，由左至右顺序编号后，则编号为N 栅格至多与8 个栅格接触，如图3 所示。其中，编号为N 的栅格在任务空间中对应第xN行，第yN列的栅格MN，其中

图3 栅格编号位置分布

显然由图3 可得，以栅格MN为当前栅格，则下一可达栅格MN'必须满足条件

2.2 路径搜索算法模型

在栅格化后的任务空间中，假设初始点A 为蚁穴，路径终点B 为食物源，则路径规划问题可类比为蚁群在任务空间中寻找食物源的过程［3］。经过大量蚂蚁群体反复搜寻，通过信息素的反馈作用，最终选择一条最优路径。根据蚁群算法一般流程，结合潜艇路径优化问题的分析，对算法中涉及的相关变量定义如下：

2.3 路径选择模型

2.3.1 路径转移模型

每个栅格的选择概率由启发信息和信息浓度确定。由于路径规划问题总是企图使规划目标安全地向终点移动，因此，启发信息可由当前栅格与终点相对关系及安全性确定，本文中采取相对距离与栅格区域的威胁程度作为启发因子ηN'

2.3.2 路径回退模型

2.3.3 信息浓度更新模型

Therapeutic drug(Yupingfeng granules,Z10930036)and placebo(placebo granules)were manufactured by Guangdong HuanQiu Pharmaceutical Company(Guangdong,China).

2.3.4 路径代价模型

其中，Pf为在路径L 中的暴露概率，当作战任务对安全隐蔽性需求较大时，增大μ 以调节路径代价指标，反之当作战任务对时间敏感性较强时则需调低μ 取值。路径L 的暴露概率表示为

2.4 基于遗传算法的改进策略

虽然在路径转移模型及信息浓度更新模型中均有涉及避免系统早熟及收敛过快的因素，但是由于蚁群算法在概率转移及信息浓度反馈中存在的固有特点，仍有可能使得系统信息浓度过快累积，影响全局搜索能力。一种解决方案是增大并行展开的搜索数量，但这将较大增大系统的计算量，降低搜索效率，这在时间敏感性较强的军事作战系统中存在较大应用限制［4］。

遗传算法是模拟生物进化过程的一种智能算法。该算法引入变异遗传的概念，合适的变异及遗传方式将使得系统能够有效地避免早熟及收敛过快。但遗传算法却有着局部收敛性的弊端，为解决局部收敛性的问题，需要适当增加变异概率及遗传代数，而这也将不可避免地增加了系统的计算量［5-6］。

结合遗传算法与蚁群算法二者在搜索算法方面不同的优势及特点，执行以下的改进策略。

2.4.1 转移算法改进策略

在2.3.1 节中，路径转移模型主要通过概率方式进行栅格选择，一旦信息浓度 N 积累过高，搜索过程将会极有可能极大概率继续指向该栅格，进而导致累积。以遗传算法的变异性为基础，设计改进策略如下：

一旦栅格信息浓度超过一定阈值TH，则产生一个随机数h，当h 超过预置的参数h0时，栅格转移过程将不以信息浓度概率为准则，而将在可达栅格集Aj中随机选择一个栅格，该策略可表示为

其中，“&”表示“逻辑与”，“|”表示“逻辑或”。

2.4.2 交叉路径改进策略

2.5 算法流程

2）初始化路径规划初始点与终止点信息；

3）根据路径转移模型及回退模型开始选择栅格，进行路径转移；

4）判断是否抵达终止点栅格，若是，执行5），否则执行3）；

5）根据途径栅格，进行交叉路径处理，求解代价函数，更新信息浓度，更新最优路径；

6）判断是否完成最大迭代次数，若达到，输出最优路径及相关指标信息，反之退至2）。

流程图表示如下页图4 所示。

3 仿真结果分析

3.1 仿真设定及参数取值

如图5 所示，经栅格化处理后，水面舰由A 点出发机动至B 点，任务空间内有岛屿、浅滩、暗礁等碍航物，存在3 组防御兵力，防御栅格范围内兵力防御能力相等，威胁概率P=0.3。

图4 算法流程图

图5 仿真任务空间

结合文献研究，本文仿真参数选取如下：

表1 仿真参数取值表

3.2 仿真结果分析

在表1 参数取值设定的条件下，经过仿真迭代15 000 次，最终得到最优路径如图5 所示，其中，实线表示路径品质取决于时间的最优路径，即μ=0时；虚线表示路径品质主要取决于安全隐蔽性时的最优路径，即μ=0.99 时。变异策略的采取和不采取，均取得相同路径，这表明两种算法的有效性。从图6可以看出，当μ=0 时，路径忽略防御威胁，选取了最短距离的路径；当μ=0.99 时，路径主要注重避免行经的威胁防御栅格，选取了安全隐蔽意义上的最优路径，需要说明的是μ 取值不为1 的原因是在以安全隐蔽性为代价指标的路径方案中，存在多组代价相同的最优路径，通过μ 取值为0.99 的方法，使得式（10）中路径距离代价占有极小的权重，以保证在安全隐蔽性最优条件下的路径距离最优。两条路径从直观上符合战场态势判断，验证了算法的有效性和可行性。

图6 最优路径图

图7 迭代速率对比图

表2 最优解更新迭代数

表2 和图7 是在μ=0.99 时，算法优化性能关系对比。由表2 可知，在设定条件下，经过变异策略改进的算法，得到最终航路所需迭代次数远低于未经改进的路径求解算法。图7 表示的是在迭代代数基本相同条件下，采取变异策略的算法与未采取变异策略的算法的路径代价取值，可以看出，在迭代代数差异不大的情况下，采取了变异策略的算法后，收敛速度有较大提高，通过交叉机制和路径转移的变异机制，能有效降低算法搜索停滞和早熟现象。

4 结论

蚁群算法是基于自然界蚁群社会现象的一种智能搜索优化方法，其信息反馈及并行能力使得该方法有极强的应用潜力［7］。本文结合潜艇路径优化问题的作战特点和战术需求，提出了基于遗传变异的改进策略和改进方法。仿真结果表明，改进后的蚁群算法，优化的收敛速度和收敛性有了一定改善，在两种不同代价指标的模型下，算法也取得了直观上战术效果较好的路径。由于本文模型中假定敌方防御兵力是静止不动的，这与实际作战中的固定防御兵力是等效吻合的，对于移动防御兵力威胁下的路径优化问题，可将算法扩展至由二维空间加上时间所构成的三维时空中进行求解。