王 琳，張永健，鐘詩勝

（1.哈爾濱工業(yè)大學 機電工程學院，黑龍江 哈爾濱 150001；2.哈爾濱工業(yè)大學（威海）船舶與海洋工程學院，山東 威海 264209）

0 引言

一般而言，企業(yè)在對產(chǎn)品進行工藝規(guī)劃時都是參照原有的工藝過程，而隨著企業(yè)的不斷發(fā)展，積累了大量的工藝數(shù)據(jù)，這些工藝數(shù)據(jù)可以作為企業(yè)的知識資源。如何挖掘這些知識并對其進行有效利用，是大規(guī)模定制（Mass Customization，MC）生產(chǎn)模式在企業(yè)制造端成功實施的關鍵。典型工藝過程是企業(yè)為典型產(chǎn)品（典型零件或部件）制定的普遍適用的工藝過程，在對與該典型產(chǎn)品相似的產(chǎn)品進行工藝規(guī)劃時，可借用該過程并對其進行適量修改，即可作為新零部件的工藝過程，以此提高產(chǎn)品工藝規(guī)劃的效率與質量。

對于典型工藝過程的獲取，目前國內(nèi)外的相關研究主要集中在工藝過程的相似性和聚類分析等方面。文獻［1］用工藝路線間的距離來衡量工藝路線的相似度，并采用凝聚層次聚類算法實現(xiàn)工藝路線的聚類劃分；文獻［2］將最長相似子序列作為度量因子，對工藝路線進行多級相似度綜合度量，并采用粒子群優(yōu)化算法實現(xiàn)了工藝路線的智能聚類劃分；文獻［3］通過建立基于特征的零部件信息模型，研究了基于實例推理的工藝相似性度量。這些研究主要對工藝序列的相似性和聚類問題給出了較好的解決方案，但是工藝過程的相似性度量方法仍不理想，另外受各工序與產(chǎn)品特征和車間資源之間存在相關性、工藝過程表達的規(guī)范性等因素的影響，計算結果與實際情況往往偏差較大。因此，需要通過建立工藝過程的數(shù)學模型，以提高其相似性的計算精度。

為提高工藝設計的效率，并對工藝規(guī)劃過程進行優(yōu)化，將圖論引入工藝規(guī)劃的研究中。文獻［4］提出用一般圖對工藝規(guī)劃進行描述的方案；文獻［5－6］通過裝配關系的特征，采用（加權）有向圖對裝配工藝建立描述模型；文獻［7］采用有向圖對數(shù)控工藝中的機床工作計劃進行數(shù)學描述；文獻［8］為實現(xiàn)零件工藝的聚類，基于加權有向圖建立了零件工藝的描述模型，將工藝聚類問題轉化為有向圖的聚類問題。有向圖在社會網(wǎng)絡和信息網(wǎng)絡等方面應用廣泛，而與此相關的有向圖聚類的研究成果較為豐富，如歐拉距離、曼哈頓距離、余弦相似度、基于Jaccard指數(shù)的相似度量等方法在有向圖頂點的相似性度量方面應用廣泛［9］；屬性圖能夠對復雜網(wǎng)絡進行有效描述，鄰域隨機游動距離、Bayesian隨機模型等為屬性圖的聚類提供了可行方案［10－12］。

典型工藝過程發(fā)現(xiàn)技術是在歷史工藝過程數(shù)據(jù)中，利用數(shù)據(jù)挖掘技術，對大量的工藝過程進行分析，研究工藝過程中工藝單元之間的關系，獲取工藝過程所具有的共性，從而獲得典型工藝過程的方法。本文采用屬性有向圖對工藝過程進行描述，通過工藝過程屬性有向圖結構與屬性相似度的計算來提高工藝過程相似性的計算精度；基于工藝過程的相似性，采用近鄰傳播算法發(fā)現(xiàn)典型工藝過程。

1 典型工藝過程發(fā)現(xiàn)問題的數(shù)學模型

1.1 基于屬性有向圖的工藝過程描述模型

