基于遗传算法的RGV动态调度模型

焦安康 邹文忠 胡涛

摘要：根据RGV的指令选取方式，将当前状态下的局部最优路径与动态优化方案相结合，建立最优路径调度模型，再对遗传算法中变异的方式进行改进，调整个体适应性评估函数，对最优子代选取的方式进行改变，得到两道工序下动态调度模型。

关键词：RGV动态调度模型；遗传算法；动态优化

1 问题一的模型建立与求解

1.1模型Ⅰ的建立

本文利用遗传算法对最优路径分析，使用到当前所有已知信息，不仅能考虑当前的最优路径，还能顾及到之后已知的八步的路径选取，使RGV移动的指令收敛到全局最优路径。

Step1 利用遗传算法建立模型

对RGV的调度进行个体与基因的模拟，个体的基因被定义为一个信号处理序列的排列。

Step2 建立动态调度模型

模拟RGV动态调度时的指令预测范围，选取step1中所得个体基因的最小单位，即第一个基因片段，视为动态情况下的全局最优解。

Step3 得到完整的个体基因

不断重复step2，更新个体每一段基因的全局最优基因，最终得到个体的最优完整基因。

1.2 问题一算法的求解

Step1 对CNC进行处理：将CNC进行编码，且对8台CNC进行无序排列，得到一个CNC队列，该队列即为模型Ⅰ中种群的初始条件。

Step2：本算法所有的指令，都是建立在模型Ⅰ中遗传算法选取最优解的基础上的，得到假想的种RGV移动作业路径。

选取初始种群：从种队列中随机选出100种队列，作为初始种群。

进行基因的变异：，将该100种队列复制2次。第一份复制得到的100种队列中每组队列随机选取两对CNC进行位置交换。第二份复制得到的队列，随机选取相邻两个的CNC随机插入到队列中其他位置。

评估个体的适应性：计算每组队列情况的RGV执行指令所需总时间记为Mi。

再将Mi （i=1，2…300）进行升序排列，选取前100个Mk （k=1，2…300），作为下一子代。

对子代重复上述操作，得到新的子代。循环繁殖30代之后，输出最终子代中用时最少的队列，即认为是最优路径。

Step3对step2中所得的最优路径，只保留其第一步选择，视为智能加工系统对RGV当前状态调度的指令。

Step4 在完成step3对其下达的指令后，重复step2、3得到下一步所需要执行的指令。

在对step2、3进行操作的过程中，对RGV执行每一步指令所需的时间进行求和，记为变量Q。直到智能加工系统连续作业8小时后，RGV回到初始位置，结束物料加工工作，计算总加工物料件数。

2 问题二的模型与求解

2.1 模型II的建立

Step1 利用遗传算法建立模型

对问题一中模型Ⅰ的遗传算法模型进行修改：

先编码模拟第一道工序的基因，再编码其所对应的第二道工序的基因，接着编码下一段第一道工序的基因，依次下去，直至编码完8段基因。

个体适应性评估的标准，同模型Ⅰ，但改变了计算编码基因段时间的方式。

Step2 建立动态调度模型

按照step1筛选出的基因也为当前最优基因片段，故选取step1中所得个体基因的最小单位。

Step3 得到完整的个体基因

不断重复step1、2，从而不断更新个体每一段基因的全局最优基因，最终得到个体的最优完整基因。

2.2 问题二算法的求解

Step2 遍历加工第一，二道工序的CNC的排列位置

对加工第一，二道工序的CNC的个数分k1=k2、k1>k2、k1

Step3 对以上每一种CNC的顺序情况进行如下操作：

依据物料加工需分工序的规则，得到种RGV移动作业路径。

选取初始种群：从种队列中随机选出100种队列，作为初始种群。

再进行基因的变异，同模型Ⅰ。

对子代重复上述操作，得到新的子代。循环繁殖30代之后，输出最终子代中用时最少的队列。

Step3對step2中所得的最优路径，将第一道工序与其对应的第二道工序的指令进行捆绑，只保留其第一步捆绑的选择，视为智能加工系统对RGV调度的下两步指令。

Step4 在重复step3得到下一步执行的指令。

在对step3进行操作的过程中，对RGV执行所有指令所需的时间进行求和，记为变量Q。直到加工系统连续作业8小时后，结束工作，计算总加工物料件数，得到最优路径。

3 模型的误差分析

在本模型中，利用遗传算法选取局部最优解时，初始种群与子代繁殖的有限性，并没有取出所有可能的解来得到全局最优解，所以会产生一定的误差，得到的最优解可能收敛到局部最优解，非全局最优解。遗传算法的实现有许多参数，如交叉率和变异率，会对结果有影响。

参考文献：

[1]吴焱明，刘永强，张栋，赵韩.基于遗传算法的RGV动态调度研究[J].合肥：合肥工业大学，2012：20-23.