基于ACO-SA算法的变电站巡检机器人路径规划

2022-11-01刘胜张豪晏齐忠张志鑫申永鹏

南方电网技术 2022年9期

刘胜，张豪，晏齐忠，张志鑫，申永鹏

(1.郑州轻工业大学，郑州 450002；2. 河南中烟工业有限责任公司南阳卷烟厂，河南南阳 473007)

0 引言

近年来我国在经济与基础建设领域发展迅猛，电力工业作为国家发展的支柱，其规模在不断扩大、自动化程度在不断提高[1 - 3]，变电站数量也随之不断增多，无人或少人值守变电站成为变电站发展的主流趋势[4]。传统人工巡检存在劳动强度大、巡检效率低、受环境因素限制等问题，已无法满足当下对供电质量的高要求[5]。引进智能巡检机器人在满足安全高效的同时，也克服了传统人工巡检的问题与不足。

路径规划是实现机器人自动导航的关键，进行路径规划的目的是在规定约束下为机器人选择一条尽可能历程最短、效率最高的无碰撞行动路线[6 - 7]。对于路径规划算法的研究，传统的蒙特卡罗模拟和迪杰斯特拉算法等贪心算法可以确保最优解，但在复杂条件下运算量过大[8 - 11]；随后人们提出了改进的蚁群算法和遗传算法此类启发式算法可以解决运算量过大的问题但仍存在收敛精度低、易落入局部最优解并且迭代复杂的问题[12 - 16]。

针对上述问题，张丽珍等通过建立节点间最优代价函数，设立“虚拟终点”，从而避免了盲目搜索，缩小了搜索空间，但易陷入局部最优[17]。孟冠军等选择在蚁群算法中加入全局距离参数，通过在运行过程中不断交叉操作以得到最快求解速度，该方法虽然降低了算法的运行时间，但所得结果并没有明显改进[18]。琚泽立等引入曼哈顿距离、重置信息素挥发机制以及设置蚁群自适应路径长度改进蚁群算法，得到了很好的路径结果，但在改进过程中也增加了算法运行的复杂性[19]。刘杰等引入自适应信息素挥发系数，实现了随机漫游的效果，避免搜索陷入停滞[20]。张凡等引入JPS算法，并优化调点数量，提高搜索效率，但未考虑提高算法运算速度[21]。薛阳等则引入蜂群算法，借助“观察蜂”和“侦查蜂”的概念完善解的适应度，这样很好地规避了局部最优的困境[22]。陈志等通过算法初期信息素不均匀分配避免盲目搜索，使用伪随机状态转移规则选择路径，同时利用动态惩罚方法解决死锁问题[23]。

本文结合模拟退火算法与蚁群算法提出了改进的蚁群-模拟退火(ant colony optimization-simulated annealing，ACO-SA)算法，通过提高蚁群前期的全局搜索能力、改善信息素分布与更新、引入回火机制避免局部最优、提高搜索效率。并通过仿真实验验证其准确性与有效性。

1 环境模型

本文采用栅格法模拟机器人工作环境，将变电站环境分解为一系列大小相等的网络单元，单元格大小以巡检机器人尺寸为标准。

假设巡检环境为长为L，宽为W的规则场地，将环境平均划分为m×n个长度、宽度分别为l、w的栅格，用Nxy表示每个小栅格，整个环境空间记为Φ，Φ的表达式如式(1)所示。

Φ=∑Nxy|(x∈[1,m],y∈[1,n])

(1)

每个栅格有无障碍信息表达如式(2)所示。

(2)

式中：Nxy为每个栅格的状态信息，取值为0表示无障碍区可自由通行，取值为1表示有障碍区禁止通行。在参考了现实变电站布局后，建立多个二值化栅格数组表示机器人巡检环境，同时设置小栅格为1×1，模型如图1所示。

图1 栅格模型Fig.1 Raster model

使用大小相等的栅格划分栅格空间，并用栅格数组表示运行环境，简单的建模过程大大降低了模型的复杂度，同时具备区分运动空间与障碍物的能力，满足路径规划的实验需求。此外，栅格法满足本文所采用的八叉树搜索策略，即机器人在搜索过程中可以朝附近8个方向的相邻栅格之间移动，机器人移动模型如图2所示。

图2 巡检机器人移动模型Fig.2 Mobile model of inspection robot

2 ACO算法和SA算法

ACO算法模拟自然环境中蚁群觅食时的探索过程，是一种寻找最优路径的启发式算法[24]。其原理是蚂蚁们在探索过程中沿途分泌信息素，随着蚁群多次往返，信息素不断积累、挥发，最后信息素浓度最高的路径即为最短路径。

