模塊邊界約束條件下產(chǎn)品設(shè)計結(jié)構(gòu)矩陣排序算法

衛(wèi)軍朝，張國淵，閆秀天

（1.西北工業(yè)大學(xué) 機電學(xué)院，西安 710072；2.西安電子科技大學(xué) 機電工程學(xué)院，西安 710071）

0 引言

產(chǎn)生模塊化的產(chǎn)品架構(gòu)是企業(yè)滿足用戶多樣性的需求和低成本要求的主要方法之一[1]。模塊化設(shè)計的一個關(guān)鍵問題是合理地規(guī)劃具有標(biāo)準(zhǔn)接口的模塊，以便高效地配置出不同性能需求的產(chǎn)品[2]。模塊識別和定義的一個基本視點是構(gòu)件之間的耦合性，其準(zhǔn)則是模塊內(nèi)部的耦合最大化，模塊間的耦合最小化[3～6]。除此之外，模塊化還常常需考慮多種基于構(gòu)件相似性的模塊化驅(qū)動因素[7～9]。在多目標(biāo)模塊識別之后，產(chǎn)品架構(gòu)被劃分為若干個模塊。

面向耦合性的產(chǎn)品設(shè)計結(jié)構(gòu)矩陣（DSM）是產(chǎn)品架構(gòu)的常用建模工具，它不僅可以支持各種聚類算法、辨識產(chǎn)品模塊，而且提供直觀、緊湊的可視化手段，幫助設(shè)計人員更深入地了解產(chǎn)品架構(gòu)[6,10]。DSM聚類方法主要分為兩種，一種是通過對角化DSM或更廣義的矩陣來人工劃分模塊[3～5]，另一種是自動劃分算法[7～9]。第一種方法的優(yōu)點在于對模塊大小和邊界的設(shè)定比較靈活，且具有更好的可視化效果，設(shè)計人員可更容易地觀察到系統(tǒng)可能存在的分層、交疊結(jié)構(gòu)，其缺點在于不易建立多目標(biāo)優(yōu)化模型處理多個模塊化驅(qū)動目標(biāo)。第二種方法的優(yōu)點在于便于建立多目標(biāo)優(yōu)化模型，自動生成模塊劃分方案，但其缺點在于優(yōu)化結(jié)果所對應(yīng)的結(jié)構(gòu)化DSM并未經(jīng)過優(yōu)化排序，影響了DSM的可視化效果。目前很少文獻將兩種方法相融合在一起。Jung和Simpson[6]提出一種聚類準(zhǔn)則，對其優(yōu)化可得到優(yōu)化的模塊劃分方案和構(gòu)件序列，但該方法并沒有涉及相似性模塊化驅(qū)動目標(biāo)。

在自動劃分算法生成產(chǎn)品模塊劃分方案之后，為了更清晰地顯示出構(gòu)件間的耦合關(guān)系，增強DSM的可視化效果，提出一種模塊邊界約束條件下的DSM排序優(yōu)化算法。優(yōu)化目標(biāo)是使得緊密耦合的構(gòu)件盡可能地沿著DSM對角線排列在一起，并且不破壞各模塊的邊界。采用人工蜂群算法（ABC），對DSM排序聚類準(zhǔn)則進行優(yōu)化。為滿足約束條件，開發(fā)了新穎的二維食物源編碼方式和二維鄰域搜索算子。

1 基于ABC的DSM排序算法

人工蜂群算法是一種基于生物群體的元啟發(fā)算法，它模仿了蜜蜂覓食的行為[11]。ABC算法具有實現(xiàn)簡單、參數(shù)設(shè)置少、優(yōu)化性能較好等優(yōu)點，目前已經(jīng)成功地應(yīng)用于流水車間調(diào)度等復(fù)雜離散問題的優(yōu)化之中[12]。文本算法開發(fā)的重點是對排序約束條件的處理。

1.1 DSM排序的聚類準(zhǔn)則

