改進(jìn)的野草入侵算法在模塊劃分中的應(yīng)用研究

趙 躍，單 泉，陳 硯，孔 芝

（東北大學(xué)秦皇島分校控制工程學(xué)院，河北 秦皇島 066004）

1 引言

模塊化設(shè)計(jì)是指在對(duì)產(chǎn)品進(jìn)行市場(chǎng)預(yù)測(cè)、功能分析的基礎(chǔ)上，綜合考慮產(chǎn)品對(duì)象，劃分并設(shè)計(jì)出一系列的功能模塊；然后根據(jù)用戶的要求，對(duì)模塊進(jìn)行選擇和組合，迅速組合成不同功能、或功能相同但性能不同、規(guī)格不同產(chǎn)品的一種設(shè)計(jì)方法。

當(dāng)前新一輪科技革命主導(dǎo)的新一輪工業(yè)革命正在到來(lái)，這也正是中國(guó)從制造大國(guó)走向制造強(qiáng)國(guó)的歷史性機(jī)遇。模塊化設(shè)計(jì)可以有效支持創(chuàng)新，符合創(chuàng)新驅(qū)動(dòng)的發(fā)展戰(zhàn)略。通過(guò)使用模塊化設(shè)計(jì)，能夠有效降低產(chǎn)品開(kāi)發(fā)設(shè)計(jì)復(fù)雜性、縮短產(chǎn)品開(kāi)發(fā)周期、有效支持企業(yè)間的協(xié)同創(chuàng)新設(shè)計(jì)、支持客戶參與產(chǎn)品開(kāi)發(fā)設(shè)計(jì)[1]。

模塊劃分是模塊化技術(shù)中的基石，模塊劃分方法根據(jù)形式可分為傳統(tǒng)模塊劃分方法和基于智能優(yōu)化算法的模塊劃分方法。文獻(xiàn)[2-4]基于模糊聚類的方法對(duì)相應(yīng)產(chǎn)品進(jìn)行了模塊劃分工作，取得一定的成果。然而模糊聚類方法在閾值的確定上往往需要反復(fù)嘗試，工作量較大，且對(duì)于組件數(shù)量較多的模塊劃分問(wèn)題，矩陣的變換分割也較為復(fù)雜。

因此，隨著計(jì)算機(jī)技術(shù)的發(fā)展，基于智能優(yōu)化算法的模塊劃分方法也得到了長(zhǎng)足的發(fā)展。遺傳算法被文獻(xiàn)[5-6]等廣泛應(yīng)用于模塊劃分工作；文獻(xiàn)[7-8]等在此基礎(chǔ)上，將遺傳算法與模擬退火算法融合，使原算法性能加以提高；文獻(xiàn)[9-10]等將免疫算法進(jìn)行改進(jìn)用于模塊劃分；離散粒子群算法也被文獻(xiàn)[11]等引入該領(lǐng)域；文獻(xiàn)[12]采用貓群算法進(jìn)行軟硬件的劃分，也取得了較好的效果。然而現(xiàn)階段基于智能優(yōu)化算法的模塊劃分方法的發(fā)展對(duì)模擬退火算法、遺傳算法、免疫算法、粒子群算法等成熟算法的依賴性較大，且以上算法在迭代精度、速度上存在一定的瓶頸，一些新算法仍有待于引入模塊劃分工作中。將野草入侵算法加以改進(jìn)引入模塊劃分中，為模塊劃分算法的設(shè)計(jì)與實(shí)現(xiàn)提供了一種全新的思路，對(duì)模塊化設(shè)計(jì)將起到一定的推動(dòng)作用。

2 算法簡(jiǎn)介

野草入侵算法是一種基于種群的無(wú)衍生優(yōu)化算法，其靈感來(lái)自田間雜草的殖民化。該算法具有入侵性、穩(wěn)健性以及適應(yīng)環(huán)境變化等特性[13]。