信息素浓度是蚁群选择路径的关键依据，为了加速路径筛选设定信息素挥发机制，当所有蚂蚁完成一次往返后对全局信息素含量进行更新，具体规则见式(3)。

τij(t+1)=(1-ρ)τij(t)+ρΔτij(t)

(3)

式中：τij(t)为返途中蚂蚁在节点i到节点j之间的路径上所留下的全局信息素含量；ρ为信息素挥发因子，ρ∈(0,1)代表信息素在自然条件下的挥发情况，1-ρ为信息素残留因子；Δτij(t)为本次往返途中蚂蚁k在节点i到节点j之间的路径上所留下的信息素含量，其数学表达式如式(4)所示。

(4)

式中m为环境地图最大栅格数。

蚂蚁对于路径的选择不仅与信息素浓度有关，在选择下一节点时会优先考虑相邻的节点，对此定义蚂蚁在两节点间的启发函数ηij以表达蚂蚁从所在节点i到达下一节点j的期望程度，详见式(5)。

(5)

(6)

式中：dij为节点i与节点j直接的欧几里得距离；ix、iy、jx、jy分别为两节点的横纵坐标。

(7)

式中：A为蚂蚁下一步可访问的节点集合；τij(t)为节点i与j之间的信息素含量；ηij为启发函数；α为信息素启发因子，α值越大则在选择路径时信息素的影响就越大，蚂蚁们就越倾向于选择较多蚂蚁走过的路径；β为期望因子，β值越大则在选择路径时启发式信息的影响就越大，蚂蚁们更倾向于移动至相邻最近的节点；C为该时刻未访问的节点集合；S为集合C中的一节点。

根据以上条件，利用经典蚁群算法在本文所建立的栅格环境(图1)中进行路径规划，其结果如图3—4所示。

图3 经典蚁群算法规划路线Fig.3 Classic ant colony algorithm for route planning

结合图3和图4可知，传统蚁群算法在迭代至30次左右时陷入局部最优导致算法处于死锁状态，之后迭代冗余无法得到最优结果。

图4 经典蚁群算法收敛曲线Fig.4 Convergence curve of classical ant colony algorithm

模拟退火算法模拟热力学中金属退火过程[25]，随着温度由高降低(退火过程)，粒子随机运动概率逐渐降低，并最终达到稳定热平衡状态。

运用模拟退火算法进行路径规划实际上是一个组合优化的过程，即从所有可行解中挑选出最优状态下的解。首先设定Ω={S1,S2,…,Sn}代表所有可行解构成的解空间，用C(Si)代表解Si所对应的目标函数的值，最终最优解S*应满足对于所有Si∈Ω都能满足C(S*)≤C(Si)。

随机生成一组可行解记为初始解状态，并计算得到该解的目标函数值C(Si),随后采用Metropolis抽样法获取新的可行解S′,计算目标函数的增量，并以如下标准判断是否接收S′作为新的当前解，数学表达式如式(8)所示。

(8)

式中：P为随机数，P∈[0,1]；Pt为接收概率，与时间t成反比，如式(9)所示。

(9)

之后重复操作迭代500次后降低温度，在新的温度条件下寻求新解，当满足终止条件后，结束退火过程并输出最优解。其中t时刻下温度T=αtT0，T0为初始温度。

3 改进算法

3.1 启发函数的改进

传统蚁群算法在设定启发式信息时仅用节点间距离的反比来构建启发函数，以此模拟蚂蚁选择最短距离路径的效果，这样在理论上确保了蚂蚁们会优先选择段距离路径，但是未考虑当前节点与下一节点的位置关系，同时在后期搜索过程中启发信息的影响程度将远低于信息素，为此我们重新定义启发函数如式(10)所示。

(10)

(11)

式中：djb为节点j到终点b的欧几里得距离；Lmax为最大迭代次数；ϑ为使启发函数动态变化而引入的参数，其值随着迭代次数的增加由大变小；L为当前迭代次数。由于前期增大了启发函数的比重，避免了蚂蚁搜索路径的盲目性，加快收敛速度，同时不会干扰后期路径选择的准确性。在其他参数不变的情况下，仅改变启发函数完成10组对照实验，实验结果如图5所示。

图5 改进启发函数验证Fig.5 Verification of improved heuristic function

由图5可知，我们在同一栅格环境进行10次重复试验，可以看出在运用改进启发函数后，迭代次数明显下降。

3.2 初始信息素改进

在经典蚁群算法中，初始时全局信息素处于同一水平，这使得蚂蚁们前期处于盲目搜索状态，导致算法运行时间增加。为了提高算法收敛速度，本文给出了初始信息素的确定公式，如式(12)所示。

