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

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

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

0 前言

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

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