在有向圖結構中，節(jié)點表示對象，每條邊都有方向，表示對象之間的關系。本文各節(jié)點包含不同的屬性描述信息，因此，首先給出以下定義。

定義 屬性有向圖。屬性有向圖可表示為一個四元組G＝（V，E，A，F(xiàn)），其中：V為M個節(jié)點的集合，E＝｛（vi，vj）｜1≤i，j≤M，i≠j｝為有向邊的集合，A＝｛a1，a2，…，aL｝為V中節(jié)點的L種分類屬性的集合。每個節(jié)點vi的屬性可用長度為L的屬性向量p（vi）＝［a1（vi），a2（vi），…，aL（vi）］進行描述，其中aj（vi）為節(jié)點vi在屬性aj上的觀測值。F＝｛f1，f2，…，fL｝為L個函數(shù)的集合，其中fi：V→D（ai）為指定某節(jié)點vi的屬性ai在其值域D（ai）中的取值。

一個工藝過程通常由一組工序經(jīng)過有序排列構成，而由于工藝種類的差別或工藝編制人員習慣的不同，導致工藝過程中工序的表達與層次劃分千差萬別。為便于工藝過程屬性有向圖模型的建立，在此定義工藝過程由一組工藝單元構成，其中工藝單元是指針對產(chǎn)品的某制造特征采用何種設備完成的特定操作。給定一組工藝單元集合，作為工藝規(guī)劃時工藝單元的選擇空間Sp，工藝規(guī)劃可以描述為在符合產(chǎn)品技術要求及工藝原理的條件下，Sp中的全部或部分工藝單元按照一定的順序進行排列。工藝過程可以用屬性有向圖進行建模，其中屬性有向圖G中的節(jié)點集V表示工藝過程的工藝單元集，V中的每個元素可以用屬性向量進行描述，即

式中：pn為工藝單元名稱；pf為工藝單元所對應的產(chǎn)品特征；pm為產(chǎn)品特征的關鍵制造信息（制造特征參數(shù)）；po為產(chǎn)品特征所對應的制造方法；pe為產(chǎn)品特征所對應的設備；pr為產(chǎn)品特征所對應的制造技術要求。

屬性向量中的各屬性值由函數(shù)集合F中相應的函數(shù)指定，有向邊集E表示工藝過程中工藝單元的操作順序。某類零件工藝過程可以用如圖1所示的有向圖模型表示，圖中虛線表示該類零件可以由兩種工藝過程實現(xiàn)其加工，因此，工藝過程的有向圖模型即為有向無環(huán)圖中最簡單的線性圖。

給定兩個工藝過程Gα和Gβ，兩者的相似度表示為S（Gα，Gβ），可以由工藝單元相似度SN（Gα，Gβ）和工藝路線相似度SS（Gα，Gβ）加權獲得，即

式中ω為加權系數(shù)，0≤ω≤1。

1.2 工藝過程有向圖模型中相似度算法

1.2.1 工藝單元相似性

對相似產(chǎn)品（包括零部件）而言，其工藝過程一般具有相似性，但在具體產(chǎn)品進行工藝規(guī)劃時，相似產(chǎn)品的工藝過程所包含的工藝單元的數(shù)量難以保證相同；即使工藝單元數(shù)量相同，各對應的工藝單元的具體內(nèi)容也很難保證一致；因此相似產(chǎn)品的工藝過程的工藝單元通常不存在完全等價的對應關系。工藝單元之間的差異性可由工藝單元節(jié)點的相似度來度量，對工藝單元節(jié)點進行匹配，基于匹配結果可得到整個工藝過程關于工藝單元的相似度。

Kuhn－Munkres算法是加權二分圖最優(yōu)匹配問題常用的求解算法，該算法基于可行頂標的概念，通過不斷修改頂標搜尋二分圖相等子圖的完備匹配。Kuhn－Munkres算法的具體步驟不在此贅述，若通過Kuhn－Munkres算法得到二分圖Gαβ的最優(yōu)匹配為M，則可獲得工藝單元相似度SN（Gα，Gβ），