對于一個產(chǎn)品系統(tǒng)的DSM，為了使構(gòu)件之間的耦合近可能地接近DSM的對角線，本文引入文獻[3]中所用到的聚類準(zhǔn)則，該聚類準(zhǔn)則是構(gòu)件序列θ的函數(shù)：

式中N是系統(tǒng)中構(gòu)件的數(shù)目；i和j分別是DSM單元的行指針和列指針。

1.2 解編碼

解采用二維數(shù)組編碼的形式，每一行表示一個已定義的模塊，行的排列順序表示了各模塊在排序后的DSM中的排序，而行內(nèi)構(gòu)件順序則表示了各構(gòu)件在模塊中的排序。圖1的左邊顯示了一個由12個構(gòu)件所組成的DSM在排序之前的標(biāo)準(zhǔn)個體。

圖1 解集合

1.3 隨機解生成算子

為了產(chǎn)生初始解集合，以及在偵察蜂階段隨機產(chǎn)生新的解（食物源），需要對標(biāo)準(zhǔn)個體隨機排序產(chǎn)生新的食物源。隨機解生成算子包含兩個階段。第一階段對各模塊的順序進行隨機打亂，如標(biāo)準(zhǔn)個體的模塊順序（PM1，PM2，PM3，PM4，PM5）被隨機打亂后，變?yōu)椋≒M3，PM1，PM2，PM5，PM4）（見圖1中的個體1）。第二階段是對各個模塊中的構(gòu)件進行隨機排序，如圖1中個體1所示。

1.4 鄰域搜索算子

本文提出2種鄰域搜索算子：二維兩點交叉算子和二維逆序變異算子。二維兩點交叉算子應(yīng)用于ABC算法的雇傭蜂階段，二維逆序變異算子應(yīng)用于ABC算法的跟隨蜂階段。

1）二維兩點交叉算子

同隨機算子類似，二維兩點交叉算子也由兩個階段所組成：第一階段對模塊重新排序；第二階段對模塊內(nèi)構(gòu)件重新排序，如圖2所示。模塊重新排序采用兩點交叉算子[13]，該算子需要兩個解參與，如圖3所示。當(dāng)切割點位置如圖3所示時，模塊序列由解1（PM3，PM1，PM2，PM5，PM4）變?yōu)樾陆猓≒M3，PM5，PM1，PM2，PM4）。在第二階段中，采用概率機制確定一個模塊中的構(gòu)件是否需要重新排序，即若隨機數(shù)小于一個門檻值Pm，則需重新排序。模塊內(nèi)構(gòu)件重新排序采用逆序變異算子[14]，如圖4所示。

圖2 二維兩點交叉算子

圖3 模塊序列的兩點交叉算子

圖4 逆序變異算子

2）二維逆序變異算子

二維逆序變異算子也由兩個階段所組成：第一階段對模塊重新排序；第二階段對模塊內(nèi)的構(gòu)件重新排序。在兩個階段中，都采用逆序變異算子進行模塊或者構(gòu)件的重新排序，如圖4所示。在第二階段中，同樣采用概率機制確定一個模塊中的構(gòu)件是否需要重新排序。

1.5 算法流程

ABC優(yōu)化方法的總體結(jié)構(gòu)有四部分：初始化階段、雇傭蜂階段、跟隨蜂階段、和偵察蜂階段。其中后三個階段循環(huán)執(zhí)行，直到循環(huán)次數(shù)到達最大循環(huán)數(shù)MCN后程序停止。除了最大循環(huán)數(shù)MCN，ABC算法所需的控制參數(shù)還包括解集合的大小SN以及實驗次數(shù)上限limit，SN即雇傭蜂或者跟隨蜂的數(shù)目，limit用于在跟隨蜂階段判斷一個解是否需要拋棄。算法流程如下：

算法1：考慮排序約束的ABC排序算法。

輸入：DSM，模塊劃分方案；ABC參數(shù)SN，limit和MCN；領(lǐng)域搜索算子的概率選擇門檻值Pm。

輸出：優(yōu)化的構(gòu)件序列。

Step 1：參數(shù)初始化：SN, limit，MCN 和Pm。

Step 2：利用隨機解生成算子生成初始解集合（食物源）：θk（k=1，2，…，SN）。

