粒子群算法優(yōu)化不同維數(shù)的連續(xù)函數(shù)以及離散函數(shù)的最小值問題

1、引言2、問題描述31.1 函數(shù)優(yōu)化問題31.2 粒子群算法根本原理3二、算法設(shè)計52.1 算法流程框圖52.2 算法實現(xiàn)52.3 算法的構(gòu)成要素62.4 算法的改良7三、算例設(shè)計83.1 測試函數(shù)介紹83.2 優(yōu)化函數(shù)特點8四、仿真實驗設(shè)計104.1 實驗參數(shù)設(shè)計104.2 根本粒子群算法在測試函數(shù)中應(yīng)用11五、仿真實驗結(jié)果分析125.1 實驗結(jié)果匯總125.2 實驗結(jié)果分析13六、總結(jié)與展望146.1 總結(jié)146.2 展望14附錄一15附錄二17引言本文主要利用粒子群算法解決連續(xù)函數(shù)以及離散函數(shù)的最小值問題,粒子群優(yōu)化是一種新興的基于群體智能的啟發(fā)式全局搜索算法,粒子群優(yōu)化算法通過粒子間的競

2、爭和協(xié)作以實現(xiàn)在復(fù)雜搜索空間中尋找全局最優(yōu)點.它具有易理解、易實現(xiàn)、全局搜索水平強等特點,倍受科學(xué)與工程領(lǐng)域的廣泛關(guān)注,已經(jīng)成為開展最快的智能優(yōu)化算法之一.慣性權(quán)重是PSO標(biāo)準(zhǔn)版本中非常重要的參數(shù),可以用來限制算法的開發(fā)(exptation)和探索(exploration)水平.慣性權(quán)重的大小決定了對粒子當(dāng)前速度繼承的多少.較大的慣性權(quán)重將使粒子具有較大的速度,從而有較強的探索水平；較小的慣性權(quán)重將使粒子具有較強的開發(fā)水平.關(guān)于慣性權(quán)重的選擇一般有常數(shù)和時變兩種.算法的執(zhí)行效果很大程度上取決于慣性權(quán)重的選取.本文介紹了粒子群優(yōu)化算法的根本原理,分析了其特點,并將其應(yīng)用于函數(shù)優(yōu)化問題求解.止匕外

3、,本文根據(jù)慣性權(quán)重對粒子群優(yōu)化算法性能影響的研究,提出了三種不同的慣性權(quán)重.通過仿真實驗,驗證了各自的收斂性.同時也說明了慣性權(quán)重在粒子群優(yōu)化算法中有很大的自由度.、問題描述1.1 函數(shù)優(yōu)化問題目標(biāo)優(yōu)化問題可以描述為：maxf(x)(1)xS或：mif(x)(2)xS這里S-Rn稱為搜索空間,f(x):S-Rn稱為目標(biāo)函數(shù).(1)式描述的優(yōu)化問題稱為極大化問題,(2)式描述的稱為極小化問題.當(dāng)把f(x)看成是一序列的函數(shù)時,上述的問題就轉(zhuǎn)變?yōu)槎嗄繕?biāo)優(yōu)化問題.對很多實際問題進(jìn)行數(shù)學(xué)建模后,可將其抽象為一個數(shù)值函數(shù)的優(yōu)化問題.由于問題種類的繁多、影響因素的復(fù)雜,這些數(shù)學(xué)函數(shù)會呈現(xiàn)出不同的數(shù)學(xué)特征,

4、比如連續(xù)的、離散的、凸的、凹的、單峰值的、多峰值的函數(shù)等等,經(jīng)常遇到的函數(shù)還有這些不同數(shù)學(xué)特征的組合,除了在函數(shù)是連續(xù)、可求導(dǎo)、低階的簡單情況下可解析地求出其最優(yōu)解外,大局部情況需要通過數(shù)值計算方法來進(jìn)行近似優(yōu)化計算.盡管人們對這個問題研究了很多年,但至今仍無一種既能處理各種不同的復(fù)雜函數(shù)、又具有良好求解結(jié)果的數(shù)值計算方法.特別是當(dāng)問題的規(guī)模比擬大時,優(yōu)化計算時的搜索空間急劇擴大,人們熟悉到要嚴(yán)格地求出其最優(yōu)解不太現(xiàn)實.所以需要研究出一種能夠在可接受的時間和可接受的精度范圍內(nèi)求出數(shù)值函數(shù)近似最優(yōu)解的方法或通用算法.粒子群優(yōu)化由于其算法的簡單,易于實現(xiàn),無需梯度信息,參數(shù)少等特點在連續(xù)優(yōu)化問題和