前文中提到工藝單元節(jié)點可用特征向量進行描述，因此工藝單元節(jié)點的相似度可用其特征向量間的相似度進行度量，本文采用余弦相似度來度量。有兩個工藝單元節(jié)點的特征向量pi＝（pi1，pi2，…，piL）和pj＝（pj1，pj2，…，pjL），則這兩個節(jié)點的相似度可用兩向量間夾角的余弦表示，即工藝單元節(jié)點的相似度

1.2.2 工藝路線相似性

工藝過程的工藝路線相似性可通過圖的鄰接矩陣體現(xiàn)。工藝過程Gα的鄰接矩陣可表示為Eα，其中元素的大小作為工藝單元節(jié)點Cαi到Cαj的有向邊的權重，表示工藝單元Cαj對Cαi的依賴程度∈［0，1］。當＝0時，表示兩工藝單元節(jié)點間無關聯(lián)關系；當＝1時，表示工藝單元Cαj完全依賴于工藝單元Cαi。當對兩個工藝過程Gα和Gβ進行比較時，由于工藝過程中的工藝單元節(jié)點不對等，需要對相應的鄰接矩陣進行規(guī)范。假設Gα和Gβ分別為如圖1所示的兩個工藝過程v1→v2→v3→v4→v5→v7和v1→v2→v6→v5→v7，分別對其鄰接矩陣進行規(guī)范化，得到規(guī)范化結構矩陣NEα和NEβ，如圖3所示。

由工藝過程Gα和Gβ的規(guī)范化結構矩陣得到結構比較矩陣DEαβ，矩陣中的元素

由此可得工藝過程Gα和Gβ的結構比較矩陣，如圖4所示。

由工藝過程Gα和Gβ的結構比較矩陣，可以得到工藝過程Gα和Gβ的工藝路線結構相似度

式中：N為規(guī)范化結構矩陣的列數(shù)；若≠1，則xij＝1，否則xij＝0。

2 典型工藝過程聚類

設有工藝過程集合GS，其大小為N，通過前文方法可以得到工藝過程集合GS中任意兩工藝過程Gi和Gj的相似度S（Gi，Gj），其中i，j∈｛1，2，…，N｝。工藝過程集合的兩兩相似度可以構成其相似度矩陣SIMG＝［S（Gi，Gj）］N×N?；谠撓嗨凭仃噷に囘^程集合進行聚類分析，進而可挖掘典型工藝過程。工藝過程的聚類具有聚類數(shù)量未知的特點，近鄰傳播（Affinity Propagation，AP）聚類算法［13］無需指定聚類數(shù)目及初始聚類的中心點，而且該算法運算速度快、穩(wěn)定性好、聚類精度高，滿足工藝過程聚類的實際需求。因此，本文基于近鄰傳播聚類，結合工藝過程聚類的有效性評價，建立典型工藝過程挖掘的半監(jiān)督聚類算法。

2.1 工藝過程聚類的有效性及評價

設工藝過程集合GS被聚為K類，Ck表示第k個聚類，1＜k≤K，gk表示Ck的聚類中心。gk作為聚類中心，與聚類Ck中其他工藝過程最為相似，聚類Ck中的其他工藝過程可以通過對聚類中心gk進行少許修改而獲得。因此，工藝過程的聚類中心具有典型性，可作為典型工藝過程。在聚類Ck中，滿足simG（gi，gk）＜αk，其中gi∈Ck，1≤i≤｜Ck｜，則稱該聚類的工藝過程集合為聚類中心gk的鄰域，αk為鄰域半徑。某聚類為一個有效的聚類，需滿足以下條件：①聚類Ck中工藝過程的數(shù)量應滿足具體要求，即｜Ck｜≥η，η為聚類中最少的工藝過程數(shù)量，若｜Ck｜＜η，則可認定該聚類不具備足夠的參考價值；②聚類中心gk與聚類Ck中其他工藝過程之間的相似度應滿足特定的約束，即當聚類中心gk的鄰域半徑αk小于規(guī)定值時，該聚類中心作為典型工藝過程才具有意義。

