0 引言

蚁群优化算法(ant colony optimization, ACO)是由意大利学者Dorigo等提出的一种模拟蚂蚁觅食行为的仿生智能算法^[1]. 蚂蚁在觅食过程中借助信息素进行信息的交流和传递, 自主选择下一步移动方向, 帮助种群寻找最佳觅食路径, 具有正反馈特点^[2]. 蚁群算法以信息素更新和概率转移为基本操作, 与其他群智能优化算法(如粒子群算法、遗传算法、模拟退火算法、差分进化算法等)相比, 蚁群算法具有正反馈并行机制、算法鲁棒性强和易与其他算法结合等优点, 适合求解各种组合优化问题^[3]. 目前已在多个领域获得了广泛应用, 如旅行商(TSP)问题^[4]、路由优化问题^[5]、机器人路径规划^[6]、车辆规划^[7]、流程调度^[8]、布局优化^[9]领域等.

蚁群算法本质上是具有正反馈特性的启发式算法, 在处理复杂问题时, 算法通过正反馈的方式积累高质量路径的信息素浓度, 往往可以得到较优解, 然而如果当前较优解不是全局最优解, 则算法会不可避免地陷入局部极值^[10], 因此正反馈特性保证了蚁群算法的稳定性和较好的搜索能力, 但也导致了算法容易陷入局部极值. 针对这一缺点, 国内外研究者进行了诸多研究. 文献[11]对蚁群算法进行权重参数改进, 提出了一种基于信息素浓度和最优解的动态加权信息素更新机制; 文献[12]引入启发信息递减系数, 提出了初始信息素不均衡分配原则, 动态调整蚁群算法的信息素累积速率, 一定程度上降低了陷入局部极值的可能性; 文献[13]根据所提出的信息素初始化策略, 在算法陷入局部最优时重新初始化各路径的信息素浓度, 以跳出当前极值; 文献[14]利用问题对象的空间信息, 采用$ k $-均值聚类的方法对问题进行分解, 定义了多类蚂蚁寻找最优路径. 上述文献都对算法进行了相关改进, 一定程度上避免了算法陷入局部极值的缺点, 但大多是引入动态参数调整机制或者信息素初始化机制, 仍属单一正反馈搜索策略下进行的改进, 依然存在陷入局部极值不易跳出的缺点. 对此本文参考群智能劳动分工策略, 在传统蚁群算法基础上引入蚁群刺激-响应分工机制, 在正反馈搜索的基础上补充负反馈分工加以平衡.

劳动分工作为群体智能方法的重要组成部分^[15], 是社会性昆虫族群中的一种普遍现象, 表现为不同的个体执行不同的任务, 在劳动分工作用下, 个体执行的任务会随着环境动态调整, 使群体表现出环境适应性. 文献[16]给出了蚁群等社会性昆虫的劳动分工行为描述, 目前已证实的劳动分工机制主要有刺激-响应机制和激发-抑制机制两种^[17], 其中刺激-响应机制是一种用于描述蚁群系统劳动分工行为的内在机制; 文献[18]详细分析了刺激-响应分工机制的作用原理, 并给出了具有负反馈特性的数学表达模型. 近年来, 随着群体智能的发展, 群智能劳动分工策略也涌现出一系列成果, 被广泛应用于各类分配问题, 如群体利益分配^[19]、空间分配^[20]、时间分配^[21]、任务分配^[22]等.

此外, 在传统的蚁群算法中, 算法初期收敛速度较慢, 计算时间较长. 根据这一缺点, 目前已有的解决方式主要分为两种: 一是改进信息素更新规则^[23-24], 二是改进或增加算法的启发式信息^[25-26]. 以上方法均可有效地提高算法的收敛速度, 但相比较而言, 引入启发式信息可能会造成算法规模和复杂程度增加, 故本文采用改进信息素更新机制的方法, 根据引入的刺激-响应分工机制, 依据精英策略, 设计一种基于刺激-响应分工模型的信息素更新机制, 以进一步加快算法收敛速度.

