基于混沌思想的可多步搜索的新型粒子群優(yōu)化算法

林博藝

（泉州信息職業(yè)技術(shù)學(xué)院，福建 泉州 362000）

基于混沌思想的可多步搜索的新型粒子群優(yōu)化算法

林博藝

（泉州信息職業(yè)技術(shù)學(xué)院，福建 泉州 362000）

針對(duì)基本PSO算法在全局優(yōu)化中收斂精度低和易陷入局部極值的不足，提出一種基于混沌思想的多步搜索的新型的粒子群優(yōu)化算法（CMPSO）.該算法先引入混沌思想對(duì)粒子種群進(jìn)行位置初始化，然后再引入多步搜索，最后引入概率條件的選擇性重新初始化.通過(guò)與其它三個(gè)改進(jìn)算法比較，結(jié)果表明CMPSO算法的有效性.

粒子群優(yōu)化；多步搜索；混沌

1995年Kennedy博士和Eberhart教授提出粒子群優(yōu)化（Particle Swarm optimization，PSO）算法[1,2]，它是一種基于群體智能（Swarm Intelligence，SI）仿生的優(yōu)化方法，該算法基本思想是源于對(duì)鳥(niǎo)群捕食行為的模擬.由于其原理簡(jiǎn)潔，參數(shù)較少，易于實(shí)現(xiàn)等優(yōu)點(diǎn)，成為繼遺傳算法后的研究熱點(diǎn)之一.其已被廣泛的應(yīng)用于函數(shù)優(yōu)化[3]，工程優(yōu)化[4]，參數(shù)估計(jì)[5-9]，電力系統(tǒng)優(yōu)化[10-14],控制器設(shè)計(jì)[15-7]，機(jī)器人路徑規(guī)劃[8]等.

類(lèi)似于GA，PSO算法也有收斂精度低，早熟等不足[18-20]，因此繼Kennedy和Eberhart之后有許多改進(jìn)型PSO算法提出.如：引入慣性權(quán)重，加入微分演化或是交叉操作，加入混沌初始化，與其它智能算法混合等，這些算法在增加算法得雜度的前提下，都不同程度的提高算法的性能.但這樣做都有悖于算法的初衷：簡(jiǎn)潔實(shí)效.本人在分析基本PSO算法不足的基礎(chǔ)上，引入混沌初始化，并將多步式位置更新引入其中，并通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證我們改進(jìn)的有效性.

1 PSO簡(jiǎn)介

一個(gè)有N個(gè)粒子的種群，在D維空間中進(jìn)行尋優(yōu)過(guò)程的算法的基本遞推公式：

其中：i=1，2，…，N；d=1，2，…，D；Xid（k+1），Xid（k），Vid（k+1），Vid（k）分別表示第 i個(gè)粒子在 k+1 和 k代的空間位置對(duì)應(yīng)的第d維值及運(yùn)動(dòng)速度對(duì)應(yīng)的第d維值；ω為慣性權(quán)重；c1，c2分別表示粒子個(gè)體和粒子群體的加速權(quán)重系數(shù)；r1，r2均為0到1之間的隨機(jī)值，分別表示粒子個(gè)體和全體的加速權(quán)重；Pid與Pgd分別表示第i個(gè)粒子個(gè)體在搜索過(guò)程中自身的歷史最佳位置和整個(gè)粒子群體目前找到的最佳位置.

2 新的PSO算法

2.1 PSO算法陷入局部收斂的原因

基本PSO算法易陷入局部極值的原因在文獻(xiàn)[3]做了詳細(xì)的分析，并通過(guò)數(shù)學(xué)推導(dǎo)得到式（3）：

