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

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

1遗传算法的介绍

进化计算是计算机里模拟进化,它包括遗传算法、进化策略和遗传编程,其中遗传算法是使用比较普遍的一种方法。遗传算法(GA)是一类基于生物进化的随机搜索算法,实现主要步骤:进化代数计数器初始化:t→0;随机产生初始群体P(t);评价群体P(t)的适应度;个体交叉运算;个体变异运算;评价群体P”(t)的适应度;对群体P’(t)进行选择运算;终止条件判断。不满足t+1→t转到第4步,继续进化过程,满足输出当前最优个体,算法结束。

2 AGV环境建模

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

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

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

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

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

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

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

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

式子中的Fi为第i路径的适应度值,P i为正比例选择概率,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.

© 版权声明
THE END
喜欢就支持一下吧
点赞0 分享
评论 抢沙发

请登录后发表评论

    暂无评论内容