一種求解綠色模塊劃分的蟻群算法

劉電霆，胡浩平

（1.桂林理工大學(xué) 機械與控制工程學(xué)院，桂林 541004；2.桂林理工大學(xué) 信息科學(xué)與工程學(xué)院，桂林 541004)

0 引言

模塊化設(shè)計是實現(xiàn)大規(guī)模批量生產(chǎn)的關(guān)鍵技術(shù)，這種技術(shù)通過將大量的零件按照對應(yīng)的屬性進行模塊組合，可以組合成不同功能和特性的產(chǎn)品，在一定程度上能滿足客戶特有的要求，同時為大批量的生產(chǎn)奠定基礎(chǔ)，提高企業(yè)的效率。綠色設(shè)計是基于傳統(tǒng)設(shè)計的層面上，面向產(chǎn)品整個生命周期內(nèi)，考慮產(chǎn)品環(huán)保屬性，比如通用性、升級性、回收性、維護性、處理性、污染性、耗能性，并將其以上作為設(shè)計目標(biāo)，同時考慮產(chǎn)品功能結(jié)構(gòu)特性，使得產(chǎn)品的環(huán)境友好性在最佳狀態(tài)[1～4]。

國內(nèi)外不泛這方面的研究，文獻[5]在確定產(chǎn)品整個生命周期的基礎(chǔ)上，采用模擬退火算法進行模塊化劃分；文獻[6]在考慮產(chǎn)品裝配/拆卸性能方面，利用遺傳算法實現(xiàn)了模塊化劃分；文獻[7]引入聚類和模塊密度等概念來進行模塊劃分。但是基于蟻群算法的求解，幾乎是空白，由于蟻群算法有其收斂速度快的優(yōu)勢，能很好的解決大批量零件的模塊化組合NP_Hard問題；基于此作者提出了一種綠色模塊劃分的蟻群優(yōu)化方法，很好的解決了實際問題。

1 問題描述

一個雙梁橋式起重機橋梁作為實例[8]，共有11 個基本單元:1.主梁、2.軌道、3.端梁、4.端梁欄桿、5.走臺、6.走臺欄桿、7.直梯、8.斜梯、9.司機室平臺、10.司機室、11.檢驗平臺；分別用T1、T2、T3、T4、T5、T6、T7、T8、T9、T10、T11表示。將進行模塊劃分，劃分成模塊內(nèi)聚合度最高，模塊之間耦合度最低，同時綠色度最大。

2 相關(guān)知識和數(shù)據(jù)

2.1 數(shù)據(jù)表示說明

功能相關(guān)性便于將實現(xiàn)同一功能的基本單元聚合成模塊，以提高模塊的功能獨立性。結(jié)構(gòu)相關(guān)性便于實現(xiàn)每種功能所對應(yīng)的模塊在結(jié)構(gòu)上的完整性。它們的相關(guān)程度是根據(jù)人的經(jīng)驗和知識進行數(shù)值來描述。假設(shè)功能相關(guān)性有屬性“很強”“強”“較強”“一般”“無”，分別用10.0,8.0,5.0,2.0,0.0。結(jié)構(gòu)相關(guān)性表示類似。零件的綠色性屬性大部分用“很好”、“好”、“較好”、“一般”,”差”和“無”6個語言標(biāo)度度量，分別用10.0,8.0,6.0,4.0,2.0,0.0表示。

2.2 零件屬性和相關(guān)性數(shù)據(jù)

假設(shè)基本零件單元有七個綠色屬性，其中五個綠色屬性：通用性、回收性、升級性、維護性和處理性是屬性值越大綠色性越好；而后面兩個屬性：污染性、耗能性是屬性值越小綠色性越好。基本單元零件綠色屬性如表1所示。

功能相關(guān)性和結(jié)構(gòu)相關(guān)性具體數(shù)據(jù)設(shè)置如表2，根據(jù)表格的對稱性，兩部件相關(guān)的值只要設(shè)置一次就可以，所以上三角形為功能相關(guān)性值，下三角形為結(jié)構(gòu)相關(guān)性值。

表1 零件屬性

表2 相關(guān)性值

3 多個目標(biāo)模型建立

3.1 模塊耦合度和內(nèi)聚度模型

設(shè)產(chǎn)品有N個基本單元，則兩兩模塊的總關(guān)聯(lián)度為 ，ωF和ωS為功能相關(guān)準(zhǔn)則的權(quán)重系數(shù)和結(jié)構(gòu)相關(guān)準(zhǔn)則的權(quán)重系數(shù)，fij為功能相關(guān)值，sij為結(jié)構(gòu)相關(guān)值。假設(shè)模塊Uh共有Ph個基本單元組成，則所有M個模塊的總聚合度C1可用下式計算：