由式（3）可知，每個(gè)粒子不僅受它自己找到的當(dāng)前最優(yōu)解的吸引，而且還受全局最優(yōu)解的吸引.如果這兩個(gè)最優(yōu)解都是局部最優(yōu)值，粒子將被這兩個(gè)值吸引而很快重復(fù)相同的搜索軌跡.由于式（1）沒(méi)有使算法跳出局部最優(yōu)的機(jī)制，隨著進(jìn)化迭代的進(jìn)行，粒子最終將聚集到由個(gè)體極值位置P0和全局極值位置Pg共同決定的位置P*上，如果P*是某個(gè)局部最優(yōu)位置，且所有粒子在向位置P*靠攏的過(guò)程中若沒(méi)有找到優(yōu)于Pg的位置，則基本PSO的進(jìn)化過(guò)程將很難跳出該局部最優(yōu)，粒子將逐步收斂到P*.另外，結(jié)合式（1）還可看出，慣性權(quán)重僅能改變粒子的搜索步長(zhǎng)，不能改變其運(yùn)行方向，從而不能克服早熟問(wèn)題.可見(jiàn)，加強(qiáng)搜索多樣性、使算法跳出局部最優(yōu)，是提高算法收斂速度和尋優(yōu)精度的重要措施.本文從以下三個(gè)方面入手，提出一種基于混沌思想和多步搜索的PSO算法.

2.2 初始化粒子群初始位置

混沌序列的運(yùn)動(dòng)特點(diǎn)：隨機(jī)性和遍歷性及規(guī)律性.本文采用混沌序列的這一特點(diǎn)對(duì)粒子進(jìn)行初始化分布，這樣可以更好的體現(xiàn)初始種群的多樣性，為在尋優(yōu)空間中找到最優(yōu)解和加快收斂速度奠定較為堅(jiān)實(shí)的基礎(chǔ).

Logistic映射是一個(gè)典型的混沌系統(tǒng)，首先利用Logistic映射產(chǎn)生混沌序列，如式（4）：

式（4）中 μ 為一個(gè)常數(shù)，μ∈[3.56，4.0]，稱(chēng)為控制參量，主要用來(lái)控制系統(tǒng)的混沌程度，L（d）∈（0，1），d=1，2，3，…，D.

第二步對(duì)處于D維中間中的N個(gè)粒子，首先產(chǎn)生 N 個(gè)初始值：L1（1），L2（1），…，Li（1），…，LN（1），把這N個(gè)初始值代入式（4）中進(jìn)行D次迭代運(yùn)算，將產(chǎn)生的結(jié)果代入式（5）中運(yùn)算：

式（5）中：Xi,d表示第i個(gè)粒子第d維坐標(biāo)，而Li（d）是第i個(gè)粒子用Li（1）經(jīng)過(guò)d次迭代運(yùn)算產(chǎn)生的值，Maxd，Mind分別是第d維的上下限.

2.3 引入多步搜索

由公式（1）知，粒子的運(yùn)動(dòng)失量由慣性項(xiàng)Vid（k），自身認(rèn)知成分項(xiàng)c1*r1*（Pid-Xid（k）），社會(huì)認(rèn)知成分項(xiàng)c2*r2*（Pgd-Xid（k））三項(xiàng)決定的，受人類(lèi)活動(dòng)行為的啟發(fā)可知：人類(lèi)在做事時(shí)，有時(shí)會(huì)慣性式的執(zhí)行，有時(shí)會(huì)加以總結(jié)靠自身的經(jīng)驗(yàn)，有時(shí)卻也會(huì)對(duì)所有信息加以匯總考慮然后再去做事（基本PSO算法則是這種方式）[19].本文在盡量不增加PSO算法的基礎(chǔ)上，對(duì)運(yùn)算過(guò)程中的三項(xiàng)結(jié)果直接加以分析迭代：

（6）Xid（k+1）3=Xid（k）ω*Vid（k）+c1*r1*（Pid-Xid（k）） （7）Xid（k+1）2=Xid（k）+ω*Vid（k）Xid（k+1）new=!###"###$Xid（k+1）2 if（f（Xid（k+1）2））