Step 3：根據(jù)式(1)計算f(θk)，評估每一個解。

Step 4：cycle =1。

Step 5：do。

Step 5.1：使用二維兩點交叉算子為雇傭蜂產(chǎn)生新解，計算f（θk）并評估。

Step 5.2：雇傭蜂執(zhí)行貪心選擇過程。

Step 5.3：使用賭輪盤方法選擇一個解θk，并且使用二維逆序變異算子為跟隨蜂產(chǎn)生一個新解。

Step 5.4：計算f（θk）并評估。

Step 5.5：執(zhí)行貪心選擇過程。

Step 5.6：根據(jù)limit值確定被拋棄的解；如果該解存在, 則偵察蜂用一個隨機產(chǎn)生的解來代替被拋棄的解。

Step 5.7：記住到目前為止的最優(yōu)解。

Step 5.8：cycle = cycle+1。

Step 6：while cycle ≤ MCN。

2 實例分析

本文采用文獻[7]中的無繩手持吸塵器作為研究案例，該產(chǎn)品由Black and Decker公司生產(chǎn)，型號為CHV1210。CHV1210被分解為57個構(gòu)件，圖5是對應(yīng)的DSM矩陣，字母編碼表示了兩個構(gòu)件之間的耦合關(guān)系類型，使用下面的縮寫形式：Attachment（連接），Dust flow （塵土流），F(xiàn)orce （力），Spatial relation （空間關(guān)系），fLow of air（空氣流），Heat rejection （熱排放），mechanical torQue（力矩）和Electrical energy（電能）。在DSM聚類計算時，所有這些字母都被數(shù)值1所代替。

對文獻[7]中的一種模塊劃分方案進行對角化處理。該方案的生成同時考慮了耦合性和相似性，方案的定義見圖5中的R01～R12。

ABC優(yōu)化算法的參數(shù)設(shè)置為：SN=50；limit=150；MCN=500；Pm=0.7。算法在Matlab R2010b（The MathWorks，Natick，Massachusetts，USA）的平臺上開發(fā)，運行算法的計算機配置為：Intel? Core?i3-2350M CPU（2.3 GHz），2GB RAM。算法運行時間約為43s。優(yōu)化后的聚類準(zhǔn)則為654，得到的DSM如圖6(a)所示。

與原始的DSM相比較，圖6(a)更清晰地顯示出各模塊/構(gòu)件之間的耦合關(guān)系。1）更清晰地顯示出關(guān)系緊密的模塊。如原本不相鄰的模塊R02和R08之間有著較多的耦合，它們被排列在了一起。2）顯示出模塊內(nèi)部結(jié)構(gòu)化組織。如模塊R02的構(gòu)件在優(yōu)化排序后明顯地劃分為了2個子模塊：{17,18,21,19,12,13,16}和{14,20,15}。{17, … ,16}是噴嘴部分的構(gòu)件集合，它與系統(tǒng)中的其他模塊之間的耦合關(guān)系很少；{14,20,15}是灰塵吸納器的構(gòu)件集合，它與R08之間有著強的耦合。3）更清晰地顯示出影響若干模塊設(shè)計的關(guān)鍵構(gòu)件。關(guān)鍵構(gòu)件與所屬模塊的其他構(gòu)件有著較多的耦合，同時又與多個其他模塊有著耦合關(guān)系，對其進行設(shè)計和再設(shè)計往往會影響到多個模塊。經(jīng)過優(yōu)化排序，緊密耦合的若干模塊盡可能地排列在一起，因此，這些關(guān)鍵構(gòu)件便更清晰地顯現(xiàn)出來。如主腔體模塊R01中的構(gòu)件1（左殼）和2（右殼）不僅是R01的總線構(gòu)件，也是模塊R01與模塊R09和R05之間的接口構(gòu)件。構(gòu)件35（結(jié)構(gòu)手柄）不僅是模塊R05的核心構(gòu)件，而且是模塊R05與R01、R07、R03之間的接口構(gòu)件。

圖5 CHV1210的DSM[7]