假設(shè)模塊Us共有Ps個基本單元組成，模塊Ut共有Pt個基本單元組成，可以得到模塊Us與Ut之間的耦合度為：

則可得所有模塊間的總耦合度為：

3.2 模塊整體綠色度模型

若模塊Uh共有Ph個基本單元組成，則它們的對于第k個綠色準(zhǔn)則共同的屬性值變?yōu)?miH（）,k=1,2,3,4,5；=max(),k=6,7；這樣產(chǎn)品劃分為M個模塊后的總綠色度為：

式中，ωk為第k個綠色準(zhǔn)則的權(quán)重系數(shù)。

4 問題求解

規(guī)劃模型為式(1)、式(3)、式(4)三個目標(biāo)函數(shù)，分別是maxC1，minC2，；在此采用加權(quán)系數(shù)法把多目標(biāo)轉(zhuǎn)化為單目標(biāo)求解求最大值，這是個NP組合問題，適合用提出的蟻群優(yōu)化算法求解。

4.1 基本蟻群算法[9,10]

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

步驟1：初始化各個參數(shù)，設(shè)置最大迭代次數(shù)N，各個路徑信息素ηij，啟發(fā)式參數(shù)值α,β,ρ等；

步驟2：循環(huán)迭代開始；

步驟3：將m只螞蟻隨機的放在n個城市上面；

步驟4：設(shè)置好禁忌表控制下一個訪問城市，保存好訪問的城市；

步驟5：根據(jù)狀態(tài)概率公式(5)來計算螞蟻選擇下一個城市j的概率，j是非禁忌表中的城市；

allowed代表非禁忌表中的城市，表示t時刻還沒有訪問的城市；

步驟6：選擇具有最大狀態(tài)轉(zhuǎn)移概率的城市，并把該城市標(biāo)記進禁忌表中，存好城市訪問次序；

步驟7：若m只螞蟻還沒有訪問完所有的城市，就轉(zhuǎn)步驟5繼續(xù)執(zhí)行；否則轉(zhuǎn)步驟8；

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

LkQ為常量，表示螞蟻循環(huán)一周在經(jīng)過的所有路徑上釋放的信息素總量，表示第k只螞蟻在本次循環(huán)中所有走過的路徑的總長度。

步驟9：若m只螞蟻均迭代最大迭代次數(shù)則輸出結(jié)束，否則清空禁忌表，城市訪問次序表以及初始化相關(guān)值轉(zhuǎn)步驟3。

4.2 提出一種求解蟻群算法

本文提出一種蟻群算法對綠色模塊劃分優(yōu)化進行求解，求解步驟如下：

步驟1：初始化各個參數(shù)以及矩陣值，螞蟻數(shù)，迭代次數(shù)，初始化信息素；存儲好功能相關(guān)性值、結(jié)構(gòu)相關(guān)性值以及綠色性值；準(zhǔn)備好禁忌表和訪問表以及模塊劃分遞增表。

步驟2：循環(huán)迭代開始。

步驟3：把螞蟻隨機存放在各個頂點上，在這里各個頂點是指各個可供選擇的各個零件，同時記錄好禁忌表和訪問表以及模塊劃分遞增表。

步驟4：按照式(9)，選擇轉(zhuǎn)移概率最大的那個作為下一個選擇，如果所得的轉(zhuǎn)移概率大于隨機數(shù)rand()，則歸為上一個頂點所在的模塊，否則作為另外一個模塊。

γij(t )表示頂點的信息素，ηij(t)表示頂點的功能相關(guān)性和結(jié)構(gòu)相關(guān)性，πij(t)表示綠色性，α為信息素啟發(fā)因子，β為功能相關(guān)新和結(jié)構(gòu)相關(guān)性啟發(fā)因子，δ為綠色性啟發(fā)因子。

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

步驟6：更新信息素，根據(jù)模塊劃分遞增表所走過的路徑，按照式(10)～式(12)對稱添加信息素，同時考慮揮發(fā)因素；比如1112234456則相同的兩個頂點之間添加信息素，跳變而不相同的相鄰兩頂點不添加信息素。

LkQ為常量，它是一個系數(shù)，Lk是螞蟻在本次循環(huán)中獲得模塊劃分適應(yīng)度值，其適應(yīng)度值按照式(13)計算，同時保留適應(yīng)度最高的那個值以及模塊劃分。

