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

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

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