5、離散優(yōu)化問題中都表現(xiàn)出了良好的效果,特別是由于其天然的實數(shù)編碼特點適合于處理實優(yōu)化問題.近年來成為國際上智能優(yōu)化領(lǐng)域研究的熱門.1.2 粒子群算法根本原理粒子群優(yōu)化算法PSO(ParticleSwarmOptimization)是一種基于群體的自適應(yīng)的搜索優(yōu)化方法.是由JamesKenned評口Eberhart在1995年提出的.PSO中,每個優(yōu)化問題的潛在解都是搜索空間中的一只鳥,稱之為粒子.所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適值(fitnessvalue),每個粒子還有一個速度決定它們飛翔的方向和距離.然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索.PSO初始化為一群隨機粒子(隨機解),

6、然后通過迭代找到最優(yōu)解.在每一次迭代中,粒子通過跟蹤兩個極值來更新自己；第一個就是粒子本身所找到的最優(yōu)解,這個解稱為個體極值；另一個極值是整個種群目前找到的最優(yōu)解,這個極值是全局極值.另外也可以不用整個種群而只是用其中一局部作為粒子的鄰居,那么在所有鄰居中的極值就是局部極值o假設(shè)在一個D維的目標(biāo)搜索空間中,有N個粒子組成一個群落,其中第i個粒子表示為一個D維的向量Xi(xi1>xi2>>xiD)i=1,2,N)0第i個粒子的飛行速度也是一個D維的向量,記為Vi=(Vi1,Vi2,Md)i=1,2,3,0第i個粒子迄今為止搜索到的最優(yōu)位置稱為個體極值,記為Pbest=(Pi1,

7、Pi2,PiD),i=12,No整個粒子群迄今為止搜索到的最優(yōu)位置為全局極值,記為gbest-(pg1,pg2,pgD)在找到這兩個最優(yōu)值時,粒子根據(jù)如下的公式(1.1)和(1.2)來更新自己的速度和位置：vid=w"vid+c1r1(RdXid)+c2r2(pgd-Xid)(11)Xid=Xid+Md(1.2)其中：勒和白為學(xué)習(xí)因子,也稱加速常數(shù)(accelerationconstant)r1和r2為0,1范圍內(nèi)的均勻隨機數(shù).式(1.1)右邊由三局部組成,第一局部為慣性(inertia)或動量(momentum)局部,反映了粒子的運動習(xí)慣(habit)代表粒子有維持自己先前速度的趨

8、勢；第二局部為認(rèn)知(cognition)局部,反映了粒子對自身歷史經(jīng)驗的記憶(memory)或回憶(remembrance)代表粒子有向自身歷史最正確位置逼近的趨勢；第三局部為社會(social)局部,反映了粒子間協(xié)同合作與知識共享的群體歷史經(jīng)驗.算法設(shè)計這局部內(nèi)容主要是針對本文主要研究問題的類型確定粒子群算法具體實現(xiàn)過程和一些參數(shù)的選擇.2.1 算法流程框圖開始初始化每個粒子的速度和位置r計算每個粒子的適應(yīng)值1求出每個粒子的個體最優(yōu)1r求出整個群體的全局最優(yōu)值1根據(jù)方程(1.1)行4對粒子的速度進(jìn)二化V1:束條件是f輸出結(jié)果2.2 算法實現(xiàn)算法的流程如下:初始化粒子群,包括群體規(guī)模N,每個粒

9、子的位置Xi和速度Vi計算每個粒子的適應(yīng)度值FJi;對每個粒子,用它的適應(yīng)度值FJi和個體極值&s/i)比擬,如果Fiti>Pbest(i),那么用Fiti替換掉Pbest；對每個粒子,用它的適應(yīng)度值Fiti和全局極值gbest比擬,如果FitiAPbes(i)那么用Fiti替gbest；根據(jù)公式(1.1),(1.2)更新粒子的速度Vi和位置Xi;如果滿足結(jié)束條件(誤差足夠好或到達(dá)最大循環(huán)次數(shù))退出,否那么返回.2.3算法的構(gòu)成要素對于構(gòu)成粒子群算法的各個參數(shù)進(jìn)行設(shè)定.本算法中主要的參數(shù)變量為慣性權(quán)值w,學(xué)習(xí)因子c1,c2,群體的大小N,迭代次數(shù)M,粒子維數(shù)Do(1)群體大小通常