基于以上内容, 本文提出基于混合反馈机制的扩展蚁群算法(extended ant colony optimization based on mixed feedback mechanism, MF-ACO), 为验证算法性能, 将算法应用于TSP和机器人路径规划问题的求解中. 使用TSPLIB中多个实例作为测试对象, 与基本蚁群算法(ACO)、最大最小蚂蚁系统(MMAS)、蚁群系统(ACS)^[27]3种经典算法以及近年来改进算法^{[14, 28-30]}进行对比, 并将复杂地图下的机器人路径规划问题作为实际案例进行求解并与其他算法比较.

1 基本蚁群算法

蚁群算法具有较强的鲁棒性和自组织特性, 遵循正反馈机制.一方面蚂蚁在构造路径时倾向于选择信息素浓度大的转移节点; 另一方面通过信息素更新策略, 使得蚂蚁在当前的最优路径上释放信息素.算法分为概率转移和信息素更新两部分.

1.1 概率转移

在t时刻下, 蚂蚁k在第i节点选择下一个节点j时的概率$ P_{ij}(k) $的大小, 是由信息素$ {\tau}_{ij}(t) $和启发式信息$ {\eta}_{ij}(t) $按照下式确定的:

$ \begin{align} P_{ij}(k)=\begin{cases} \dfrac{[{\tau}_{ij}(t)]^\alpha[\eta_{ij}(t)]^\beta}{ \sum\limits_{s \in A_{k}} [{\tau}_{is}(t)]^\alpha[\eta_{is}(t)]^\beta}, j \in A_{k};\\ 0, {\rm otherwise}. \end{cases} \end{align} $

(1)

其中: $ A_{k}(k = 1, 2, \ldots, m) $为蚂蚁k当前可选择的节点集合; $ \alpha $为信息素启发因子; $ \beta $为期望启发式因子; $ \eta_{ij}(t) $设定为$ (i, j) $两节点间距离$ d_{ij} $的倒数, 即

$ \begin{align} {\eta_{ij}(t)} = 1/{d_{ij}}. \end{align} $

(2)

1.2 信息素更新

蚂蚁经过的路径留下信息素, 同时信息素会随时间挥发, 因此需要对信息素进行更新. ACO算法在所有蚂蚁完成一次迭代后, 对信息素$ \tau $进行更新:

$ \begin{align} &{{\tau}_{ij}(t+1)} = (1-\rho){{\tau}_{ij}(t)}+\rho\Delta{{\tau}_{ij}(t)}. \end{align} $

(3)

$ \begin{align} &\Delta{{\tau}_{ij}(t)} =\begin{cases} \dfrac{Q}{L_{k}} , \text{蚂蚁}k\text{当前路径};\\ 0, {\rm otherwise}. \end{cases} \end{align} $

(4)

其中: $ \rho $为信息素挥发系数, $ \Delta{{\tau}_{ij}(t)} $为蚂蚁k在t时刻后路径$ (i, j) $上的信息素增量, Q为信息素强度系数.

2 刺激-响应分工机制

群智能劳动分工是一类自下而上的任务分配方法, 特点是无需全局信息和中心控制, 而且能够适应动态变化的环境. 本文引入的劳动分工机制为蚁群的刺激-响应机制.

2.1 分工机制

蚁群中个体对多个任务的选择分配是按照感知到的任务紧迫性程度划分的, 每个任务都有一个环境刺激与其对应, 刺激强度与任务的紧急程度成正比; 同时蚂蚁个体对应每个任务也存在响应阈值, 当一个任务的刺激强度超过了某个蚂蚁对应该任务的响应阈值时, 蚂蚁会以较大概率执行这项工作^[31].

假设蚁群中某个蚂蚁有多个任务可以选择, 令: $ S_{i} $表示任务i的环境刺激量, 描述执行该任务的外部驱动; $ \theta_{i} $表示个体对任务i的响应阈值, 反映个体执行任务的内部倾向, 此时个体执行任务i的概率$ \varGamma_{i} $可表示为^[18]

$ \begin{align} \varGamma_{i} = \dfrac{{{S_{i}^2}}}{{{S_{i}^2} + {\theta_{i}^2}}}. \end{align} $

(5)

2.2 特性分析

