復雜產(chǎn)品設(shè)計變更傳播多目標路徑優(yōu)化研究

李孟澤，盛健超，李玉鵬，亓文輝

（中國礦業(yè)大學礦業(yè)工程學院工業(yè)工程系，江蘇 徐州 221116）

1 引言

復雜產(chǎn)品的設(shè)計變更對于企業(yè)快速適應(yīng)市場變化，響應(yīng)多樣化的客戶需求起著舉足輕重的作用[1]。企業(yè)為了保持核心競爭力，經(jīng)常要對產(chǎn)品進行設(shè)計變更。變更的傳播可能會影響產(chǎn)品研發(fā)進度和產(chǎn)品質(zhì)量。另外，復雜產(chǎn)品的零部件之間結(jié)構(gòu)關(guān)系錯綜復雜，變更的傳播會使開發(fā)過程的難度提高，增加設(shè)計成本和風險。

針對設(shè)計變更問題，國內(nèi)外學者開展了深入的研究。如文獻[2]提出了公理化設(shè)計矩陣與設(shè)計結(jié)構(gòu)矩陣（Design Structure Matrix，DSM）同步演化的思想，并闡述了其演化的內(nèi)在機制。文獻[3]運用網(wǎng)絡(luò)層次分析法評估模塊化產(chǎn)品設(shè)計變更傳播的影響，該方法僅僅適用于解決模塊化產(chǎn)品問題，而對于難以實現(xiàn)模塊化的產(chǎn)品其優(yōu)勢并不明顯。文獻[4]對產(chǎn)品設(shè)計變更進行了并行處理，以變更處理時間作為判據(jù)來搜索最優(yōu)的傳播路徑。文獻[5]以累積變更傳播強度最小為目標，根據(jù)零部件參數(shù)連接關(guān)系建立設(shè)計變更分析模型，運用改進的蟻群算法進行求解?？傊?，雖然有關(guān)設(shè)計變更傳播的研究較為豐富，但針對復雜產(chǎn)品設(shè)計變更多目標路徑優(yōu)化問題，沒有進行針對性的研究。

近年來，復雜網(wǎng)絡(luò)理論的興起為解決復雜產(chǎn)品設(shè)計變更問題提供了新思路，復雜產(chǎn)品的零部件可以抽象為網(wǎng)絡(luò)的節(jié)點，物理或功能關(guān)聯(lián)關(guān)系可以抽象為網(wǎng)絡(luò)中的邊。目前，常見的復雜網(wǎng)絡(luò)有隨機網(wǎng)絡(luò)（ER模型）[6]、無標度網(wǎng)絡(luò)（BA模型）[7]以及小世界網(wǎng)絡(luò)（WS模型）[8]。文獻[9]將有向加權(quán)網(wǎng)絡(luò)看作復雜產(chǎn)品的形式化表達，對設(shè)計變更的影響進行分析。文獻[10]基于BBV無標度網(wǎng)絡(luò)演化模型，對復雜產(chǎn)品設(shè)計變更傳播影響進行定量化評估。

鑒于以上研究，首先根據(jù)復雜產(chǎn)品零部件的物理連接關(guān)系構(gòu)建復雜網(wǎng)絡(luò)，根據(jù)變更傳播特點建立設(shè)計變更多目標路徑優(yōu)化模型，運用蟻群算法求解得到最優(yōu)傳播路徑，所得最優(yōu)方案可有效節(jié)省設(shè)計時間和成本，降低變更影響。

2 復雜產(chǎn)品設(shè)計變更網(wǎng)絡(luò)模型構(gòu)建

2.1 小世界網(wǎng)絡(luò)模型

Watts等在1998年提出了一種介于規(guī)則網(wǎng)絡(luò)和隨機網(wǎng)絡(luò)之間的小世界網(wǎng)絡(luò)模型，該理論的提出是復雜網(wǎng)絡(luò)研究的一項開創(chuàng)性成果。小世界網(wǎng)絡(luò)有兩個重要的特征參數(shù)：特征路徑長度L和聚類系數(shù)C。

（1）特征路徑長度是任意兩個節(jié)點之間最短距離的平均值，表示為：

式中：dij—任意兩個連通節(jié)點間的最短距離。

（2）聚類系數(shù)用于衡量相鄰節(jié)點聯(lián)系緊密程度，表示為：

式中：di—節(jié)點vi的度；ti—節(jié)點vi的相鄰節(jié)點之間存在的邊數(shù)。小世界網(wǎng)絡(luò)具有很高的聚類系數(shù)和較小的平均距離?？梢?/p>

表示為：

式中：Cr、Lr—對應(yīng)隨機網(wǎng)絡(luò)的聚類系數(shù)和平均距離。

2.2 變更傳播模型構(gòu)建

為了建立變更傳播模型，首先將復雜產(chǎn)品分解為有著物理連接關(guān)系的零部件。將零部件之間的關(guān)系映射為n×n階方陣，即產(chǎn)品的DSM。若零件ai的變更會引起零件aj的變更，則aij=1（i≠j），反之a(chǎn)ij=0。一個包含6個零部件的產(chǎn)品，容易發(fā)現(xiàn)，若零部件a1發(fā)生設(shè)計變更，則零部件a2和a6有可能會受到影響，如圖1所示。