野草入侵算法有四個(gè)主要步驟：初始化、繁殖、空間分布和競(jìng)爭(zhēng)排斥。在初始化步驟中，在搜索域隨機(jī)生成一定量的個(gè)體，組成初始種群；繁殖個(gè)體，每個(gè)個(gè)體根據(jù)其適應(yīng)度值產(chǎn)生種子數(shù)量。第三步，使用高斯分布在搜索空間上分布生成的種子，由于新生種子數(shù)量與個(gè)體的適應(yīng)度有關(guān)，因此使用高斯函數(shù)完成空間分布能夠有效提高空間搜索的效率；由于繁殖過(guò)程，其種群大小在每次迭代時(shí)都會(huì)增加，因此算法的最后一步是競(jìng)爭(zhēng)排斥，通過(guò)從群體中移除最差的個(gè)體來(lái)限制最大允許群體大小至規(guī)定值，從而控制群體大小。

與傳統(tǒng)遺傳算法相比，野草入侵算法不需要交叉變異等操作，因此其操作簡(jiǎn)潔，計(jì)算效率高，運(yùn)行時(shí)間短。但其新生個(gè)體的策略導(dǎo)致了算法由全局搜索逐步轉(zhuǎn)變?yōu)榫植克阉鳎蛊淙炙阉髂芰Σ粡?qiáng)，易于陷入局部最優(yōu)。此外，該算法的隨機(jī)搜索特性對(duì)其收斂速度也存在著一定的影響。

3 改進(jìn)的野草入侵算法在模塊劃分中的應(yīng)用

野草入侵算法創(chuàng)立之初，是為了解決多元函數(shù)的最小值求解問(wèn)題。與多元函數(shù)極值問(wèn)題不同，組合問(wèn)題中解空間的各個(gè)維度并不存在最優(yōu)值，且存在著相互關(guān)聯(lián)，其最優(yōu)解決定于分組情況。將該算法應(yīng)用于模塊劃分中，需要對(duì)算法做出適當(dāng)?shù)男薷模詽M足其約束條件以及使用要求。

首先，模塊的組成需要滿足以下兩個(gè)約束條件：任意模塊之間不能含有相同的元素；所有模塊的集合構(gòu)成待劃分元素庫(kù)的整體。針對(duì)以上條件，對(duì)該算法中各個(gè)部分加以修改，修改后應(yīng)用于模塊劃分的野草入侵算法流程，如圖1所示。

圖1 應(yīng)用于模塊劃分的改進(jìn)野草入侵算法流程Fig.1 Flow of Improved Weed Invasion Algorithm Applied to Module Partitioning

以求取適應(yīng)度函數(shù)最大值時(shí)的分組方式為例，采用MATLAB進(jìn)行程序編寫具體步驟如下：

（一）初始化種群，隨機(jī)生成N0個(gè)模塊劃分的形式，針對(duì)每個(gè)個(gè)體，其模塊劃分結(jié)果將是相互獨(dú)立的。由經(jīng)驗(yàn)公式，模塊劃分中默認(rèn)模塊數(shù)目的最大整數(shù)）。根據(jù)確定的模塊數(shù)量求取方式，確定模塊數(shù)量，將n個(gè)代表元素代碼的數(shù)字隨機(jī)存入代表模塊的元胞（cell）中，并確保每個(gè)元胞中均存在元素。通過(guò)該方法完成模塊劃分，并分別求出每個(gè)個(gè)體對(duì)應(yīng)的適應(yīng)度函數(shù)值，完成種群初始化的工作。

（二）根據(jù)適應(yīng)度函數(shù)值對(duì)種群從大到小進(jìn)行排序，并記錄每次迭代的最大值與最小值。

（三）結(jié)合所記錄的最大值與最小值，計(jì)算每種分組方式對(duì)應(yīng)的新種子個(gè)數(shù)。使用如下的式（1）用于新種子個(gè)數(shù)的求解。

（四）對(duì)原算法進(jìn)行改進(jìn)，根據(jù)求得的新生種子數(shù)量，對(duì)選定的個(gè)體進(jìn)行鄰域的搜索，以替代在一定范圍內(nèi)隨機(jī)生成新種子的操作。即選取任意模塊中任意組件，將該組件放入任意其他模塊中，完成模塊的重新生成，并重新求解在該分組情況下的適應(yīng)度函數(shù)值。需要指明一點(diǎn)，為了使重組后的模塊劃分不存在空模塊的情況，被選中遷出組件的模塊原組件數(shù)必須大于1。