由式（8）可知，粒子在搜索過(guò)程中，先利用自身慣性做第一步位移Xid（k+1）2，如果此步位移得到搜索位置最好，則取之；否則進(jìn)一步利用自身認(rèn)知經(jīng)驗(yàn)項(xiàng)得到位移點(diǎn)Xid（k+1）3，同進(jìn)也可再利用社會(huì)認(rèn)識(shí)經(jīng)驗(yàn)得到 Xid（k+1）.最后比較 Xid（k+1），Xid（k+1）2，Xid（k+1）3，取其最優(yōu)者做為下一步的運(yùn)動(dòng)位置更新點(diǎn).

綜上所述，改進(jìn)的PSO算法具有PSO算法的基本特點(diǎn)，簡(jiǎn)單，易實(shí)現(xiàn)，運(yùn)算量較小等優(yōu)點(diǎn)，同時(shí)兼顧了搜索效率和收斂精度，此外，新算法并未引入新的參數(shù)，這樣就易于通用，因?yàn)樾滤惴▽⑺阉鞯闹虚g值加以利用和分析，省去了參數(shù)調(diào)節(jié)的煩瑣計(jì)算，因此新算法較簡(jiǎn)單通用.

2.4 重新初始化

在粒子群的進(jìn)化過(guò)程中，當(dāng)?shù)玫降淖顑?yōu)解在連續(xù)的M次迭代中都無(wú)變化時(shí)，用一個(gè)計(jì)數(shù)器記錄到目前為止停滯的代數(shù)T，可以這樣設(shè)定：如果連續(xù)兩次得到的最優(yōu)解相同則將T增1，否則將其清0；當(dāng)T≥M時(shí)，則說(shuō)明算法可能停滯，在M次的迭代中，粒子沒(méi)有能力跳出局部最優(yōu).此時(shí)，為加強(qiáng)粒子的對(duì)空間的搜索可以對(duì)某些粒子在概率性選擇下進(jìn)行隨機(jī)重新初始化.搜索空間區(qū)域?yàn)椋篬XMind,XMaxd]，在其內(nèi)部重新初始化即為：

其中：β為事先設(shè)定的一個(gè)閾值，可取[0.8,1].

在迭代過(guò)程中，當(dāng)粒子有可能陷入局部極值時(shí)，為避免過(guò)大的破壞粒子原有的運(yùn)行狀態(tài)，僅選擇少部分粒子進(jìn)行重新初始化.

3 實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

