白云飞，胡大裟，蒋玉明，冯鲁波

(1. 四川大学计算机学院，成都 610065；2. 四川省大数据分析与融合应用技术工程实验室，成都 610065)

0 前言

随着全球工业自动化时代的到来，自动导引小车(Automated Guided Vehicle，AGV)在工业生产中起到了中流砥柱的作用。AGV对于提高工业生产效率、减少工作人员负担和降低生产成本具有重要意义。而路径规划是AGV完成工业生产过程中物料配送的前提。在过去的几十年里，研究人员做了许多工作。其中重要的算法有Dijkstra算法、A*算法等经典方法，以及智能优化算法，如蚁群算法和遗传算法[1]。

由于遗传算法在路径规划问题中，可以通过需求设定不同的编码方式，具有更好的鲁棒性和全局搜索能力，因此被广泛的应用到AGV路径规划中。但算法本身却有易陷入局部最优和收敛速度慢等缺点，不少学者对此进行了一些改进。如文献[2]利用自整定优化策略改进双交叉算子，并引入静态路径繁忙程度改进适应度函数，使规划后的路径更符合实际情况。文献[3]优化传统遗传算法中的双交叉算子和变异算子，提出一种利用地图特征信息的改进型遗传算法；文献[4]利用退火算法提高种群差异性，通过自整定策略提高算法收敛速度；文献[5]通过随机交叉的方式维持种群多样性，从而防止算法早熟。综上所述，虽然对传统遗传算法加以改进，但是算法仍然存在一些缺点需要优化：首先，还是使用传统的双交叉方式；其次对于适应度的改进依旧停留在静态环境中[6-8]，而不能对每次迭代的解进行动态修正；而且并未考虑多AGV规划可能会导致拥堵，路径转弯数过多导致运行耗时过长，降低工作效率。

本文结合AGV路径规划的特点，使用拓扑法建立地图模型；采用三启发交叉算子获得更多父代信息保证个体多样性，提高算法收敛速度，防止陷入局部最优解；为了提高AGV的运行效率，减少其转弯次数，对规划的路径进行平滑判断；为了减少AGV间的碰撞和拥堵概率，根据路径上AGV数量，进行拥堵程度判断；利用路径平滑程度描述转弯次数，拥堵系数表达路径的拥堵程度。然后将二者作为规划指标加入到适应度函数中，对每代最优路径进行奖励，最差路径进行惩罚，从而寻找到符合实际的路径。

1 改进的遗传算法路径规划

1.1 环境建模

本文采用拓扑法建立地图环境，采用符号编码方式，将拓扑节点的序号对应染色体的基因值。拓扑地图如图1所示[10]

图1 AGV环境模拟拓扑图

集合{V|V1，V2，V3，…，V9}为节点，表示现实工厂的工作机台，M表示为接货点。节点之间的数据是路径权重，表示运行路径上的具体信息。拥堵系数由Dis_Jam(S，P)的形式表达，其中Dis_Jam为两点之间的距离，S为路径平滑程度，P为拥堵系数。

1.2 三交换启发式交叉算子

传统的双交叉方式只继承父代的基本特征，使得子代多样性较低，无法继承过多父代的优良基因。导致交叉的概率减小，进化受阻，收敛速度缓慢。而且当子类多样性偏低时，也会导致变异的概率减少，不易产生新样本，从而陷入局部最优解。

三交换启发式交叉算子利用三个父代染色体间产生一个子代。与传统的双交叉方式相比，增加了产生子代染色体的信息，提高子代多样性。

而对于四交叉、五交叉的情况，如图2所示。在同样目标下，虽然父代染色体的增多，提高了继承双亲优良性状的可能性，但交叉次数过多，会导致收敛速度过慢。

图2 交叉次数对比图

1.3 适应度函数

为了使规划路径符合实际，充分考虑真实路况和多AGV的影响，引入路径平滑程度和拥堵系数优化适应度函数。

计算公式如下：

(1)

公式(1)中：f为目标函数；dis(vk，vk+1)表示个体vk和个体vk+1之间的距离；Pk和S分别为的拥堵系数和路径平滑程度。

其中若目标函数越小，代表所耗路径越短，规划的路径越优秀。反之，目标函数越大，代表所耗路径越长，规划的路径越差。

1.3.1 路径平滑程度

由于AGV易受到动力学和运动学的约束，拐弯幅度不宜过大，且相对平滑的路径更适合运行。为保证规划路径的合理性，利用路径平滑程度描述AGV的转弯次数及转弯的角度大小。

为方便计算，根据拐角大小对AGV的转弯情况做4个层次划分。假设AGV的正常转弯速度为vr，arc为拐角角度，引入惩罚系数α。α计算公式如下：

路径平滑程度计算公式如下：

(2)

其中vt为直线速度，vr为转弯速度，速度匀速不变；R为转弯半径；num为整条路径上拐角的个数。α为惩罚系数；

