雜草算法收斂性分析及其在工程中的應(yīng)用

張 氫,陳丹丹,秦仙蓉,高 倩

(同濟大學(xué)機械工程學(xué)院, 上海201804)

進化類算法是根據(jù)自然界中生物的繁衍、進化機制演化而來的一種搜索尋優(yōu)技術(shù), 它遵循達爾文的“物競天擇,適者生存” 原則, 對一個隨機生成的初始種群進行不斷迭代進化, 逐步提高種群體的質(zhì)量,從而逐步逼近所求問題的最優(yōu)解[1].其中遺傳算法(GA)通過隨機的選擇、交叉和變異算子來完成整個尋優(yōu)過程,其本質(zhì)是對上代群體進行隨機、無指導(dǎo)性的搜索, 由此導(dǎo)致算法的早熟、局部搜索能力差, 以及中后期搜索效率低.另外, 由于遺傳算法的魯棒性差, 初始參數(shù)的設(shè)置對結(jié)果的影響較大[2].

粒子群算法(PSO)通過群體中粒子之間的合作與競爭產(chǎn)生的群體智能指導(dǎo)優(yōu)化搜索.在每次迭代時, 根據(jù)更新規(guī)則改變粒子的位置和速度,通過跟蹤微粒自身的歷史最優(yōu)值和群體內(nèi)所有個體找到的最優(yōu)值迭代尋找潛在解, 最后通過群體的協(xié)作找到最優(yōu)解.PSO 仍然存在著早熟和收斂放慢的現(xiàn)象,種群的多樣性隨著迭代增加而下降,導(dǎo)致無法收斂到全局最優(yōu)解的缺點[3].

蟻群算法(ACO)則模仿螞蟻覓食機理, 通過狀態(tài)轉(zhuǎn)移準則依概率搜索前進路徑,以信息素強度的局部和全局更新來控制和優(yōu)化搜索方向.ACO 具有較好的協(xié)作性和魯棒性,尋優(yōu)特性好, 但存在搜索時間長、收斂速度慢、容易陷于局部最優(yōu)解等缺點, 其收斂效果和計算效率與參數(shù)設(shè)置、信息素增量的選取等都有很大關(guān)系[4].

2006 年,Mehrabian 和Lucas 提出一種從自然界雜草進化原理演化而來的隨機搜索算法——擴張性雜草進化算法(IWO)[5].IWO 充分利用種群中的優(yōu)秀個體來指導(dǎo)群體的進化, 進化過程中子代個體以正態(tài)分布的方式疊加于父代個體周圍, 而此正態(tài)分布的標準差又隨著進化代數(shù)而動態(tài)地調(diào)整變化,兼顧了選擇力度和種群的多樣性,能夠有效克服不成熟收斂,而且算法結(jié)構(gòu)簡單、參數(shù)少、魯棒性較好.但原文并未對算法的收斂性進行分析.本文系統(tǒng)分析了IWO 的收斂性, 并將其應(yīng)用于工程實際優(yōu)化問題.

1 IWO 算法

有別于一般進化算法, IWO 算法建立了一種子代繁衍機制:按照種群中個體的適應(yīng)度值按比例分配其所產(chǎn)生子代的數(shù)目, 適應(yīng)度高的個體繁衍的子代數(shù)目多, 而適應(yīng)性較差的個體也有生存和繁殖的機會, 這種機制在加強較優(yōu)個體周圍的局部搜索的同時,兼顧群體多樣性,與自然界雜草群落真實發(fā)生的狀況更為相似[5].

IWO 算法的實現(xiàn)可以通過以下初始化、繁殖、空間分布及競爭淘汰等4 個步驟來完成:

步驟1,參數(shù)初始化.

步驟2,在搜索空間內(nèi)按均勻分布的方式產(chǎn)生N0個初始解.

步驟3 ,更新進化代數(shù)及種群中子代個體正態(tài)分布的標準差.

步驟4 ,繁殖子代,并將新種群分布于搜索空間.按適應(yīng)度值大小分配個體產(chǎn)生的子代個體數(shù)目, 適應(yīng)度值最大的個體產(chǎn)生的子代數(shù)目最多, 適應(yīng)度值最小(fmin)的個體產(chǎn)生的子代數(shù)目最少,其余各個個體生成的子代個體數(shù)目與其適應(yīng)度值服從線性關(guān)系.以父代個體為均值,子代個體以正態(tài)分布方式分布于父代個體周圍,產(chǎn)生的子代個體作為新種群.判斷新種群個體數(shù)目是否達到最大種群規(guī)模pmax,若小于pmax,轉(zhuǎn)步驟3 ,再轉(zhuǎn)步驟4 ;否則轉(zhuǎn)步驟3 再轉(zhuǎn)步驟5 .