圖6 DSM優(yōu)化排序結(jié)果

在無約束條件下對本案例中的DSM進行對角化，得到的構(gòu)件排序結(jié)果如圖6(b)所示。圖中有多個模塊的邊界被打破，如模塊R04、R09等。這便為設(shè)計人員直觀地分析模塊/構(gòu)件之間的耦合關(guān)系帶來了不便。如在圖6(a)中很容易辨識出模塊R09是一個鏈?zhǔn)浇Y(jié)構(gòu)（50-48-49），而在圖6(b)的構(gòu)件序列中，R09的構(gòu)件50與構(gòu)件48、49相距較遠，R09的架構(gòu)特點并不容易直觀地辨識出來。為滿足約束條件需對圖6(b)的排序結(jié)果進行人工調(diào)整，其過程非常繁瑣，設(shè)計人員需要不斷地評估構(gòu)件的新序列是否優(yōu)化。

3 結(jié)論

為了使DSM更清晰地顯示出模塊/構(gòu)件之間的耦合關(guān)系，幫助設(shè)計人員更深入地了解產(chǎn)品架構(gòu)，提出一種預(yù)定義模塊邊界約束條件下的DSM排序優(yōu)化算法。該算法不破壞模塊的邊界，將緊密耦合的模塊盡可能地排列在一起，同時對模塊內(nèi)的構(gòu)件進行排序，將緊密耦合的構(gòu)件盡可能地放置在一起，避免了無約束排序算法后繁瑣的人工排序過程。

[1]Simpson TW, Maier J R A,Mistree F.Product platform design: method and application[J].Research in Engineering Design,2001,13(1):2-22.

[2]Ericsson A E G.Controlling design variants: modular product platforms[M].New York:ASME Press,1999.

[3]汪文旦,秦現(xiàn)生,閻秀天,白晶.一種可視化設(shè)計結(jié)構(gòu)矩陣的產(chǎn)品設(shè)計模塊化識別方法[J].計算機集成制造系統(tǒng),2007.13(12):2345-2350.

[4]Daie P, Li S. Matrix-based hierarchical clustering for developing product architecture[J].Concurrent Engineering-Research and Applications,2016,24(2):139-152.

[5]Sarkar S,Dong A,Henderson J A,et al.Spectral characterization of hierarchical modularity in product architectures[J].Journal of Mechanical Design, 2013,136(1): 249-256.

[6]Jung S, Simpson T W.New modularity indices for modularity assessment and clustering of product architecture[J].Journal of Engineering Design,2017,28(1):1-22.

[7]Borjesson F, H?ltt?-otto K. A module generation algorithm for product architecture based on component interactions and strategic drivers[J].Research in Engineering Design, 2014, 25(25):31-51.

[8]李中凱,千紅濤.環(huán)境意識模塊化產(chǎn)品體系結(jié)構(gòu)的設(shè)計優(yōu)化方法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,2015,27(1):166-174.

[9]魏巍,許少鵬,梁赫.基于環(huán)境資源因子的產(chǎn)品平臺模塊劃分方法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,2016,28(2):335-344.

[10]EPPINGER S D, BROWNING T R. Design structure matrix methods and applications[M]. Cambridge:MIT Press,2012.

[11]Karaboga D, Gorkemli B, Ozturk C, et al.A comprehensive survey: artificial bee colony (ABC) algorithm and applications[J].Artificial Intelligence Review, 2014, 42(1):21-57.

[12]張培文,潘全科,李俊青,等.有限緩沖區(qū)流水車間調(diào)度的混合人工蜂群算法[J].計算機集成制造系統(tǒng),2013,19(10):2510-2520.

[13]Murata T, Ishibuchi H. Performance evaluation of genetic algorithms for flowshop scheduling problems[A].Proceedings of the First IEEE Conference on Evolutionary Computation[C],1994:812-817.

[14]Fogel D. A parallel processing approach to a multiple travelling salesman problem using evolutionary programming[A].Proceedings of the Fourth annual Symposium on Parallel Processing, Fullerton,CA,USA[C],1990:318-326.