基于改进遗传算法的自动导航小车路径规划调度

于佳乔，李岩

(长春工业大学电气与电子工程学院，吉林长春 130012)

0 前言

随着“中国制造2025”计划的实施，制造业的生产模式发生了巨大变化，智能制造为传统制造业开辟了一条新的道路。在新型智慧工厂中，柔性制造系统已应用于大多数企业。柔性制造系统(Flexible Manufacturing System，FMS)是由统一的信息控制系统、物料储运系统和数字控制加工设备组成，能适应加工对象变换的自动化机械制造系统。其中自动导航小车(Automated Guided Vehicle，AGV)在柔性生产系统的物料搬运中发挥着越来越重要的作用。随着AGV的广泛应用，随之带来的问题也不断增加，其中路径规划是这一领域的重点问题。如何对AGV进行合理的规划，以提高物料搬运效率和降低生产成本一直是企业关注的焦点。目前，国内外已有许多学者对AGV路径规划问题进行研究：文献[5]中采用改进的A*算法对智能车路径进行优化；文献[6]中应用多种群遗传算法对路径规划进行研究;文献[7]中提出了一种自适应遗传算法的路径规划方法,采用了人工势场对种群初始化,提高了算法收敛速度；文献[8]中应用Voronoi图法对移动机器人进行路径规划；文献[9]中提出了一种混合算法解决移动机器人全局路径规划问题,提高AGV路径的质量；文献[10]中将一种新的变异方法应用到机器人动态路径规划中；文献[11]中在遗传算法中加入转弯角度因素对移动机器人路径规划进行分析；文献[12]中提出一种新的基于排序遗传算法的多目标最优路径规划；文献[13]中提出了纵横协同的多种群遗传算法解决AGV调度问题；文献[14]中采用了整数编码和多参数编码相结合的方式对遗传算法进行改进，优化AGV的任务排序列表以及行走路径。

本文作者在传统遗传算法基础上对编码规则、变异算子以及交叉算子进行改进，在AGV数量及补料工位数量不同的情况下，拟优化出任务最短路径及排序，期望得到最优方案。

1 问题描述

在柔性生产系统中，通常存在一个集中配料区，有序存放车间生产所需所有物料资源，当有工位加工物料低于存储安全值时，就需要AGV及时为其补充物料。在生产过程中，可能出现多个工位同时需要AGV为其补充物料的情况，这时候就需要对AGV补料的顺序及路径进行优化，使AGV在最短的时间内为所有工位完成补料任务。本文作者在此基础上以多个AGV 同时服务于多个工位为背景，对AGV路径规划进行研究，拟达到降低AGV运行成本及车间生产成本的目的。

对于AGV路径规划问题现做出如下假设：

(1)AGV出发点(物料存储地)固定;

(2)上下料时间恒定且固定，故忽略不计;

(3)任何任务都可以分配给任何一台AGV;

(4)AGV容量足够大，且无差别;

(5)同一任务只能被一台AGV所执行。

2 数学模型

柔性生产车间AGV调度问题可描述为辆AGV服务个工位，AGV编号为:∈{1,2,3，…，}，工位编号为:∈{1,2,3,…,}，AGV任务编号为:∈{1,2,3,…,}。染色体用表示,现根据以上约束条件及假设，建立如下数学模型：

(1)

(2)

0=0 ∀,

(3)

=1 ∀

(4)

其中：式(1)表示总路径长度为各AGV路径长度总和；式(2)表示每辆AGV的每个任务只为一个工位进行补料；式(3)表示每辆AGV执行任务前统一在初始位置集合；式(4)表示每辆AGV可装载量足够且固定。

3 改进的遗传算法

遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机制的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。传统的遗传算法虽能寻找到最优解，但是在求解速度以及局部最优解问题的处理上并不理想。本文作者在传统的遗传算法基础上对编码、解码、变异算子及交叉算子进行改进，应用改进的遗传算法求解问题，以达到准确、快速、高效解决问题的目的。

3.1 编码设计

传统的遗传算法中编码方法有二进制编码、浮点数编码、实数编码。针对文中所研究的内容，提出一种双层实数编码方式：将染色体分为前后两部分：前一部分代表工位编号(工位编号先后即AGV补料顺序先后)；后一部分为AGV编号。例如：一条染色体为“2354113213”，其含义如图1所示。

图1 染色体编码

基于以上染色体编码方式其读取方式为：第一辆AGV补料任务地点为工位1、工位4；第二辆AGV补料任务地点为工位3；第三辆AGV补料地点为工位2、工位5。

染色体编码后按上述读取规则对AGV行走路径进行解码，通过读取AGV行走路径及搬运顺序记录染色体目标值。个体的适应度函数()定义如下：

式中：()为第辆AGV行走总路径之和。将所有AGV行走路径之和加在一起组成个体的适应度函数。根据上述定义可知，个体适应度值越大，目标值越小。当目标值最小时，得出最优解。

3.2 初始种群的生成

由于文中在染色体生成时使用双层编码方式，同时满足两个变量要求：工位数和AGV数，所以传统的种群生成方式不适用。文中初始种群的生成具体步骤如下：

(1)根据工位的数量确定第一层工位编码范围[1,…,]；