在聚類完成后，需對工藝過程聚類結果的優(yōu)劣進行評價。Silhouette指標作為眾多評價指標之一，由于其性能好、簡單易用，故將其作為工藝過程聚類的評價指標。Silhouette指標體現(xiàn)了聚類內(nèi)部的緊密程度和聚類之間的稀疏程度。對于任意有效工藝過程聚類Ci中的任一工藝過程實例gi，其Silhouette指標為

式中：a（i）為工藝過程實例gi與工藝過程聚類Ci中其他工藝過程實例的平均距離，

b（i）為工藝過程實例gi與其他有效工藝過程聚類的距離，

單個工藝過程聚類中所有工藝過程實例的Sil平均值包含了該類的緊密性，而整個工藝過程數(shù)據(jù)集的所有工藝過程實例的Sil平均值則反映了聚類結果的質量，Silhouette指標越大表示聚類質量越好。

2.2 基于近鄰傳播聚類的典型工藝過程發(fā)現(xiàn)算法

近鄰傳播聚類算法是在由聚類樣本之間的相似度形成的相似矩陣SIM的基礎上進行聚類的，而矩陣元素的取值一般為距離的負值。對于工藝過程聚類，AP算法將所有工藝過程樣本作為可能的聚類中心，并通過樣本間不斷地進行信息傳遞形成最終聚類。在工藝過程樣本之間存在可信度r（i，j）和可用度a（i，j）兩種信息量參數(shù)。其中：r（i，j）是指相對于其他工藝過程，gj適合作為gi的典型工藝過程的程度；a（i，j）是指相對于其他工藝過程，gi選擇gj作為其典型工藝過程的合適程度。AP算法的核心過程就是兩個信息量交替更新的過程，如式（10）～式（12）所示：

式中sim（gi，gj）為相似矩陣SIM的矩陣元素，一般取sim（gi，gj）＝－（1－simG（gi，gj）），i≠j。

鑒于前文對工藝過程聚類有效性的闡述，將AP算法用于工藝過程的聚類時需做以下工作：

（1）典型工藝過程的過濾初選 由于AP算法將所有工藝過程樣本都視為潛在的聚類中心，在考慮工藝過程聚類的有效性時，可以對工藝過程數(shù)據(jù)樣本進行必要的過濾篩選。根據(jù)有效聚類的條件，對于給定的工藝過程樣本gi，若｜N（gi，ε）｜＜η，則gi不能作為有效聚類的中心，因此可在AP算法初始化時將其對應的偏好參數(shù)設置為最小值；若｜N（gi，ε）｜＝0，則gi為游離的工藝過程，可從工藝過程的數(shù)據(jù)集中直接刪除以減少算法的復雜度。

（2）相似度矩陣的稀疏化 由有效聚類的條件可知，聚類中心的鄰域半徑允許取的最大值為ε，而AP算法迭代過程中可信度與可用度的信息傳遞只需在相似度小于ε的工藝過程樣本之間產(chǎn)生。因此，對相似度矩陣SIM的所有元素進行遍歷，將相似度大于ε的元素設置為最小值，從而將相似度矩陣稀疏化。

（3）最佳聚類數(shù)的確定 在AP算法中，偏好參數(shù)p影響著最終聚類的數(shù)目，由于p的取值暫無確定的方法，在給定取值的情況下所得的聚類結果不能確保為最優(yōu)結果。本文參照文獻［14］給出的確定偏好參數(shù)取值區(qū)間［pmin，pmax］的方法，通過調(diào)節(jié)步長pstep遍歷取值空間，首先通過Silhouette指標來評價聚類的有效性，而后采用IGP指標［15］對有效的聚類結果進行評價，以獲得最佳聚類數(shù)目。IGP指標是基于概率統(tǒng)計思想提出的有效性評價指標，用來衡量在某一聚類中距離每個樣本最近的樣本是否在同一聚類中。對于類標為k的聚類，IGP指標定義為

式中：jN為距離樣本j最近的樣本；Class（j）為樣本j的類標；＃為滿足條件的個數(shù)。

所有有效聚類的IGP指標越大，表示聚類的質量越好，其最大值對應的聚類數(shù)即為最佳聚類數(shù)。

