基于遺傳算法的RGV動態(tài)調(diào)度模型

焦安康 鄒文忠 胡濤

摘要：根據(jù)RGV的指令選取方式，將當(dāng)前狀態(tài)下的局部最優(yōu)路徑與動態(tài)優(yōu)化方案相結(jié)合，建立最優(yōu)路徑調(diào)度模型，再對遺傳算法中變異的方式進(jìn)行改進(jìn)，調(diào)整個體適應(yīng)性評估函數(shù)，對最優(yōu)子代選取的方式進(jìn)行改變，得到兩道工序下動態(tài)調(diào)度模型。

關(guān)鍵詞：RGV動態(tài)調(diào)度模型；遺傳算法；動態(tài)優(yōu)化

1 問題一的模型建立與求解

1.1模型Ⅰ的建立

本文利用遺傳算法對最優(yōu)路徑分析，使用到當(dāng)前所有已知信息，不僅能考慮當(dāng)前的最優(yōu)路徑，還能顧及到之后已知的八步的路徑選取，使RGV移動的指令收斂到全局最優(yōu)路徑。

Step1 利用遺傳算法建立模型

對RGV的調(diào)度進(jìn)行個體與基因的模擬，個體的基因被定義為一個信號處理序列的排列。

Step2 建立動態(tài)調(diào)度模型

模擬RGV動態(tài)調(diào)度時的指令預(yù)測范圍，選取step1中所得個體基因的最小單位，即第一個基因片段，視為動態(tài)情況下的全局最優(yōu)解。

Step3 得到完整的個體基因

不斷重復(fù)step2，更新個體每一段基因的全局最優(yōu)基因，最終得到個體的最優(yōu)完整基因。

1.2 問題一算法的求解

Step1 對CNC進(jìn)行處理：將CNC進(jìn)行編碼，且對8臺CNC進(jìn)行無序排列，得到一個CNC隊列，該隊列即為模型Ⅰ中種群的初始條件。

Step2：本算法所有的指令，都是建立在模型Ⅰ中遺傳算法選取最優(yōu)解的基礎(chǔ)上的，得到假想的種RGV移動作業(yè)路徑。

選取初始種群：從種隊列中隨機(jī)選出100種隊列，作為初始種群。

進(jìn)行基因的變異：，將該100種隊列復(fù)制2次。第一份復(fù)制得到的100種隊列中每組隊列隨機(jī)選取兩對CNC進(jìn)行位置交換。第二份復(fù)制得到的隊列，隨機(jī)選取相鄰兩個的CNC隨機(jī)插入到隊列中其他位置。

評估個體的適應(yīng)性：計算每組隊列情況的RGV執(zhí)行指令所需總時間記為Mi。

再將Mi （i=1，2…300）進(jìn)行升序排列，選取前100個Mk （k=1，2…300），作為下一子代。

對子代重復(fù)上述操作，得到新的子代。循環(huán)繁殖30代之后，輸出最終子代中用時最少的隊列，即認(rèn)為是最優(yōu)路徑。

Step3對step2中所得的最優(yōu)路徑，只保留其第一步選擇，視為智能加工系統(tǒng)對RGV當(dāng)前狀態(tài)調(diào)度的指令。

Step4 在完成step3對其下達(dá)的指令后，重復(fù)step2、3得到下一步所需要執(zhí)行的指令。

在對step2、3進(jìn)行操作的過程中，對RGV執(zhí)行每一步指令所需的時間進(jìn)行求和，記為變量Q。直到智能加工系統(tǒng)連續(xù)作業(yè)8小時后，RGV回到初始位置，結(jié)束物料加工工作，計算總加工物料件數(shù)。

2 問題二的模型與求解

2.1 模型II的建立

Step1 利用遺傳算法建立模型

對問題一中模型Ⅰ的遺傳算法模型進(jìn)行修改：

先編碼模擬第一道工序的基因，再編碼其所對應(yīng)的第二道工序的基因，接著編碼下一段第一道工序的基因，依次下去，直至編碼完8段基因。

個體適應(yīng)性評估的標(biāo)準(zhǔn)，同模型Ⅰ，但改變了計算編碼基因段時間的方式。

Step2 建立動態(tài)調(diào)度模型

按照step1篩選出的基因也為當(dāng)前最優(yōu)基因片段，故選取step1中所得個體基因的最小單位。

Step3 得到完整的個體基因

不斷重復(fù)step1、2，從而不斷更新個體每一段基因的全局最優(yōu)基因，最終得到個體的最優(yōu)完整基因。

2.2 問題二算法的求解

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

對加工第一，二道工序的CNC的個數(shù)分k1=k2、k1>k2、k1

Step3 對以上每一種CNC的順序情況進(jìn)行如下操作：

依據(jù)物料加工需分工序的規(guī)則，得到種RGV移動作業(yè)路徑。

選取初始種群：從種隊列中隨機(jī)選出100種隊列，作為初始種群。

再進(jìn)行基因的變異，同模型Ⅰ。

對子代重復(fù)上述操作，得到新的子代。循環(huán)繁殖30代之后，輸出最終子代中用時最少的隊列。

Step3對step2中所得的最優(yōu)路徑，將第一道工序與其對應(yīng)的第二道工序的指令進(jìn)行捆綁，只保留其第一步捆綁的選擇，視為智能加工系統(tǒng)對RGV調(diào)度的下兩步指令。

Step4 在重復(fù)step3得到下一步執(zhí)行的指令。

在對step3進(jìn)行操作的過程中，對RGV執(zhí)行所有指令所需的時間進(jìn)行求和，記為變量Q。直到加工系統(tǒng)連續(xù)作業(yè)8小時后，結(jié)束工作，計算總加工物料件數(shù)，得到最優(yōu)路徑。

3 模型的誤差分析

在本模型中，利用遺傳算法選取局部最優(yōu)解時，初始種群與子代繁殖的有限性，并沒有取出所有可能的解來得到全局最優(yōu)解，所以會產(chǎn)生一定的誤差，得到的最優(yōu)解可能收斂到局部最優(yōu)解，非全局最優(yōu)解。遺傳算法的實現(xiàn)有許多參數(shù)，如交叉率和變異率，會對結(jié)果有影響。

參考文獻(xiàn)：

[1]吳焱明，劉永強(qiáng)，張棟，趙韓.基于遺傳算法的RGV動態(tài)調(diào)度研究[J].合肥：合肥工業(yè)大學(xué)，2012：20-23.