10、,群體太小那么不能提供足夠的采樣點,以致算法性能很差,容易陷入局部最優(yōu)；群體太大盡管可以增加優(yōu)化信息,阻止早熟收斂的發(fā)生,但無疑會增加計算量,造成收斂時間太長,表現(xiàn)為收斂速度緩慢.本文對函數(shù)的優(yōu)化選擇種群規(guī)模為500.(2)最大迭代次數(shù)迭代次數(shù)越多能保證解的收斂性,但是影響運算速度,本文對函數(shù)的優(yōu)化選最大迭代次數(shù)為100畋.(3)慣性權(quán)值慣性權(quán)重w表示在多大程度上保存原來的速度.w較大,全局收斂水平強,局部收斂水平弱；w較小,局部收斂水平強,全局收斂水平弱.(4)學(xué)習(xí)因子加速常數(shù)Ci和c2分別用于限制粒子指向自身或鄰域最正確位置的運動.建議4=c+c2三4.0,并通常取G=c2=2.本文中取G

11、=c2=2.(5)粒子維數(shù)粒子維數(shù)取決于待優(yōu)化函數(shù)的維數(shù),例如本文主要有三個函數(shù)主要：第一個函數(shù)是2維的,第二個函數(shù)是10維的,第三個函數(shù)是30維的.(6)粒子空間的初始化較好的選擇粒子初始化空間,將大大縮短收斂的時間.在本文中我們主要是選用隨機對粒子進(jìn)行初始化.2.4算法的改良對于函數(shù)的優(yōu)化我們主要選擇的是對于慣性權(quán)重的優(yōu)化.慣性權(quán)重是粒子優(yōu)化算法的重要參數(shù),算法的成敗很大程度上就取決于參數(shù)的選取和調(diào)節(jié),本文采用固定權(quán)重、時變權(quán)重和隨機權(quán)重三種權(quán)重.(1)固定權(quán)重即賦予慣性權(quán)重以一個常數(shù)值,一般來說,該值在0和1之間.固定的慣性權(quán)重使粒子在飛行中始終具有相同的探索和開發(fā)水平.顯然對于不同的問

12、題,獲得最好優(yōu)化效果的常數(shù)是不同的,要找到這個值需要大量的實驗.通過實驗發(fā)現(xiàn)：種群規(guī)模越小,需要的慣性權(quán)重越大,由于此時種群需要更好的探索水平來彌補粒子數(shù)量的缺乏,否那么粒子極易收斂；種群規(guī)模越大,需要的慣性權(quán)重越小,由于每個例子可以更專注于搜索自己附近的區(qū)域.(2)時變權(quán)重希望粒子群在飛行開始的時候具有較好的探索水平,隨著迭代次數(shù)的增加,特別是在飛行后期,希望有較好的開發(fā)水平.所以使用動態(tài)調(diào)節(jié)慣性權(quán)重.可以通過時變的慣性權(quán)重來實現(xiàn).設(shè)慣性權(quán)重的取值范圍為：仲min©max,最大迭代次數(shù)為Iter_max,那么第i次迭代時的慣性權(quán)重可以為："max-"min.二-

13、iimaxItermax(3)隨機權(quán)重隨機權(quán)重是在一定范圍內(nèi)隨機取值,在本文中我們采用的是：入Random=0.5其中Random為0-1之間的隨機數(shù).這樣慣性指數(shù)將在0.5-1之間隨機變化.均值為0.75.對于動態(tài)優(yōu)化問題來說,不能夠預(yù)測在給定的時間粒子群于要更好的探索水平還是更好的開發(fā)水平.所以,可以使慣性權(quán)重在一定范圍內(nèi)隨機變化.需要說明的是,本文的程序允許改變除慣性權(quán)重以外的其他參數(shù),由于本文編寫的程序參照MATLAB工具箱,留給用戶解決這類問題一個接口函數(shù),上述的各個參數(shù)正是接口函數(shù)的參數(shù),因此允許改變.另外對于也可采用變參數(shù)法,即隨迭代次數(shù)增加,利用經(jīng)驗公式使它們動態(tài)調(diào)整,本文采用

14、固定值.三、算例設(shè)計3.1測試函數(shù)介紹本文主要選取三個函數(shù)：一個2維連續(xù)函數(shù)、一個10離散函數(shù)、一個30維離散函數(shù),利用MATLAB編寫粒子群算法程序來優(yōu)化它們.本文選取了三個函數(shù),分別如下:sinx2x1-0.5f1二0.5r10.001x2x210_-2f2='(xi-10cos(2-xi)10)i1(30301-2xixi-JIIcos()14000i1i1i其中f1求最大值,f2和f3為求最小值.3.2優(yōu)化函數(shù)特點Schaffer函數(shù):f1=0.5-sin.Xi2x；-0.5(1+0.001(x2+x；求其最大值.目標(biāo)函數(shù)的效果圖如圖3.1下:10.80.60.40.2055圖