基于以上工作，可以得到基于AP算法的工藝過程半監(jiān)督最優(yōu)聚類算法流程，如圖5所示。

3 實例驗證

下面以衛(wèi)星結構板的制造工藝為研究對象，驗證典型工藝過程發(fā)現(xiàn)算法的有效性。衛(wèi)星結構板是各型號衛(wèi)星上都大量采用的一類典型件，由于其功能、結構基本相似，研制流程基本一致，涵蓋了面板機加、蜂窩芯材機加、嵌入件機加、嵌入件裝配膠接等工藝過程。本文以面板機加工藝為例，從某衛(wèi)星研制單位的結構板的歷史工藝中取100個面板機加工藝過程實例，由于所取得的工藝過程實例的原始表達不能完全滿足建立屬性有向圖模型的條件，根據(jù)1.1節(jié)中的描述，對工藝過程實例的表達進行再組織，建立了以備料、鈑、銑輪廓、鉆孔、鏜孔、料＿檢、鈑＿檢、數(shù)＿檢和入庫等為工藝單元為基礎的工藝過程實例庫，對該工藝過程實例庫進行聚類分析并發(fā)現(xiàn)面板機加的典型工藝過程。由結構板面板材料、制造特征及其關鍵參數(shù)等因素，可以確定面板的機加工藝分為5種類型，包括一般金屬面板機加兩類、加強金屬面板機加兩類和復合材料面板機加一類。所取的100個面板機加工藝過程實例包含這5種類型的工藝過程，其中包含了10個特殊面板機加工藝作為干擾樣本。

衛(wèi)星結構板機加工藝過程聚類設置其有效聚類中所包含的最少工藝過程實例數(shù)為15，最大鄰域半徑為0.5，偏好參數(shù)調(diào)節(jié)步長為0.05。采用上文的聚類算法對衛(wèi)星結構板機加工藝過程實例進行聚類。當偏好參數(shù)p＝－0.65時，聚類評價指標Sil取得最大值3.349 6，此時，聚類數(shù)目為6和有效聚類數(shù)目為5，同時有效聚類數(shù)目為5時，其IGP指標取得最大值4.721 9，如圖6和圖7所示。參照文獻［16］中偏好參數(shù)的選取方法，由兩圖中曲線的變化趨勢可知，p較小時，聚類中所包含的工藝過程實例數(shù)量較多，有效聚類數(shù)量與實際聚類數(shù)量相近，聚類質量較高，且Sil與IGP指標變化趨勢一致。此外，數(shù)據(jù)挖掘中常用的聚類方法還包括k－means方法、層次聚類方法等，其中，k－means方法對初始聚類中心的選擇較為敏感，且聚類之前需指定目標聚類數(shù)目，不適用于典型工藝過程的聚類；層次聚類雖然無需事先確定聚類數(shù)目，但根據(jù)聚類層次樹來確定最終的聚類結果仍存在困難，在此以所選取的工藝過程實例之間的相似度作為層次聚類中樣本之間的距離，對工藝過程實例進行層次聚類，結果如圖8所示，從圖中的聚類層次樹很難確定聚類結果。因此，相對于層次聚類，采用AP算法可以實現(xiàn)工藝過程的聚類。

4 結束語

本文針對工藝過程歷史數(shù)據(jù)重用率低的問題，采用AP算法對歷史工藝過程數(shù)據(jù)進行聚類分析，從而獲取典型工藝過程。首先利用屬性有向圖對工藝過程進行描述，便于計算工藝過程實例間的相似度；將工藝過程的相似度矩陣作為AP聚類算法的輸入進行聚類分析，并以Sil和IGP作為聚類結果的評價指標，以確定有效聚類及其最佳聚類數(shù)目。通過衛(wèi)星結構板機加工藝的實例仿真驗證了算法的有效性。在進行實例驗證的過程中，雖然樣本數(shù)量小、工藝過程實例的復雜度低，但工藝過程實例相似度的計算相對繁雜，因此降低工藝過程相似度計算的復雜性是后續(xù)的研究問題之一。