结合公式(1-2)可看出，若路径平滑程度越高，表示惩罚越大，使得目标函数f增大。根据遗传算法轮盘赌机制，易抛弃f值较大路径，从而防止算法得到转弯次数过多的路径。

1.3.2 拥堵系数

由于运行过程中可能发生多AGV拥堵或者碰撞的情况，通过定义拥堵系数，对拥堵程度较高的路径惩罚，避开较拥堵路段。其中拥堵系数是表达T时段内，该节点经过的次数对于总节点数的比重。拥堵系数计算流程图如图3。

图3 拥堵系数计算流程图

计算公式如下：

(3)

(4)

n为节点号；k为已使用的节点号；HK表示时间周期T内k节点使用频率；集合M表示节点k出现的次数；集合A为当前节点AGV出现的次数；MAX为小车总数。Pk表示路段k的拥堵系数。

结合公式(1)、(4)可看出，若拥堵系数越大，表示惩罚程度越大，导致目标函数f增大。

2 实验与分析

利用软件VS2015和C#语言对图1所示的地图环境进行路径规划测试，运行速度：vt=0.5m/s，vr=0.2m/s；小车数量：4辆；为增加合理性对比验证，分别对传统遗传算法、Dijkstra、蚁群算法和本文改进遗传算法进行多次实验。

2.1 遗传算法和改进遗传算法的对比

基本遗传算法中，选择方式为轮盘赌选择，使用二交换启发交叉算子，适应度只考虑路径长度。终止条件为迭代次数500次；耗时：242.5813；路径长度：147.9752；

利用三交换启发算子改进的遗传算法中，选择方式为轮盘赌选择，使用三交换启发交叉算子，适应度考虑路径长度。终止条件为迭代次数500次；耗时：126.7127；路径长度：120.9981；

利用三交换启发算子，并引入路径平滑程度和动态拥堵系数改进的遗传算法中，选择方式为轮盘赌选择，使用三交换启发交叉算子，适应度考虑路径长度，路径平滑程度，动态拥堵系数。终止条件为迭代次数500次；耗时：116.7127；路径长度：118.9981；

在不同的初始化种群条件下进行多次仿真，通过分析遗传算法收敛曲线，最终得到如图4、5所示的结果。

从图4可以看出利用三交换启发算子和适应度优化的遗传算法和传统的遗传算法对比，迭代次数少，且加快了收敛速度；

图4 对比收敛曲线

原因在于传统遗传算法受自身的交叉变异机制，很容易造成种群差异性小，且相对于其他群智能算法收敛速度较慢。再加上使用轮盘赌的方法，有极高的概率破坏优良个体，使算法易陷入局部最优。而改进的遗传算法采用三交叉方式提高了子代多样性，降低了轮盘赌的不良影响。从而使算法能较快收敛且不易“早熟”。

在仅改进交叉算子和同时优化适应度和交叉算子的对比中，如图5可以看出，同时优化适应度和交叉算子的曲线能较快收敛。原因是采用三交叉算法虽然能使种群差异性提高，但同时增加了较差子代的概率。而且传统算法的适应度设计过于简单，对于较差子代也能拥有很高的适应度，从而使算法不能较快收敛。通过对适应度的优化可以融入更多的信息，加强适应度函数的判断能力，加快算法收敛。

图5 对比收敛曲线

2.2 蚁群算法和改进遗传算法的对比

将传统蚁群算法与改进的遗传算法进行比较，实验结果如图6所示。从图中可以明显看出，虽然蚁群

图6 对比收敛曲线

算法能更快地找到最优解，有较好的收敛性。但蚁群算法具有正反馈的特点，初始时刻环境中的信息素完全相同，算法几乎按随机方式完成解的构建，这些解必然会存在优劣之分，且容易陷入局部最优。而在迭代数20～60之间，改进遗传算法曲线发生波动，证明此时种族差异性大，跳出局部最优解的可能性增大。

2.3 多AGV路径规划比较

将Dijkstra算法、蚁群算法、传统的遗传算法和改进的遗传算法的搜索结果进行对比，并加入路径平滑和拥堵系数，测试在多AGV和考虑道路状况的情况下三种算法的计算效率。

通过表1算法仿真结果对比，改进的遗传算法所规划的路径长度更短，耗时更少。而且对于路径平滑程度的考虑，改进的遗传算法选择到了最优路径，而Dijkstra和传统遗传算法并未选择到平滑程度最高的路线，即转弯次数最少。对于蚁群算法，虽然耗时很短，但很容易陷入局部最优解。

表1 算法仿真结果对比

3 结语

针对遗传算法在规划AGV路径时，存在易陷入局部最优，收敛速度慢的问题，将路径的长度，路径平滑程度，拥堵系数，作为评价指标对适应度函数进行改进；采用三交叉启发式算子代替传统的二交叉模式，使子类个体获得更多的父类信息。根据仿真结果证明，改进的遗传算法和传统遗传算法相比具有全局搜索能力强、收敛性能好的优点；与其他路径规划算法相比，能获得更优秀的解。