量子动态交叉正余弦混合并行算法的路径规划*

李月英

(郑州科技学院电子与电气工程学院，郑州 450064)

复杂环境中，移动机器人的最优路径规划求解方法主要包含传统算法和元启发式算法。传统路径规划算法主要有栅格法、人工势场、连接图法等[1]。这些传统方法无法保证求解移动机器人路径规划问题时的求解精度、成功率，搜索效率等，尤其对于高维的复杂环境[2]。元启发式算法相比传统方法具有易实现，求解精度高和收敛快等优点，近年来，元启发式算法被广泛应用于复杂环境中移动机器人最优路径规划中。例如：遗传算法[3]，胞遗传算法[4]，粒子群算法[5]等。这些算法在不同的地图环境中，都可以成功地求解移动机器人路径规划问题，但是它们具有共同的缺点就是不易跳出局部最优，稳定性较差，求解精度略低等。鉴于此，如何提高这些算法的求解移动机器人路径规划问题时的寻优性能一直是研究者关注的一个问题。研究者，一般通过引入改进变异算子和多种算法集成的方法得以提高算法寻优性能。比如改进粒子群算法[6]，改进灰狼算法[7]，改进蚁群算法[8-9]，动态分组蚁群算法[10]，量子风驱动算法[11]，改进ACO[12]，混合烟花-蚁群算法[13]，粒子群-蚁群混合算法[14]等。改进的算法提升了原有标准算法的寻优性能，同时可提高复杂环境中移动机器人最优路径规划的求解精度和效率。但是，随着地图环境的复杂度的增加，这些改进算法在求解过程中，仍存停滞现象，寻优精度和效率仍需进一步提升。

鉴于此，为更好解决移动机器人路径规划问题，提出一种量子动态交叉正余弦搜索的混合并行算法(QDCSCPA)。提出动态交叉分级精细搜索方法和混合并行方式。基于以上方法，该算法通过引入量子位Bloch球面算子扩充算法的初始种群数量和保证初始种群的质量，提高算法的初始寻优能力。同时利用动态交叉边界因子对种群进行动态实时分级分配，并混合自适应精英引导正余弦策略，正余弦-乘除策略和正余弦-帝企鹅策略对种群进行混合并行搜索，以提高算法全局寻优能力，增强跳出局部最优的能力。嵌入逐维随机反向学习和退火扰动混合扰动机制对个体进行更新，进一步平衡算法的全局探索与局部开发能力。通过复杂环境下移动机器人最优路径规划问题验证了所提出的算法的有效性。

1.1 量子位Bloch球面初始化种群

为保证种群的多样性，提高算法的迭代初期的寻优性能，采用量子位Bloch球面[15]初始化种群。

量子比特是量子信息的基本单位，1个量子比特可由量子位状态表示，量子位状态可表示为基态|0>和|1>的叠加态，空间内量子比特的一个量子位状态如式(1)和式(2)所示，并通过改变θ和φ，量子比特可呈现无穷多个不同的量子位状态。

(1)

|φ>=[cosφsinθsinφsinθcosθ]T

(2)

算法的种群个体通过量子位Bloch球面进行坐标编码，假定Xi是种群中第i个备选解，则Xi可按式(3)进行编码。

(3)

式中，D为维数；
i=1,2,…,N；
N为种群规模；
0≤φiD≤2π；
0≤θiD≤2π。

由此Xi可以转换为空间内并列三组解Xi,x,Xi,y,Xi,z如式(4)所示。

(4)

因此，可将Xi上第j个量子位的Bloch坐标可表示为[xij,yij,zij]T，则对应的空间解变量如式(5)所示。

(5)

式中，i=1,2,…,N；
j=1,2,…,D；
lbj和ubj为第j个量子位的下限和上限。

这样算法采用量子位Bloch球面初始化，可以丰富初始种群的多样性和增强算法的全局寻优能力。

1.2 动态交叉混合并行搜索策略

在高效的并行搜索策略中嵌入正余弦波动方式，采用动态交叉边界因子，实现算法种群的动态分级精细划分。提出自适应精英引导正余弦策略，正余弦-乘除策略和正余弦-帝企鹅策略对种群进行混合并行搜索，以提高算法全局寻优能力，增强跳出局部最优的能力，如图1所示。

图1 动态交叉正余弦混合并算法

