適應(yīng)性微粒群尋優(yōu)算法

適應(yīng)性微粒群尋優(yōu)算法

1適應(yīng)性粒子群優(yōu)化算法pso優(yōu)化算法是金元等提出的基于種群搜索的自適應(yīng)進(jìn)化算法。該算法受鳥(niǎo)和魚(yú)類(lèi)活動(dòng)規(guī)律的啟發(fā)，采用自然選擇機(jī)制取代了攻擊和魚(yú)類(lèi)活動(dòng)的組織行為，并通過(guò)組間個(gè)人合作開(kāi)展最優(yōu)解決方案。與其他全局優(yōu)化算法(如遺傳算法)一樣,粒子群優(yōu)化算法同樣存在早熟收斂現(xiàn)象,尤其是在較復(fù)雜的多峰搜索問(wèn)題中.另外,PSO算法在種群初始化和微粒飛行過(guò)程中均具有隨機(jī)性,使得算法的執(zhí)行結(jié)果也具有隨機(jī)性.Millonas研究了群體在遷徙過(guò)程中的合作智能,Kennedy等提出的PSO算法受到了Millonas研究成果的啟發(fā).考察標(biāo)準(zhǔn)PSO算法,存在著進(jìn)一步模擬社會(huì)行為的可能性.Millonas指出,社會(huì)性的群體尋優(yōu)應(yīng)該是在秩序與混沌之間的平衡.基于該想法,本文提出了適應(yīng)性粒子群優(yōu)化算法,在標(biāo)準(zhǔn)PSO上引入了反映適應(yīng)性的隨機(jī)項(xiàng).為了分析適應(yīng)性粒子群優(yōu)化算法的性能,采用4個(gè)Benchmark函數(shù)進(jìn)行測(cè)試,并與標(biāo)準(zhǔn)PSO,HPSO,DPSO和AEPSO算法進(jìn)行對(duì)比分析.結(jié)果顯示,適應(yīng)性粒子群優(yōu)化算法具有較好的收斂穩(wěn)定性.2帶選擇的psoMillonas研究群體在遷徙過(guò)程中的合作智能,提出了5個(gè)規(guī)律:1)接近規(guī)律,種群能夠做基本的空間和時(shí)間計(jì)算;2)質(zhì)量規(guī)律,種群不僅應(yīng)該考慮空間和時(shí)間的花費(fèi),也要考慮食物的質(zhì)量和所在地的安全;3)多樣性規(guī)律,種群不應(yīng)支配它所有的資源沿著過(guò)度狹窄的線(xiàn)路,應(yīng)該分配它的資源選擇多種模式來(lái)應(yīng)對(duì)環(huán)境波動(dòng)的突然變化;4)穩(wěn)定性規(guī)律,種群在環(huán)境發(fā)生波動(dòng)時(shí),不應(yīng)輕易改變自己的行為模式,由于這些改變需要能量消耗,可能不會(huì)對(duì)投資產(chǎn)生一個(gè)合理的回報(bào);5)適應(yīng)性規(guī)律,當(dāng)改變行為習(xí)慣的報(bào)酬可能值得在能量上投資時(shí),種群應(yīng)該做出轉(zhuǎn)變的決定.最好的決策是在完全秩序和徹底混沌中間尋找平衡,所以在種群中存在一定水平的隨機(jī)性是很重要的.當(dāng)然隨機(jī)噪聲會(huì)帶來(lái)多樣性,若它太大將會(huì)破壞合作的行為習(xí)慣.Millonas指出,很多復(fù)雜適應(yīng)系統(tǒng)的行為可能會(huì)符合這些規(guī)則.有趣的是,這些規(guī)則同很多好的經(jīng)濟(jì)決定規(guī)律是類(lèi)似的:時(shí)間就是金錢(qián);寧可求穩(wěn),以免事后后悔;一鳥(niǎo)在手,勝于二鳥(niǎo)在林(最好滿(mǎn)足于現(xiàn)有的,以免因貪心而失去一切);不要把你的雞蛋放在一個(gè)籃子里面;為未來(lái)投資.Kennedy等人于1995年提出PSO的最初版本,其后Shi等人引入了慣性權(quán)重對(duì)算法進(jìn)行了改進(jìn),形成了當(dāng)前的標(biāo)準(zhǔn)版本.在每次迭代過(guò)程中,粒子的位置式確定如下:vi(t)=wvi(t?1)+c1r1(pi?xi(t?1))+c2r2(pg?xi(t?1)),(1)xi(t)=vi(t)+xi(t?1).(2)vi(t)=wvi(t-1)+c1r1(pi-xi(t-1))+c2r2(pg-xi(t-1)),(1)xi(t)=vi(t)+xi(t-1).(2)式中:xi為粒子位置;vi為粒子飛行速度;w為慣性權(quán)重;c1和c2為加速度常數(shù),取正常數(shù);r1和r2是在范圍變化的隨機(jī)數(shù);pi為粒子在歷史中的最好位置;pg為整個(gè)群體中的最好位置.Kennedy等人闡述了算法均滿(mǎn)足Millonas提出的體現(xiàn)群體合作智能的5個(gè)規(guī)律.求解問(wèn)題屬于n維空間,并且花費(fèi)一連串時(shí)間進(jìn)行迭代.種群飛向質(zhì)量因子pi和pg,在pi與pg之間的隨機(jī)分布保證了多樣性.只有當(dāng)pg改變時(shí),種群才改變自身狀態(tài),符合穩(wěn)定性規(guī)則;當(dāng)pg改變時(shí),種群也隨之改變,符合自適應(yīng)規(guī)律.但是PSO算法存在一個(gè)固有的缺陷,其粒子總是向全局最優(yōu)、個(gè)體最優(yōu)飛行,經(jīng)過(guò)一定次數(shù)的迭代后,可能發(fā)生全局最優(yōu)、個(gè)體最優(yōu)和所有粒子都相同的情況.這時(shí)按式(1)和(2)迭代,所有粒子的速度為0,粒子的位置不再發(fā)生變化,即發(fā)生早熟收斂.當(dāng)發(fā)生早熟收斂后,顯然對(duì)于自適應(yīng)群體的5個(gè)規(guī)律全部不滿(mǎn)足.為了避免早熟收斂,一些學(xué)者提出了通過(guò)控制種群多樣性來(lái)提高算法性能.提出了帶選擇的PSO,具有高斯變異的PSO,具有繁殖和子種群的PSO等改進(jìn)算法;考慮到微粒間合理高效的相互作用關(guān)系,提出了簇分析PSO,勞動(dòng)分工PSO和協(xié)同PSO等;還有的學(xué)者提出了進(jìn)化PSO,多階段PSO等.Xie在2002年提出耗散型PSO(DPSO),通過(guò)對(duì)微粒速度或位置引入一個(gè)小概率隨機(jī)變異操作來(lái)增強(qiáng)種群多樣性,使得該算法能夠有效地進(jìn)行全局搜索.但過(guò)大的變異率在增加種群多樣性的同時(shí)也將導(dǎo)致種群發(fā)生混亂,使種群不能進(jìn)行精確的局部搜索,延緩算法的收斂速度.Ratnaweera等人提出了自適應(yīng)層次PSO(HPSO),在自組織算法的基礎(chǔ)上給出了一種變異操作的自適應(yīng)參數(shù)選擇方式.HPSO算法消除了速度公式的慣性部分,發(fā)生變異的條件是微粒速度為0,使微粒不能快速、有效地逃出局部極小點(diǎn).赫然等人在2005年提出自適應(yīng)逃逸PSO(AEPSO),當(dāng)微粒飛行速度過(guò)小時(shí),通過(guò)逃逸運(yùn)動(dòng)使微粒能夠有效地進(jìn)行全局和局部搜索,具有較快的收斂速度,但該算法存在不穩(wěn)定性.目前對(duì)PSO的改進(jìn)使得PSO算法越來(lái)越復(fù)雜.Kennedy等指出,為什么社會(huì)行為如此普遍存在于動(dòng)物王國(guó),因?yàn)樗莾?yōu)化的,解決工程優(yōu)化問(wèn)題比較好的途徑就是模擬社會(huì)行為.仿效自然而不控制它,讓算法看起來(lái)簡(jiǎn)單而不是復(fù)雜.大自然已經(jīng)提供了第一流的信息處理技術(shù).本文注意到DPSO,HPSO和AEPSO在確保種群多樣性所進(jìn)行的有價(jià)值的工作,這幾種算法在引入隨機(jī)行為產(chǎn)生多樣性時(shí)都有各自發(fā)生的條件.本研究試圖在更大的范圍內(nèi)引入隨機(jī)行為,來(lái)進(jìn)一步模擬社會(huì)型的群體行為,獲取簡(jiǎn)單、具有穩(wěn)定性的尋優(yōu)算法.3適應(yīng)性粒子群尋優(yōu)算法考察標(biāo)準(zhǔn)PSO算法.式(1)的第1部分為微粒先前的速度,第2部分為認(rèn)知部分,表示微粒本身的思考;第3部分為社會(huì)部分,表示微粒間的信息共享與相互合作.這3部分都體現(xiàn)社會(huì)行為中的秩序,盡管在系數(shù)上給出各種隨機(jī)變化,但只是改變遵守秩序的規(guī)則.最終的結(jié)果導(dǎo)致把雞蛋放在同一個(gè)籃子里,沒(méi)有為未來(lái)投資,缺乏多樣性.哥倫布等探險(xiǎn)家的行為體現(xiàn)出社會(huì)行為的另一個(gè)方面,作為遵守規(guī)則和秩序的反面,冒險(xiǎn)、偏執(zhí)、狂妄、嫉妒、逆反等心理和其他非理性行為同時(shí)支配社會(huì)行為,保持種群高度的多樣性,以開(kāi)拓更廣泛的空間.社會(huì)性的群體尋優(yōu)應(yīng)該是在遵守秩序和隨機(jī)非理性行為之間的平衡,文獻(xiàn)提出的自適應(yīng)慣性權(quán)PSO算法中引入的隨機(jī)因子和動(dòng)量加速操作,實(shí)際上展現(xiàn)了這種隨機(jī)非理性行為對(duì)保持優(yōu)化解的多樣性和克服早熟收斂所起的作用.為此,本文在標(biāo)準(zhǔn)PSO公式中,持續(xù)引入一個(gè)體現(xiàn)隨機(jī)行為的項(xiàng),形成了適應(yīng)性粒子群尋優(yōu)算法(APSO).在每次迭代過(guò)程中,速度由下式確定:vi(t)=wvi(t?1)+c1r1(pi?xi(t?1))+c2r2(pg?xi(t?1))+(1?2r3)βRi.(3)vi(t)=wvi(t-1)+c1r1(pi-xi(t-1))+c2r2(pg-xi(t-1))+(1-2r3)βRi.(3)式中:r3是在范圍變化的隨機(jī)數(shù);β為混沌常數(shù),取正值;Ri為各維的搜索長(zhǎng)度;(1-2r3)βRi體現(xiàn)一種不可預(yù)測(cè)的隨機(jī)行為,命名為隨機(jī)項(xiàng).式(3)體現(xiàn)了對(duì)速度的決策存在著正反面,前3項(xiàng)體現(xiàn)秩序,最后1項(xiàng)體現(xiàn)隨機(jī)非理性.將式(3)與式(1)相比,可以看出即使出現(xiàn)發(fā)生全局最優(yōu)、個(gè)體最優(yōu)和粒子都相同的情況,也能保證粒子進(jìn)行運(yùn)動(dòng),并保持一種強(qiáng)勁的搜索欲望,克服了早熟收斂問(wèn)題.即使已經(jīng)找到了全局最優(yōu)解,隨機(jī)項(xiàng)的存在依然促使粒子再度進(jìn)行尋優(yōu).β控制隨機(jī)決策行為的強(qiáng)弱,過(guò)大會(huì)淹沒(méi)遵守秩序的意識(shí),過(guò)小會(huì)降低種群多樣性和全局搜索能力.參考慣性權(quán)重采用隨代數(shù)下降的策略可獲得較好的尋優(yōu)結(jié)果.在算法中,β按式(4)的規(guī)律下降,表示在尋優(yōu)初期種群有強(qiáng)烈的隨機(jī)行為,而在尋優(yōu)后期種群有較強(qiáng)的秩序,有β=βmax(1?iter/maxitr)2.(4)β=βmax(1-iter/maxitr)2.(4)式中:βmax是混沌因子最大值,iter為迭代次數(shù),maxitr為最大迭代代數(shù).Ratnaweera認(rèn)為,速度慣性量的作用是作為自我認(rèn)知和社會(huì)認(rèn)知之間的平衡.那么如何平衡秩序和隨機(jī)這兩個(gè)相反的行為呢?向中心靠攏,或稱(chēng)為中庸之道,也是社會(huì)型群體智能的一種.在研究中,一般按照式(2)和(3)來(lái)確定粒子的位置,較少讓粒子飛行到群體的中心,描述粒子的行為如下:xid=∑j=1Nxjd/N,r<cp.(5)xid=∑j=1Νxjd/Ν,r<cp.(5)式中:cp是飛向中心的概率,N代表種群規(guī)模.實(shí)驗(yàn)表明式(5)的引入將會(huì)提高算法的收斂深度.4aepso算法性能測(cè)試為分析APSO算法的收斂穩(wěn)定性和全局搜索性能,本文選取4個(gè)Benchmark優(yōu)化問(wèn)題進(jìn)行分析,表1顯示了這些Benchmark函數(shù)的定義和搜索空間.選擇標(biāo)準(zhǔn)PSO,DPSO,HPSO,AEPSO,同APSO進(jìn)行性能比較.所有實(shí)驗(yàn)的維數(shù)d=30,種群規(guī)模N=60,最大迭代次數(shù)Nt=4000,函數(shù)評(píng)價(jià)次數(shù)為N*Nt=24000,最大速度為0.5,收斂因子為0.01,循環(huán)次數(shù)為200.表2顯示了各個(gè)算法的實(shí)驗(yàn)參數(shù)設(shè)計(jì).PSO,DPSO,HPSO,AEPSO選用文獻(xiàn)中的參數(shù).測(cè)試結(jié)果見(jiàn)表3.對(duì)于Sphere函數(shù),幾種算法均得到了100%的收斂概率,DPSO和AEPSO體現(xiàn)出快速的收斂能力,但是APSO體現(xiàn)出收斂的穩(wěn)定性,最優(yōu)解、平均解和最劣解在數(shù)值之間是最為接近的.對(duì)于Rosenbrock函數(shù),AEPSO取得較好的收斂概率和收斂的深度,但收斂結(jié)果不穩(wěn)定.APSO的收斂概率和收斂深度性能同DPSO和HPSO的性能是類(lèi)似的.值得注意的是在最劣解當(dāng)中,APSO的值是最小的.對(duì)于Rastrigrin函數(shù),AEPSO和DPSO取得了較好的收斂概率和收斂深度,但也體現(xiàn)出AEPSO的不穩(wěn)定性,AEPSO存在收斂到0的概率,但平均解3.98e-002沒(méi)有小于收斂因子,其解是不可預(yù)測(cè)的.APSO雖然沒(méi)有收斂,但是最優(yōu)解、平均解和最劣解在數(shù)值之間是最為接近的.在30維多模態(tài)Griewank函數(shù)上,APSO全局搜索能力優(yōu)于標(biāo)準(zhǔn)PSO及另幾種改進(jìn)算法,產(chǎn)生較高的收斂概率和最好的平均解.AEPSO在Griewank函數(shù)上卻存在較低的收斂概率和極大的不穩(wěn)定性,該結(jié)果同文獻(xiàn)的結(jié)論是一致的.Griewank是一個(gè)復(fù)雜的多模態(tài)函數(shù),各維之間顯著相關(guān),某一維位置的變化不能提供微粒的適應(yīng)值,只有各維同時(shí)發(fā)生變化時(shí)才有可能提高微粒的適應(yīng)值.DPSO是進(jìn)行小概率下的變異,HPSO是在某維粒子速度為0時(shí)進(jìn)行變異,AEPSO是在某維速度小于Td時(shí)進(jìn)行逃逸,均不能做到各維同時(shí)變化,因此這幾種算法逃出極小點(diǎn)的概率較小.APSO能夠做到在各維同時(shí)發(fā)生隨機(jī)變化,使得APSO在Griewank函數(shù)上發(fā)生了較高的收斂概率,并獲得了最好的平均解.5在gso和hpso算法下的穩(wěn)定性在標(biāo)準(zhǔn)PSO中,粒子總是向個(gè)體最優(yōu)和群體最優(yōu)的方向飛行,盡管在飛行過(guò)程中存在著隨機(jī)性,但其決策行為的本身是有序的、理性的,最終粒子將聚集在最優(yōu)粒子位置.本文繼續(xù)考察動(dòng)物學(xué)的社會(huì)行為,根據(jù)Millonas的觀(guān)點(diǎn),提出一種新穎的改進(jìn)算法適應(yīng)性微粒群算法.DPSO,HPSO和AEPSO均通過(guò)隨機(jī)操作來(lái)增強(qiáng)多樣性.DPSO進(jìn)行極小概率下的變異,HPSO在DPSO算法的基礎(chǔ)上,將發(fā)生變異的行為調(diào)整為速度為0時(shí),AEPSO在DPSO和HPSO算法基礎(chǔ)上將發(fā)生變異的行為調(diào)整為小于某一個(gè)不斷下降的閥值.本文的APSO與其不同之處在于:沒(méi)有先決條件的,持續(xù)地在有序決策的基礎(chǔ)上疊加隨機(jī)非理性的行為.適應(yīng)性微粒群算法的本質(zhì)是在有序的