［1］ LIU S，ZHANG Z，TIAN X.A typical process route discovery method based on clustering analysis［J］.The International Journal of Advanced Manufacturing Technology，2007，35（1/2）：186－194.

［2］ ZHANG Hui，QIU Lemiao，ZHANG Shuyou，et al.Typical product process route extraction method on intelligent clustering analysis［J］.Computer Integrated Manufacturing Systems，2013，19（3）：490－498（in Chinese）.［張 輝，裘樂淼，張樹有，等.基于智能聚類分析的產(chǎn)品典型工藝路線提取方法［J］.計算機集成制造系統(tǒng)，2013，19（3）：490－498.］

［3］ LONG Hongneng，YIN Guofu，CHENG Erjing，et al.Algorithm of process similarity analysis from case－based reasoning［J］.Journal of Sichuan University：Engineer Science Edition，2004，36（1）：77－82（in Chinese）.［龍紅能，殷國富，成爾京，等.基于實例推理的相似工藝度量算法［J］.四川大學學報：工程科學版，2004，36（1）：77－82.］

［4］ THIMM G，JIANG F，BENG T S，et al.A graph representation scheme for process planning of machined parts［J］.The International Journal of Advanced Manufacturing Technology，2002，20（6）：429－438.

［5］ DEMOLY F，YAN X T，EYNARD B，et al.An assembly oriented design framework for product structure engineering and assembly sequence planning［J］.Robotics and Computer－Integrated Manufacturing，2011，27（1）：33－46.

［6］ ZHANG Zhiying，LI Zhen，JIANG Zhibin.Computer－aided block assembly process planning in shipbuilding based on rulereasoning［J］.Chinese Journal of Mechanical Engineering，2008，21（2）：99－103.

［7］ BERGER U，KRETZSCHMANN R，NOACK J.An Approach for a Knowledge－based NC programming system［EB/OL］.［2014－02－13］.http：//www－docs.tu－cottbus.de/automatisierungstechnik/public/2008＿Kretzschmann＿Madeira.pdf.

［8］ ZHAO Gang，JIANG Pingyu.Weighted directed graph based part clustering model［J］.Computer Integrated Manufacturing Systems，2006，12（7）：1007－1012（in Chinese）.［趙 剛，江平宇.基于加權有向圖的零件聚類模型研究［J］.計算機集成制造系統(tǒng)，2006，12（7）：1007－1012.］

［9］ SCHAEFFER S E.Graph clustering［J］.Computer Science Review，2007，1（1）：27－64.

［10］ ZHOU Y，CHENG H，YU J X.Graph clustering based on structural/attribute similarities［J］.Proceedings of the VLDB Endowment，2009，2（1）：718－729.

［11］ CHENG H，ZHOU Y，YU J X.Clustering large attributed graphs：a balance between structural and attribute similarities［J］.ACM Transactions on Knowledge Discovery from Data，2011，5（2）：1－33.

［12］ XU Zhiqiang，KE Yiping，WANG Yi，et al.A model－based approach to attributed graph clustering［C］//Proceedings of the 2012ACM SIGMOD International Conference on Management of Data.New York，N.Y.，USA：ACM，2012：505－516.

［13］ WANG Xianhui，QIN Zheng，ZHANG Xuanping，et al.Cluster ensemble algorithm using affinity propagation［J］.Journal of Xi'an Jiaotong University，2011，45（8）：1－6（in Chinese）.［王羨慧，覃 征，張選平，等.采用仿射傳播的聚類集成算法［J］.西安交通大學學報，2011，45（8）：1－6.］

［14］ FREY B J，DUECK D.Clustering by passing messages between data points［J］.Science，2007，315（5814）：972.

［15］ KAPP A V，TIBSHIRANI R.Are clusters found in one dataset present in another dataset？［J］.Biostatistics，2007，8（1）：9－31.

［16］ ZHANG Yongjian.Research on methods and applications of complex product design process optimization［D］.Harbin：Harbin Institute of Technology，2011（in Chinese）.［張永健.復雜產(chǎn)品設計過程優(yōu)化方法及其應用研究［D］.哈爾濱：哈爾濱工業(yè)大學，2011.］