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

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

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

3、,本文根據(jù)慣性權(quán)重對(duì)粒子群優(yōu)化算法性能影響的研究,提出了三種不同的慣性權(quán)重.通過仿真實(shí)驗(yàn),驗(yàn)證了各自的收斂性.同時(shí)也說明了慣性權(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ù)時(shí),上述的問題就轉(zhuǎn)變?yōu)槎嗄繕?biāo)優(yōu)化問題.對(duì)很多實(shí)際問題進(jìn)行數(shù)學(xué)建模后,可將其抽象為一個(gè)數(shù)值函數(shù)的優(yōu)化問題.由于問題種類的繁多、影響因素的復(fù)雜,這些數(shù)學(xué)函數(shù)會(huì)呈現(xiàn)出不同的數(shù)學(xué)特征,

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

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

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

7、Pi2,PiD),i=12,No整個(gè)粒子群迄今為止搜索到的最優(yōu)位置為全局極值,記為gbest-(pg1,pg2,pgD)在找到這兩個(gè)最優(yōu)值時(shí),粒子根據(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)的均勻隨機(jī)數(shù).式(1.1)右邊由三局部組成,第一局部為慣性(inertia)或動(dòng)量(momentum)局部,反映了粒子的運(yùn)動(dòng)習(xí)慣(habit)代表粒子有維持自己先前速度的趨

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

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

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

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

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

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

14、固定值.三、算例設(shè)計(jì)3.1測(cè)試函數(shù)介紹本文主要選取三個(gè)函數(shù)：一個(gè)2維連續(xù)函數(shù)、一個(gè)10離散函數(shù)、一個(gè)30維離散函數(shù),利用MATLAB編寫粒子群算法程序來優(yōu)化它們.本文選取了三個(gè)函數(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ù)特點(diǎn)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ù)是個(gè)二維函數(shù),常用于測(cè)試粒子群算法性能的測(cè)試函數(shù),全局在(0,0)處取得最大值,具有強(qiáng)烈震蕩的狀態(tài),而在Xi(-3.14,3.14)范圍內(nèi),有無限個(gè)次全局最大點(diǎn).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ù),存在大量按正弦拐點(diǎn)排列的、很深的局部最優(yōu)點(diǎn).其在(0,0,0)處取得全局最小值,在Xiw(-5.12,5.12)范圍內(nèi)大約有10個(gè)局部

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

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

18、算法在函數(shù)優(yōu)化中問題中的效果.步驟1:首先依據(jù)根本粒子群算法的流程圖編寫粒子群算法的MATLAB程序見附錄一；步驟2:分別編寫各個(gè)函數(shù)的適應(yīng)值函數(shù)程序見附錄二；步驟3:在MATLAB環(huán)境中用根本粒子群算法分別調(diào)用三個(gè)函數(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ù)收斂效果圖五、仿真實(shí)驗(yàn)結(jié)果分析5.1 實(shí)驗(yàn)結(jié)果匯總表1統(tǒng)計(jì)了固定迭代次數(shù)為1000次時(shí),三個(gè)測(cè)試函數(shù)分別在固定權(quán)重、隨機(jī)權(quán)重和時(shí)變權(quán)重三種慣性權(quán)重策略下求解的平均值和最差的的一次求解結(jié)果.慣性權(quán)重SchafferGriewank平均值最差值平均值最差值固定權(quán)重.=0.6118.2616.91隨機(jī)權(quán)重入Random=0.52時(shí)變權(quán)重116.2115.92表1算法運(yùn)行100次搜索到的解的平均值和最差值Rastrigrin平均值最差值1.

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

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

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

23、于變異的改良算法、帶有梯度加速的的改良算法,同時(shí)智能優(yōu)化方法處理約束的一般性策略都可以借鑒到粒子群算法中,也可以根據(jù)粒子群優(yōu)化的特性來設(shè)計(jì)專門的約束處理方式,可以通過以上的優(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機(jī)初始化位子y=randn(N,D);v=randn(N,D);%隨機(jī)初始化速度p=rand(N,1);%先計(jì)算各個(gè)粒子的適應(yīng)度,并初始化pi-粒子個(gè)體極值和pg-全局極值fori=1:Np(i