基于綠色模塊劃分的多目標蟻群算法*

胡浩平　劉電霆

(①深圳信息職業技術學院財經學院，廣東 深圳 518172；②桂林理工大學機械與控制工程學院，廣西 桂林 541004)

?

基于綠色模塊劃分的多目標蟻群算法*

胡浩平①劉電霆②

(①深圳信息職業技術學院財經學院，廣東 深圳 518172；②桂林理工大學機械與控制工程學院，廣西 桂林 541004)

針對模塊劃分問題中基本單元本身又是一個零件庫的情況，基于綠色模塊劃分的多目標模型，提出了一種多目標蟻群算法；以減速器為實例，建立聚合度、耦合度、綠色度3個目標函數，然后在同一個種群中，又分出3個螞蟻群體，每個螞蟻群體最優一個目標函數，三者共享全局信息素，設置合理啟發式因子、信息素更新原則和3個外部精英解，以均值來解決擁擠距離維護外部精英集。3個螞蟻群體中的解分別與外部精英解比較，如果是非支配的就更新全局信息素；如果是互不支配的就按照均值來更新全局信息素，其他只考慮信息素的揮發。實驗證明收斂速度極快，容易找到最優解，對各個因子和參數的改變算法均表示穩定收斂，驗證了方法的可行性，具有極好的實用性。

綠色設計；模塊化設計；多目標蟻群算法；組合優化

綠色設計是在傳統設計的層面上，面向產品整個生命周期的設計，重點考慮產品環保屬性，比如通用性、升級性、回收性、維護性、處理性、污染性、耗能性，并將其以上作為設計目標，同時考慮產品功能結構特性，使得產品的環境友好性盡量處于最佳狀態。[1-4]

模塊化設計是大規模批量生產的關鍵技術，它通過將大量的零件按照對應的屬性進行模塊組合，組合成不同功能和特性的產品，在一定程度上還能滿足客戶個性化的要求，同時為大批量的生產奠定基礎，提高生產效率。

國內外不乏這方面的研究，文獻[5]采用模擬退火算法在產品整個生命周期進行模塊化劃分；文獻[6]利用遺傳算法實現了在產品裝配和拆卸性能方面模塊化劃分；文獻[7]采用聚類和模塊密度等來進行模塊劃分，文獻[8]詳細論述了模塊劃分建模過程以及GA求解。但是結合零件庫中零件特性的建模和運用多目標蟻群算法的求解，尚無文獻研究，由于蟻群算法有其收斂速度快的優勢，能很好地解決大批量零件之間模塊組合NP·Hard問題；在求解模塊化過程中，作為基本單元的零件本身又是一個零件庫，在零件庫中的基本單元相當多的時候，任選一個零件出來組合都會因為各自特性而使得組成的最優結果各異，導致不同的模塊劃分，這些復雜的計算仍是NP-Hard問題，以往的研究往往得到的解集比較單一；基于此作者提出了一種綠色模塊劃分的多目標蟻群優化方法，從建立綠色模塊劃分多目標模型入手，基于實驗數據，用所提方法進行實驗，結果證明方法切實可行，有其實用價值。

1　問題描述

以一個減速器作為案例，減速器結構由聯軸器、潤滑、齒輪、軸、箱體、軸承、端蓋、密封、螺釘、鍵等10個基本單元組成。分別用T1、T2、T3、T4、T5、T6、T7、T8、T9、T10表示。設10個基本單元都有自己的零件庫，每個零件庫里面僅選一個零部件參與模塊劃分，使得整體多目標模型協調最優。將進行模塊劃分，使得模塊內聚合度、模塊之間耦合度和整體綠色度盡最大可能最優。這是個NP-Hard問題，適合用多目標蟻群算法求解。

2　相關知識和數據

2.1數據表示說明

