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

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

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

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

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

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

1 IWO 算法

有別于一般進(jìn)化算法, IWO 算法建立了一種子代繁衍機(jī)制:按照種群中個(gè)體的適應(yīng)度值按比例分配其所產(chǎn)生子代的數(shù)目, 適應(yīng)度高的個(gè)體繁衍的子代數(shù)目多, 而適應(yīng)性較差的個(gè)體也有生存和繁殖的機(jī)會(huì), 這種機(jī)制在加強(qiáng)較優(yōu)個(gè)體周?chē)木植克阉鞯耐瑫r(shí),兼顧群體多樣性,與自然界雜草群落真實(shí)發(fā)生的狀況更為相似[5].

IWO 算法的實(shí)現(xiàn)可以通過(guò)以下初始化、繁殖、空間分布及競(jìng)爭(zhēng)淘汰等4 個(gè)步驟來(lái)完成:

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

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

步驟3 ,更新進(jìn)化代數(shù)及種群中子代個(gè)體正態(tài)分布的標(biāo)準(zhǔn)差.

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

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

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

2 IWO 算法的收斂性分析

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

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

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

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

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

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

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

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

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

2.2 IWO 算法馬爾可夫鏈?zhǔn)諗啃苑治?/h3>

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

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

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

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

式中,P(t)為下三角矩陣, 其中.記此馬爾可夫鏈的k步轉(zhuǎn)移矩陣為P(k),由馬爾可夫鏈的性質(zhì)得P(k)=Pk,且P(k)收斂到一個(gè)全正穩(wěn)定隨機(jī)矩陣=(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算法進(jìn)化足夠多代數(shù)后,群體中的最優(yōu)個(gè)體以概率1 收斂到全局最優(yōu)解,且從以上證明可以看出, 算法的收斂與初始狀態(tài)無(wú)關(guān).它表示算法經(jīng)過(guò)相當(dāng)長(zhǎng)的時(shí)間后趨于平衡狀態(tài).這時(shí), 各個(gè)解的概率分布既不依賴于初始狀態(tài), 也不再隨時(shí)間的推移而改變.

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

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

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

代入實(shí)際數(shù)據(jù)后, 此問(wèn)題可抽象為如下數(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 算法對(duì)工程實(shí)例優(yōu)化的效果, 同樣將遺傳算法(GA)、蟻群算法(ACO)、粒子群算法(PSO)用于上述減速器模型的優(yōu)化, 各算法都進(jìn)化200 代,其余參數(shù)設(shè)置如下:

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

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

[2] 曹先彬, 羅文堅(jiān), 王煦法.基于免疫網(wǎng)絡(luò)調(diào)節(jié)的改進(jìn)遺傳算法[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] 曾淵, 李源, 許家棟.改進(jìn)微粒群算法在光子晶體優(yōu)化中的應(yīng)用[J] .計(jì)算機(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] 張志霞, 邵必林.基于改進(jìn)蟻群算法的運(yùn)輸調(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.