15、3.1Schaffer函數(shù)的效果圖由圖知此函數(shù)是個二維函數(shù),常用于測試粒子群算法性能的測試函數(shù),全局在(0,0)處取得最大值,具有強烈震蕩的狀態(tài),而在Xi(-3.14,3.14)范圍內(nèi),有無限個次全局最大點.10(2) Rastrigrin函數(shù)：f2=£(x2-10cos(2nxi)+10)i1目標(biāo)函數(shù)的效果圖如圖3.2所示：1008060402005A：.<0050-5-5圖3.2Rastrigrin函數(shù)的效果圖由圖知此函數(shù)是10維多峰值函數(shù),存在大量按正弦拐點排列的、很深的局部最優(yōu)點.其在(0,0,0)處取得全局最小值,在Xiw(-5.12,5.12)范圍內(nèi)大約有10個局部

16、極小點,不難優(yōu)化查找到全局最優(yōu)值.130230Xi(3) Girewank函數(shù)：f3=、xi-cos()14000yy.i目標(biāo)函數(shù)的效果圖如圖3.3所示：圖3.3Girewank函數(shù)的效果圖由圖知此函數(shù)為一個多峰值函數(shù),為30維函數(shù),變量之間有相互關(guān)系,該函數(shù)有很多局部最優(yōu)點,其全局最優(yōu)點全局最小值在(Xi,X2,Xn)=(0,0,0)取得,目標(biāo)函數(shù)最優(yōu)為00四、仿真實驗設(shè)計4.1 實驗參數(shù)設(shè)計(1)權(quán)重參數(shù)設(shè)計本文對每個測試函數(shù)將使用三種不同的慣性權(quán)重策略進(jìn)行實驗,分別為固定權(quán)重：«=.6.隨機權(quán)重：金=0.5+Random1；時變權(quán)重：颯二.max-'儂"min

17、引,其中缶max=0.9,min=0.2.Itermax2其他參數(shù)設(shè)計對于Schaffer函數(shù),種群規(guī)模N=500,最大迭代次數(shù)M=1000,學(xué)習(xí)因子G=.2=2,f1函數(shù)是2維的,粒子維數(shù)取Di=2.對于Rastrigrin函數(shù)種群規(guī)模N=500,最大迭代次數(shù)M=1000,學(xué)習(xí)因子Cl=C2=2,f2函數(shù)是10維的,粒子維數(shù)D2=10.對于Girewank函數(shù),種群規(guī)模N=500,最大迭代次數(shù)M=1000,學(xué)習(xí)因子G=c2=2,f3函數(shù)是30維,粒子維數(shù)D3=30.4.2 根本粒子群算法在測試函數(shù)中應(yīng)用以Schaffer函數(shù)、Rastrigrin函數(shù)、Girewank函數(shù)為例來說明根本粒子群

18、算法在函數(shù)優(yōu)化中問題中的效果.步驟1:首先依據(jù)根本粒子群算法的流程圖編寫粒子群算法的MATLAB程序見附錄一；步驟2:分別編寫各個函數(shù)的適應(yīng)值函數(shù)程序見附錄二；步驟3:在MATLAB環(huán)境中用根本粒子群算法分別調(diào)用三個函數(shù)的適應(yīng)值程序,得到收斂效果圖.Schaffe幅數(shù)、Rastrigrin函數(shù)、Girewank函數(shù)的收斂效果圖分別如圖4.1、4.2、4.3所示：1,11p1p0.99980.9996-0.9994-0.9992-0.999-°.9988010020.30040.50.60.70.s0°1000圖4.1Schaffer函數(shù)收斂效果圖圖4.2Rastrigrin

19、函數(shù)收斂效果圖0.070.060.050.040.030.020.01001002003004005006007008009001000圖4.3Girewank函數(shù)收斂效果圖五、仿真實驗結(jié)果分析5.1 實驗結(jié)果匯總表1統(tǒng)計了固定迭代次數(shù)為1000次時,三個測試函數(shù)分別在固定權(quán)重、隨機權(quán)重和時變權(quán)重三種慣性權(quán)重策略下求解的平均值和最差的的一次求解結(jié)果.慣性權(quán)重SchafferGriewank平均值最差值平均值最差值固定權(quán)重.=0.6118.2616.91隨機權(quán)重入Random=0.52時變權(quán)重116.2115.92表1算法運行100次搜索到的解的平均值和最差值Rastrigrin平均值最差值1.