選用4個(gè)典型基準(zhǔn)測(cè)試函數(shù)，與基本PSO及sPSO[18[18]，HPSO-TVAC[15]等算法比較，驗(yàn)證CMPSO的可行性.這4個(gè)常用的基準(zhǔn)函數(shù)、函數(shù)形式、搜索范圍及維數(shù)、理論極值（極小值）和優(yōu)化目標(biāo)精度等見(jiàn)表1；其中：HPSO-TVAC，sPSO和tPSO參數(shù)設(shè)置與文獻(xiàn)[18]與文獻(xiàn)[15]一致，CMPSO參數(shù)設(shè) 置 為 ：ω0=1.2,c1=c2=2,ω=ω0*exp（-0.5*k*k）,μ=3.99,Max=10，β=0.8.

對(duì)算法性能評(píng)估采用如下方法[18]：（1）固定迭代次數(shù)下的實(shí)驗(yàn)效果對(duì)比；（2）固定收斂精度的實(shí)驗(yàn)效果對(duì)比.

3.2 實(shí)驗(yàn)結(jié)果分析

3.2.1 固定迭代次數(shù)下的實(shí)驗(yàn)效果對(duì)比

固定代數(shù)下的的實(shí)驗(yàn)結(jié)果對(duì)比如圖1所示，實(shí)驗(yàn)結(jié)果是采用獨(dú)立運(yùn)行50次后的平均值給出.其中：粒子數(shù)目為50，進(jìn)化代數(shù)為1000；圖1（a）～圖1（h）是五種算法分別在測(cè)試函數(shù)f1～f8的適應(yīng)度值的對(duì)數(shù)曲線（為方便顯示統(tǒng)一加10-10做為適應(yīng)度的截止值）.

從圖1-1（a）到圖1-1（h）可以看出，PSO算法在1000代內(nèi)都難以收斂到目標(biāo)精度，其他改進(jìn)算法表現(xiàn)在總體上均優(yōu)于PSO算法.下面依次詳細(xì)分析.

從圖1-1中可以看出，CMPSO算法較其它四中算法均得到較大改進(jìn)，對(duì)8個(gè)函數(shù)的優(yōu)化來(lái)看基本上在100代以?xún)?nèi)都能收斂到目標(biāo)精度，有的函數(shù)甚至在20代以?xún)?nèi)都能收斂到目標(biāo)精度，可以說(shuō)CMPSO算法表現(xiàn)是較其它算法是最佳的.其它算法中sPSO，再次是tPSO算法收斂情況較好.在對(duì)Rosenbrock函數(shù)f6（一個(gè)經(jīng)典的復(fù)雜優(yōu)化問(wèn)題，取值區(qū)間內(nèi)平坦，為算法提供了少量的信息，要收斂到全局最優(yōu)位置的機(jī)會(huì)非常小，所以它一般用來(lái)測(cè)試算法的執(zhí)行效率[19]）及Schaffer’s函數(shù)f8這兩個(gè)函數(shù)上，CMPSO將其改進(jìn)后的開(kāi)求精能力和開(kāi)挖能力充分表現(xiàn)出來(lái)：如Rosenbrock函數(shù)f6，其在400代后又進(jìn)一步向高精度深度求精；在Schaffer’s函數(shù)f8表現(xiàn)更為明顯，在1000代以?xún)?nèi)不斷向更高精度逼進(jìn)，充分體現(xiàn)了其對(duì)空間的開(kāi)挖能力和求精能力.

表1 8個(gè)基準(zhǔn)測(cè)試函數(shù)

圖1-1 f1～f8在5個(gè)實(shí)驗(yàn)中的適應(yīng)度值進(jìn)化曲線

表2 實(shí)驗(yàn)結(jié)果對(duì)比

因此，CMPSO算法改善了PSO算法對(duì)空間的全局搜索效果，提高了算法的收斂速度和精度，較為有效的避免了早熟問(wèn)題，與其它改進(jìn)算法相比也是有較大的改進(jìn)，如：較tPSO算法參數(shù)少，更具有通用性；較sPSO收斂速度和精度也有較大的提高.因此，在固定迭代次數(shù)的前題下，CMPSO算法改進(jìn)有效性得到有力證實(shí).

3.2.2 固定收斂精度的實(shí)驗(yàn)效果對(duì)比

作如下規(guī)定：同樣是種群規(guī)模為50，在表1指定的收斂精度下，對(duì)達(dá)到收斂精度所需的迭代次數(shù)進(jìn)行比較.由達(dá)到目標(biāo)精度的最小值，均值，最大值，方差等方面加以考察.表2是由表1指定精度下獨(dú)立50次所得 （如果算法在10000代內(nèi)還沒(méi)有收斂到目標(biāo)精度于以終止）.

由表2可見(jiàn)：在收斂速度上PSO算法最差，其次是HPSO-TVAC，這兩個(gè)算法在大部分情況下不能收斂到目標(biāo)精度，而其它三種算法基本上均能收斂到目標(biāo)精度.CMPSO在固定收斂精度下，其收斂速度均優(yōu)于其它算法，而sPSO在收斂速度上優(yōu)于tPSO，三者中CMPSO表現(xiàn)最佳，說(shuō)明了改進(jìn)有效性.

4 總結(jié)

本文在分析基本PSO算法收斂精度低，早熟等不足的基礎(chǔ)上，受自然現(xiàn)象的啟發(fā)，提出了一種改進(jìn)型的PSO算法.用經(jīng)典的測(cè)試函數(shù)來(lái)測(cè)試算法，經(jīng)驗(yàn)證，充分表明了改進(jìn)算法的有效性.

