基于組合馬爾科夫模型的工序推送方法*

畢 東，王裴巖，張桂平

(沈陽航空航天大學(xué) 人機(jī)智能研究中心, 沈陽 110136)

0 引言

工藝編制作為連接產(chǎn)品設(shè)計與制造的橋梁，在產(chǎn)品快速更新迭代的環(huán)境下，仍作為諸多企業(yè)制約產(chǎn)品周期的重要因素[1]。雖然許多企業(yè)采用較為先進(jìn)的計算機(jī)輔助工藝規(guī)劃(Computer Aided Process Plan)系統(tǒng)來加快工藝編制的速度，使其編制的過程電子化、自動化，一定程度上提升了工藝編制的水平[2-3]。但是目前工藝編制還是過分的依賴于人的經(jīng)驗，工藝編制的水平往往受到工藝編制人員的經(jīng)驗程度影響，出現(xiàn)嚴(yán)重水平差異。

飛機(jī)鈑金零件工藝設(shè)計是指根據(jù)給定的最終成形零件的信息，可用的資源信息和工藝信息，設(shè)計從板料到制造零件過程中的加工方案，其所得到的工藝文件為零件制造指令(fabrication order，F(xiàn)O)[4]。其中，工藝流程信息是FO的核心組成部分，從原料到成品的加工工序進(jìn)行安排[5]。工藝流程信息的編制需要考慮零件材料等多方面信息，對于工藝編制人員經(jīng)驗要求較高，多數(shù)工藝編制人員還處于參考典型工藝案例和工藝知識檢索的狀態(tài)，所以需要一種根據(jù)當(dāng)前編制能夠?qū)崟r的推送工序的方法來改善當(dāng)前現(xiàn)狀。

國內(nèi)外學(xué)者對工藝編制中知識推送技術(shù)進(jìn)行相關(guān)的研究，但是具體到工序的推送很少。多數(shù)使用相似度和聚類分析方法[6-9]得到典型工藝或典型工藝路線而進(jìn)行推送，工藝編制人員還需對所推送的多個工藝案例進(jìn)行查閱分析，選擇其中可復(fù)用的部分，沒有讓工藝編制人員完全從知識檢索中解放出來。文獻(xiàn)[10]提出了工序模型驅(qū)動的工藝設(shè)計方法，每規(guī)劃一道工序，生成一個工序模型，然后基于該工序模型進(jìn)行下一道工序的規(guī)劃。該方法新穎可行，但是需要構(gòu)建n-1個模型，每個模型需要進(jìn)行三維模型的特征提取過于復(fù)雜。文獻(xiàn)[11]提出了幾何演變驅(qū)動下的機(jī)加工藝知識表示方法和以此為基礎(chǔ)的工藝知識模型對機(jī)加工序進(jìn)行推送，雖然該方法能夠?qū)庸ぬ卣鞯膸缀窝葑兲匦赃M(jìn)行表達(dá)和詮釋，從多個零件工藝實例中提取并重組得到下一步工序，但是同時要求工藝編制人員自身技術(shù)水平過高。

面向工藝編制過程中工序推送問題，本文提出一種基于組合馬爾科夫模型的工序推送方法。該方法能夠構(gòu)建描述工序間關(guān)系的馬爾科夫模型，在不改變其當(dāng)前工作狀態(tài)的前提下，根據(jù)編制人員當(dāng)前的輸入，實時感知編制人員行為并分析其當(dāng)前需求，推送當(dāng)前場景下所需工序。與現(xiàn)有方法相比，本文所提出的方法基于工藝數(shù)據(jù)構(gòu)建模型具有較好的普適性，并且單步工序推送更貼合工藝編制人員的實際應(yīng)用場景，能夠減少工藝編制人員大量重復(fù)的檢索工作，同時該方法實際應(yīng)用中對于工藝編制人員自身水平要求較低，在2348份飛機(jī)鈑金零件工藝數(shù)據(jù)上驗證了該方法的有效性。

1 工藝編制中的工序推送

工藝編制人員在實際的工藝編制過程中，大多會根據(jù)編寫的工藝零件的結(jié)構(gòu)特征、加工特點(diǎn)等內(nèi)容，來合理安排后續(xù)工序。由此可見，工序間一定存在某種相關(guān)性，為此可以根據(jù)工藝編制人員當(dāng)前編寫的工序內(nèi)容，智能的推送后續(xù)工序，以此來提高工藝編制的效率。