功能相關性便于使近似功能的基本單元聚合成模塊，以提高模塊的功能獨立性。結構相關性便于某種功能所對應的模塊在結構上的完整性。它們的相關程度是一種定性問題，可以根據知識和人的經驗使用模糊數值來描述。假設功能相關性有屬性“無”、“差”、“一般”、“較強”、“強”和“很強”，用0.0、2.0、4.0、6.0、8.0、10.0表示。結構相關性表示方法相同。零件的綠色性屬性可用“無”、”差”、“一般”、“較好”、“好”、“很好”度量，可用0.0、2.0、4.0、6.0、8.0、10.0表示。

2.2零件屬性和相關性數據

假設基本零件單元有7個綠色屬性，其中通用性、回收性、升級性、維護性、處理性是屬性值越大綠色性越好；污染性、耗能性是屬性值越小綠色性越好。為了節約版面空間，每個基本單元零件庫中的零件個數暫定2個；基本單元零件綠色屬性如表1。

表1　零件屬性

功能相關性和結構相關性具體數據設置如表2，為了節約版面空間，根據表格的對稱性和線性矩陣的原理，兩部件相關的值只要設置一次就可以，所以上三角形為功能相關性值，下三角形為結構相關性值。

表2　相關性值

3　多個目標模型建立

設產品有N個基本單元，則兩兩模塊的關聯度為aij=ωFfij+ωSsij;i,j=1,2,…,N；ωF和ωS為權重系數,fij為功能相關值，sij為結構相關值。設模塊Uh共有Ph個基本單元組成，則所有M個模塊的總聚合度C1可用式(1)計算；同時它們第k個綠色屬性為gk,h=min(gk,1,gk,2,…,gk,Ph),k=1,2,3,4,5，取其組合最小值；gk,h=max(gk,1,gk,2,…,gk,Ph),k=6,7，取其組合最大值。

前5個綠色屬性是正能量，后兩個綠色屬性是負能量，所以產品劃分為M個模塊后的總綠色度為式(2)[8]，ωk為第k個綠色性的權重系數。設模塊U1由P1個基本單元組成，模塊U2由P2個基本單元組成，則可得所有模塊間的總耦合度為式(3)：[8]

(1)

(2)

(3)

4　問題求解

規劃模型為式(1)～(3)3個目標函數，分別是maxC1，minC2，maxG，這是個NP組合問題，為了得到非單一解集，適合用提出的多目標蟻群優化算法[9]求解。

4.1pareto支配

定義1：支配定義：?a,b∈Z；若fn(a)≤fn(b)，(n=1,2,…,k)；且?y∈{1,2,…,r}，使fy(a)≤fy(b)，則稱a支配b，表示為a?b。此時我們稱a為非支配的，b為被支配的，其中“?”表示支配關系[10]

定義2：不相關定義：?a,b∈Z；若a和b之間沒有支配關系，則稱a和b無關或不相關或者互不支配。

定義3：非支配集定義：?a∈Z，若?b∈Z，使b?a，則稱a是非支配的個體；則稱由所有Z中非支配的個體組成的集合為非支配集。

4.2基本蟻群算法

蟻群算法的初衷是用于求解TSP問題，然后又有著色問題。作業問題等組合問題。TSP問題非常類似于蟻群的覓食過程；基于TSP問題的基本蟻群算法步驟如下[11-12]：

步驟1：初始化各個參數，設置啟發式參數值α、β、ρ，各個路徑信息素ηij，最大迭代次數N，等。

步驟2：迭代循環開始。

步驟3：將m只螞蟻隨地的放在n個城市上面，并做好相應記錄。

步驟4：設置好禁忌表控制下一個訪問城市，保存已訪問的城市做好相應記錄。

步驟5：根據狀態概率公式(4)來計算螞蟻選擇下一個城市j的概率，j是非禁忌表中的城市，城市不再重復選擇。

(4)

allowed代表非禁忌表中的城市，表示t次迭代還沒有訪問到的城市。

