基于混合遺傳算法的虛擬裝配作業(yè)過程規(guī)劃

焦玉民,徐 婷,劉 斌,于光亮

(1.94679部隊,南京210038; 2.陸軍工程大學 野戰(zhàn)工程學院,南京 210007)

國家自然科學基金青年基金資助項目(51505498)

焦玉民(1984—),男,工程師,博士.E-mail:602093540@qq.com

基于混合遺傳算法的虛擬裝配作業(yè)過程規(guī)劃

焦玉民1,徐 婷2,劉 斌2,于光亮1

(1.94679部隊,南京210038; 2.陸軍工程大學 野戰(zhàn)工程學院,南京 210007)

提出了一種基于回報機制和逆向求解機制的裝配作業(yè)規(guī)劃方法.使用遺傳算法與Q學習算法相結合,共同對作業(yè)過程規(guī)劃問題進行求解.構建適合信息融合和進化計算的“維修元”模型,并將“維修元”進行排列組合,構成裝配作業(yè)序列,解決裝配作業(yè)過程中的信息融合問題.為保證作業(yè)序列的可行性和維修元的可操作性,將特征匹配機制作為啟發(fā)機制,避免不可行序列參與進化計算,提高進化效率,解決了虛擬裝配過程中多要素融合條件下的規(guī)劃問題.

混合遺傳算法; 虛擬裝配; 過程規(guī)劃; 維修元

虛擬維修訓練系統作為一種智能化的訓練手段,以其突出的特點和優(yōu)勢,成為訓練模式向現代化發(fā)展的必然趨勢.虛擬維修訓練過程設計越來越注重訓練內容的完整性和實用性[1-2].拆卸與裝配是訓練過程模型設計的重要內容,但對比于拆卸過程,裝配過程涉及的維修要素類型復雜很多.目前，在具備規(guī)劃功能的虛擬維修訓練系統中,規(guī)劃方法均較注重結果的有效性,忽視了操作者的作用,對于與操作者緊密聯系的工藝性內容(維修工具選擇、維修行為選擇、裝配類型判斷等)涉及較少.如何將眾多不同種類的信息進行融合,并應用于作業(yè)過程的實時規(guī)劃,是裝配作業(yè)過程規(guī)劃研究的重點.

有向圖方法憑借圖形化描述和參數化表達的優(yōu)勢,能夠較為完整地記錄維修作業(yè)過程中發(fā)生的事件,因此常被用于過程建模[3-4];但由于該方法缺乏智能特性,難以將不同類型的信息進行規(guī)劃,對操作者的指導意義有限.智能算法作為目標優(yōu)化問題的求解方法,被廣泛應用于作業(yè)規(guī)劃問題[5-6];但智能算法的編碼方式很難做到表達全部的維修知識信息,更重要的是,對于裝配過程這類工程類問題,運算過程會頻繁得到不可行解,極大地影響了進化效率和準確率[7].Q學習算法作為一種逆向求解的學習算法[8],支持從結果向原因逆向推理,借助啟發(fā)機制,可以有效避免不可行序列參與進化計算.

針對上述問題,選取虛擬維修作業(yè)過程中與操作者相關的典型要素(維修工具、維修行為、裝配類型)作為規(guī)劃內容,構建“維修元”模型作為信息融合設計方案,使用遺傳算法和Q學習算法共同對規(guī)劃問題進行求解.為避免不可行序列參與進化計算,使用零件空間干涉機制和任務特征匹配機制作為啟發(fā)機制,避免在復雜虛擬維修環(huán)境中,得到不符合操作規(guī)程的裝配序列,增強規(guī)劃結果對操作者的指導意義.

1 基于Q學習算法的裝配作業(yè)過程模型

