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

劉電霆，胡浩平

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

0 引言

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

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

1 問題描述

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

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

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

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

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

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

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

表1 零件屬性

表2 相關(guān)性值

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

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

設(shè)產(chǎn)品有N個(gè)基本單元，則兩兩模塊的總關(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個(gè)基本單元組成，則所有M個(gè)模塊的總聚合度C1可用下式計(jì)算：

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

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

3.2 模塊整體綠色度模型

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

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

4 問題求解

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

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

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

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

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

步驟3：將m只螞蟻隨機(jī)的放在n個(gè)城市上面；

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

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

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

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

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

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

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

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

4.2 提出一種求解蟻群算法

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

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

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

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

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

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

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

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

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

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

4.3 實(shí)驗(yàn)數(shù)據(jù)

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

表3 實(shí)驗(yàn)結(jié)果

通過十次實(shí)驗(yàn)均獲得收斂，該蟻群算法所均在一秒鐘內(nèi)完成算法的計(jì)算，同時(shí)獲得收斂，收斂速度極快；最優(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)模塊劃分為{主梁、軌道、端梁、端梁欄桿}為同一模塊，{走臺(tái)、走臺(tái)欄桿}為同一模塊，{直梯、斜梯、司機(jī)室平臺(tái)}為同一模塊，{司機(jī)室}為一單獨(dú)模塊，{檢驗(yàn)平臺(tái)}為一獨(dú)立模塊；這也符合文獻(xiàn)[8]的結(jié)論和實(shí)際要求。

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

5 結(jié)束語(yǔ)

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

[1]郭偉祥.綠色產(chǎn)品概念設(shè)計(jì)過程與方法研究[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è)計(jì)研究現(xiàn)狀及展望—一般理論及方法[J].航空制造技術(shù),2004,10:73-78.

[4]王日君,張進(jìn)生,葛培琪,等.模塊化設(shè)計(jì)中模塊劃分方法的研究[J].組合機(jī)床與自動(dòng)化加工技術(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ì)方法研究[J].機(jī)械工程學(xué)報(bào),2003,39(11):149-154.

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

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

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