步驟5 ,競爭淘汰,適者生存.當種群數(shù)目達到或超過pmax時,按步驟4 的相同方式進行種群繁殖和子代個體分布, 然后父代個體與子代個體按適應(yīng)度值大小一起進行排列, 消滅其中適應(yīng)度值較低的個體, 保持群體規(guī)模為pmax .

步驟6 ,判斷是否達到最大迭代代數(shù)Tmax,若當前進化代數(shù)小于Tmax,重復(fù)步驟3 及步驟5 ;如果達到了Tmax,則種群中適應(yīng)度最好的個體作為最優(yōu)解輸出.

2 IWO 算法的收斂性分析

2.1 IWO 算法全局收斂的基礎(chǔ)

對于一種算法, 其收斂性往往是人們所關(guān)心的首要問題.IWO 算法在進化過程中依賴優(yōu)秀個體的指導(dǎo)信息進行繁殖進化的機制是算法收斂的基礎(chǔ),算法中子代個體分布的標準差的動態(tài)調(diào)整是算法收斂的關(guān)鍵, 以正態(tài)分布的方式將子代個體疊加于父代個體周圍, 使算法能夠兼顧選擇力度和群體多樣性, 有效避開局部極值點,為算法的全局收斂提供了穩(wěn)定的保障.而且,算法中各參數(shù)的取值范圍較為寬裕, 對初始種群的依賴性也不高.

IWO 算法避開局部極值, 有效實現(xiàn)全局尋優(yōu)的因素主要有以下幾點:

(1)IWO 算法在初始化種群時, 以均勻分布的方式隨機將初始種群分布于整個搜索空間內(nèi), 保證了初始種群的多樣性.

(2)在進化過程中, 一旦發(fā)現(xiàn)一個優(yōu)秀的個體(即適應(yīng)度高的可行解),類似的個體亦將大量繁殖.優(yōu)秀個體不是被機械地保留和利用, 而是通過加強在其周圍的局部搜索, 充分發(fā)掘利用優(yōu)秀個體所反映的特征信息,變盲目產(chǎn)生子代個體為有指導(dǎo)地產(chǎn)生子代個體, 通過群體中優(yōu)秀個體的進化來指導(dǎo)整個群體向最優(yōu)解進化.

(3)子代個體以正態(tài)分布的方式, 疊加在父代個體周圍.由正態(tài)分布的知識可知,子代個體的產(chǎn)生多集中于上一代優(yōu)秀個體的附近,但也顧及了上一代優(yōu)秀個體附近以外的區(qū)域.這說明IWO 算法在加強對問題局部搜索能力的同時,也兼顧了全局搜索.

(4)IWO 算法中子代個體分布的標準差隨著進化代數(shù)而變化,通過對標準差的動態(tài)調(diào)整,在進化的早期和中期, 生成的群體在加大對優(yōu)秀個體附近解空間的投點密度的同時, 也兼顧了對優(yōu)秀個體附近解空間以外區(qū)域的搜索.這樣群體能保持較好的多樣性,可以有效地避免不成熟收斂現(xiàn)象的出現(xiàn).而在進化的后期, 隨著標準差變小, 局部搜索能力不斷加強, 算法以更高精度逐步逼近全局最優(yōu)解.標準差的動態(tài)調(diào)整是IWO 算法的重要技術(shù)環(huán)節(jié), 它可以在群體多樣性和選擇力度之間起到調(diào)節(jié)作用.

(5)IWO 算法中, 適應(yīng)度較差的個體也有繁殖的機會,并且與子代個體一起進行競爭淘汰.由于進化算法是一個隨機性和再現(xiàn)性的方法, 在演化過程中,有時種群中適應(yīng)性較差的個體反而比適應(yīng)性好的個體攜帶更多有用的信息, 因此就有可能在其子代個體中找到高適應(yīng)度的個體, 特別是當搜索空間為非線性、非凸時,較差個體所繁殖的子代可能會幫助算法完成突變, 跨過不可行域,這使獲得最優(yōu)解變得更為容易.

綜上所述,IWO 算法把進化建立在群體中優(yōu)秀個體的基礎(chǔ)上, 通過標準差的動態(tài)調(diào)整把局部搜索和全局搜索有機地結(jié)合起來.相比于其他進化算法,IWO 算法中的群體只是起到搜索引擎的作用, 優(yōu)秀個體的進化是基于一定概率規(guī)則引導(dǎo)下的一種統(tǒng)計結(jié)果.

2.2 IWO 算法馬爾可夫鏈收斂性分析