（五）將原始種群與新生個(gè)體進(jìn)行合并，組成新的種群，之后按照適應(yīng)度函數(shù)值從大到小對(duì)新種群進(jìn)行排序。由于新個(gè)體的加入，每次迭代種群中個(gè)體數(shù)量都會(huì)有所增加，因此通過(guò)從群體中移除最差的個(gè)體（即排名末位的個(gè)體）來(lái)將種群中個(gè)體數(shù)量減小至Nmax，從而達(dá)到競(jìng)爭(zhēng)排斥的效果。

（六）當(dāng)滿足迭代終止條件時(shí)，退出迭代，輸出最大的適應(yīng)度函數(shù)值以及與之相對(duì)應(yīng)的最佳模塊劃分方式。

保留原算法中新生種子個(gè)數(shù)的計(jì)算方式，使新生種子對(duì)原有種群優(yōu)良性狀的繼承性得到增強(qiáng)，且提升算法對(duì)最優(yōu)解的探索效率。同時(shí)，借鑒鄰域搜索操作，代替野草入侵算法中的以正態(tài)分布隨機(jī)生成種子的方法，增強(qiáng)算法的全局搜索能力，能夠彌補(bǔ)其在全局收斂上表現(xiàn)較差的情況，改善其容易陷入局部最優(yōu)值的問(wèn)題，增強(qiáng)該算法的穩(wěn)健性，確保算法在每次優(yōu)化過(guò)程中均能收斂到其全局最優(yōu)的模塊劃分方案上。

同時(shí)選用野草入侵算法中的競(jìng)爭(zhēng)排斥機(jī)制進(jìn)行較差個(gè)體剔除的工作，減少算法迭代中的計(jì)算量，保持算法簡(jiǎn)潔易于操作的特性，提高程序的運(yùn)行速度，保證了算法迭代的高效性，并能夠有效解決陷入局部最優(yōu)值的問(wèn)題。與此同時(shí)，另一個(gè)重要改進(jìn)在于在算法中進(jìn)一步刪除種群變異、隨機(jī)生成新生種子等操作，進(jìn)一步簡(jiǎn)化算法，從而能夠保證算法收斂的速度與準(zhǔn)確性。

4 實(shí)例驗(yàn)證

為了驗(yàn)證本方法的正確性且不失一般性，分別以文獻(xiàn)[15]中24個(gè)元件的直齒輪減速器以及文獻(xiàn)[16]中24個(gè)元件的錐齒輪三級(jí)減速器作為實(shí)例1與實(shí)例2進(jìn)行驗(yàn)證。適應(yīng)度函數(shù)值由式（2）給出。實(shí)例1的最優(yōu)適應(yīng)度函數(shù)值是0.32749，其最優(yōu)模塊劃分結(jié)果是{1，2，9，10，19}、{3，4，11，12，13，20，23}、{5，6，14，15，16，21，24}和{7，8，17，18，22}；實(shí)例2最優(yōu)適應(yīng)度函數(shù)值是0.4399，其最優(yōu)模塊劃分結(jié)果是{1，5，17，18，19}、{2，6，9，11，14，20，23}、{3，7，10，12，15，21，24}和{4，8，13，16，22}。

其中，Im（i，j）—第i個(gè)組件與第j個(gè)組件之間的相關(guān)度，即設(shè)計(jì)結(jié)構(gòu)矩陣中第i行第j列元素的取值。

設(shè)定模塊數(shù)量為4，設(shè)定其初始種群數(shù)量為50，最大迭代次數(shù)500，最大種子最大值為4，最小值為0，實(shí)例1使用改進(jìn)的野草入侵算法進(jìn)行模塊劃分，當(dāng)?shù)降?7 次時(shí)，適應(yīng)度函數(shù)值收斂，得到適應(yīng)度函數(shù)的最優(yōu)值0.32749，模塊劃分結(jié)果與文獻(xiàn)[15]相同；實(shí)例2使用改進(jìn)的野草入侵算法進(jìn)行模塊劃分，當(dāng)?shù)降?1次時(shí)，適應(yīng)度函數(shù)值收斂，得到適應(yīng)度函數(shù)的最優(yōu)值0.4399，模塊劃分結(jié)果與文獻(xiàn)[16]相同。證明應(yīng)用于模塊劃分的改進(jìn)的野草入侵算法是一種有效的模塊劃分算法。