步驟6：選擇具有最大狀態轉移概率的城市，并把該城市標記在禁忌表中，存好城市訪問次序，記錄好相應輔助記錄。

步驟7：若m只螞蟻還沒有訪問完所有的城市，就轉步驟5繼續執行；否則轉步驟8執行。

步驟8：采用蟻周模型，對路徑上的信息素按式(5)～(7)進行更新。

γij(t+n)=(1-ρ)·γij(t)+Δγij(t)

(5)

(6)

(7)

Q為常量，表示螞蟻循環一周在經過的所有路徑上釋放的信息素總量，這個值根據經驗和實驗次數來設定，Lk表示第k只螞蟻在本次迭代中所有走過的路徑總長度，是個變值。

步驟9：若m只螞蟻均迭代最大迭代次數或者達到預計效果則輸出結束，否則初始化相關值、清空禁忌表以及城市訪問次序表轉步驟3。

4.3提出一種多目標蟻群算法

用多目標蟻群算法求解綠色模塊劃分，國內還未出現；對于這種NP問題，本文提出一種多目標蟻群算法對綠色模塊劃分優化進行求解，求解步驟如下[13-15]：

步驟1：根據目標函數的個數，將種群分為3個螞蟻群體，每個群體分配一個目標函數，每個螞蟻群體分別將求對應目標函數最優，但是它們共享同一個全局信息素；初始化各個參數以及矩陣值，螞蟻數，迭代次數，初始化信息素；存儲好功能相關性值、結構相關性值以及綠色性值；準備好各個禁忌表、訪問表以及模塊劃分遞增表和記錄數表。

步驟2：循環迭代開始。

步驟3：在3個螞蟻群體中每只螞蟻隨機存放在各個頂點上，這里每個頂點是指對應的零件庫T1、T2、T3…等，同時記錄好各個禁忌表和訪問表以及模塊劃分遞增表和記錄數表。

步驟4：每一個螞蟻群體里面的螞蟻都按照公式(8)，選擇轉移概率最大的那個作為下一個選擇，并設置一個隨機數rand()，如果所得的轉移概率大于隨機數rand()，則歸為上一個頂點所在的模塊，否則作為另外一個模塊。各個螞蟻群體里的螞蟻互不干擾，只有共享公共信息素。

(8)

式中：γij(t)表示頂點的信息素，ηij(t)表示頂點的功能相關性和結構相關性，α為信息素啟發因子，β為功能相關性和結構相關性啟發因子。

步驟5：如果每只螞蟻所有頂點還沒有訪問完，則繼續步驟3，否則步驟6。

步驟6：采用蟻周模型進行全局信息素更新：對每個螞蟻群體里面的螞蟻獲得的解，都與3個外部精英解比較，如果支配外部精英解，則更新外部精英解以及記錄數表，替代其支配的外部精英解并且全局更新信息素；如果是互不支配的關系就按式(9)進行均值比較，如果當前的解均值小，則替換其外部精英解以及記錄數，更新外部精英解并且全局更新信息素。以上全局信息素的更新，均采用如下步驟：根據模塊劃分遞增表所走過的路徑，按照式(10)～(12)對稱性添加信息素，同時考慮揮發因素；對于依次走過并且劃分在同一個模塊中的頂點之間添加信息素，跳變而不相同的相鄰兩頂點不添加信息素，同時Lk根據所在的螞蟻群體而取值不同。

F=w1×C1-w2×C2+w3×G;

(9)

γij(t+n)=(1-ρ)·γij(t)+Δγij(t)

(10)

(11)

Lk

(12)

式中：Q為常量，是螞蟻在3個相應螞蟻群體中適應度值，當在對應目標函數為模塊聚合度最大的螞蟻群體的時候，它取值為聚合度適應值C1，當在對應目標函數為耦合度最小的螞蟻群體的時候，它取值為耦合度適應值C2，當在對應目標函數為綠色度最大的螞蟻群體的時候，它取值為綠色度適應值G。

