焦安康 鄒文忠 胡濤
摘要:根據(jù)RGV的指令選取方式,將當(dāng)前狀態(tài)下的局部最優(yōu)路徑與動態(tài)優(yōu)化方案相結(jié)合,建立最優(yōu)路徑調(diào)度模型,再對遺傳算法中變異的方式進行改進,調(diào)整個體適應(yīng)性評估函數(shù),對最優(yōu)子代選取的方式進行改變,得到兩道工序下動態(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)度進行個體與基因的模擬,個體的基因被定義為一個信號處理序列的排列。
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進行處理:將CNC進行編碼,且對8臺CNC進行無序排列,得到一個CNC隊列,該隊列即為模型Ⅰ中種群的初始條件。
Step2:本算法所有的指令,都是建立在模型Ⅰ中遺傳算法選取最優(yōu)解的基礎(chǔ)上的,得到假想的種RGV移動作業(yè)路徑。
選取初始種群:從種隊列中隨機選出100種隊列,作為初始種群。
進行基因的變異:,將該100種隊列復(fù)制2次。第一份復(fù)制得到的100種隊列中每組隊列隨機選取兩對CNC進行位置交換。第二份復(fù)制得到的隊列,隨機選取相鄰兩個的CNC隨機插入到隊列中其他位置。
評估個體的適應(yīng)性:計算每組隊列情況的RGV執(zhí)行指令所需總時間記為Mi。
再將Mi (i=1,2…300)進行升序排列,選取前100個Mk (k=1,2…300),作為下一子代。
對子代重復(fù)上述操作,得到新的子代。循環(huán)繁殖30代之后,輸出最終子代中用時最少的隊列,即認為是最優(yōu)路徑。
Step3對step2中所得的最優(yōu)路徑,只保留其第一步選擇,視為智能加工系統(tǒng)對RGV當(dāng)前狀態(tài)調(diào)度的指令。
Step4 在完成step3對其下達的指令后,重復(fù)step2、3得到下一步所需要執(zhí)行的指令。
在對step2、3進行操作的過程中,對RGV執(zhí)行每一步指令所需的時間進行求和,記為變量Q。直到智能加工系統(tǒng)連續(xù)作業(yè)8小時后,RGV回到初始位置,結(jié)束物料加工工作,計算總加工物料件數(shù)。
2 問題二的模型與求解
2.1 模型II的建立
Step1 利用遺傳算法建立模型
對問題一中模型Ⅰ的遺傳算法模型進行修改:
先編碼模擬第一道工序的基因,再編碼其所對應(yīng)的第二道工序的基因,接著編碼下一段第一道工序的基因,依次下去,直至編碼完8段基因。
個體適應(yīng)性評估的標(biāo)準,同模型Ⅰ,但改變了計算編碼基因段時間的方式。
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ù)物料加工需分工序的規(guī)則,得到種RGV移動作業(yè)路徑。 選取初始種群:從種隊列中隨機選出100種隊列,作為初始種群。 再進行基因的變異,同模型Ⅰ。 對子代重復(fù)上述操作,得到新的子代。循環(huán)繁殖30代之后,輸出最終子代中用時最少的隊列。 Step3對step2中所得的最優(yōu)路徑,將第一道工序與其對應(yīng)的第二道工序的指令進行捆綁,只保留其第一步捆綁的選擇,視為智能加工系統(tǒng)對RGV調(diào)度的下兩步指令。 Step4 在重復(fù)step3得到下一步執(zhí)行的指令。 在對step3進行操作的過程中,對RGV執(zhí)行所有指令所需的時間進行求和,記為變量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é)果有影響。 參考文獻: [1]吳焱明,劉永強,張棟,趙韓.基于遺傳算法的RGV動態(tài)調(diào)度研究[J].合肥:合肥工業(yè)大學(xué),2012:20-23.