記IWO 算法的解空間為Ω,解個體為x,x∈Ω,每一代的最優(yōu)個體記為(t為進化代數(shù), 下同),{ ,t=0 ,1,…}構(gòu)成了一個離散時間的隨機過程.IWO 算法在父代個體的基礎(chǔ)上, 通過疊加服從正態(tài)分布的隨機變量產(chǎn)生下一代群體.記父代群體中的最優(yōu)個體為(其對應(yīng)狀態(tài)為Ei), 子代群體中的即最優(yōu)個體為(對應(yīng)狀態(tài)為E j).顯然,此狀態(tài)轉(zhuǎn)移構(gòu)成了一個離散的馬爾可夫鏈, 即子代個體的產(chǎn)生只與父代個體相關(guān),而與之前各代的個體無關(guān).由于標準差隨著進化代數(shù)而動態(tài)調(diào)整,此馬氏鏈是非時齊的(non-time homogeneous), 即其狀態(tài)轉(zhuǎn)移概率f(x*)] =1 .與進化代數(shù)有關(guān).設(shè)為從第t代的狀態(tài)E i轉(zhuǎn)移到第t+1 代的狀態(tài)Ej的轉(zhuǎn)移概率.從保留最優(yōu)個體的角度考慮

定義1 設(shè)全局最優(yōu)解為x*, 如果對于隨機過程{ ,t=0 ,1,…},有=f(x*)] =1成立,則稱算法以概率1 收斂于全局最優(yōu)解.

定理1 IWO 算法以概率1 收斂到全局最優(yōu)解.

證明 如果將群體中的個體按適應(yīng)度值從大到小進行排列,則IWO 算法的有限狀態(tài)馬氏鏈第t代的一步轉(zhuǎn)移概率矩陣為

式中,P(t)為下三角矩陣, 其中.記此馬爾可夫鏈的k步轉(zhuǎn)移矩陣為P(k),由馬爾可夫鏈的性質(zhì)得P(k)=Pk,且P(k)收斂到一個全正穩(wěn)定隨機矩陣=(1 ,1,…,1)T(p1,p2,…,p n),其中(p1,p2,…,p n)惟一滿足(p1,p2,…,p n)P =(p1,p2,…,p n)=1,及.即(p1,p2,…,p n)是矩陣P 的特征值為1 且每一分量為正數(shù)的左乘特征向量.所以

所以,從馬氏鏈的極限分布可以得知,IWO 算法以概率1 收斂于全局最優(yōu)解,由此定理1 得證.該定理表明, IWO算法進化足夠多代數(shù)后,群體中的最優(yōu)個體以概率1 收斂到全局最優(yōu)解,且從以上證明可以看出, 算法的收斂與初始狀態(tài)無關(guān).它表示算法經(jīng)過相當長的時間后趨于平衡狀態(tài).這時, 各個解的概率分布既不依賴于初始狀態(tài), 也不再隨時間的推移而改變.

3 IWO 算法的工程應(yīng)用

減速器優(yōu)化設(shè)計模型是一個較典型的高維、多約束優(yōu)化設(shè)計問題.圖1 是某型減速器結(jié)構(gòu)布置圖,優(yōu)化目標為減速器的體積最小(或質(zhì)量最輕), 問題的約束是齒的彎曲和接觸應(yīng)力及扭轉(zhuǎn)變形和應(yīng)力等滿足預(yù)定值.設(shè)計變量:x1為齒面寬度, cm ;x2為齒輪模量, cm ;x3為副齒輪齒數(shù);x4為軸1 上兩軸承之間的距離,cm ;x5為軸2 上兩軸承之間的距離, cm ;x6為軸承1 的直徑, cm ;x7為軸2 的直徑,cm .模型的具體推導(dǎo)過程可見文獻[6] .

圖1 某型減速器結(jié)構(gòu)布置圖Fig.1 Structural layout of a type of reducer

代入實際數(shù)據(jù)后, 此問題可抽象為如下數(shù)學(xué)模型:

式中:x1,x2,x4,x5,x6,x7為連續(xù)變量;x3為離散整數(shù)變量.

變量的上下界約束為:2 .6 cm ≤x1≤3 .6 cm ,0 .7 cm ≤x2≤0 .8 cm,17 cm ≤x3≤28 cm,7 .3 cm ≤x4 ≤8 .3 cm,7 .8 cm ≤x5 ≤8 .3 cm,2 .9 cm ≤x6 ≤3 .9 cm ,5 .0 cm ≤x7≤5 .5 cm ,g1(X)～g11(X)是所優(yōu)化模型的約束函數(shù).