由以上模型可知, 执行任务i的概率与刺激$ S_{i} $和阈值$ \theta_{i} $的大小有关, 当$ S_{i}\gg\theta_{i} $时, 执行该任务的概率较高.此外在任务选择过程中, 任务刺激$ S_{i} $和个体阈值$ \theta_{i} $会随着族群需求和个体表现发生变化, 使得个体可以灵活地执行任务. 例如$ S_{i} $的变化取决于任务的执行情况, 个体执行某任务, 导致该任务的需求程度下降, 刺激强度会随之降低, 而刺激强度降低又使得个体执行任务的概率下降; 反之, 若未执行该任务, 该任务需求未被满足, 刺激强度随之升高, 则增加任务的执行概率, 显然以上变化呈现负反馈特性.

3 基于混合反馈机制的扩展蚁群算法设计

将刺激-响应分工机制与蚁群算法结合, 利用负反馈分工特性对蚁群算法的单一正反馈搜索方式进行平衡, 提出具有混合反馈机制的扩展蚁群算法.

3.1 扩展蚂蚁

在传统蚁群算法中, 所有蚂蚁个体遵循相同的搜索规则, 构造路径时依赖于信息素浓度. 本文在传统蚁群的基础上, 除信息素搜索的常规蚂蚁外, 另外引入扩展蚂蚁. 如图 1所示, 假设种群共有m只蚂蚁个体, 其中常规蚂蚁数量为$ m_{1} $, 扩展蚂蚁个体数量为$ m_{2} $, 扩展蚂蚁不依赖信息素选择路径, 而是选取目前已有路径进行组合交换, 基于已知解的信息构造新的路径.

3.1.1 选择策略

在每代蚂蚁种群开始搜索时, 首先由常规蚂蚁构造$ m_{1} $个当前路径作为已知解.随后算法依据正比选择(proportional selection)策略对当前路径进行选择, 依次分配给每只扩展蚂蚁. 其中第i条路径被选择的概率$ P_{i} $正比于该条路径的总长度$ L_{i} $的倒数$ 1/{L_{i}} $, 保证扩展蚂蚁优先选择长度越短的路径, 即

$ \begin{align} P_{i} = \dfrac{1/{L_{i}}}{ \sum\limits_{i=1}^{m_{1}}{1/{L_{i}}}}. \end{align} $

(6)

得到概率后, 采用轮盘法旋转$ m_{2} $轮, 选出$ m_{2} $个路径分配到每只扩展蚂蚁.为避免多个扩展蚂蚁重复选择到同一个当前路径, 在选择时需剔除已被选择过的路径, 也正是由于扩展蚂蚁基于常规蚂蚁的路径进行选择, 在算法设计中扩展蚂蚁个体数量应小于等于常规蚂蚁的个体数量, 即$ m_{2}\leqslant m_{1} $.

3.1.2 组合交换

选择完成后, 每只扩展蚂蚁在除自身外其余扩展蚂蚁中随机挑选对象进行组合, 组合交换方法的设计参考遗传算法中的两点交叉算子. 在遗传算法中, 交叉算子得到的新个体差异性更强, 可以产生的大量新个体使得算法具有较强的全局搜索能力^[32].因此组合交换有利于跳出局部极值, 保证全局寻优能力. 需注意路径在组合时节点首尾相连且不允许重复. 例如当第k只蚂蚁随机选中另一只个体g执行路径组合操作时, 具体步骤如下:

1) 对个体k和g的节点进行index索引标注;

2) 在所有节点中随机选择两节点X、Y, 如图 2所示, 随机选择$ {X}=2, {Y}=5 $;

3) 分别在X、Y两节点后剪开, 得到交换对象$ k_{XY} $、$ g_{XY} $;

4) 分别删除蚂蚁k和蚂蚁g的原有路径中关于$ g_{XY} $、$ k_{XY} $的重复节点;

5) 标注剩余节点索引, 在X节点后插入交换对象的无重复节点, 得到交换后的最终路径.

按照上述流程进行组合交换, 其中每只扩展蚂蚁进行组合交换$ N_{C} $次, 并选择其中距离最短的一种组合保留构造新路径.

3.2 基于刺激-响应模型的角色平衡机制

如图 3所示: 常规蚂蚁参照信息素浓度构造个体路径, 具有正反馈特性, 保证算法有效收敛以及稳定性; 扩展蚂蚁通过已有路径构造新路径, 具有较强的全局搜索能力, 保证种群多样性. 角色平衡机制则用于动态调整蚁群中常规蚂蚁和扩展蚂蚁的数量占比, 平衡算法的收敛能力和全局搜索能力. 该机制基于刺激-响应分工模型设计, 本质上是一种任务负反馈模式下的调节方法.