步驟7：迭代次數未完則清空禁忌表等相應初始化操作轉步驟2，否則結束輸出最優解。

4.4實驗數據

采用C_FREE5.0為運行環境，C語言編寫程序，迭代次數均為1 000次，設置不同的參數獲得的實驗結果如表3所示。

4.5實驗分析

通過2次實驗均獲得收斂，該蟻群算法迭代1 000次，均在幾秒鐘內完成算法的計算，同時獲得收斂，收斂速度極快；在最后的迭代過程中，模塊劃分收斂結果基本不再變化，以上2次實驗在第10-1 000次迭代過程中，模塊劃分都是在如下9種模塊劃分中選擇，而且每次迭代得到3個精英解所對應的模塊劃分是一樣的；最佳模塊劃分數值為5,4,4,3,3,3,3,2,1,1；6,5,5,4,4,4,3,2,1,1；6,5,5,2,2,1,2,4,3,3；1,5,5,4,4,4,4,3,2,2；5,1,1,4,4,4,4,3,2,2；6,1,1,5,5,5,4,3,2,2；6,5,5,1,2,2,2,4,3,3；5,4,4,1,1,1,1,3,2,2；1,6,6,5,5,5,4,3,2,2；相同的數字為同一個模塊，最后趨于穩定的3個外部精英解分別為3種：其一最優模塊劃分為{聯軸器；潤滑、齒輪；軸、箱體、軸承、端蓋；密封；螺釘、鍵}；其二最優模塊劃分為{聯軸器；潤滑、齒輪；軸、箱體、軸承；端蓋；密封；螺釘、鍵}；其三最優模塊劃分為{聯軸器；潤滑、齒輪；軸、箱體、端蓋；軸承；密封；螺釘、鍵}；其中用分號分隔為不同模塊，頓號分隔的是同一個模塊。最優記錄表記錄數取值為2,1,1,2,1,2,1,1,1,2，2,1,1,2,1,2,2,1,1,2；1表示相應表選第一條記錄，2表示相應表選第二條記錄；實驗結果符合生產實際要求。

雖然以上只列舉了2次試驗的結果，在很多次實驗中，無論怎樣改變蟻群算法的相應參數，該算法均表示很大的穩定性，不同于以往文獻的研究：①參數的設置隨意性較大，啟發因子α、啟發因子β、揮發系數ρ和螞蟻數目М均可以有較大的隨意性，不會過多影響收斂結果和最優結果；②收斂速度極快。尤其和文獻[8]比起來，作者提出的多目標蟻群算法更有特色：①作者考慮了日益豐富的零件庫，提供了更大的選擇空間進行組合配置；②求解速度比GA速度快，這種多目標蟻群算法體現了1 000次迭代幾秒收斂，而且一開始就收斂；③不是單一解，結論選擇余地更大；④提出一種多目標蟻群求解算法，用基于PARETO集的概念求解，方法更貼近實際，優于依據經驗設置權重所采用加權系數法把多目標轉化為單目標的求法。但是也發現一些需要進一步研究的問題：①任何一次迭代的路徑遍歷中，每只螞蟻只有部分會走最優路徑，這跟生活當中螞蟻覓食過程中，所有螞蟻趨向最優路徑有點不同；②過早收斂，需要在生產當中去發現錯誤。

表3　實驗結果

5　結語

本文基于綠色模塊劃分提出了一種多目標蟻群算法，考慮聚合度、耦合度和綠色度3個目標函數，分3個螞蟻群體各自最優，并按支配原則和均值比較對3個外部精英解更新全局信息素；結果符合實際要求，實驗方法具有可行性和應用性；把此方法移植到制造業信息化當中，能夠給企業帶極大效益，帶動企業競爭力。當可供選擇的零件急劇增大的時候，如果是1 000個零件庫的1 000重循環，此時的求解都是NP難問題，因此大數據情況下速度的考慮和對于算法容易陷入局部收斂增加揉動因素將是下一步的研究。

