遗传算法在AGV的路径规划中的应用

扈先勤 李巍巍

DOI：10.16660/j.cnki.1674-098X.2016.18.097

摘 要：使用有向图对AGV路径进行建模，在求解最优路径问题上采用了遗传算法和相关的遗传算子及终止条件。根据遗传算法的进行过程，首先对AGV路径进行建模、编码和确定适应度函数，其次设计选择、交叉及变异算子和遗传算法的终止条件。其中对不同的长度染色体采用禁止交叉策略，以便更好地适应AGV复杂的工作路径。

关键词：AGV 有向图 路径规划 遗传算法

中图分类号：TP21/27 文献标识码：A 文章编号：1674-098X（2016）06（c）-0097-02

AGV（自动导引小车）是现代物流系统中的关键设备之一。AGV路径优化问题，就是寻找一条从起点到终点能够防止AGV之间无碰撞的最短路径。传统方法是将路径考虑成一系列的路径点，进行规划并行实现，这种方法虽然在实时性方面有很大的优势，但对于全局最优解的寻找却无能为力。因此，可引入遗传算法来帮助寻找全局最优解。

1 遗传算法的介绍

进化计算是计算机里模拟进化，它包括遗传算法、进化策略和遗传编程，其中遗传算法是使用比较普遍的一种方法。

遗传算法（GA）是一类基于生物进化的随机搜索算法，实现主要步骤：进化代数计数器初始化：t→0；随机产生初始群体P（t）；评价群体P（t）的适应度；个体交叉运算；个体变异运算；评价群体P”（t）的适应度；对群体P（t）进行选择运算；终止条件判断。不满足t+1→t转到第4步，继续进化过程，满足输出当前最优个体，算法结束。

2 AGV环境建模

在建模过程中，假设AGV是工作在二维空间中的运动，用折线表示AGV可通过的所有路径，AGV抽象为质点；AGV在每个节点的停留时间长都一定且相等。对AGV的路径简化，将相对应的节点及路径可得到相对应的有向图，如图1所示。

3 AGV路径中遗传算法参数的设计与优化

采用遗传算法对AGV路径规划，要求设置部分遗传算法的参数和相关技术，有解码与编码、适应度函数、复制、交叉、变异算子以及控制参数的设定。

对上述路径简化有向图进行顺序编码，如图2所示，图中的数字是编码的基因。图中的线段长度不代表实际长度。

从图中可以看出路径染色体的基因编码及遗传算法的种群初始化，如2359、1369、136789等。鉴于AGV的路径规划中，适应度函数采用距离公式，同时规定路径中染色体基因中，前一个基因编号必须比后面的一个基因编号小。

对初始路径进行复制操作首先确定各个路径的适应度函数值，计算各个路径被选择的概率，计算公式如下：

（1）

式子中的Fi为第i路径的适应度值，Pi为正比例选择概率，N为子代和父代的总体个数。在使用遗传算法对AGV路径进行选择时，分析Pi值的大小，选择Pi越大的个体进行后续的交叉和变异。

由于之前单模式路径问题中的遗传算子针对的路径编码是同质的，各个位置的基因性质对等，可以进行任意交叉及变异。设置对等染色体之间进行交叉和变异计算，在各个同等基因的染色体交叉算子统一采用单点交叉策略，如图3所示，4基因父类（A、B）不能与5基因父类（1，2，4，5，9）进行交叉。

在遗传算法中通常将变异概率设定为一个已知的数，而且值也很小，由于AGV路径比较简单，因此变异概率选择0.01或者更小，使整个遗传算法体系的染色体处于正常状态，同时变异的方法选择位置变异。

遗传算法的终止条件：（1）判别遗传算法进化代数是否达到预定的最大代数；（2）判别染色体的适应度函数值是否已趋于稳定。整个遗传算法的流程图如图4所示。

4 结语

对AGV的工作空间采用有向图进行建模，在一定程度上简化了AGV路径规划的难度，同时将遗传算法运用到AGV路径规划中，可以适应更加复杂多变的AGV工作环境。分别对不同长度路径中交叉与变异算子进行设计，使遗传算法能够更加准确高效地把握进化方向。

参考文献

[1] 张晓萍.现代生产物流及仿真（修订版）[M].北京：清华大学出版社，2011：105-235.

[2] 贾建成.AGV视觉导引及其路径规划策略研究[D].秦皇岛：燕山大学，2010.

[3] 蒲亮亮，张小栋.光导AGV智能循迹测控系统的建与仿真[J].测控技术，2011（5）：85-89.

[4] 周明，孙树栋.遗传算法原理及应用[M].北京：国防工业出版社，2014.