3.2.1 负反馈调节模式

已知个体总数为m, 常规蚂蚁为$ m_{1} $, 扩展蚂蚁为$ m_{2} $. 在平衡机制运作过程中, 需根据算法运行情况, 对$ m_{1} $和$ m_{2} $数值动态调整, 因此可将常规蚂蚁增加和扩展蚂蚁减少看作任务1($ m_{1}\!\uparrow $ and $ m_{2}\!\downarrow $); 常规蚂蚁减少和扩展蚂蚁增加看作任务2($ m_{1}\!\downarrow $ and $ m_{2}\!\uparrow $).当构造路径时, 所有个体走过的路径越多、路径相似程度越弱, 则种群多样性越强; 反之, 当种群逐渐聚焦于某些路径时, 相似程度越强, 种群多样性越弱.

如图 4所示, 当种群多样性减弱到某一程度时, 个体均在相似路径上更新信息素, 此时算法陷入极值点, 按照平衡机制开始执行任务2, 即扩展蚂蚁增加, 常规蚂蚁减少, 算法的全局搜索能力增强, 进而增加种群多样性; 进一步, 当多样性增加至某一阈值时, 个体的路径均有差异, 虽然此时全局性很强, 但算法整体呈现随机搜索状态, 不利于快速收敛, 因此按照平衡机制开始执行任务1, 即常规蚂蚁增加, 扩展蚂蚁减少, 以增强信息素累积速率, 增强算法正反馈特性, 使算法快速收敛, 但全局搜索能力下降.

算法运行过程中, 可将每次增加或减少的蚂蚁数量设为$ \Delta m $.当$ \Delta m $越大时, 单步调整数量越大, 负反馈响应速度越快, 但易造成震荡, 难以平衡算法的搜索能力和收敛速度, 不利于算法精确求解; 而当$ \Delta m $越小时, 单步调整数量越小, 有利于算法找到两类蚂蚁之间的平衡点, 有利于算法求得最优解, 但负反馈速度较慢, 所需时间较长.

综上所述, 角色平衡机制是根据种群多样性情况对个体角色进行调整的一种负反馈调节方法, 本文基于刺激-响应分工模型建立其数学模型.

3.2.2 数学模型

根据刺激-响应模型, 需要通过环境刺激和响应阈值得到蚂蚁种群执行任务1和任务2的概率, 首先设置外部环境刺激S和个体响应阈值$ \theta $.

环境刺激S描述了个体执行任务的外部驱动力, 刺激越大, 任务越紧急. 在常规蚂蚁和扩展蚂蚁两类角色中, 二者数量之和为常数, 角色之间属于竞争关系. 一般认为两类角色之间的平衡表现为: 当种群多样性较好时, 通过增加常规蚂蚁数量保证算法开采效率; 当种群多样性较差时, 通过增加扩展蚂蚁数量增加多样性, 避免陷入局部极值, 因此环境刺激与种群的多样性相关.

多样性表现为个体之间的差异, 反映种群的分布情况. 本文的多样性度量方法参考文献[33]进行设计. 将多样性看成蚂蚁构造路径的差异性, 这种差异可以由路径长度体现. 例如m只蚂蚁共得到的m条路径$ R_{i} $, 其长度分别为$ L_{i} (i\in 1, 2, \ldots, m) $. 用第k只蚂蚁的路径长度$ L_{k} $和种群平均长度$ L_{\rm mean} $之差体现这只蚂蚁到种群中心点的差距. 此时整体多样性度量方法如下:

$ \begin{align} {\rm diversity}\_{\rm ant} = \dfrac{1}{m}\sum\limits_{i=1}^{m} {\sqrt {{{( {{L_{i}} - {L_{\rm mean}}} )}^2} } }. \end{align} $

(7)

其中: m为种群的蚂蚁数量, 当所有蚂蚁到种群中心的差距之和越大时, 认为种群多样性越大. 式(7)不依赖种群大小和空间范围, 能较好地度量多样性大小. 给定角色转换任务的环境刺激如下:

$ \begin{align} S_{\rm role} = {\rm diversity}\_{\rm ant}. \end{align} $

(8)

响应阈值$ \theta $描述了执行任务的内部倾向性. 阈值越小, 倾向性越强. 不同算例的维度和求解空间大小不同, 所以响应阈值应设置为可表征算例离散距离的参数. 在本文中$ \theta $与各节点间的平均距离$ D_{\rm mean} $有关, 具体为

$ \begin{align} &\theta_{\rm role}=n\cdot D_{\rm mean}, \\ &D_{\rm mean}= \dfrac{1}{(N-1)^2}\Big({\sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} {d_{ij}}}\Big). \end{align} $

(9)

其中: $ d_{ij} $为节点$ (i, j) $间的距离, n为节点个数.

在刺激-响应分工机制中, 角色调整任务的环境刺激和响应阈值共同决定个体执行任务的概率$ \varGamma $, 如下所示:

$ \begin{align} &\varGamma_{{\rm role{\_}1}} = \dfrac{{{S_{\rm role}^2}}}{{{S_{\rm role}^2} + {\theta_{\rm role}^2}}}, \end{align} $

(10)

$ \begin{align} &\varGamma_{{\rm role{\_}2}} =1-\dfrac{{{S_{\rm role}^2}}}{{{S_{\rm role}^2} + {\theta_{\rm role}^2}}}. \end{align} $

(11)

其中: $ \varGamma_{{\rm role{\_}1}} $为执行任务1的概率, $ \varGamma_{{\rm role{\_}2}} $为执行任务2的概率.

设计算法参数时, 需对两类蚂蚁的初始数量占比进行设定.在算法初期, 为了加快信息素的正反馈累加速度, 常规蚂蚁个体数量需占绝对优势, 以保证算法的收敛速度, 因此本文设定常规蚂蚁初始比例为80 %, 扩展蚂蚁初始比例为20 %, 且$ m_{2}\leqslant m_{1} $.

3.3 基于刺激-响应模型的信息素更新机制

为加快收敛, 本文引入精英策略, 设计一种基于刺激-响应模型的信息素更新机制. 所有个体遵循此信息系更新机制. 信息素更新机制的设计思路如下:

1) 将是否更新当前路径的信息素看作任务;

2) 每个蚂蚁均有各自的信息素更新阈值, 该阈值与蚂蚁个体对应的路径长度有关;

3) 外部环境有对应刺激, 刺激值与种群的平均适应度函数值(即平均路径)有关;

4)) 蚂蚁个体更新对应路径信息素的概率大小与该蚂蚁的阈值和外部环境刺激值有关, 遵循刺激-响应模型.

令$ S_{ph} $表示信息素更新任务的环境刺激, $ \theta_{i\_ph} $表示个体i的响应阈值, 则个体执行任务的概率为

$ \begin{align} &\varGamma_{i\_ph} =\frac{{{S_{ph}^2}}}{{{S_{ph}^2} + {\theta_{i\_ph}^2}}}, \end{align} $

(12)

$ \begin{align} &S_{ph} =L_{\rm mean}, \end{align} $

(13)

$ \begin{align} &\theta_{i\_ph} = L_{i} . \end{align} $

(14)

当前路径长度越大时, 对应算法解的质量越差, 根据上述模型, 其信息素更新的概率也越小; 当路径长度越小时, 对应算法解的质量越好, 其信息素更新的概率越大. 因此, 在算法运行初始阶段, 各可行解之间的质量差距较大, 质量高的可行解会以较大概率更新信息素, 保证了初始阶段的信息素的快速积累, 加快了算法收敛速度.

3.4 算法流程

本文算法(MF-ACO)整体框架如图 5所示, 包括角色分配、路径构造和信息素更新3部分. 此外, 为进一步加强算法的局部搜索能力, 算法引入2-opt交换规则^[34]帮精英个体进行局部调优, 选取路径最短的5 %个体为精英进行2-opt交换.算法具体步骤如下:

step 1:设置参数包括m、$ \Delta m $、n、Q、$ \rho $、$ \alpha $、$ \beta $、$ N_{\rm MAX} $、$ N_{C} $等;

step 2:初始化两类蚂蚁个体$ m_{1} $、$ m_{2} $占比;

