基于遺傳算法的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.