為了研究IWO 算法對工程實例優(yōu)化的效果, 同樣將遺傳算法(GA)、蟻群算法(ACO)、粒子群算法(PSO)用于上述減速器模型的優(yōu)化, 各算法都進化200 代,其余參數(shù)設(shè)置如下:

GA ——種群大小取40 ,變量編碼的二進制位數(shù)取25 ,采用兩點交叉的方式, 交叉概率取0 .7,變異概率取0 .028 ;

ACO ——螞蟻個數(shù)為40,初始信息素濃度取0 .01 ,信息素揮發(fā)系數(shù)取0 .99 ;

PSO ——粒子個數(shù)取40,慣性權(quán)重ω=0 .729 8 ,加速度常數(shù)c1=c2=1 .496 2 .

IWO 算法在優(yōu)化此減速器模型時算法中各參數(shù)的設(shè)置如下:D=7 ,N0=10 ,pmax=30 ,最大種子數(shù)smax=5 ,最小種子數(shù)smin=1 ,n=3,初始標準差σini=[1,0 .1,9 ,1,0 .5,1 ,0 .5] ,最終標準差σfin=[0 .1,0 .1 ,0 .1 ,0 .1 ,0 .1 ,0 .1 ,0 .1] .

由于優(yōu)化算法本身不具備處理約束的能力, 為增加可比性, 在將上述各算法用于本文中減速器的優(yōu)化時, 一致采用文獻[7] 基于可行性規(guī)則的約束處理技術(shù)來處理約束, 將所求問題演化為一個無約束優(yōu)化模型,得出的結(jié)果列于表1 .

表1 減速器設(shè)計優(yōu)化結(jié)果對比Tab.1 Contrast of op tim ization resu lts of the reducer

從表1 可以看出,相比于其他3 個算法, IWO 算法在嚴格滿足約束條件的前提下,得出了更好的解.

4 結(jié)論

(1)IWO 算法以群體中優(yōu)秀個體來指導(dǎo)種群的進化, 以正態(tài)分布的方式將子代個體疊加在父代個體周圍,通過標準差的動態(tài)調(diào)整,兼顧了群體的多樣性和選擇力度.本文通過馬爾可夫鏈的極限分布, 證明算法以概率1 收斂到全局最優(yōu)解,并用算例與其他智能算法進行了對比.

(2)本文通過將IWO 算法應(yīng)用于減速器質(zhì)量最輕數(shù)學(xué)模型的優(yōu)化, 對該算法的有效性進行了討論.結(jié)果表明,IWO 算法能夠快速、有效地搜索到高質(zhì)量的優(yōu)化解, 對于解決工程實際問題具有較大的潛力.

(3)隨著函數(shù)維數(shù)和群體規(guī)模的增加, 如何有效縮短算法的運行時間,提高求解精度, 并提高約束優(yōu)化問題的適應(yīng)性,為今后的研究方向.

[1] 黃友銳.智能優(yōu)化算法及其應(yīng)用[M] .北京:國防工業(yè)出版社, 2008.H UANG You rui.Intelligent optimization algorithm s and its application[M] .Beijing :National Defense Industry Press, 2008.

[2] 曹先彬, 羅文堅, 王煦法.基于免疫網(wǎng)絡(luò)調(diào)節(jié)的改進遺傳算法[J] .高技術(shù)通訊, 2000, 10(10):23.CAO Xianbin, LUO Wenjian, WANG Xufa .An im proved genetic algorithm based on idiotypic network regulation[J] .High Technology Letters, 2000, 10(10):23.

[3] 曾淵, 李源, 許家棟.改進微粒群算法在光子晶體優(yōu)化中的應(yīng)用[J] .計算機仿真, 2008, 25(3):202.ZE NG Yuan, LI Yuan, XU Jiadong .Improved particle swarm optimization and its application in photonic crystal [J] .Compu ter Simulation, 2008, 25(3):202.

[4] 張志霞, 邵必林.基于改進蟻群算法的運輸調(diào)度規(guī)劃[J] .公路交通科技, 2008, 25(4):137.ZHANG Zhixia, SHAOBilin.Vehicle routing and scheduling based on improved ACO [J] .Journal of Highway and Transportation Research and Development,2008, 25(4):137.

[5] Mehrabian A R, Lucas C .A novel numerical optimization algorithm inspired from weed colonization [J] .Ecological Informatics, 2006, 1:355.

[6] Rao S S .Engineering optimization [M] .New York:John Wiley,1996.

[7] Kalyanamoy Deb .An efficient constraint handing method for genetic algorithms [J] .Compu ter Methods in Applied Mechanics and Engineering,2000(186):311.