step 3:常规蚂蚁依据信息素浓度构造$ m_{1} $个路径(方法与基本蚁群算法ACO一致);

step 4:根据式(6)和轮盘法, 选择已有路径分配给扩展蚂蚁;

step 5:扩展蚂蚁依据第3.1.2节的组合交换规则构造$ m_{2} $个新路径;

step 6:所有个体进行排序, 选择路径最短的5 %个体执行2-opt交换;

step 7:根据式(12)计算每个个体的更新概率, 且每个个体生成(0 $ \sim $ 1)区间内的随机数, 比较随机数和更新概率的大小, 对本次迭代满足条件的个体依据式(3)进行信息素更新;

step 8:根据式(10)、(11)计算种群的角色调整概率, 然后生成随机数, 比较随机数和更新概率的大小, 判断选择执行任务1或任务2;

step 9:记录最优值, 判断是否满足算法终止条件, 不满足则返回step 3, 否则输出最优结果.

4 仿真实验

为验证本文算法的改进效果, 选取标准TSP实例进行仿真实验. 算法基于Matlab 2017实现, 运行环境为Windows10; CPU为Intel(R) Core(TM) i7-7500U;运行内存为8 GB.

4.1 参数设置

由前文已知$ \Delta m $与负反馈调节作用的大小有关, 本节主要讨论$ \Delta m $对算法性能的影响.选取实例eli76和eil101进行仿真对比. 除$ \Delta m $外其余参数设置如下: $ \alpha=2, \beta=5, \rho=0.6, Q=100 $, 迭代次数$ N_{\rm MAX}=500 $, 蚂蚁总数$ m=1.5n $(n为路径节点数), 初始常规蚂蚁个数$ m_{1}=0.8m $, 扩展蚂蚁$ m_{2}=0.2m $, 扩展蚂蚁组合循环次数$ N_{C}=n $.

根据$ \Delta m $的大小分成5组, 每组进行20次独立实验, 结果如表 1所示. 已知解为当前所知的最短路径长度, 来自于TSPLIB标准库; 最优值为20次运算所得最短路径; 平均迭代次数$ N_{\rm ave} $为达到最优值时的迭代次数求平均值后取整.

由表 1结果可知, 当$ \Delta m $取0.05倍的m时, 算法效果最好, 此时若减小$ \Delta m $, 则迭代次数明显增加, 无法保证算法在500次内收敛; 而若增大$ \Delta m $, 虽可以略微降低平均迭代次数, 但最优值变差.故算法设定最终$ \Delta m={\rm ceil}(0.05m) $, 其中ceil$ (\cdot) $为向上取整函数.

4.2 结果对比 4.2.1 与经典算法对比

将本文算法与ACO、MMAS、ACS三种经典蚁群算法进行对比, 表 2为对比结果. 共选取14个实例进行仿真, 3种算法的参数参考文献[4, 23, 27]进行设置, 迭代次数为500. 所有算法均独立运行20次.

如表 2所示, 在所有实例中, MF-ACO所得的最优解、最优偏差、平均值和平均偏差均优于3种经典算法. 此外由于在编程时以浮点数计算结果, 所得最优解与已知最优解之间存在很小的偏差.

4.2.2 与改进算法对比

将算法与其他改进算法进行对比, 首先与文献[14]提出的面向对象的多角色蚁群(OMACO)算法以及文献[28]提出的基于频率图的蚁群优化(FGACO)算法进行对比, 对比结果见表 3. 这两种改进算法均重点提高了蚁群算法的全局搜索能力. 根据原始文献, 两种算法的参数设置如下: OMACO算法: $ m=1.5n $, $ \alpha=1 $, $ \beta=5 $, $ \rho=0.9 $, $ Q=120 $, $ \varepsilon=1.5 $, $ \xi=6 $, $ N_{\rm MAX}=1 000 $; FGACO算法: $ m=1.5n $, $ \alpha=3 $, $ \beta=2 $, $ \rho=0.05 $, $ Q=100 $, $ N_{\rm MAX}=1 000 $.

3种算法的对比结果如表 3所示. 除lin105中算法的最优值相同之外, 其余实例中其结果最优值均优于OMACO和FGACO算法. 可见本文算法较这两种改进算法的精确度和收敛性均有一定提高.