(1)动态交叉边界因子。由图1可知，可将种群数量N，采用动态交叉边界N1，N2，N3可由式(6)确定，可将种群Xi划分为Xi1,j，Xi2,j，Xi3,j，可由式(7)确定。由图2可知，种群Xi1,j，Xi2,j，Xi3,j随着迭代次数增加可实现非线性动态调整。种群Xi1,j，Xi2,j呈现出非线性动态衰减变化，且在迭代中期前，随着迭代次数的增加，种群动态调整变化率Δk1和Δk2逐渐减小。但种群Xi3,j可实现非线性动态递增变化，种群动态调整变化率Δk3逐渐递增。这可提高算法前期搜索精度。迭代中后期，Δk1，Δk2和Δk3趋于平稳，有利于形成不同种群之间的动态平衡，可增强算法后期在搜索空间内的解的搜索。由图2看出，随着动态交叉种群数量n的改变，种群Xi3,j的变化幅度Δn3明显大于种群Xi1,j和Xi2,j的变化幅度Δn1和Δn2，这种变化幅度差异性，有利于实现种群进行交叉学习，实现算法种群中个体之间搜索信息的交流，增强算法的搜索遍历性。

(6)

式中，k为当前迭代次数；
kmax为最大迭代次数。

(7)

图2 种群动态交叉分级调整策略

(2)混合并行分级精细搜索策略。种群Xi1,j，Xi2,j，Xi3,j可由动态交叉边界实现自由动态调整，可持续地保持种群多样性，增强算法寻优能力。一方面，对种群实施并行式精细搜索，可进一步提升算法的搜索效率与全局收敛精度。另一方面，嵌入以正余弦为基础的混合算法搜索模式，可改善算法局部停滞问题。因此，对种群Xi1,j，Xi2,j，Xi3,j采用混合并行分级精细搜索，可动态协调算法局部与全局搜索，提升算法整体寻优性能。

①自适应正余弦精英指引搜索策略。对种群Xi1,j，在SCA算法[17]位置更新模式基础上，引入自适应因子和精英个体指引机制，使得种群Xi,j1可以自适应地实现波动搜索，增强种群个体跳出局部最优的能力。因此，种群Xi,j1位置更新如式(8)所示。

(8)

w=0.5/(0.5+e-k)

(9)

r1=2/(1+e-k2)

(10)

②正余弦-乘除搜索策略。AOA算法中乘除位置更新方式，有利于增强算法的全局寻优能力[18]，种群Xi,j2采用乘除搜索策略存在寻优过程中解的分散性较弱，易发生早熟。为此，融合正余弦波动与乘除搜索机制，可使算法的整体寻优性能进一步提升。因此，种群Xi,j2采用正余弦-乘除搜索策略对个体位置进行更新，如式(11)和式(12)所示。

(11)

(12)

式中，r6为[0,2π]内任意角；
r5和r7为[0,1]内随机数；
LB和UB为搜索空间的下限和上限；
α=5；
u=0.5。

③正余弦-帝企鹅搜索策略。在EPO算法中，种群个体采用精细网格化式的搜索方法，算法保持了较高的搜索效率[19]。但控制参数f和l随机性较强，影响算法的寻优性能。为全面提升算法的收敛性能，对原有的EPO中，控制参数f和l采用非线性递减函数进行改进，同时将正余弦搜索机制引入到EPO的位置更新方式中，这样可以实现提高算法的寻优能力和对抗局部极值的能力目的。因此，种群Xi3,j可按正余弦-帝企鹅搜索策略进行位置更新，如式(13)～式(21)所示。

(13)

(14)

(15)

A=(β×(T′+Pgird)×rand())-T′

(16)

式中，β=2。

f=2+1/(1+e(10×(k-0.5kmax)/kmax))

(17)

l=1.5+0.5/(1+e(10×(k-0.5kmax)/kmax))

(18)

S=(f×e-k/l-e-k)2

(19)

(20)

式中，C为[0,1]范围内的一个随机向量。

(21)

式中，r8和r10为[0,1]内随机数；
r9为[0,2π]内任意角。

1.3 逐维随机反向学习和退火混合搜索策略

算法的寻优性能很大程度上受种群多样性的影响。在有限的搜索空间内，算法不断迭代寻优的进化过程中，种群多样性无法能够得到充足的保障，造成算法搜索效率低下，易发生早熟。为增强算法的寻优性能，通过引入随机反向学习策略[16]如式(22)所示，在种群Xi1,j、Xi2,j、Xi3,j精细搜索后，对其进行反向学习，保证算法具有高质量的种群进行迭代寻优，避免过早地陷入局部最优。