(2)根据可调用AGV数量确定第二层AGV编码范围[1,…,]；

(3)将第一层与第二层组成一条完整的染色体序列；

(4)重复步骤3、4，生成一组含有多个染色体的初始种群。

3.3 变异算子

变异操作是遗传算法中一个重要的过程，变异算子的主要作用是改善系统的全局搜索能力，维持种群的多样性。过小的变异率会导致新生成的种群产生新个体的能力较弱，抑制早熟现象的能力变差；过大的变异率会使系统随机性更大，增加不必要的计算。本文作者在综合考虑其影响因素后，提出一种变异方法：双层编码多次变异。多次的变异过程不仅增大了解的空间，而且维持了种群的多样性，降低了算法陷入局部最优解的概率。具体步骤如图2所示。

图2 变异过程

改进的变异操作在第一层编码的两点变异后加入了逆转变异以及滑动变异来增大解的空间，增强算法的搜索能力，可以更好地找到最优解。逆转变异及滑动变异具体原理如图3—图4所示(由于只对第一层编码有效，示例仅编写第一层编码)：

(1)逆转变异。在变异前产生随机数<，例如=4，即染色体前4位进行逆转变异，由原始“53214”变为“12354”，如图3所示。

图3 逆转变异

(2)滑动变异。首先将原始染色体复制，组成一条新的染色体=[,]，长度为二倍；其次生成随机数<，取的第位到第+-1位为新染色体,如图4所示。

图4 滑动变异

3.4 交叉操作

交叉算子是遗传算法中控制全局搜索的一种算子，算子大小的调试对整个算法有重要影响：较大的交叉算子会增强算法开辟新的搜索区域的能力，但是过大的算子会增加不必要的计算成本；当交叉算子过小时，系统会陷入迟钝状态，在搜索新个体时速度变慢，导致运行停滞，增大运行时间。基于双层编码方式对染色体进行双层两点交叉，即对染色体第一、二层同时进行两点交叉。首先将所有染色体分为两两一组，组成若干个染色体对，为每个染色体对分配随机数，当0.5时，对染色体第二层进行交叉，交换两染色体AGV编号，产生新的染色体。相较于原染色体，新染色体为相同补料工位使用不同的AGV来完成任务，增加了补料工位分配任务的解空间。交叉完成后对于第一层染色体片段工位编码部分，可能会出现重复工位的可能，因此在交叉后会对交叉后的染色体进行修补：取交叉片段补集随机排列到非交叉片段。具体过程如图5—图6所示。

图5 染色体修补过程

图6 交叉过程

3.5 迭代终止条件

迭代终止条件在遗传算法中控制着算法运行时间长短：过小的终止条件会让算法在未寻找到最优值时停止，而没有完成任务；过大则会增加算法不必要的过程，增加程序运行成本。在遗传算法中终止迭代有多种方法：(1)人为设置种群在迭代多次后强行终止，这种情况一般设置迭代次数为20～500之间；(2)当种群在多次迭代后目标值没有发生变化时停止迭代；(3)当迭代后的结果小于人为设定的值时，程序停止运行。文中选用第一种：当迭代次数为20～500代时，终止程序。这种方法会让程序变得更加可控，在不断观察运行结果时调整参数，以达到最优的效果。

4 仿真实验与分析

环境地图中最多有20个工位，将各工位置于-坐标系中并计算其坐标，结果如图7所示。

图7 工位点坐标

以此坐标作为地图，应用改进的遗传算法分别对相同工位数量、不同AGV数量以及相同AGV数量、不同工位数量在不同节拍要求下进行仿真实验，通过对比计算出约束下的最优方案。此算法中基本参数设置如下：种群数量=100；选择方式：轮盘赌选择；变异率：PM=0.1；交叉率：PC=0.7。迭代次数：当工位数量较多时=500，工位数低于10时=300。部分仿真结果如图8所示。

图8 20工位4车优化结果

以20个工位为例：当车间共有20个工位需要补料时，应用改进的遗传算法即可优化出在固定节拍要求下的最优路径及最优AGV数量，当节拍允许范围为100 s以下时，评估车辆成本及时间差成本选择最优车辆为4辆，由图8可知AGV1运输路径为：16→18→1→2；AGV2运输路径为：12→5；AGV3运输路径为：17→11→9→20→15→6→14→19；AGV4运输路径为：8→10→7→4→13→3。图9只是其中一种结果。如表1所示：完成任务时总运行距离为399.6 m；平均节拍为99.9 s。相对于传统算法AGV行走路径长度缩短了74.8 m，平均节拍减少了18.7 s，在节约成本的同时缩短了完成任务的工期，证明了文中算法的实用性。

图9 20工位4车仿真结果

表1 不同工位-AGV组合比较

5 结束语

本文作者在不同条件背景下对多AGV多任务模式调度问题进行研究，应用改进的遗传算法对模型进行优化，当任务较多时，改进的遗传算法无论从AGV行走距离、任务完成时间、迭代次数等方面都优于传统遗传算法，从而证明了算法的有效性；随后应用于模型中并达到了预期效果，也证明改进算法的实用性。通过算法对AGV进行调度，使工厂变得更加数字化、智能化、科学化，同时响应智慧工厂发展趋势。