(12)

式中：a、i、j、b分别表示起始点、当前节点、下一节点、终点；dab、dai、dij、djb为各点之间的欧几里得距离；λ为平衡系数。20×20栅格环境中初始信息素浓度如图6所示。

图6 初始信息素浓度Fig.6 Initial pheromone concentration

以颜色深度表示初始信息素浓度，从图6可以看出，初始信息素浓度是以始末连线为中心，沿中垂线向外呈正态分布且浓度逐渐降低。这使得初始条件下各节点由于位置不同信息素分布不均匀，避免了蚂蚁在初期盲目探索，提高了搜索效率。

3.3 初始信息素改进

在经典蚁群算法中信息素挥发因子通常为常数，这使得信息素的更新无法满足我们对算法收敛速度与全局最优的要求。对此本文给出信息素动态挥发因子见图7，此时ρ的值随着迭代次数的增加而减小。ρ的数学表达式如式(13)所示。

图7 两种ρ函数对比Fig.7 Comparison of the two ρ functions

ρ=ce-t1/2

(13)

式中：t为算法运行时间；c为平衡系数，其值可变以确保函数可进行自适应变化。

改进后的信息素更新机制前期ρ值较大可以扩大搜索范围，后期ρ值较小以便快速筛选出优势路径。为验证改进的可行性，在其他条件不变的前提下，使用不同信息素挥发因子进行对照实验，实验结果如图8所示。

图8 改进信息素挥发机制验证Fig.8 Verification of improved pheromone volatilization mechanism

3.4 初始信息素改进

为了避免局部最优我们引入模拟退火算法中的回火机制，蚂蚁选择下一节点j时的选择函数见式(14)。

(14)

(15)

4 改进算法

为验证改进算法的有效性，使用MATLAB R2016a进行计算机仿真实验，具体实验环境为Windows 10操作系统，CPU为core i5 8th gen，8 G内存。为验证ACO-SA算法的优越性，将仿真结果与经典蚁群算法进行比较。

4.1 算法实现

仿真实验参数如表1所示。同时由于模拟过程若设定Tmin=0则需要过长时间运行，迭代次数过多使精度和时间上产生矛盾。因此设定的终止条件为T<0.000 1或最优解保持不变。

表1 参数配置Tab.1 Parameter configuration

按图9流程进行算法仿真。

图9 ACO-SA算法流程Fig.9 Flow chart of ACO-SA algorithm

步骤1：构建栅格地图，设定初始参数，即蚂蚁数量N、降温系数、初始温度、回火次数、迭代次数。

步骤2：设定不均匀初始信息素浓度，并设定启发函数。

步骤3：派出蚂蚁探索全图，根据信息素浓度及启发函数前往下一节点，所有蚂蚁完成一次往返或无法行走时本次迭代结束。

步骤4：历次迭代完成后，接受最短路径，并更新全局信息素浓度。

步骤5：采用回火机制，与前一温度时刻比较，若当前解(最短路径长度)优于上一解则接受新解，对于劣解根据公式得到接受概率，同时产生随机数Y(取值范围为[0,1])，若Y

步骤6：更新当前温度，当迭代次数或当前温度满足结束条件时退出循环，否则进入下一次迭代循环。

步骤7：输出解集中的最优解为最终路径。

4.2 结果分析

根据上述算法步骤，本文分别建立场景1(20×20)、场景2(25×25)、场景3(30×30)栅格地图，并逐步增加地图环境复杂程度，检验算法的普适性。为了更直观地验证ACO-SA算法的可行性，将文献[20]的改进蚁群算法与本文提出的融合算法进行对比。场景1、2、3的实验结果分别如图10—12所示。

图10 场景1实验结果Fig.10 Experimental results of scenario 1

图11 场景2实验结果Fig.11 Experimental results of scenario 2

图12 场景2实验结果Fig.12 Experimental results of scenario 2

ACO-SA算法、文献[20]算法在3个场景中关于最优路径长度、算法运行时间、迭代次数的对比结果如表2所示。

表2 结果对比Tab.2 Comparison of results

结果显示，在3个场景中相较于文献[20]算法，ACO-SA路径长度减少了8.44%、9.97%和10.27%，运算时间分别缩短了29.17%、35.45%和37.71%，迭代次数缩减了64.71%、22%和16.28%，由于采用新的信息素更新机制，ACO-SA算法的最优路径长度较经典算法有明显改进，并且转移概率中增大启发函数的作用，将随机性选择和确定性选择相结合，使收敛速度更快，更稳定。