圖1 設(shè)計結(jié)構(gòu)矩陣Fig.1 Design Structure Matrix

依據(jù)產(chǎn)品的DSM構(gòu)建變更傳播模型，其網(wǎng)絡(luò)模型可以表示為 G=（V，E），V=（v1，v2，…，vn）為節(jié)點的集合，E=｛eij|i，j=1，2，…，n，i≠j｝為邊的集合。節(jié)點代表DSM中的元素，節(jié)點間的連接邊代表元素之間的關(guān)系，從而確定節(jié)點之間是否存在連接關(guān)系。

2.3 變更傳播強度評估

從工程變更角度看，復雜產(chǎn)品可以由大量節(jié)點與邊構(gòu)成的復雜網(wǎng)絡(luò)表示，網(wǎng)絡(luò)中的節(jié)點代表產(chǎn)品的零部件，邊代表零部件之間的物理連接關(guān)系。在對產(chǎn)品的復雜網(wǎng)絡(luò)拓撲結(jié)構(gòu)的統(tǒng)計特征進行分析后發(fā)現(xiàn)，其特征路徑長度和聚類系數(shù)滿足式（3），具有小世界特性[11]。在該網(wǎng)絡(luò)中，網(wǎng)絡(luò)節(jié)點的度對設(shè)計變更的傳播起著重要作用[12]，某個節(jié)點度越大，它對應(yīng)的傳播路徑越多，擴散范圍就越大。

定義變更傳播強度與傳播概率和節(jié)點的度有關(guān)。傳播概率Pij表示節(jié)點vi傳播到節(jié)點vj的可能性大小。當節(jié)點vi和節(jié)點vj之間沒有連接邊，則Pij=0；當節(jié)點之間傳播概率越大，變更傳播越傾向經(jīng)過該連接邊。dj表示節(jié)點vj的度。度大的節(jié)點擁有較多連接邊，變更傳播的影響范圍比較大。用Fk表示傳播第k步可達到節(jié)點集合。變更傳播強度定義為：

式中：ωp+ωd=1，ωp和ωd—傳播概率和節(jié)點度對應(yīng)的權(quán)重。在與相關(guān)專家確定后ωp=ωd=0.5較為合適。在上述分析中，變更傳播強度的大小代表復雜網(wǎng)絡(luò)中節(jié)點之間的邊權(quán)，權(quán)重越大，表示變更通過此邊進行傳播產(chǎn)生越大的影響。

3 設(shè)計變更傳播路徑搜索算法

3.1 設(shè)計變更傳播方式

零部件的變更傳播存在兩種方式：串行傳播和并行傳播。對于串行傳播，如圖2（a）所示。零件變更的傳播是依次進行的；對于并行傳播，如圖2（b）所示。一個零件的變更可以同時影響多個零件，其傳播路徑是由多個串行傳播路徑組成。在實際傳播中，兩種變更傳播方式都存在。

圖2 變更傳播方式Fig.2 Change Propagation Patterns

3.2 設(shè)計變更傳播最優(yōu)路徑搜索

設(shè)計變更傳播路徑的搜索是一個NP-hard問題[13]，運用啟發(fā)式算法求解此類問題有較好的效果。蟻群算法是文獻[14]提出的一種啟發(fā)式智能優(yōu)化算法，已成功應(yīng)用于求解許多NP問題、組合優(yōu)化問題等，如旅行商問題、車輛調(diào)度問題。因此，采用蟻群算法求解復雜產(chǎn)品的設(shè)計變更傳播路徑優(yōu)化問題?；谝呀⒌膹碗s網(wǎng)絡(luò)模型，以變更傳播強度、零件設(shè)計成本和設(shè)計時間為多個優(yōu)化目標，將復雜產(chǎn)品設(shè)計變更多目標路徑優(yōu)化的數(shù)學模型描述為：

式中：Ci—零件ai的設(shè)計成本；Ti—零件ai的設(shè)計時間，目標函數(shù)為傳播路徑上的變更傳播強度、零件的設(shè)計成本和設(shè)計時間的加權(quán)總和最小。Δρu—初始變更節(jié)點的初始變更影響。為了讓變更傳播停止，定義ρi為節(jié)點vi的變更吸收能力，k為變更傳播的步數(shù)。

在尋找最優(yōu)路徑的過程中，螞蟻會在其經(jīng)過的路徑上留下信息素，之后的螞蟻會根據(jù)這些信息素的強弱選擇路徑。每一次循環(huán)迭代，螞蟻的信息素更新按如下規(guī)則：

式中：Q—常數(shù)；Dl—第l只螞蟻在本次循環(huán)的目標函數(shù)值；γ—信息揮發(fā)系數(shù)；Δτlij—在本次循環(huán)中第l只螞蟻留在邊eij上的信息素；Δτij—在本次循環(huán)中邊eij上的信息素的增量。因為變更優(yōu)先選擇傳播影響小的邊進行傳播，所以定義啟發(fā)因子為：