為了進(jìn)行對(duì)比，加入標(biāo)準(zhǔn)野草入侵算法、粒子群算法、遺傳算法、免疫算法進(jìn)行相同的分組。設(shè)置各個(gè)算法初始種群數(shù)量均為50，最大迭代次數(shù)500。野草入侵算法的最大種子最大值為4，最小值為0；粒子群算法的位置最大最小值為4和1（位置最大值代表模塊個(gè)數(shù)），速度最大值為2；遺傳算法的變異概率為0.2，交叉概率為0.6，選擇精英個(gè)數(shù)為10；免疫算法的克隆親本個(gè)數(shù)為10，克隆數(shù)量為5，突變概率為0.5。分別得到最優(yōu)模塊劃分結(jié)果，優(yōu)化曲線，如圖2所示。其中上半部分為實(shí)例1的優(yōu)化曲線，下半部分為實(shí)例2的優(yōu)化曲線。

圖2 五種算法的優(yōu)化結(jié)果對(duì)比圖Fig.2 Comparison of Optimization Results of Five Algorithms

由圖可知，在兩個(gè)實(shí)例中，改進(jìn)的野草入侵算法均達(dá)到最快的收斂。為了不失一般性，將以上各個(gè)算法重復(fù)運(yùn)行50次，對(duì)運(yùn)行時(shí)間、最快收斂代數(shù)、最慢收斂代數(shù)、平均收斂代數(shù)，收斂代數(shù)的標(biāo)準(zhǔn)差幾個(gè)參數(shù)進(jìn)行考察，如表1所示。

表1 五種算法結(jié)果對(duì)比Tab.1 Comparison of the Results of the Five Algorithms

由以上兩個(gè)實(shí)例可知，改進(jìn)的野草入侵算法與其他算法相比，性能提升較為明顯，且在運(yùn)行速度和收斂速度上均大幅優(yōu)于其他四種算法，且收斂代數(shù)的標(biāo)準(zhǔn)差最小，說(shuō)明了該算法較強(qiáng)的魯棒性。由此可知應(yīng)用于模塊劃分領(lǐng)域的改進(jìn)的野草入侵算法是一種高效且準(zhǔn)確可靠的算法。

5 模塊劃分軟件系統(tǒng)的編寫

基于以上結(jié)果，參考設(shè)計(jì)人員的工作習(xí)慣，并提高模塊劃分的效率，增加算法整體的可移植性，采用Python3.7開(kāi)發(fā)人機(jī)交互的最優(yōu)模塊劃分結(jié)果求取的軟件系統(tǒng)，其主界面，如圖3所示。

圖3 模塊劃分系統(tǒng)主界面圖Fig.3 Main Interface Diagram of the Module Partitioning System

其后臺(tái)迭代程序仍采用如圖1的算法流程進(jìn)行編寫，在此基礎(chǔ)上對(duì)迭代過(guò)程中的適應(yīng)度函數(shù)加以改進(jìn)，采用如下公式進(jìn)行迭代計(jì)算。

與式（2）類似，其中，N—組件數(shù)量之和；Nm—第m個(gè)模塊的組件數(shù)量；r—模塊數(shù)；Im（i，j）—整體結(jié)構(gòu)設(shè)計(jì)矩陣中第i行j列元素；Ck—模塊內(nèi)得組合數(shù)。

式（6）中第一項(xiàng)可作為各個(gè)模塊中組件數(shù)量相似性的度量，即可對(duì)模塊劃分結(jié)果中各個(gè)模塊中組件數(shù)量的平均程度加以保障；第二項(xiàng)中的分子與分母分別為內(nèi)聚度和耦合度的表征。因此當(dāng)模塊劃分結(jié)果呈現(xiàn)出“高內(nèi)聚、低耦合”特性，且各模塊中組件數(shù)量近似相等時(shí)，適應(yīng)度函數(shù)取得最大值。

應(yīng)用本軟件系統(tǒng)，用戶可以完成的主要功能有：用戶輸入結(jié)構(gòu)設(shè)計(jì)矩陣的保存、已存在結(jié)構(gòu)設(shè)計(jì)矩陣的讀取、最優(yōu)組合結(jié)果的輸出、迭代過(guò)程的顯示與儲(chǔ)存。仍采用文獻(xiàn)[15]中的實(shí)例對(duì)該軟件系統(tǒng)的使用過(guò)程進(jìn)行說(shuō)明，使用過(guò)程如下：