經(jīng)過對2348份飛機(jī)鈑金零件制造指令文件統(tǒng)計分析發(fā)現(xiàn)，在支架、蒙皮、框肋等不同零件組件類別中，共有86種不同工序，工序間具有強(qiáng)關(guān)聯(lián)性，例如當(dāng)前工序為備料，下一步工序97.82%為檢驗；當(dāng)前工序為劃線，下一步工序34.62%為切割外形、38.1%為銑切外形、16.27%為手工剪切。正是因為這種強(qiáng)關(guān)聯(lián)性，工藝流程信息也可以理解為由工序組成的有序序列，那么可以用機(jī)器學(xué)習(xí)方法去進(jìn)行有序序列中元素的預(yù)測。在人機(jī)協(xié)同的編制環(huán)境下，工藝編制人員接受編制任務(wù)后，根據(jù)當(dāng)前編制狀態(tài)建立工序知識需求，然后根據(jù)推送算法推送工序的候選集合，工藝編制人員根據(jù)當(dāng)前需求進(jìn)行選擇，然后更新工序知識需求，重復(fù)以上步驟，直至工藝編制人員完成編制，具體工序推送實現(xiàn)過程如圖1所示。

本文所提出的工序推送方法嵌入到工藝編制業(yè)務(wù)系統(tǒng)中，可以輔助工藝編制人員在當(dāng)前編制情況下實時準(zhǔn)確的推送所需工序。

圖1 工藝流程信息編制流程

2 組合馬爾科夫模型算法

將組合馬爾科夫模型方法運(yùn)用到工藝編制過程中，讓計算機(jī)學(xué)習(xí)工藝編制過程中內(nèi)在關(guān)聯(lián)的工序，進(jìn)而實現(xiàn)人機(jī)協(xié)同的工藝編制，提升工藝編制質(zhì)量和效率。下面詳細(xì)介紹馬爾科夫模型建立和組合馬爾科夫模型算法。

2.1 馬爾科夫模型建立

馬爾科夫模型由俄國數(shù)學(xué)家馬爾科夫于1907年提出[12]，在實際中有廣泛應(yīng)用，常用來對序列數(shù)據(jù)建模，進(jìn)行位置預(yù)測、用戶推薦和DNA分類等研究[13-14]。工序流程是一個由工序組成的有序序列，所以本文將馬爾科夫模型應(yīng)用到工序推送。

假設(shè)一段工序序列是...,Xn-2,Xn-1,Xn,Xn+1,...，工序Xn+1出現(xiàn)的概率與其之前的N個工序有關(guān)，而與過去的工序無關(guān)，即為N階馬爾科夫模型。例如二階馬爾科夫模型，工序Xn+1的出現(xiàn)僅僅依賴于前面兩個工序Xn-1和Xn，如公式(1)。

P(Xn+1|X1X2...Xn)=P(Xn+1|XnXn-1)

(1)

在計算P(Xn|X1X2...Xn-1)的轉(zhuǎn)移概率時，本文采用極大似然估計法進(jìn)行求解，如公式(2)，其中C(X1X2...Xn)表示X1X2...Xn出現(xiàn)次數(shù)。

(2)

研究發(fā)現(xiàn)，隨著階數(shù)的增大計算的數(shù)量級成指數(shù)上升趨勢，并且數(shù)據(jù)稀疏性程度增大[15]，本文共建立了5個基礎(chǔ)模型，1階、2階、3階、4階和5階馬爾科夫模型。

表1中數(shù)據(jù)源自飛機(jī)鈑金零件制造指令文件中工序訓(xùn)練的N階馬爾科夫模型，以工序片段“切割外形、鉆孔、擴(kuò)孔、去毛刺、檢驗”為例，標(biāo)準(zhǔn)答案工序為“稱重”，對比N階馬爾科夫模型，分析發(fā)現(xiàn)：①標(biāo)準(zhǔn)答案工序“稱重”不在1階推送下一步工序集合(Top1～Top5)內(nèi)，而是排在了第15位，說明低階模型只對高頻工序有效，低階模型由于未能充分利用歷史工序信息，存在精度不高問題。②隨著階數(shù)的增大，推送工序覆蓋率降低，5階模型推送工序平均為2.7個，說明高階模型發(fā)生工序覆蓋率低的問題。③在4階和5階模型中出現(xiàn)工序等概率事件，經(jīng)對模型統(tǒng)計發(fā)現(xiàn)，隨著階數(shù)的增加，工序等概率事件機(jī)率增大，這一現(xiàn)象嚴(yán)重影響推送工序的排序準(zhǔn)確率。

表1 N階馬爾科夫模型工序推送示例

2.2 組合馬爾科夫模型