式中：傳播影響Aij=ω1Iii+ω2Ci+ω3Ti，該啟發(fā)因子表示螞蟻從節(jié)點vi到節(jié)點vj的期望程度。第l只螞蟻從節(jié)點vi到節(jié)點vj的轉(zhuǎn)移概率為：

式中：α（α≥0）—信息素的相對重要程度，即軌跡的相對重要性；β（β≥0）—啟發(fā)因子的相對重要程度，即能見度的相對重要性；—第l只螞蟻在節(jié)點vi下一步允許選擇的節(jié)點集合。運用蟻群算法尋找變更傳播最優(yōu)路徑的搜索步驟，如圖3所示。

圖3 最優(yōu)變更傳播路徑搜索算法框架Fig.3 Algorithm Framework of Optimal Change Propagation Path Searching

（1）通過對復雜產(chǎn)品各零部件之間連接關(guān)系分析，將零部件映射為節(jié)點，物理連接關(guān)系映射為邊，建立復雜產(chǎn)品網(wǎng)絡(luò)模型。

（2）依據(jù)復雜網(wǎng)絡(luò)模型，計算每個節(jié)點的出入度；通過從數(shù)據(jù)庫中提取節(jié)點與節(jié)點之間傳播概率。利用式（4），計算每條邊的變更傳播強度。

（3）輸入初始變更節(jié)點。評估每個節(jié)點變更吸收能力，設(shè)置初始變更節(jié)點影響，運用蟻群算法進行求解，得到最優(yōu)的傳播路徑。

4 案例分析

為了驗證所建模型和算法的有效性，以某型號摩托車發(fā)動機為例進行分析。產(chǎn)品由汽缸蓋，氣門，氣門固定螺母，曲柄銷，氣缸墊片，氣門固定軸，曲軸箱，活塞等30種零部件組成。根據(jù)該發(fā)動機零部件間的物理連接關(guān)系，得到產(chǎn)品的DSM，并建立零部件結(jié)構(gòu)網(wǎng)絡(luò)模型，如圖4所示。

圖4 零部件結(jié)構(gòu)網(wǎng)絡(luò)模型Fig.4 Structure Network Model of Parts

在設(shè)計變更傳播的路徑搜尋過程中，根據(jù)設(shè)計變更歷史數(shù)據(jù)庫得到經(jīng)過每條邊的概率，如圖5所示。圖中為30階方陣，每一方格的顏色深淺代表傳播概率的大小，顏色越深表示概率越大，變更傳播越容易經(jīng)過這條路徑。依據(jù)式（4）計算得到每條邊的變更傳播強度以及由產(chǎn)品設(shè)計變更數(shù)據(jù)庫得到的每個零部件的設(shè)計成本和設(shè)計時間，經(jīng)過計算得到的發(fā)動機變更傳播影響矩陣，如圖6所示。氣缸體是摩托車發(fā)動機的重要零部件，且在現(xiàn)實生活中容易發(fā)生變更，故選取節(jié)點編號為22的氣缸體為初始變更節(jié)點，初始變更影響設(shè)置為0.30，運用蟻群算法求解。算法通過VisualStudio2013進行開發(fā)，運行算法的計算機配置為IntelR CoreTMi5-3210M CPU（2.5 GHz），4GB RAM，得到最路徑為 22→30→21→19→4→25。為說明所提方法的有效性，僅考慮變更傳播強度單個目標所得最優(yōu)路徑為22→1→30→19→10→21。由以上結(jié)果比較得出，如果僅考慮變更傳播強度，單目標設(shè)計變更傳播最優(yōu)路徑的變更傳播強度（2.52）小于多目標求解時變更傳播強度（2.80）。但在比較其設(shè)計成本和設(shè)計時間時，發(fā)現(xiàn)后者的設(shè)計總成本和總時間分別為2220元和23天，都遠高于前者的設(shè)計總成本和總時間：1970元，18天。如果在變更傳播強度沒有很大差距的情況下，對前者路徑上的零件進行變更，將會節(jié)省大量的設(shè)計時間和設(shè)計成本，提高設(shè)計的敏捷性。

圖5 傳播概率矩陣Fig.5 Matrix of Propagation Likelihood

圖6 發(fā)動機變更傳播影響矩陣Fig.6 Matrix of Change Propagation Impact on Engine

5 結(jié)論

針對復雜產(chǎn)品設(shè)計變更傳播多目標優(yōu)化問題，提出了一種基于小世界網(wǎng)絡(luò)的方法。該方法考慮了節(jié)點的度和節(jié)點間的傳播概率兩個變量計算變更傳播強度，又引入零件的設(shè)計成本和設(shè)計時間，建立設(shè)計變更傳播多目標路徑優(yōu)化模型，運用蟻群算法求解得到一條傳播影響最小的路徑。在實例研究中，以某型號摩托車發(fā)動機為例，對上述模型和算法進行了驗證。所提方法僅從零件層次考慮，對設(shè)計變更傳播的影響進行了分析，得出有效的結(jié)論。由于變更的執(zhí)行必須要從零部件的設(shè)計參數(shù)著手，未來我們將會從復雜產(chǎn)品零部件的參數(shù)角度考慮展開研究。