首先，用戶在組件數(shù)量對(duì)話框中輸入組件數(shù)量24，點(diǎn)擊右側(cè)“創(chuàng)建結(jié)構(gòu)設(shè)計(jì)矩陣”按鈕，在界面中按照順序輸入各個(gè)組件之間的相關(guān)度，完成結(jié)構(gòu)設(shè)計(jì)矩陣的建立，點(diǎn)擊“保存”，將結(jié)構(gòu)設(shè)計(jì)矩陣保存為Excel表格文件，如圖4所示。

圖4 創(chuàng)建結(jié)構(gòu)設(shè)計(jì)矩陣頂級(jí)窗口Fig.4 The Top-level Window for Creating the Design Structure Matrix

之后，點(diǎn)擊“請(qǐng)選擇結(jié)構(gòu)設(shè)計(jì)矩陣”后的“點(diǎn)擊選擇”按鈕完成文件的讀取的工作，此時(shí)文件所對(duì)應(yīng)的路徑便會(huì)顯示在右側(cè)的文本框中。之后，通過(guò)復(fù)選按鈕確定參與計(jì)算的結(jié)構(gòu)設(shè)計(jì)矩陣，并對(duì)其設(shè)定相應(yīng)的權(quán)重值。最后，通過(guò)右側(cè)三個(gè)單選按鈕對(duì)結(jié)果的顯示與保存方式進(jìn)行選擇，即可完成最佳分組情況計(jì)算前的準(zhǔn)備工作。準(zhǔn)備工作結(jié)束后，點(diǎn)擊開(kāi)始迭代按鈕，迭代過(guò)程與分組結(jié)果即顯示在文本框中，如圖5所示。此時(shí)根據(jù)輸出結(jié)果顯示，計(jì)算后的最佳分組是{1，2，9，10，19}、{3，4，11，12，13，20，23}、{5，6，14，15，16，21，24}和{7，8，17，18，22}，與文獻(xiàn)[15]中結(jié)果相同，證明本軟件系統(tǒng)在模塊劃分中的真實(shí)可靠性。

圖5 迭代過(guò)程與模塊劃分結(jié)果的顯示Fig.5 Iterative Process and Display of Module Partitioning Results

本軟件基于模塊劃分的步驟，使設(shè)計(jì)人員通過(guò)創(chuàng)建、選取加載結(jié)構(gòu)設(shè)計(jì)矩陣并設(shè)置相應(yīng)的權(quán)重等過(guò)程，求得最佳分組結(jié)果及其所對(duì)應(yīng)的適應(yīng)度函數(shù)值，并可以根據(jù)用戶的需求顯示并保存所需結(jié)果。軟件整體使用流程符合設(shè)計(jì)人員的設(shè)計(jì)習(xí)慣，能夠有效提高設(shè)計(jì)人員的設(shè)計(jì)效率，減少重復(fù)性勞動(dòng)，對(duì)模塊化設(shè)計(jì)起到較大的促進(jìn)作用。

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

將野草入侵算法加以改進(jìn)應(yīng)用于模塊劃分中，改變?cè)惴ㄖ行律鷤€(gè)體的操作，并刪除種群變異、隨機(jī)生成新生種子等操作，使程序編碼簡(jiǎn)潔，算法易于實(shí)現(xiàn)，且新算法兼顧收斂速度與準(zhǔn)確性兩個(gè)重點(diǎn)，與原算法相比在性能上有較大的提升。并通過(guò)實(shí)例驗(yàn)證，證明了該算法的可行性，為模塊劃分算法的設(shè)計(jì)提供了一種新的思路。并且將該算法與粒子群算法、遺傳算法、免疫算法進(jìn)行比對(duì)，證明了該算法在模塊劃分中的高效性。并基于該算法，開(kāi)發(fā)出模塊劃分軟件系統(tǒng)，以提高設(shè)計(jì)人員的設(shè)計(jì)效率，減少重復(fù)性勞動(dòng)，促進(jìn)模塊化設(shè)計(jì)的發(fā)展。