馬爾科夫模型存在階長選擇的問題，為了兼顧模型的精度和復(fù)雜度，學(xué)者們提出了能夠建立任意階長的變階馬爾科夫模型[16]，根據(jù)實際情況動態(tài)自適應(yīng)使用合適的階長進(jìn)行計算，該模型得到廣泛的研究與應(yīng)用[17-19]。但是在本文工藝編制的應(yīng)用場景下，針對工序推送發(fā)現(xiàn)變階馬爾科夫模型方法出現(xiàn)推送工序覆蓋率低，推送工序等概率出現(xiàn)次數(shù)較多等問題，對推送工序的準(zhǔn)確率和排序準(zhǔn)確度影響較大。為此，本文提出組合馬爾科夫模型，考慮融合更多歷史信息，即將高階馬爾科夫模型和低階馬爾科夫模型進(jìn)行線性組合。

組合馬爾科夫模型在最高階n的選擇上和變階馬爾科夫模型相同，使用Katz的BackOff模型思想實現(xiàn)。優(yōu)先考慮概率計算的準(zhǔn)確率，從高階馬爾科夫模型進(jìn)行嘗試，發(fā)現(xiàn)推送目標(biāo)工序在模型中出現(xiàn)次數(shù)小于閾值時再降低馬爾科夫模型階數(shù)，通常閾值設(shè)置為1。組合馬爾科夫模型確定最高階n后，將n,n-1,...,1階馬爾科夫模型進(jìn)行線性組合，然后計算下一步工序出現(xiàn)概率，如公式(3):

(3)

其中，P(n)為工序X在N階模型中的轉(zhuǎn)移概率，參數(shù)λ滿足λ1+λ2+...+λn=1。

本文在參數(shù)λ的選擇上對比分析了三種方法分別是等值參數(shù)、等差參數(shù)以及動態(tài)參數(shù)。如下所示：

(1) 等值參數(shù)，將參數(shù)λ進(jìn)行等值分配，可以理解為高階模型和低階模型同等重要，具體如公式(4)：

(4)

(2) 等差參數(shù)，為保證高階模型優(yōu)先性，使高階模型參數(shù)大于低階模型參數(shù)，根據(jù)最高階n計算公差，令λ1等于公差，參數(shù)服從等差數(shù)列進(jìn)行分配，具體如公式(5)，其中i≤n。

(5)

(3) 動態(tài)參數(shù)，同樣保證高階模型的優(yōu)先性，與等差參數(shù)不同，需要根據(jù)當(dāng)前狀態(tài)信息對參數(shù)進(jìn)行計算，先統(tǒng)計各階模型中下一步工序總次數(shù)，然后取倒數(shù)并歸一化，參數(shù)λ隨工序出現(xiàn)次數(shù)而變化，如高階模型中工序出現(xiàn)的次數(shù)較少，與之對應(yīng)其參數(shù)越大，具體如公式(6)：

(6)

其中，C(Xi)表示該工序在模型中出現(xiàn)的次數(shù)。動態(tài)參數(shù)與前兩種參數(shù)相比，動態(tài)參數(shù)能夠更好的平衡多個馬爾科夫模型之間的關(guān)系，即能保證高階模型的優(yōu)先性，也能使低階模型發(fā)揮作用。

3 實驗

3.1 實驗設(shè)置

實驗數(shù)據(jù)使用2348份鈑金零件制造指令文件。經(jīng)統(tǒng)計，平均每份文件有26.24步工序，共有86種不同工序。為驗證本文方法在同一組數(shù)據(jù)集下是否有效，做十折交叉驗證。模擬工藝編制人員工作，根據(jù)工藝編制人員已輸入的當(dāng)前工序，使用基于組合馬爾科夫模型方法得到推送工序結(jié)果集合，按照概率值大小選擇排序前5(Top1～Top5)作為最終推送。

評價指標(biāo)采用MRR(Mean Reciprocal Rank)和準(zhǔn)確率(Top1～Top5 precision)。本實驗對所推送工序候選集合進(jìn)行排序，因此評價指標(biāo)采用了信息檢索中常用的MRR，MRR關(guān)心推送集合內(nèi)準(zhǔn)確答案的位置，位置越靠前則表明用戶體驗越好。MRR和準(zhǔn)確率P定義如下：

(7)

(8)

其中，rank表示工序排名，如果目標(biāo)工序出現(xiàn)在推薦結(jié)果結(jié)集合的第二位，那么rank=2；C1表示目標(biāo)工序出現(xiàn)在推送結(jié)果集合中的次數(shù)，C2表示推送總次數(shù)。

3.2 實驗結(jié)果與分析

本文列舉了基于N階馬爾科夫模型方法和組合馬爾科夫模型的工序推送方法，并對比分析N階馬爾可夫模型方法、變階馬爾科夫模型方法以及組合馬爾科夫模型方法。