20、82e-0062.04e-0052.14e-0061.74e-0051coigmemaxmin"i='max-i17.72Itermax18.93.20e-0092.16e-0085.2 實驗結(jié)果分析慣性權(quán)重是粒子群優(yōu)化算法標(biāo)準(zhǔn)版本的重要參數(shù),算法的成敗很大程度上取決于該參數(shù)的選取和調(diào)節(jié).本文重點研究了慣性權(quán)重對優(yōu)化效果的影響.從表1可以看出,1在其他參數(shù)選擇適當(dāng)?shù)臈l件下,利用三種不同慣性權(quán)重策略的PSO算法得到的平均值和最差值相差不太,較為穩(wěn)定.2固定權(quán)重、隨機權(quán)重以及時變權(quán)重對Schaffer函數(shù)都具有較好的優(yōu)化效果,并能較快地迭代到最優(yōu)值.2對于Rastrigrin函數(shù)

21、,三種慣性權(quán)重策略下都未能搜索到目標(biāo)函數(shù)的理想最優(yōu)點,但相比之下利用隨機權(quán)重進(jìn)行函數(shù)優(yōu)化具有較好的效果,時變權(quán)重并未取得比固定權(quán)重好的優(yōu)化效果.3對于多峰函數(shù)Girewank函數(shù),慣性權(quán)重采用時變權(quán)重優(yōu)化效果明顯比固定權(quán)重、時變權(quán)重好,取得了不錯的收斂結(jié)果.六、總結(jié)與展望6.1 總結(jié)本文主要用粒子群算法優(yōu)化不同維數(shù)的連續(xù)函數(shù)以及離散函數(shù)的最小值問題,主要有以下幾個方面：首先介紹了粒子群的算法在智能優(yōu)化中的地位,也介紹了粒子群算法的主要特點,并通過對粒子群算法的學(xué)習(xí)和了解為下面粒子群改良算法在對不同維數(shù)的函數(shù)優(yōu)化問題打下了很好的根底.其次對粒子群算法解決最優(yōu)化問題的統(tǒng)一框架進(jìn)行了分析,在此根底上

22、提出了粒子群優(yōu)化算法的設(shè)計步驟；又對粒子群優(yōu)化算法的原理進(jìn)行了分析,從而對粒子群算法有了更深刻的了解.最后將根本的粒子群算法與改良的粒子群算法分別對函數(shù)的優(yōu)化問題在MATLAB中進(jìn)行了仿真,從而將根本算法和改良算法在函數(shù)優(yōu)化問題中的仿真結(jié)果進(jìn)行了比照,從而驗證了改良算法的相對優(yōu)越性,并且驗證了改良算法的實際可行性.6.2 展望本文中主要利用改變權(quán)重的方法來對函數(shù)進(jìn)行優(yōu)化,實際用粒子群算法對函數(shù)進(jìn)行優(yōu)化還有很多方法：改變鄰域拓?fù)浣Y(jié)構(gòu)、改變學(xué)習(xí)因子,對于離散函數(shù)的優(yōu)化可以采用二進(jìn)制編碼和順序編碼來實現(xiàn)同時也可以使用基于遺傳策略和梯度信息的集中改良方法例如：基于選擇的改良算法.基于交叉的改良算法、基

23、于變異的改良算法、帶有梯度加速的的改良算法,同時智能優(yōu)化方法處理約束的一般性策略都可以借鑒到粒子群算法中,也可以根據(jù)粒子群優(yōu)化的特性來設(shè)計專門的約束處理方式,可以通過以上的優(yōu)化方法來解決函數(shù)優(yōu)化問題.附錄一主函數(shù)%fitness-是要優(yōu)化的目標(biāo)函數(shù),N-種群數(shù),c1,c2-學(xué)習(xí)因子,w-慣性權(quán)重,M-迭代次數(shù),D-粒子維數(shù).formatlong;%初始化種群%c1=2;%c2=2;%N=500;%w=0.6;%M=1000;c1=2;c2=2;N=500;%w=0.6;M=1000;D=30;x=randn(N,D);%B機初始化位子y=randn(N,D);v=randn(N,D);%隨機初始化速度p=rand(N,1);%先計算各個粒子的適應(yīng)度,并初始化pi-粒子個體極值和pg-全局極值fori=1:Np(i