步驟7：迭代次數(shù)未完則轉(zhuǎn)步驟2，否則結(jié)束輸出最優(yōu)解。

4.3 實驗數(shù)據(jù)

采用C_FREE5.0為運行環(huán)境，C語言編寫程序，迭代次數(shù)均為500次，設(shè)置不同的參數(shù)獲得的實驗結(jié)果如表3所示。

表3 實驗結(jié)果

通過十次實驗均獲得收斂，該蟻群算法所均在一秒鐘內(nèi)完成算法的計算，同時獲得收斂，收斂速度極快；最優(yōu)適應(yīng)值為26.000;最佳模塊劃分?jǐn)?shù)值為1,1,1,1,5,5,4,4,4,3,2和5,5,5,5,1,1,4,4,4,3,2；最優(yōu)模塊劃分為{主梁、軌道、端梁、端梁欄桿}為同一模塊，{走臺、走臺欄桿}為同一模塊，{直梯、斜梯、司機室平臺}為同一模塊，{司機室}為一單獨模塊，{檢驗平臺}為一獨立模塊；這也符合文獻[8]的結(jié)論和實際要求。

在十次實驗中，無論改變蟻群算法的相應(yīng)參數(shù)，該算法均表示很大的穩(wěn)定性，不同于以往的基本蟻群算法的情況有兩點：1）參數(shù)的設(shè)置隨意性較大，信息素啟發(fā)因子α，功能相關(guān)性和結(jié)構(gòu)相關(guān)性啟發(fā)因子β，綠色性啟發(fā)因子δ，揮發(fā)系數(shù)ρ，螞蟻數(shù)目М均可以較大的隨意性，不會影響收斂結(jié)果和最優(yōu)結(jié)果；2）收斂速度極快。但是也發(fā)現(xiàn)一些需要進一步研究的問題：當(dāng)螞蟻M數(shù)目比較小時候，發(fā)現(xiàn)螞蟻走的路徑幾乎每一次迭代遍歷路徑中，螞蟻都是走的最優(yōu)路徑，最優(yōu)值都是26.000；但是當(dāng)螞蟻數(shù)目M設(shè)置比較大的時候，任何一次迭代的路徑遍歷中，每只螞蟻只有部分會走最優(yōu)路徑，這跟生活當(dāng)中螞蟻覓食過程中，最后所有螞蟻趨向最優(yōu)路徑有點不同。

5 結(jié)束語

本文提出了一種蟻群算法來求解同時考慮模塊功能相關(guān)性和結(jié)構(gòu)相關(guān)性以及零件綠色性的綠色模塊劃分最優(yōu)組合問題；結(jié)果符合實際要求，實驗方法具有可行性和應(yīng)用性。當(dāng)可供選擇的零件急劇增大的時候，往往這些問題都是NP問題，大數(shù)據(jù)獲取信息需要的是速度和方法結(jié)果的正確性，把此方法移植到制造業(yè)信息化當(dāng)中，能夠給企業(yè)帶來節(jié)省財力人力的利益，帶來企業(yè)競爭力。通過大量的實驗作者，發(fā)現(xiàn)蟻群算法繼續(xù)發(fā)揮它自身的特點，收斂速度極快，作者提出的蟻群算法能極大效率的解決綠色模塊劃分問題，在實驗中發(fā)現(xiàn)螞蟻不盡是走向同一條最優(yōu)路徑，可能跟作者在算法中的進行模塊劃分時提出的隨機數(shù)大小比較有關(guān)；作者將繼續(xù)改進算法，下一步的研究將是基于PARETO求解的多目標(biāo)離散蟻群算法獲取解集的多樣性，還會引入帶約束條件的目標(biāo)隨機模型等，解決更多的生產(chǎn)實際問題。

[1]郭偉祥.綠色產(chǎn)品概念設(shè)計過程與方法研究[D].合肥:合肥工業(yè)大學(xué),2005.

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

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

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

[5]Hwai-En Tseng,Chien-Chen Chang,Jia-Diann Li.Modular design to support green life-cycle engineering[J].Expert Systems with Applications,2008,34:2524-2537.

[6]Yasushi Umeda，Shinichi Fukushige，Keita Tonoike，etal.Product modularity for life cycle design[J].CIRP Annals-Manufacturing Technology,2008(57):13-16.

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

[8]劉瓊,徐洋,鄧明中面向產(chǎn)品配置的模塊劃分方法[J].南華大學(xué)學(xué)報(自然科學(xué)版) 2012-626(2).

[9]汪定偉,王俊偉,王洪峰,張瑞友.智能優(yōu)化方法[M].北京:高等教育出版社,2007.

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