表2列出了N階馬爾科夫模型在鈑金零件制造工藝數(shù)據(jù)集上驗證推送工序的實驗結(jié)果。從表2可見：① 2階馬爾科夫模型推送工序準(zhǔn)確率達(dá)0.9483，MRR值達(dá)0.8248，馬爾科夫模型能夠有效的對工序進(jìn)行推送，能夠保證排序靠前的工序滿足編制人員的需求，說明馬爾科夫模型對工序推送問題的可行性。② 1階馬爾科夫模型對工序推送效果最差，1階模型只考慮當(dāng)前一步工序，使得模型的精度低，只對高頻工序有效；階馬爾科夫模型對工序推送效果最好，2階模型和1階模型相比增加一步工序信息，模型描述工序間關(guān)系更精確，使推送準(zhǔn)確率大幅提高；隨著階數(shù)的增加，推送工序效果明顯下降，雖然高階模型對于工序間關(guān)系描述精確，但是需要克服高階模型數(shù)據(jù)稀疏，推送工序覆蓋率低等問題。

表2 N階馬爾科夫模型實驗結(jié)果

表3列出了3種不同參數(shù)的組合馬爾科夫模型在鈑金零件制造工藝數(shù)據(jù)集上驗證推送工序的實驗結(jié)果。從表3可見：①隨著階數(shù)的增加，MRR和準(zhǔn)確率不斷增大，組合馬爾科夫模型方法解決了N階馬爾科夫模型方法中存在的問題，不僅提升了工序推送結(jié)果的準(zhǔn)確率，而且保證了推送工序的排序準(zhǔn)確度。②組合馬爾科夫模型推送方法，MRR最高為0.8516，準(zhǔn)確率最高為0.9642，推送工序結(jié)果可以滿足用戶需求。

表3 組合馬爾科夫模型實驗結(jié)果

針對不同參數(shù)推送工序結(jié)果進(jìn)一步分析發(fā)現(xiàn)：等值參數(shù)效果最差，動態(tài)參數(shù)效果最好。同階模型不同參數(shù)推送工序結(jié)果不同，原因在于保證高階模型推送工序的優(yōu)先性問題和高階模型中有大量的等概率工序等影響因素。等值參數(shù)分配參數(shù)時高階和低階相等對于該情況影響不大；等差參數(shù)分配參數(shù)時高階和低階相差太大，雖然解決高階模型等概率工序問題，保證高階模型推送結(jié)果的絕對優(yōu)先性，使得推送工序排序準(zhǔn)確率有所提升，但是忽略了低階模型信息，使工序推送準(zhǔn)確率受影響；動態(tài)參數(shù)根據(jù)統(tǒng)計結(jié)果進(jìn)行分配參數(shù)，保證了高階模型推送結(jié)果的優(yōu)先性，同時使低階模型發(fā)揮作用，使推送工序更加精準(zhǔn)。

表4列出3種工序推送方法的結(jié)果。對比發(fā)現(xiàn)：①變階馬爾科夫模型方法與2階馬爾科夫模型方法相比，雖然變階馬爾科夫模型推送的工序排序準(zhǔn)確度高，但是出現(xiàn)了推送工序覆蓋率低等問題。②組合馬爾科夫模型方法與N階馬爾科夫模型方法相比，MRR提高0.0268、準(zhǔn)確率提高0.0159，組合馬爾科夫模型方法有效解決了N階馬爾科夫模型階長選擇問題，保證了高階模型的優(yōu)先性，使推送工序更精確。③組合馬爾科夫模型方法與變階馬爾科夫模型方法相比，MRR提高0.011、準(zhǔn)確率提高0.0255，組合馬爾科夫模型方法即保證了高階模型的優(yōu)先性同時也使低階模型發(fā)揮作用，融合低階模型信息后有效地解決了高階模型中出現(xiàn)的工序等概率事件問題和高階模型工序覆蓋率低問題。

表4 對比實驗結(jié)果

4 總結(jié)

本文提出了基于組合馬爾科夫模型的工序推送方法，模擬工藝編制人員在工藝編制環(huán)境下根據(jù)編制人員當(dāng)前輸入實時的推送工序。該方法能夠有效地對工序進(jìn)行實時推送，同時能夠保證排序靠前的工序即為工藝編制人員所需。與傳統(tǒng)的N階馬爾科夫模型方法和變階馬爾科夫模型方法相比，該方法解決高階模型過擬合問題和低階模型精度問題，同時使推送工序的準(zhǔn)確率和排序準(zhǔn)確度有明顯提升。未來，將嘗試根據(jù)工藝編制人員自身編制特點(diǎn)構(gòu)建個性化模型，增加推送內(nèi)容，然后推送更多工序知識。