本文將虛擬維修過程離散化為“狀態(tài)—動作”反復轉換的過程,該過程中操作者可以按照某種先后順序或策略完成虛擬訓練過程中的維修任務.相應地,本文將裝配作業(yè)過程中涉及的裝配工具選擇、裝配行為選擇、裝配類型選擇形式化為“動作”概念,與Q學習模型保持一致.為便于描述,在對規(guī)劃問題進行求解之前,將虛擬裝配過程形式化描述為三元組U={S,A,R},其中:S={s1,s2,…,sn}表示虛擬裝配作業(yè)狀態(tài)空間;A={a1,a2,…,an-1}∈{L,F,G}表示導致狀態(tài)發(fā)生變化的動作備選集;R={r(s1,a1),r(s2,a2),…,r(sn,an)}表示“動作”的立即回報值.動作備選集中,L表示工具類備選集,L={lj|j= 1,2,…,J},〈s1,lj〉表示虛擬人在狀態(tài)s1選擇工具lj進行作業(yè);F表示行為類備選集,F={fk|k=1,2,…,P},〈s1,fk〉表示虛擬人在狀態(tài)s1選擇行為fk進行作業(yè);G表示裝配類型備選集,G={gh|h=1,2,…,H},〈s1,gh〉表示虛擬人在狀態(tài)s1選擇裝配類型gh進行裝配,參數J,P,H分別表示對應各“動作”節(jié)點數量.如狀態(tài)s1表示端蓋螺栓,工具lj表示套筒扳手,行為fk表示使用行為,裝配類型gh表示螺栓緊固,則在狀態(tài)s1處,單次裝配操作可描述為O=〈s1,lj∪fk∪gh〉.過程規(guī)劃通常是對狀態(tài)序列進行規(guī)劃[9],但在虛擬場景中,評價虛擬人是否準確完成裝配作業(yè),是通過其是否選擇正確的動作來判斷的.因此,本文將狀態(tài)序列規(guī)劃轉化為動作選擇規(guī)劃,即將狀態(tài)積累回報轉換成動作積累回報,改善虛擬維修環(huán)境中狀態(tài)轉移未知的問題.令sn為裝配作業(yè)目標狀態(tài),裝配作業(yè)過程規(guī)劃步驟如下:

(1) 初始化狀態(tài)集S和動作集A;

(2) 在每個離散時間點t,系統處于當前狀態(tài)st,選擇動作at,到達一個新狀態(tài)st+1=δ(st,at),能夠得到回報值rt=r(st,at);

(4) 設Q(si,ai)為計算機在狀態(tài)si下選擇動作ai獲得的回報值,Q值函數定義如下:

Q(si,ai)=r(si,ai)+

(1)

maxQ(si+1,ai+1)=argmaxV(π)

(2)

為防止虛擬裝配過程中重復選擇動作導致回報值Q(s,a)無限增大,出現無法收斂到最優(yōu)策略的情況,引入回報折算因子γ,0≤γ<1.若γ=0,則只考慮立即回報;若γ接近1,則增強后續(xù)回報的重要程度.式(1)和式(2)中,當前回報值與后續(xù)回報值直接相關,采用這種倒序的迭代算法,經過數次的動作選擇,總能使作業(yè)策略收斂到一穩(wěn)定值,即策略中每個動作a的積累回報值Q(s,a)都是最大的.然而,使用此算法存在風險[10-11],作業(yè)策略可能過度束縛在早期具有較高Q值的動作,而不能探索到其他有更高Q值的動作.因此,本文建立基因組模型,將遺傳算法與Q學習算法相結合,共同對裝配作業(yè)過程規(guī)劃問題進行求解,保證裝配過程信息的全面性和全局收斂效率.

2 面向虛擬裝配作業(yè)過程的混合遺傳算法

以差速器裝配為例(見圖1),將裝配動作中包含的零件、行為、工具和裝配類型等要素融合為一個維修元,一個維修元可表示為

C={B,L,F,G}

式中:B,L,F,G是維修元中4個基本要素,分別為部件、裝配該部件所使用的維修工具、執(zhí)行的裝配行為和裝配類型.維修元支持對維修要素的擴充,具有較好的通用性和可擴展性.為便于描述,將待裝零件抽象為“狀態(tài)”概念,將工具、行為、裝配類

圖1 差速器裝配體三維分解圖Fig.1 Decomposition of differential gear structure

型抽象為“動作”概念,對算法進行描述,具體步驟如下:

(1) 組建初始維修元,并通過維修元的排列組合構建初始裝配作業(yè)序列,如圖2所示.

圖2 初始裝配作業(yè)序列Fig.2 Assembly operation sequence

(2) 根據已知回報值r(s,ai),更新每一個動作ai的Q值,

(3)

令s←s′,直到s為目標狀態(tài),即裝配完畢,得出初始Q值表.

(3) 采用實值編碼的方式,將圖2中的維修元xi作為基因值,構建遺傳算法的初始化染色體X0=[x1x2…xn].

(4) 構造值函數Qi向適應度函數Fi的映射.

(6) 以概率Pc進行交叉操作,

X′←Crossover[X0]

(4)

(7) 分別以概率Pml和Pmf對維修元和維修序列進行變異操作,

X″←Mutation[X′]

(5)

(8) 終止原則.若連續(xù)幾代Q值的差異小于某一較小的閾值或者到達指定的進化代數后,就停止運算.

3 裝配作業(yè)過程規(guī)劃求解步驟

3.1進化策略表示

為便于識別,避免頻繁的譯碼解碼,本文采用實值編碼的方式對問題空間進行編碼.1條染色體即對應了1個裝配作業(yè)序列,使用幾何約束方法和特征匹配方法作為約束條件,保證該作業(yè)序列為可行序列,可行序列表示方法如圖3所示.

圖3 可行序列表示方法Fig.3 Representaiton of feasible sequence

3.2適應度函數與選擇操作

本文采用Q值函數作為遺傳算法的適應度函數,之所以使用Q值函數而不是直接使用回報值r作為適應度函數,因為Q值是從全局角度衡量作業(yè)效率,而回報值r僅是對局部狀態(tài)進行分析,適應度函數F(x)定義如下:

(7)

式中:Qt為第t次迭代時的Q值估計,t為進化代數,染色體復制方法采用輪盤賭選擇法[12].

3.3交叉操作

裝配可行性是交叉時需要考慮的重要問題,因此，交叉操作一要強調繼承父代維修元的相對次序,二要強調繼承父代維修元的絕對位置.本文在兩點交叉的基礎上,采用變長度的方式對交叉片段進行選取,既提高染色體的變化能力,又保證種群的多樣性.具體步驟如下:

(1) 設待裝配部件數目為6,產生一個隨機數σ=2(σ∈[1,5]).

(2) 隨機在父代選取交叉區(qū)域,交叉長度為2,父代種群如圖4所示.

(3) 將交叉區(qū)域維修元插入到另一個體交叉區(qū)域維修元之前,交叉前與交叉后染色體變化如圖5所示.

(4) 這樣交叉后的染色體出現重復的維修元(見過渡個體),在非交叉區(qū)域依次刪除與交叉區(qū)域維修元相同的維修元,得到子代種群,如圖6所示.

圖4 父代種群表達Fig.4 Discription of parent population

圖5 交叉操作Fig.5 Crossover operatior

圖6 刪除操作Fig.6 Delete operator

上述交叉過程滿足了基因重組的要求,并將父代部分序列遺傳至子代,產生了適合進一步進化的子代個體.

3.4變異操作

對于由維修元構成的染色體,變異操作既要考慮裝配序列的改變,也要考慮裝配要素的改變,因此,本文對整體(裝配序列)和個體(維修元)兩部分進行變異操作,步驟如下:

(1) 裝配序列變異.對于選定的染色體Xt=[x1x2…x6],采用逆轉方法進行變異操作,即隨機選取基因段中的兩個點d1和d2作為逆轉點,將兩個逆轉點的基因值對調得到新染色體,如圖7所示.

圖7 逆轉變異算子示意Fig.7 Reverse mutation operator

(2) 維修元變異.逆轉變異是在全局角度對作業(yè)序列進行改變,而對序列中包含多類要素的維修元,同樣需要實施變異操作.針對維修元局部信息,本文采用選擇變異算子對父代染色體進行操作,構建每個部件的匹配特征表.表中包含了每個零件在裝配過程中的可用工具集、可用行為集和可用裝配類型集,使用表中的元素對父代維修元中要素進行替換,達到要素變異的目的,變異方式如圖8所示.