(22)

在迭代后期，种群中最优个体存在陷入局部极值邻域内，为进一步提升算法迭代后期的寻优精度，退火策略属于一种局部优化技术，可以有效地提升算法的局部寻优性能，为此，混合随机反向学习与退火机制对算法最优个体进行逐维扰动如式(23)所示，不仅可以扩大算法搜索空间，继续丰富种群多样性，算法的收敛效率和全局收敛精度得以进一步提升，增强了算法全局搜索与局部搜索之间的平衡。

(23)

文中提出的基于QDCSCPA算法的移动机器人路径规划算法流程图如图3所示，详细步骤如下：

步骤1：算法初始化参数设置：设置栅格地图信息包含大小和起始点。同时设置QDCSCPA算法初始参数种群数量，最大迭代次数等。

步骤2：采用量子球面初始化算法种群如式(1)～式(5)所示，评估路径目标函数并确定初始最短路径信息。

步骤3：采用动态交叉分级方式如式(6)和式(7)所示，进行种群动态划分。

步骤4：利用混合并行分级精细搜索策略对种群Xi1,j、Xi2,j、Xi3,j进行位置动态更新。种群Xi1,j由式(8)～式(10)更新位置，种群Xi2,j由式(11)和式(12)更新位置，种群Xi3,j由式(13)～式(21)更新位置，同时分别对种群Xi1,j、Xi2,j、Xi3,j由式(22)进行学习。

步骤5：重新评估路径适应度值更新最佳路径长度及路径信息。

步骤6：根据式(23)对最短路径个体进行变异，同时更新最短路径长度和最优路径规划信息。

步骤7：判断是否满足最大迭代次数，若是，则输出全局最佳路径长度及最优路径信息，反之，返回步骤3继续寻优。

步骤8：输出最优路径规划结果。

图3 QDCSCPA算法流程图

3.1 QDCSCPA算法寻优性能分析

QDCSCPA算法的寻优能力通过6个基准测试函数来测试，如表1所示。算法分别选择QDCSCPA，SCA[17]，AOA[18]和EPO[19]算法，各种对比算法控制参数设置：对于QDCSCPA算法控制参数设置为α=5，u=0.5，β=2，动态交叉种群数量n=5。对于SCA算法：A=2，对于AOA算法：u=0.499，α=5。对于EPO算法：f=[2,3]，l=[1.5,2]。实验仿真环境为：采用小型戴尔Precision工作站，系统为Windows10 64位，内存为16 G，显卡为NVIDIA®Quadro®RTX 5000，均由MATLAB 2020a软件实现仿真计算。各算法种群数量设置为30，最大迭代次数为1000，独立计算30次，选取平均解和标准差作为性能评价指标。实验结果如表2所示。

表1 测试函数

表2 测试函数实验结果

续表

由表2可知，对于单峰函数F1和F2，QDCSCPA算法平均解与全局最优解相同且标准差为0。对单峰函数F3，QDCSCPA算法平均解和标准差优于SCA，EPO和AOA。对于多峰函数F4和F6，QDCSCPA算法的平均解和标准差优于其他算法。对于多峰函数F5，QDCSCPA和AOA的平均解和标准差相同。但QDCSCPA获得结果优于EPO和SCA。

综上所述，QDCSCPA算法的寻优能力明显优于SCA，EPO和AOA算法。同时QDCSCPA具有较好的稳定性和鲁棒性。这表明了以动态交叉正余弦并行搜索策略，一方面，可增强种群之间的信息交流和提高算法跳出局部最优的能力，另一方面，融合量子位Bloch球面策略，逐维随机反向学习和退火机制策略，可以提高算法的搜索效率和收敛精度。因此，可将QDCSCPA算法应用于求解移动机器人路径规划问题。

3.2 路径规划实验与分析

(1)路径规划实验设置。为更好验证所提出的QDCSCPA算法求解复杂环境下移动机器人路径规划的寻优性能。实验中将采用动态交叉混合并行搜索策略的算法记为QDCSCPA-Ⅰ，同时采用量子位Bloch球面初始化和动态交叉混合并行搜索策略的算法记为QDCSCPA-Ⅱ，将同时采用逐维随机反向学习和退火混合机制及动态交叉混合并行搜索策略的算法记为QDCSCPA-Ⅲ；
将采用量子位Bloch球面初始化、逐维随机反向学习和退火混合机制和动态交叉混合并行搜索策略的算法记为QDCSCPA。路径规划实验对比算法设置为QDCSCPA，QDCSCPA-Ⅰ，QDCSCPA-Ⅱ，QDCSCPA-Ⅲ，SCA[17]，AOA[18]和EPO[19]算法。

