基于改进遗传算法的AGV路径规划

苑光明 翟云飞 丁承君 张鹏

[摘要]针对AGV在自动化生产线中原有路径规划算法存在路径拐弯次数多，不利于AGV自动控制的问题，提出了一种改进遗传算法。为提高AGV运行的效率，该算法引入了拐弯因素。针对在路径规划中传统遗传算法收敛速度慢的问题，结合分层方法，改进传统的精英保留策略。在算法进化过程中，根据个体适应度的变化动态调整交叉概率和变异概率，加快算法的收敛速度。Matlab仿真实验结果显示：改进遗传算法能够规划出一条更合理的路径，相比较传统方法减少了转弯次数，改善了搜索路径质量，表明该算法可以满足自动化生产线AGV路径规划的要求。

[关键词]自动导航车；路径规划；改进遗传算法；转弯次数

[中图分类号]TP 273[文献标志码]A[文章编号]10050310（2018）01006505

AGV Path Planning Based on Improved Genetic Algorithm

Yuan Guangming， Zhai Yunfei， Ding Chengjun， Zhang Peng

（Institute of Mechanical Engineering，Hebei University of Technology，

Tianjin 300132，China）

Abstract： In order to solve the problem that the path planning algorithm in AGV automation production line has the number of turns， which is not conducive to the automatic control of AGV， an improved genetic algorithm is proposed. In order to improve the efficiency of AGV automatic control， the algorithm introduces the turning factor. Aiming at the problem of slow convergence of the path planning in the traditional genetic algorithm， the traditional elitism strategy is improved with hierarchical method. In the process of evolutionary algorithm， the crossover probability and mutation probability are dynamically adjusted according to the change of individual fitness， and the convergence speed of the algorithm is accelerated. Matlab simulation results show that the improved genetic algorithm can plan a more reasonable path， and the number of turns is reduced compared with the traditional methods， and the quality of the search path has been improved， which show that the algorithm can meet the requirements of automated production line AGV path planning.

Keywords：

Automated Guided Vehicle（AGV）； Path planning； Improved genetic algorithm； Turn times

0引言

隨着自动化技术的不断发展，目前国内大部分制造业，尤其是在汽车制造、制药等劳动力密集的制造企业，传统的物料运输方式效率低，柔性较差，且需要的人工量大，对于企业来说难以达到其高效生产的要求。为了克服这种现状，相关领域积极引入AGV（Automated Guided Vehicle）自动导航车，达到物料运输的目的[12]。AGV在实际应用中仍然有一些需要解决的问题，路径规划是其中比较重要的一个问题，当AGV收到调度系统下达的任务后，会自动规划出1条从当前位置到达目标位置的路径，该路径需要优化的方面有行程时间、行程距离、所需能耗等[3]。AGV路径规划可以抽象建模成多目标优化问题，多目标通过惩罚函数使其成为单目标优化问题[4]。智能算法相比较传统算法具有全局搜索能力强、搜索效率高、易于实施等优点，已经被应用在很多复杂问题的求解中[5]。遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索优化方法，具有算法效率高、鲁棒性强、可实现并行搜索等特点[6]，被广泛用于解决人工智能、路径规划等领域的问题。

1问题描述

在自动化生产线的AGV路径规划中，从当前位置到目标位置需要找到一条最优路径。大部分路径规划的最优路径为最短路径，也有部分路径规划考虑到路径转弯次数对 AGV运行的影响，并在传统算法基础上引入了转弯因素[7]。但传统算法搜索效率低，不能保证搜索到全局最优解。本文所研究的最优路径具有路径短、转弯次数少等特点。

在生产车间AGV运行区域中，可以分为装卸货物区域、工位区和行走线路。图1是车间的AGV运行环境地图

（长度单位为m），本文将其简化为无向的连接图，该连接图由工作站点、线路转弯节点及行走线路组成。例如AGV收到任务从站点7到站点32，此时的最短路径不止1条。

789101819203132是其中一条最短路径，但路径转弯次数多，降低了AGV的运行效率，传统的遗传算法无法在多个最短路径中得到转弯次数更少的路径。

2改进的遗传算法

本文应用改进遗传算法求解最优路径，适应度函数包括路径长度和惩罚函数。将分层算法应用到精英策略中，改进的精英策略确保种群多样性的同时，优良个体能遗传到下一代。种群的选择操作采用改进的精英策略和轮盘赌规则[8]，根据适应度变化动态调整交叉概率和变异概率的取值，图2是改进的遗传算法流程图。

21遗传算法路径规划模型建立

遗传算法中的每1条染色体，对应着遗传算法的1个解决方案，在AGV路径规划中，基因是由起始点、目标点和AGV经过的若干个点组成。本文采用实数对基因进行编码，相对于二进制编码在求解过程中具有效率高、占用存储空间少及编码更加灵活等优点。如图3所示，X1 Y1起点、Xn Yn目标点和n-2个中间点构成了1条携带从起点到目标点AGV路径信息的染色体。