圖8 選擇變異算子示意Fig.8 Selection mutation operation

由圖8可見,首先確定某一維修元(虛線部分)執(zhí)行選擇變異操作,如對零件b2執(zhí)行變異操作,根據零件編號b2搜索特征匹配表中可用工具、行為和裝配類型,并將原有要素進行替換,這樣既保證了選定維修元中各要素能夠隨機的發(fā)生變化,又保證了維修元內部各要素的匹配合理性.

4 規(guī)劃實例與結果分析

4.1規(guī)劃實例

采用混合遺傳算法對裝配作業(yè)過程規(guī)劃進行求解,并做出比較分析.以圖1中差速器為例,構建差速器裝配作業(yè)過程特征匹配表,如表1所示.

表1 差速器裝配過程特征匹配表Tab.1 Task characteristic match Table for gear adjustment

注:“/*”表示匹配內容為空,可選工具為空即為徒手操作.

差速器虛擬裝配作業(yè)過程中,狀態(tài)轉移過程即在初始狀態(tài)下執(zhí)行一系列“維修元”后(即執(zhí)行一個策略π=(a1,a2,…,an),包括使用工具lj、選擇操作行為fk、選擇裝配類型gh)到達目標狀態(tài)的過程.裝配目標為裝配完畢,且目標函數值最大.

對混合遺傳算法進行驗證之前,設定折算回報因子γ=0.9,回報值r(s,a)根據式(1)進行求解.設定作業(yè)序列中維修元交叉概率Pc=0.8,變異概率Pm=0.02;維修元中工具要素變異概率Pml=0.02,行為要素變異概率Pmf=0.02,裝配類型要素變異概率Pmf=0.02;回報函數中工具選擇、行為選擇、裝配類型選擇的權重均設定為1,即λ1=λ2=λ3=1;設定回報函數獎勵因子α=2.迭代的每一步,均選取每組染色體中回報值r(s,a)較高的維修元所代表的動作,參與狀態(tài)轉移過程.設最大進化代數G=100,種群規(guī)模設定M=20.為保證初始種群中染色體均由可行序列組成,20個染色體均由操作者自主拆卸產生,使用4元數對維修元進行表達,即b1l1f1g1表達為(1 1 1 1);使用連續(xù)4元組對染色體進行表達,初始種群中,一個可行裝配序列染色體表達如下:(7 0 2 1)(5 3 2 2)(4 2 2 2)(6 2 2 2)(3 1 2 2)(2 2 3 2)(9 3 4 2)(1 0 1 1)(10 0 1 1)(8 2 2 2)(11 5 4 1).其中對于維修元中的某一位,若無匹配內容,則使用0表示.該作業(yè)序列適應度函數為F(X)=532,nl=9,nf=5,ng=4.使用本文所述方法和Q學習算法分別對規(guī)劃問題進行計算,得到進化結果,如圖9所示.

算例中Q學習算法僅找到次優(yōu)解,混合遺傳算法無論在收斂速度和收斂性能方面都比Q學習算法優(yōu)越,得到最優(yōu)作業(yè)序列:(7 0 2 3)(4 2 2 2)(5 2 2 2)(3 2 2 2)(6 2 2 2)(8 2 2 2)(9 2 3 2)(2 2 3 2)(1 0 2 1)(10 0 2 1)(11 2 2 1).該序列中,適應度值F(X)=590,工具更換次數、行為更換次數、裝配類型更換次數分別為nl=3,nf=2,ng=2.

圖9 混合遺傳算法與Q學習算法的性能比較Fig.9Performance comparison between hybrid geneticalgorithm and Q-learning algorithm

5 結語

混合遺傳算法之所以能夠快速收斂,源于它的逆向求解機制和回報機制,它總能在解序列的源頭對規(guī)劃問題進行分析,因此,相對較容易避免不可行序列的計算.多次驗算發(fā)現,使用Q學習算法難以使規(guī)劃結果快速收斂,主要局限在于:缺少特征匹配機制容易導致不可行裝配序列持續(xù)增長,降低了算法的效率,可以預料,若裝配體干涉情況復雜、特征匹配內容數目多,使用Q學習算法必須更多的迭代次數.這對實時性要求較高的虛擬維修環(huán)境來說是不實際的.仿真結果表明,即使在信息含量較大的情況下,混合遺傳算法依然具有較高的全局收斂性,為多信息融合條件下的裝配作業(yè)規(guī)劃問題提供了一種實用的解決方法.

[1] LI J R,KHOO L P,TOR S B.Generation of possiblem multiple components disassembly sequence for maintenance using a disassembly constraint graph[J].International Journal of Production Economics,2006,102(1):51-65.

[2] 于海全,彭高亮,劉文劍.基于虛擬環(huán)境的維修性信息模型的建立[J].兵工學報,2010,31(7):998-1002.

YU H Q,PENG G L,LIU W J.Research on the maintainability information model based on VR[J].Acta Armamentarii,2010,31(7):998-1002.

[3] FREY G.Assembly line sequencing based on Petri-net T-invariants[J].Control Engineering Practice,2000,8(1):63-69.

[4] YEE S,VENTURA J A.A Petri net model to determine optimal assembly sequences with assembly operation constrains[J].Journal of Manufacturing System,1999,18(3):203-213.

[5] CHUNG C,PENG Q.An integrated approach to selective-disassembly sequence planning[J].Robotics and Computer-Integrated Manufacturing,2005,21(4/5):475-485.

[6] 高金蓮,楊杰,李春書.基于遺傳算法的裝配作業(yè)優(yōu)化[J].機械設計,2007,24(1):43-45.

GAO J L,YANG J,LI C S.Optimization of assembling operation based on genetic algorithm[J].Journal of Machine Design,2007,24(1):43-45.

[7] 楊鵬,劉繼紅,管強.面向裝配序列優(yōu)化的一種改進基因算法[J].計算機集成制造系統,2002,8(6):467-471.

YANG P,LIU J H,GUAN Q.An improved genetic algorithm for assembly sequence optimization[J].Computer Integrated Manufacturing Systems,2002,8(6):467-471.

[8] WATKINS C J,DAYAN P.Q-learning[J].Machine Learning,1992,8(3):279-292.

[9] MITCHELL T M.機器學習[M].北京:機械工業(yè)出版社,2003.

MITCHELL T M.Machine learning[M].Beijing:China Machine Press,2003.

[10] JONATHAN D,PARRIS K E,DAVID C.Enhancing computer graphics through machine learning:a survey[J].The Visual Computer,2007,23(1):24-43.

[11] GUO M Z,LIU Y,MALEC J.A new Q-learning algorithm based on the metropolis criterion[J].IEEE Trans on System,Man and Cybernetrics,2004,34(5):2140-2143.

[12] 陳有青,徐蔡星,鐘文亮,等.一種改進選擇算子的遺傳算法[J].計算機工程與應用,2008,44(2):44-49.

CHEN Y Q,XU C X,ZHONG W L,et al.Genetic algorithm with improved selection operator[J].Computer Engineering and Applications,2008,44(2):44-49.

Hybridgeneticalgorithm-basedplanningmethodforvirutalassemblyoperation

JIAOYumin1,XUTing2,LIUBin2,YUGuangliang1

(1.94679 Troop,Nanjing 210038,China; 2.College of Field Engineering,PLA Army Engineering University,Nanjing 210007,China)

To aid in finding the optimal strategy,sequence constraint mechanism and characteristics matching mechanism are proposed,which are suitable for the condition of multi-information fusion.In order to make planning content be more abundant,the concept of maintenance unit is presented,which is suitable for information integration and evolutionary computation.Based on maintenance unit,the assembly sequence model is established.To solve this model,an assembly process planning method based on hybrid genetic algorithm is put forward.To aid in finding the optimal strategy,sequence constraint mechanism and characteristics matching mechanism are proposed,which are suitable for the condition of multi-information fusion.

hybrid genetic algorithm; virtual assembly operation; process planning; maintenance unit

TP 391.9

A

1672-5581(2017)04-0342-06