〔1〕Kennedy J,Eberhart R C.Particle swarm optimization [C].In:Proc.of the IEEE Internationa1 Conference on Neura1 Networks,Perth,Australia.1995,1942-1948.

〔2〕ShiY,EberhartR C.A modified particle swarm optimizer [C].In:Proc.of the IEEE International Conference on Evolutionary Computation.1998,69-73.

〔3〕Clerc M,Kennedy J.The particle swarm:Explosion stability and convergence in a multidimensional complex space[J].IEEE Trans.on Evolutionary Computation.2002,6（1）:58-73.

〔4〕武忠勇，緱錦，趙志強(qiáng).具有自適應(yīng)鄰域探測(cè)機(jī)制的改進(jìn)型PSO算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2010，31（9）：1938-1945.

〔5〕鄭宣耀，李歡，滕少華.自適應(yīng)變鄰域混沌搜索微粒群算法 [J].計(jì)算機(jī)工程與應(yīng)用，2007，43（31）：90-93.

〔6〕趙娜，張伏生，魏平，等.基于改進(jìn)多粒子群算法的電力系統(tǒng)無(wú)功優(yōu)化 [J].西安交通大學(xué)學(xué)報(bào)，2006，34（4）：463-467.

〔7〕張勇，鞏敦衛(wèi)，張婉秋.一種基于單純形法的改進(jìn)微粒群優(yōu)化算法及其收斂性分析[J].自動(dòng)化學(xué)報(bào)，2009，35（3）：289-298.

〔8〕Parsopoulos K E,Vrahatis M N.UPSO:A unified particle swarm optimization scheme[C].In:Proc.of the ICCM SE 2004.Attica.2004:868-873.

〔9〕Mendes R,Kennedy J,Neves J.The fully informed particle swarm:Simpler,maybe better[J].IEEE Trans.on Evolutionary Computation.2004,8（3）:204-210.

〔10〕赫然，王永吉，王青，等.一種改進(jìn)的自適應(yīng)逃逸微粒群算法及實(shí)驗(yàn)分析 [J].軟件學(xué)報(bào)，2005，16（12）：2036-2044.

〔11〕Peram T,Veeramachaneni K.Fitness-Distance-Ratio based particle swarm optimization[C].In:Proc.of the IEEE Swarm Intelligence Symp.Indianapolis.2003,174-181.

〔12〕〔13〕Trelea IC.The particle swarm optimization algorithm:Convergence analysis and parameter selection [J].Information Processing Letters.2003,85（6）:317-325.

〔14〕潘峰，陳杰，甘明剛，等.粒子群優(yōu)化算法模型分析[J].自動(dòng)化學(xué)報(bào)，2006，32（3）：368-377.

〔15〕Ratanaweera A,Halgamuge S K,Watson H C.Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients [J].IEEE Trans.on Evolutionary Computation,2004,8（3）:240-255.

〔16〕Liang J J,Qin A K.Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J].IEEE Trans.on Evolutionary Computation,2006,10（3）:281-295.

〔17〕呂艷萍，李紹滋，陳水利，等.自適應(yīng)擴(kuò)散混合變異機(jī)制微粒群算法 [J].軟件學(xué)報(bào)，2007，18（11）：2740-2751.

〔18〕胡旺，李志蜀.一種簡(jiǎn)化而高效的粒子群優(yōu)化算法[J].軟件學(xué)報(bào)，2007，18（4）：861-868.

〔19〕高芳，崔剛，吳智博，等.一種新型多步式位置可選擇更新粒子群優(yōu)化算法 [J].電子學(xué)報(bào)，2009，37（3）：529-534.

〔20〕紀(jì)震，周家銳，廖惠連，等.智能單粒子優(yōu)化算法[J].計(jì)算機(jī)學(xué)報(bào)，2010，33（2）：556-561.

TP18

A

1673-260X（2012）10-0015-05