实验参数设置：各种对比算法控制参数设置：对于QDCSCPA，QDCSCPA-Ⅰ，QDCSCPA-Ⅱ，QDCSCPA-Ⅲ算法控制参数均设置为α=5，u=0.5，β=2，动态交叉种群数量n=5。对于SCA算法：A=2，对于AOA算法：u=0.499，α=5。对于EPO算法：f=[2,3]，l=[1.5,2]。所有算法种群数量设置为80，最大迭代次数为300。地图参数设置：通过栅格法[7]分别建立大小为25 m×25 m，35 m×35 m，45 m×45 m的机器人路径规划地图环境，如图4～图6所示。地图中黑色代表障碍物，白色代表可通行区域，起点和终点均已设置。起始栅格为S=1，3种不同规格的路径栅格G=625,1225,2025。

图4 25 m×25 m栅格化地图环境 图5 35 m×35 m栅格化地图环境

图6 45 m×45 m栅格化地图环境

路径规划实验仿真环境为：采用小型戴尔Precision工作站，系统为Windows10 64位，内存为16 G，显卡为NVIDIA®Quadro®RTX 5000，均由MATLAB 2020a软件实现仿真计算。实验统计结果选取20次各个算法获取路径的最小值，平均值，标准差和折弯次数。

(2)路径规划实验结果分析。在25 m×25 m，35 m×35 m，45 m×45 m地图环境下，路径规划实验结果如表3～表5所示。最短路径规划与收敛曲线对比结果如图7～图9所示。

(a) 最短路径 (b) 收敛曲线

(a) 最短路径 (b) 收敛曲线

(a) 最短路径 (b) 收敛曲线

由表3～表5路径规划结果可知，对于25 m×25 m，35 m×35 m和45 m×45 m路径规划地图，QDCSCPA算法获取的最小路径长度分别为36.756 m，50.490 m，69.161 m。QDCSCPA算法可获得的平均路径长度分别为37.305 m，51.474 m，70.483 m。且QDCSCPA算法对应的标准差分别为0.267，0.947，0.305。QDCSCPA-Ⅰ算法获取的最小路径长度分别为37.145 m，51.541 m，70.778 m。QDCSCPA-Ⅰ算法可获得的平均路径长度分别为37.305 m，51.474 m，71.508 m。且QDCSCPA-Ⅰ算法对应的标准差分别为0.423，1.025，0.608。QDCSCPA-Ⅱ算法获取的最小路径长度分别为36.854 m，51.109 m，69.864 m。QDCSCPA-Ⅱ算法可获得的平均路径长度分别为37.578 m，52.374 m，71.047 m。且QDCSCPA-Ⅱ算法对应的标准差分别为0.407，0.966，0.597。QDCSCPA-Ⅲ算法获取的最小路径长度分别为36.944 m，50.983 m，69.608 m。QDCSCPA-Ⅲ算法可获得的平均路径长度分别为37.599 m，52.206 m，71.026 m。且QDCSCPA-Ⅲ算法对应的标准差分别为0.267，0.947，0.305。

表3 25 m×25 m地图路径规划实验结果

表4 35 m×35 m地图路径规划实验结果

表5 45 m×45 m地图路径规划统计结果

由此看出，对于不同的地图环境，QDCSCPA-Ⅰ，QDCSCPA-Ⅱ和QDCSCPA-Ⅲ算法相比，QDCSCPA算法的最小路径长度和平均路径长度均短于SCA，EPO和AOA算法，路径长度标准差小于SCA，EPO和AOA算法。同时，与QDCSCPA-Ⅰ，QDCSCPA-Ⅱ和QDCSCPA-Ⅲ算法相比，QDCSCPA算法的最小路径长度和平均路径长度最小，且路径长度标准差较小。这可以看出采用3种改进策略(量子位Bloch球面初始化，动态交叉混合并行搜索和逐维随机反向学习与退火混合搜索策略)的QDCSCPA算法求解移动机器人路径规划的优化性能更优。