22基于分层方法的选择算子设计

为了选出优秀的个体，使优良的基因得以延续，要采用精英选择策略。传统的精英选择策略是将适应度高的个体（一般是适应度排名为前10%的个体）直接复制到下一代，由于这种方法只是保留了适应度最高的一小部分个体，随着迭代次数的增加，种群多样性会快速降低，容易得到局部最优解而非全局最优解[9]。本文将种群以适应度函数为标准分成4个层次a、b、c、d，处在4个层次中的个体其适应度满足（1）式，Fi是个体的适应度值。

Fa>Fb>Fc>Fd。（1）

其中a、b、c这3个层次的个体直接复制到下一代，保证种群基因的多样性，原则上a层次个体的数量少于b层次的，b层次个体数量少于c层次的。本文初始种群数50，分别取a、b、c层次个体数量为1、2、3个，种群中剩下的个体为d层次。每次迭代更新种群后，先按分层方法操作a、b、c这3个层次个体，再按轮盘赌规则选择个体复制到下一代。

23交叉算子和变异算子设计

交叉操作是对自然界的基因重组过程进行模拟，是遗传算法产生新个体的主要方法。本文采用部分映射方式进行染色体的交叉操作，生成两个随机数m、n，将x、y染色体位于m和n之间的基因片段互换。变异操作模拟自然界基因突变的过程，迭代过程中染色体上的基因会随机发生突变来产生新个体。

在算法进化过程中，交叉和变异概率影响着算法的局部和全局搜索能力，固定的交叉概率和变异概率无法保证算法较快地收敛并搜索到全局最优解[10]。本文根据算法进化过程中个体适应度的变化，动态调整Pc和Pm，交叉和变异概率公式如（2）和（3）：

Pc=Pcmax-（Pcmax-Pcmin）（Fc-Fmin）Fmax-Fmin，（2）

Pm=Pmmax-（Pmmax-Pmmin）（Fm-Fmin）Fmax-Fmin。（3）

式中：Pcmax和Pmmax分别表示交叉概率和变异概率的最大值；Pcmin和Pmmin分别表示交叉概率和变异概率的最小值；Fmax和Fmin分别表示种群中最大适应度值和最小适应度值，Fc表示两个要交叉个体中较大的适应度值，Fm表示要变异个体的适应度值。

24适应度函数设计

在遗传算法中，适应度函数是评判种群中个体存活能力的标准，它是依据目标函数确定的。适应度函数是非负的并且和目标函数不完全对应，在问题求解中适应度函数的值越大越好。在AGV路径规划中，适应度函数的首要指标是路径长度，除此之外还有路径能耗等指标[11]。本文的AGV路径规划目标是路径最短和更少的转弯次数，因此引入了惩罚系数α，在这里适应度函数值和目标函数值呈负相关关系，一条路径转弯次数越多其目标函数值越大，适应度值越小，在进行选择操作时个体被保留下来的概率越小。目标函数如式（4）：

f=n-1i=1d（pi，pi+1）+αm（v-vt）π2rvt。（4）

式中：f为目标函数；d（pi，pi+1）表示基因点pi和pi+1连接形成线段的距离；α为惩罚系数，一般取α≥1；m为路径染色体上全部节点连接起来时的转弯次数，m=0时路径为直线；v是AGV直线行走时的速度，vt是AGV转弯时的速度，假设v和vt大小恒定，vt小于v；r是AGV转弯半径。

3算法仿真及分析

在Matlab 2013环境下对算法进行仿真，参数设置如下：α=2，v=15，r=1。分别采用传统遗传算法和本文改进的遗传算法，去搜索站点7到站点32的最优路径，得到遗传算法的收敛曲线，在不同的初始化种群条件下进行多次仿真，绝大多数能得到如图4所示的结果，可以看出改进的遗传算法相比于传统的遗传算法迭代次数少，收敛速度较快，提高了搜索效率；在极少数情况下出现了如图5所示的结果，可以看出传统遗传算法陷入了局部最优，改进的遗传算法具有更好的全局搜索能力。

将A*算法、传统的遗传算法和改进的遗传算法的搜索结果进行对比，如表1所示，可以看出3种算法都能搜索到最短路径，但从起始点到目标点有多条最短路径时，3种算法搜索出来的路径会有不同。

为了进一步验证改进遗传算法的有效性，去搜索站点27到站点13的最优路径，得到路径272823178910111213，转弯次数为2次，成功地从长度相同最大转弯次数为5次的最短路径集合中找到了转弯次数最少的路径，算法收敛曲线如图6所示，可以看出改进遗传算法的收敛速度更快。改进的遗传算法能够高效地搜索到转弯次数更少的路径，相比于其他路径更有利于AGV的自动控制，具有明显的优势。

4結束语

针对AGV在自动化生产线中原有路径规划算法存在路径转弯次数多，不利于AGV自动控制的问题，本文将规划路径的拐