之后将本算法与基于虚拟蚂蚁的局部优化蚁群(VLACO)算法^[29]和基于方向信息素协调的蚁群(AADC)算法^[30]进行对比. 这两种算法通过改进启发信息来提高收敛速度力和搜索能力. VLACO算法参数为$ m=n $, $ \alpha=2 $, $ \beta=3 $, $ \rho=0.328 $, $ Q=100 $; AADC算法参数为$ m=n $, $ \alpha=1 $, $ \beta=5 $, $ \rho=0.9 $, $ Q=100 $.

对比结果如表 4所示, MF-ACO算法所得最优值和平均值最小, 优于文献[29]和文献[30]的算法. 此外, 在收敛性能上, 本文算法最优值的平均迭代次数$ N_{\rm ave} $远小于文献[29]算法, 与文献[30]相比也有一定提高.

4.3 算法分析 4.3.1 平衡性分析

本文算法将种群分为常规蚂蚁和扩展蚂蚁两类, 以平衡机制动态调节两类蚂蚁的数量比例. 其中常规蚂蚁保证了算法的稳定性和收敛性, 而扩展蚂蚁则在算法陷入停滞时, 帮助算法跳出局部极值, 保持种群多样性. 由算法仿真对比可知, 本文提出的MF-ACO算法在精确度和收敛性上较以往的蚁群算法及相关改进算法均有较大提高.

图 6为MF-ACO算法运行在eil101上得到的运行结果. 其中: 图 6(a)为最短线路、图 6(b)为收敛曲线、图 6(c)为扩展蚂蚁数量变化曲线.

由图 6(b)收敛曲线可知, 算法迭代300次左右达到最优值, 配合扩展蚂蚁数量变化曲线图 6(c)进行分析: 在算法运行初期, 扩展蚂蚁个体数量处于较低水平, 常规蚂蚁个体数量占绝对优势, 此时从收敛曲线中可以看出, 算法处于快速收敛阶段; 而当算法迭代至100次左右时, 收敛速度急剧下降, 陷入局部极值, 此时扩展蚂蚁数量快速上升到达峰值, 种群多样性增加, 帮助算法跳出局部最优, 重新开始收敛; 之后扩展蚂蚁呈现周期性变化, 当种群多样性下降时, 扩展蚂蚁数量增加, 多样性上升后, 扩展蚂蚁数量减少, 这一变化规律符合算法设计原理: 初期常规蚂蚁保证算法的收敛速度, 当常规蚂蚁的正反馈搜索陷入局部极值时, 扩展蚂蚁个体增加, 利用组合交换规则跳出局部极值.

4.3.2 复杂度分析

传统蚁群算法的复杂度主要与蚂蚁数量m、路径节点个数n、迭代次数$ N_{\rm MAX} $有关, 可以表示为$ O(N_{\rm MAX}\cdot m\cdot n^2) $. 在本文算法中, 常规蚂蚁与基本蚁群算法的路径构造策略相同, 信息素更新则需要增加一次分工概率计算和判断, 增加部分的计算复杂度为$ O(N_{\rm MAX}\cdot m_{1}) $, 对整体影响不大, 故常规蚂蚁的时间复杂度仍可近似看作$ O(N_{\rm MAX}\cdot m_{1}\cdot n^2) $. 扩展蚂蚁主要有选择和组合操作, 其中选择操作每代执行$ m_{2} $次, 组合操作每代执行$ N_{C}\cdot m_{2} $次, $ N_{C} $等于n, 故扩展型蚂蚁的时间复杂度为$ O(N_{\rm MAX}\cdot m_{2}+N_{\rm MAX}\cdot n\cdot m_{2}) $, 约等于$ O(N_{\rm MAX}\cdot n\cdot m_{2}) $. 此外, 算法引入了2-opt策略进行局部优化, 但执行个体所占整体的比例极少, 对复杂度的影响很小. 综上所述, MF-ACO算法整体复杂度为$ O(N_{\rm MAX}\cdot m_{1}\cdot n^2+N_{\rm MAX}\cdot n\cdot m_{2}) $, 与基本蚁群算法$ O(N_{\rm MAX}\cdot m\cdot n^2) $差别不大, 故本文算法的相关改进并未增加算法的复杂度.

5 机器人路径规划