从耗时来看，对于所有的地图环境，QDCSCPA-Ⅰ，QDCSCPA-Ⅱ，QDCSCPA-Ⅲ，QDCSCPA算法的时间长于SCA，EPO和AOA算法。这是由于QDCSCPA-Ⅰ算法集成了SCA，EPO和AOA算法的寻优机制，在QDCSCPA-Ⅰ算法的基础上，QDCSCPA-Ⅱ，QDCSCPA-Ⅲ和QDCSCPA算法嵌入了各种新的变异算子(如并行动态搜索，动态交叉边界因子，随机反向学习，退火机制等)，进一步提高了搜索过程中算法种群的质量和多样性，使得种群进行精细化地搜索，这就在一定程度上会增加算法的寻优时间，但是算法的寻优精度得到了大幅提升，这种耗时的增加是可以接受的。

对于25 m×25 m，35 m×35 m和45 m×45 m路径规划地图，QDCSCPA-Ⅰ，QDCSCPA-Ⅱ，QDCSCPA-Ⅲ，QDCSCPA算法的折弯次数明显均小于SCA，EPO和AOA算法，但是QDCSCPA算法的折弯次数最小，并且随着地图环境复杂度的增加，折弯次数变化不大，相对稳定。这说明QDCSCPA算法具有较快的路径规划效率。

由图7～图9可知，针对不同的地图环境，QDCSCPA算法的最短路径规划最短，路径中折弯次数较少，路径平滑度更优，均能够提供较为合理的移动机器人路径规划线路。从收敛曲线可知，QDCSCPA算法的最短路径收敛线始终处于QDCSCPA-Ⅰ，QDCSCPA-Ⅱ，QDCSCPA-Ⅲ，SCA，EPO和AOA算法的下方，可以快速得到最短路径，收敛速度和全局最短路径精度明显优于QDCSCPA-Ⅰ，QDCSCPA-Ⅱ，QDCSCPA-Ⅲ，SCA，EPO和AOA算法。这可以看出，QDCSCPA算法采用动态交叉分级精细搜索方法和混合并行的搜索方式，并融入量子球面、非线性自适应、逐维随机反向学习和退火等算子，平衡了算法全局与局部之间的搜索能力。

综上所述，在复杂环境中，QDCSCPA算法可以快速的实现移动机器人最优路径规划，具有较强的寻优性能。

(1)为提高元启发式算法求解移动机器人路径规划问题的寻优性能，提出了一种量子动态交叉正余弦搜索的混合并行(QDCSCPA)算法。该算法以动态交叉分级精细搜索和混合并行搜索方式为基础，采用量子位Bloch球面初始化种群保证初始种群质量；
采用动态交叉混合并行分级精细搜索方式，实现种群个体的位置的实时动态分级更新，进一步引入逐维随机反向学习和退火混合搜索策略对种群个体进行学习，提升算法全局与局部的寻优能力。

(2)提出了一种动态交叉混合并行搜索策略，降低了算法求解复杂环境下移动机器人路径规划问题时容易陷入局部最优的可能性，同时，可为改善元启发式算法的性能提供了改进方法。

(3)实验表明，与QDCSCPA-Ⅰ，QDCSCPA-Ⅱ，QDCSCPA-Ⅲ，AOA，SCA和EPO算法相比，QDCSCPA算法寻优能力更优，稳定性与鲁棒性更强，弥补了AOA，SCA，EPO算法存在的不足。QDCSCPA算法能够实现实时地躲避障碍物，以较少的折弯次数获得最短的路径规划结果，稳定性和鲁棒性较强，可适用于求解高维复杂的优化问题(如车间调度、路径规划、特征选择、图像处理、结构优化、故障诊断等)。

猜你喜欢 余弦移动机器人交叉 移动机器人自主动态避障方法北京航空航天大学学报(2022年6期)2022-07-02基于粒子滤波的欠驱动移动机器人多目标点跟踪控制计算机测量与控制(2021年12期)2021-12-22菌类蔬菜交叉种植一地双收今日农业(2021年12期)2021-11-28移动机器人路径规划算法综述现代仪器与医疗(2021年1期)2021-06-09“六法”巧解分式方程初中生世界·八年级(2019年6期)2019-08-13移动机器人技术的应用与展望现代职业教育·中职中专(2018年11期)2018-06-11椭圆余弦波的位移法分析计算机辅助工程(2018年2期)2018-06-03两个含余弦函数的三角母不等式及其推论中学数学杂志(高中版)(2016年6期)2017-03-01实施正、余弦函数代换破解一类代数问题福建中学数学(2016年7期)2016-12-03连数小学生导刊(低年级)(2016年9期)2016-10-13