近年来，随着人工智能行业不断取得新的突破，智能机器人被广泛应用于各行各业，人们对于移动机器人的需求在不断的增加．路径规划问题是移动机器人研究中的一个重要方向．为解决移动机器人的路径规划问题，智能算法的设计是一个关键问题，目前应用较为广泛的路径规划算法主要有Dijkstra算法[1-2]、人工势场法[3-4]、模拟退火法[5-6]、A-Star算法[7-10]和遗传算法[10-13]等．遗传算法的优点在于直接把目标函数值作为搜索信息，具有群体搜索特性，但也具有相同染色体之间交叉无效及迭代过程中出现退化现象等缺点．诸多学者针对以上问题进行了改进，文献[14]通过将总适应度函数分为路径长度适应度函数和路径平滑度适应度函数两部分，使所得路径更加平滑；设计自适应策略对交叉和变异概率进行调整，解决了算法陷入局部最优的问题；文献[15]针对多任务路径规划存在收敛速度慢、易陷入局部最优解的问题，提出一种融合模拟退火准则的改进遗传算法．虽然仿真实验表明以上对遗传算法的改进可行且有效，但是仍存在一些不足．例如：传统遗传算法生成的初始种群个体适应度差距较大，导致收敛速度下降；传统遗传算法中交叉操作通常使用单点或多点交叉，而在采样点模型下，个体之间很少存在重合点用以交叉操作，同时传统变异方式缺乏方向性，得到的路径质量不可控，甚至出现适应度高的个体被破坏的情况．基于以上问题，本研究提出一种改进遗传算法用于机器人路径规划．设计了基于终距概率的初始化方法来生成初始种群，提高初始种群质量；提出一种不依赖于交叉点的自由交叉方式和基于目标导向的变异算子，可以在采样点模型下进行有效的交叉操作，当进行变异操作选择变异节点时，以父节点前后两节点的连线为导向选择变异节点，既保证了种群的多样性又使得变异点选择时更具有方向性，算法收敛速度更快．大量的仿真结果表明本研究的改进遗传算法在解决机器人路径规划问题上的改进效果明显．1 改进遗传算法1.1　环境建模图1所示为本研究所创建的20 m×20 m的地图环境M1，图中：白色方格表示障碍物；蓝色区域为移动机器人可自由行走的区域．在此区域内生成若干采样点即图中黑色点，第n个采样点的坐标为(xn，yn)，机器人可在采样点之间的连线上运动，左下角红点为起点，右上角红点为终点．10.13245/j.hust.240403.F001图1地图环境M11.2　终距概率初始化通常传统遗传算法所生成的初始种群质量较差，而质量差的初始种群会直接导致算法收敛速度降低．为提高算法的收敛速度，本研究提出一种基于终距概率选择的初始化方法．首先当初始化参数时设置每条路径经过的采样点数目为n，设置当前步数为m，有l=hi/ki，(1)式中：l为当前节点的步长；hi为当前节点到终点的距离；ki为路径经过的采样点数目n减当前步数m．按照式(1)计算当前节点的步长l．以当前节点为圆心，以该步长为半径，确定当前的搜索范围．搜索范围如图2所示，图中：左下角红点为起点；右上角红点为终点；中心红点为当前节点；红线为已走路径；黑色虚线圆圈为搜索范围；黑色虚线圆圈内的红色小圆圈为可行节点；圈外蓝色小圆圈为其他采样点．10.13245/j.hust.240403.F002图2搜索范围示意图当前节点i到下一节点j的选择概率pij可表示为pij=ηijβ∑s∈aηisβ  (j∈a);0  (j∉a), (2)式中：ηij=1/sij为启发函数，其中sij为从当前节点i到下一节点j之间的距离；β为启发函数重要程度因子；a为可行节点列表．根据式(2)可以确定pij．为验证上述种群初始化方法的正确性和合理性，在图1所示的地图M1中进行种群初始化仿真实验，与传统遗传算法进行15次对比实验，实验数据如表1所示．10.13245/j.hust.240403.T001表1初代路径长度平均值及方差对比初始化方法长度平均值长度方差平均路径最长路径最短路径平均路径最长路径最短路径随机初始化45.4754.6536.0910.4222.885.07终距概率初始化32.9935.0530.650.270.730.33m由表1的实验结果可知：本研究初始化方法得到的初始种群路径平均长度降低了12.48 m，得到的初始种群最长路径长度降低了19.60 m，得到的初始种群最短路径长度降低了5.44 m．传统随机方法产生的初始种群路径长度的方差更大，说明每次实验得到的初始路径长度变化幅度较大，路径质量参差不齐．本研究改进的初始化方法所产生的路径长度方差更小，每次实验所得的初始路径长度较为稳定，可以稳定地输出高质量的初始种群．1.3　自由交叉算子传统遗传算法一般采用单点交叉或多点交叉的方式进行交叉操作，须要将历代个体的重合点作为交叉点，而在采样点模型下个体之间很少存在重合点．因此本研究提出一种不依赖于交叉点的新的交叉方式，只须要在生成初始种群时保证每条路径的节点数量一致，即使路径之间没有重合点，也可以进行交叉操作，提高了找到最优路径的概率．首先在父代种群中按照交叉概率选取两条路径进行交叉操作，从起点开始，在两路径的对应两节点中间计算得到一个边长分别为x和y的矩形范围．若第n条父代路径的节点(xnn,ynn)和(xnn+1,ynn+1)满足交叉要求，则两节点所形成的范围可表示为：x∈(xnn,xnn+1),y∈(ynn,ynn+1)  (xnn≤xnn+1,ynn≤ynn+1);x∈(xnn+1,xnn),y∈(ynn,ynn+1)  (xnn+1xnn,ynn≤ynn+1);x∈(xnn,xnn+1),y∈(ynn+1,ynn)  (xnn≤xnn+1,ynn+1ynn);x∈(xnn+1,xnn),y∈(ynn+1,ynn)  (xnn+1xnn,ynn+1ynn).然后在规定范围内随机选取一点，若该节点与路径前一节点连线不经过障碍物，则将该点作为交叉节点．如图3所示，左下角和右上角的两红色节点分别为起点和终点，上下两条黑色路径为父代路径，中间红色路径为交叉所得子代路径，节点(xnn,ynn)和(xnn+1,ynn+1)形成的矩形区域即红色虚线所示，区域内的红色小圆圈为可选节点，随机选择每个矩形区域中的一个节点并连接前一节点与该变异节点．10.13245/j.hust.240403.F003图3交叉操作演示为验证上述交叉方法的正确性和合理性，在图1所示的地图M1中进行交叉实验(忽略变异操作)，设置地图左下角为起点，右上角为终点，并与传统遗传算法对比．图4为路径长度迭代对比图，图中：D为路径长度；I为迭代次数．10.13245/j.hust.240403.F004图4路径长度迭代图由仿真结果可知：使用本研究改进的交叉方法所产生的种群路径的最终平均长度为28.87 m，最优路径长度为27.4 m，而使用传统的交叉方法所产生的种群路径的最终平均长度为29.89 m，最优路径长度为29.49 m．本研究改进的交叉方法所得的路径质量更好．从迭代收敛代数上看，本方法的平均路径和最优路径均比传统方法提前5代收敛，因此使用本方法的收敛速度更快．1.4　基于目标导向的变异算子传统的遗传算法通常采用随机的方法选取变异节点，这种方法当选择变异节点时缺乏方向性，得到的变异效果不可控．当种群进化到一定程度时，个体大部分趋于最优解，此时随机的变异操作就很容易破坏这些适应度较高的个体，因此当本研究进行变异操作选择变异节点时，以父节点前后两节点的连线为导向以一定概率进行随机选择，既保证了种群的多样性又使得在变异点选择时更具有方向性，得到的路径质量更好．在交叉完成后的种群内选取路径中的某节点为父节点，进行变异操作．连接父节点前后的两节点得到一条直线，父节点到该直线的距离为A．按照Li=1.4A计算得到Li，以父节点(x,iyi)为圆心，以Li为半径确定一个圆形区域，该圆形区域即变异范围．若待选节点坐标为(xj,yj)，则该待选节点到直线的距离为di．每个节点的选择概率可表示为Pi=∑diβ/diβ．如图5所示，红线为父代路径，中间的节点为父节点，左下角为父节点前一个点和右上角为父节点后一个点，黑色虚线圆圈为搜索范围，黑色虚线圆圈内的红色小圆圈为可行节点，圈外蓝色小圆圈为其他采样点．以父节点为圆心、以Li为半径形成圆形变异范围，选择范围中的一个节点，若该节点到前一个的节点和后一个节点均不经过障碍物，则该点为变异子节点．10.13245/j.hust.240403.F005图5变异操作为验证上述变异方法的正确性和合理性，在图1所示的地图M1中进行变异实验(忽略交叉操作)，地图左下角为起点，右上角为终点，并与传统遗传算法对比．设置相同的初始种群，初始种群平均长度为33.15 m，初始种群最优长度为30.35 m．表2为经过50次迭代的路径长度数据对比．10.13245/j.hust.240403.T002表250次迭代路径长度数据对比变异方法平均路径长度最优路径长度10代20代30代40代50代10代20代30代40代50代随机变异33.0635.7234.0034.0430.7229.8230.0429.9929.9329.00目标导向变异28.9728.7328.6328.5928.5828.4327.4327.4327.3327.33m由实验数据可知：使用本研究改进的基于目标导向的变异方法所产生的历代种群路径，当到第10代时最优路径长度下降了1.92 m，当到第50代时最优路径长度下降了3.02 m；而传统遗传算法当到第10代时最优路径长度下降了0.53 m，当到第50代时最优路径长度下降了1.35 m．传统的变异方法在第20代和第40代时平均路径长度反而增大，同时最终的路径长度变化很小，而本研究改进变异方法对变异点的选择方向给出了引导，每一代路径长度均保持递减．2 仿真实验与分析为验证本研究提出的改进遗传算法的正确性和合理性，运用python3.8编制程序进行仿真．硬件环境信息：CPU2.5 GHz，i5处理器．分别在M2和M3地图下进行仿真，并与传统遗传算法进行比较，其中，M2为20 m×20 m的环境模型，M3为30 m×30 m的环境模型．以左下角节点为起点，右上角节点为终点．设置采样点数量为300，初代个体数为20，交叉概率为0.8，变异概率为0.3，仿真结果如图6、图7及表3所示，图中：红色实线所示路线为本研究改进遗传算法所得；绿色虚线所示路线为传统遗传算法所得．10.13245/j.hust.240403.F006图6M2地图环境下的仿真结果10.13245/j.hust.240403.F007图7M3地图环境下的仿真结果10.13245/j.hust.240403.T003表3算法实验数据对比算法地图环境初代路径长度/m最终路径长度/m收敛代数平均最优平均最优平均最优传统遗传算法M236.4532.8831.5529.602723M356.4548.8449.3344.333329本研究M236.4532.8829.0728.73119M356.4548.8444.0741.911612由仿真结果可知：相比于传统遗传算法，本研究改进遗传算法在M1，M2和M3环境下的最终路径分别缩短了0.66，0.87和2.42 m，收敛速度也较传统遗传算法更快，M1，M2和M3环境下的平均路径收敛速度比传统算法的收敛速度分别快了11，16和17代，最优路径收敛速度比传统算法的收敛速度分别快了13，14和17代，最优路径收敛速度比传统遗传算法提高约60%．为了进一步验证本研究算法的有效性，将本研究算法与文献[16]的改进蚁群算法和文献[17]中的改进遗传算法进行仿真比较，其中，M4为文献[16]的地图模型，M5为文献[17]的地图模型．设置采样点数量为300，交叉概率为0.6，变异概率为0.1，与文献[16]及文献[17]对比试验的初代个体数分别设置为50和80，并将实验结果进行对比，如图8、图9及表4所示．10.13245/j.hust.240403.F008图8本研究改进遗传算法与文献[16]算法运行结果10.13245/j.hust.240403.F009图9本研究算法与文献[17]算法运行结果10.13245/j.hust.240403.T004表4仿真结果对比地图环境算法初代平均路径长度/m初代最优路径长度/m最后一代平均路径长度/m最终路径长度/m最优路径收敛代数M4文献[16]78.8870.0043.5842.0060本研究51.9047.2142.2541.9730M5文献[17]122.00——29.97120本研究60.0855.7430.0628.8772通过仿真实验可知：本研究改进遗传算法所得最优路径结果分别为41.97和28.87 m，均优于文献中改进算法所得结果42.00和29.97 m，且本研究改进遗传算法迭代收敛代数分别为30代和72代，相比于文献算法所得的60和120代收敛速度显著提高．由于文献[17]未提及初代最优路径长度和最后一代平均路径长度，因此在表4中以“—”代替．将本研究改进遗传算法与文献[18-20]中的其他改进智能优化算法进行对比实验，可进一步验证本研究改进遗传算法的可行性和有效性．M6为文献[18]的地图模型，M7为文献[19]的地图模型，M8为文献[20]的地图模型，设置采样点数量为300，交叉概率为0.6，变异概率为0.1，初代个体数为50，并将实验结果进行对比，如表5所示．10.13245/j.hust.240403.T005表5实验结果对比地图环境算法最优路径长度/m最优路径收敛代数M6文献[18]38.0016本研究26.827M7文献[19]29.796本研究28.596M8文献[20]28.7925本研究28.0411由表5实验数据可知：相对于其他改进智能优化算法，本研究改进遗传算法所得的最优路径更短，收敛速度更快，比其他文献算法的最优路径收敛速度最多提高56%．通过上述对比仿真实验可知：使用本研究改进遗传算法的路径规划效率明显优于传统遗传算法，且比其他改进的遗传算法和改进智能优化算法效果都好，说明本研究算法在路径优化方面的具备一定的可行性与实用性．3 结语传统遗传算法当解决采样点模型下的路径规划问题时生成的初始种群随机性强，个体适应度差距较大且分布不均，且传统遗传算法当应用于采样点模型时，由于交叉点数量少，从而导致交叉操作效率低，变异操作随机性过强，生成的路径质量不可控，导致算法迭代速度慢，最终路径质量差．本研究通过设计一种基于终距概率的初始化方法来生成初始种群，提高了找到最优路径的概率，从而加快了算法收敛速度．然后提出一种不依赖于交叉点的新的自由交叉方式，使交叉操作能够适用于采样点模型，产生足够多的新个体．最后提出基于目标导向的变异算子，当进行变异操作选择变异节点时，既能保证种群的多样性又使得在变异点选择时更具有方向性，得到的路径质量更好，因此本研究算法收敛速度更快．仿真结果表明：本研究改进遗传算法所产生的初始种群质量高，交叉操作的有效性提高，收敛速度更快，变异后的路径质量更好，验证了本算法在不同复杂环境中的可行性与优越性．