为验证MF-ACO算法在实际问题上的有效性, 将算法应用于机器人路径规划问题^[12]进行求解.

5.1 基于路径规划问题的MF-ACO算法设计

本文MF-ACO算法是基于TSP问题设计的, 为了适配于实际路径规划问题, 需进行补充和修改的算法相关策略如下.

策略1:增加初始信息素不均衡分配策略.

使用蚁群算法求解路径规划问题时, 会面临收敛性差、盲目搜索的问题, 因此本文采用初始信息素不均衡分配策略^[12], 减少蚁群搜索的盲目性. 该策略主要思想为在起始节点与目标节点之间的所有节点, 规定其初始信息素略大于其他节点.

策略2:修改扩展蚂蚁组合策略.

在路径规划问题中, 两路径需有交叉节点时才可以进行交换操作, 故组合策略需修改为如下形式:

1) 每只扩展蚂蚁随机挑选对象进行组合.

2) 挑选完成后, 判断被选蚂蚁的路径与自身路径是否有相交节点: 若有相交节点则以节点为交换点进行交换; 若不相交, 则返回重新选取, 直至选择NC次后停止.

3) 选择距离最短的一种组合保留, 构造新路径.

策略3:删除2-opt交换策略.

在TSP问题中, 算法利用2-opt策略对少数精英个体进行局部寻优, 但在路径规划问题中, 该策略违背路径规划逻辑, 因此删除此条策略.

5.2 实验与结果

采用栅格法设计$ 20\times 20 $、$ 30\times 30 $地图各一个, 先将本文算法与ACO算法对比, 两种算法蚂蚁个数为100, 迭代次数为100, 其余参数与第4节相同, 仿真结果如表 5所示, $ 30\times 30 $仿真示意图如图 7所示.

在$ 20\times 20 $环境下, ACO算法用60次迭代收敛到32.98, 本文算法只用了27次迭代便收敛于最优路径31.55. 在$ 30\times 30 $环境下, ACO算法用89次迭代搜索到最优路径51.11, 本文算法用41次迭代便收敛于最优路径48.04. 因此本文提出的MF-ACO算法相比ACO算法, 其搜索到的路径更短, 收敛速度也更快, 在收敛性和全局搜索能力上均得到较大提高, 也验证了MF-ACO算法在解决实际问题时的有效性.

扩大对比范围, 将本文算法与常用的最短路径A*算法^[35]和Dijkstra算法^[36]进行对比, 算法对比结果如表 6所示.

由表 6可知, $ 20\times 20 $地图环境下, MF-ACO算法与A*以及Dijkstra算法均可以找到31.55长度的最短路径. 在$ 30\times 30 $地图环境下, 与MF-ACO算法和Dijkstra算法相比, A*算法由于加入部分启发式策略, 在障碍地图环境下未能找到最短路径. 此外, 与A*以及Dijkstra等全局规划算法相比, MF-ACO算法属于局部路径规划算法, 即算法在进行每一步搜索时, 仅需对周围的节点信息进行探索, 而不需要知道全局信息, 可以用来处理动态环境下的路径规划问题.

6 结论

本文针对传统蚁群算法初期收敛速度慢、易陷入局部最优值的缺点, 通过引入刺激-响应分工机制, 提出了一种具有混合反馈机制的扩展蚁群算法. 本文算法既包含基于信息素的正反馈式搜索, 也包含具有负反馈特性的动态平衡机制, 解决了单一信息素正反馈搜索的缺点, 保证了算法的全局搜索能力; 此外, 为进一步加快算法收敛, 本文基于刺激-响应模型和精英化思想设计了一种新的信息素更新机制. 所提出的算法在TSP和路径规划问题实例上与其他算法进行了仿真对比, 并得到了较好效果, 验证了MF-ACO算法的有效性和优越性.

从实验结果看, MF-ACO算法相比于已有算法有一定提高, 但仍有不足: 1) 本文引入改进策略的同时也引入了新的参数, 在应用中需要调节更多参数, 某种程度上增加了参数敏感性; 2) 本文算法属于局部搜索算法, 未用到全局信息, 在某些实际可以得到全局信息的场景中, 若加入全局信息, 则求解效率可以得到进一步提高, 因此在实际应用时, 可将本文算法与全局算法结合使用.