[1]郭偉祥.綠色產品概念設計過程與方法研究[D].合肥:合肥工業大學,2005.

[2]Leo A,Jens B L.Life-cycle engineering and design[J].Annals of the CIRP,1995,144(2):568-580．

[3]李方義,李劍峰,汪勁松,等.產品綠色設計研究現狀及展望一般理論及方法[J].航空制造技術,2004,12(10):73-78.

[4]王日君,張進生,葛培琪,等.模塊化設計中模塊劃分方法的研究[J].組合機床與自動化加工技術,2008(7):17-21.

[5]Hwai E T,Chien C C,Jia D L.Modular design to support green life-cycle engineering[J].Expert Systems with Applications,2008,34(4):2524-2537.

[6]Yasushi U,Shinichi F,Keita T,et al.Product modularity for life cycle design[J].CIRP Annals-Manufacturing Technology,2008,128(57):13-16.

[7]唐濤,劉志峰.綠色模塊化設計方法研究[J].機械工程學報,2003,39(11):149-154.

[8]劉電霆.綠色設計中產品模塊劃分的不確定優化及GA求解[J].桂林理工大學學報,2013,33(4):743-748.

[9]李露蓉,王蕾,高應波,等.基于優化蟻群算法的動態路徑規劃問題研究[J].廣西大學學報:自然科學版,2013,38(2):359-366.

[10]Smith S,Yen C C.Green product design through product modularization using atomic theory [J]. Robotics and Computer Integrated Manufacturing,2010,26(6):790-798.

[11]汪定偉,王俊偉,王洪峰,等. 智能優化方法[M]. 北京:高等教育出版社,2007.

[12]劉乃文,劉方愛.蟻群算法用于TSP的并行策略及模型[J].計算機應用研究,2007,24(12):37-39.

[13]胡乃平,王延智.多種群蟻群算法在多目標優化中的研究[J].高校講壇，2012,36(17):122-123.

[14]池元成,蔡國飆.基于蟻群算法的多目標優化[J].計算機工程,2009,35(15):168-172.

[15]王永貴,韓瑞蓮.基于改進蟻群算法的云環境任務調度研究[J].計算機測量與控制,2011,19(5):1203-1204,1211.

(編輯李靜)

如果您想發表對本文的看法，請將文章編號填入讀者意見調查表中的相應位置。

Multi objective ant colony algorithm based on green module

HU Haoping①, LIU Dianting②

(①Institute of Finance And Economics,Shenzhen Institute of Information Technology,Shenzhen 518172, CHN;②College of Information Science and Engineering, Guilin University of Technology, Guilin 541004, CHN)

Aiming at the module partition problem of the basic unit itself is a parts library, based on the multi objective model of green module division, this paper presents a multi-objective ant colony algorithm; the reducer as an example, establish the degree of polymerization, coupling degree, green degree three objective functions, and then in the same population, and divided into three groups each ant, ant colony optimization of an objective function, the global pheromone three share, set reasonable heuristic factor, pheromone update rule and three external elite solution, to mean to solve the crowding distance to maintain external elite set. Three ant colonies solution respectively compare with external elite solution, if the non dominant update global pheromone; if it is not dominated by the mean to update global pheromone, others only consider the volatile pheromone. The experiments show that the convergence speed, to find the optimal solution easily, change the algorithm to each factor and parameter indicated stable convergence, verify the feasibility of the method, the practicability is excellent.

green design; modular design; multi objective ant colony algorithm; combinatorial optimization

TH122, TP301.6, O224

A

2015-07-07)

160116

*國家自然科學基金項目(51265008);廣西自然科學基金項目(2012GXNSFAA053193);廣西汽車零部件與整車技術重點實驗室項目(2013KFMS10);廣西碩士研究生科研創新項目(YCSZ2014153)