模塊邊界約束條件下產品設計結構矩陣排序算法

衛軍朝，張國淵，閆秀天

（1.西北工業大學 機電學院，西安 710072；2.西安電子科技大學 機電工程學院，西安 710071）

0 引言

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

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

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

1 基于ABC的DSM排序算法

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

1.1 DSM排序的聚類準則

對于一個產品系統的DSM，為了使構件之間的耦合近可能地接近DSM的對角線，本文引入文獻[3]中所用到的聚類準則，該聚類準則是構件序列θ的函數：

式中N是系統中構件的數目；i和j分別是DSM單元的行指針和列指針。

1.2 解編碼

解采用二維數組編碼的形式，每一行表示一個已定義的模塊，行的排列順序表示了各模塊在排序后的DSM中的排序，而行內構件順序則表示了各構件在模塊中的排序。圖1的左邊顯示了一個由12個構件所組成的DSM在排序之前的標準個體。

圖1 解集合

1.3 隨機解生成算子

為了產生初始解集合，以及在偵察蜂階段隨機產生新的解（食物源），需要對標準個體隨機排序產生新的食物源。隨機解生成算子包含兩個階段。第一階段對各模塊的順序進行隨機打亂，如標準個體的模塊順序（PM1，PM2，PM3，PM4，PM5）被隨機打亂后，變為（PM3，PM1，PM2，PM5，PM4）（見圖1中的個體1）。第二階段是對各個模塊中的構件進行隨機排序，如圖1中個體1所示。

1.4 鄰域搜索算子

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

1）二維兩點交叉算子

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

圖2 二維兩點交叉算子

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

圖4 逆序變異算子

2）二維逆序變異算子

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

1.5 算法流程

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

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

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

輸出：優化的構件序列。

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

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

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

Step 4：cycle =1。

Step 5：do。

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

Step 5.2：雇傭蜂執行貪心選擇過程。

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

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

Step 5.5：執行貪心選擇過程。

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

Step 5.7：記住到目前為止的最優解。

Step 5.8：cycle = cycle+1。

Step 6：while cycle ≤ MCN。

2 實例分析

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

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

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

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

圖5 CHV1210的DSM[7]

圖6 DSM優化排序結果

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

3 結論

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

[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]汪文旦,秦現生,閻秀天,白晶.一種可視化設計結構矩陣的產品設計模塊化識別方法[J].計算機集成制造系統,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]李中凱,千紅濤.環境意識模塊化產品體系結構的設計優化方法[J].計算機輔助設計與圖形學學報,2015,27(1):166-174.

[9]魏巍,許少鵬,梁赫.基于環境資源因子的產品平臺模塊劃分方法[J].計算機輔助設計與圖形學學報,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]張培文,潘全科,李俊青,等.有限緩沖區流水車間調度的混合人工蜂群算法[J].計算機集成制造系統,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.