李曉靜

（廣西幼兒師范高等專科學(xué)校，廣西　南寧　530022）

一種新的簡(jiǎn)化粒子群優(yōu)化算法*

李曉靜

（廣西幼兒師范高等?？茖W(xué)校，廣西南寧530022）

針對(duì)粒子群算法在尋優(yōu)中存在早熟和收斂精度不高等問題，論文對(duì)粒子位置的更新策略以及更新公式進(jìn)行改進(jìn)，提出了一種新的簡(jiǎn)化粒子群優(yōu)化算法（New Simple Particle Swarm Optimization，NSPSO），并將其在15個(gè)多極值基準(zhǔn)函數(shù)進(jìn)行全局最優(yōu)化測(cè)試，實(shí)驗(yàn)結(jié)果表明，NSPSO算法收斂的精度大大提高了，而且算法收斂速度也很快，對(duì)于高、低維復(fù)雜函數(shù)的優(yōu)化均適用.

粒子群優(yōu)化算法；簡(jiǎn)化公式；群體智能；全局最優(yōu)

0　引言

1995年，Kennedy和Eberhart發(fā)表研究論文首次提出了粒子群優(yōu)化算法[1]（particle swarm optimization，PSO），該算法是通過觀察鳥群集體出動(dòng)捕食的相互協(xié)助行為而提出的一種仿生優(yōu)化算法，該算法收斂速度和全局優(yōu)化能力均表現(xiàn)良好.而且該算法與遺傳算法相比，算法的參數(shù)更少，使用也更簡(jiǎn)單，因此算法自提出后已被廣泛用于各種工程實(shí)踐的優(yōu)化問題.然而，這種隨機(jī)算法本身的尋優(yōu)過程均是利用迭代機(jī)制進(jìn)行更新，算法往往快速收斂到一定程度之后就停滯了，即所謂“早熟”.因此算法對(duì)復(fù)雜問題的收斂精度不高.針對(duì)這個(gè)問題，很多學(xué)者對(duì)粒子群算法提出了許多改進(jìn)的方案，如基于逃離局部最優(yōu)的DPSO[2]，去掉了飛行速度項(xiàng)的一種簡(jiǎn)化粒子群算法[3]，通過釋放因子增強(qiáng)可利用的種群信息的改進(jìn)算法[4]，綜合學(xué)習(xí)的粒子群算法[5]（CLPSO），以及其他的改進(jìn)算法[6－8].這些改進(jìn)算法都在一定程度提高了算法的收斂精度，但都還沒有挖掘出粒子群算法最大潛力.

群智算法或者仿生算法都存在“早熟”現(xiàn)象，既能抑制算法過早出現(xiàn)“早熟”而又能保證算法的收斂是每種群智算法的改進(jìn)目標(biāo)，要達(dá)成這個(gè)目標(biāo)就必須在算法收斂的同時(shí)，盡可能的保持算法種群的多樣性.為此，筆者提出一種新的簡(jiǎn)化粒子群算法，即NSPSO算法.算法對(duì)粒子群算法的更新策略和更新公式進(jìn)行一些改進(jìn)，使改進(jìn)后粒子群算法在迭代優(yōu)化過程時(shí)，一定程度上保持了種群的多樣性，同時(shí)算法還具有拋棄某些粒子收斂停滯位置尋找新位置的能力.

1　粒子群優(yōu)化算法

由于PSO優(yōu)化算法是從鳥群捕食行為的基礎(chǔ)上提出的，因此在算法中的一個(gè)粒子相當(dāng)于鳥群中的一只鳥.而每一只鳥出去捕食均可能找到食物，故每一個(gè)粒子（鳥）可以視為待優(yōu)化問題的一個(gè)可能解（食物），算法尋優(yōu)的過程就相當(dāng)于鳥群尋找食物的過程.該算法搜尋的過程需要通過每個(gè)個(gè)體的個(gè)體極值與種群極值之間的信息分享來改變搜索的路徑，算法中粒子的更新公式如下：

其中，m為種群數(shù)；n為解空間的維數(shù)；Xi＝（χi1，…，χin）為第i個(gè)粒子的目前位置；Vi＝（vi1，vi2，…，vin）表示第i個(gè)粒子的飛行速度；Pi＝（pi1，pi2，…，pin）為到目前為止粒子i搜索到的最好位置，稱為個(gè)體極值；Pg＝（pg1，pg2，…，pgn）為到目前為止，整個(gè)找到的最好位置，稱為種群極值.j為粒子位置（共n維）的第j維；k表示進(jìn)化（搜索）的代數(shù)（輪數(shù)），c1和c2為記憶因子，r1和r2為兩個(gè)0～1之間產(chǎn)生的隨機(jī)數(shù).

事實(shí)上，通過文獻(xiàn)[9]證明：將粒子速度vid約束在[－vmax，vmax]等價(jià)于添加約束因子α的基礎(chǔ)上，文獻(xiàn)[3]通過嚴(yán)格數(shù)學(xué)推導(dǎo)，證明粒子群算法的速度參數(shù)對(duì)于算法進(jìn)化是無關(guān)的.如若將速度這一參數(shù)直接去掉，整個(gè)算法收斂的精度與速度會(huì)受到影響.因此，算法中的更新公式可以簡(jiǎn)化為[2]：

（3）式右邊的第1項(xiàng)表示過去搜索結(jié)果對(duì)現(xiàn)在的影響，ω為慣性系數(shù)；第2項(xiàng)則表示粒子的自身調(diào)節(jié)進(jìn)化；第3項(xiàng)表示粒子間的信息交流.

2　粒子群優(yōu)化算法的改進(jìn)

2.1減少每個(gè)粒子的更新位置

從更新式（1）和式（2）均可知，在以往的粒子群算法中，每個(gè)粒子均以更新公式進(jìn)行單點(diǎn)位置的更新.每一輪的尋優(yōu)中，算法總是將粒子的位置一次性更新，使粒子個(gè)體大幅度向個(gè)體和種群的極值靠攏，如果尋優(yōu)的問題不太復(fù)雜，一般的PSO算法均可以快速的找到最優(yōu)解.但是，如果待解決的問題相對(duì)來說更加復(fù)雜，且具有多個(gè)極值點(diǎn)的時(shí)候，算法就極可能快速的陷入某個(gè)局部最優(yōu)解而無法跳出來，最后種群中的個(gè)體都“聚集”在某一個(gè)點(diǎn)周圍，即算法出現(xiàn)“早熟”現(xiàn)象.為此，筆者借鑒蜂群算法中更新策略，提出將PSO算法在每一輪中，僅利用隨機(jī)的辦法生成T（T取1～5）個(gè)位置，對(duì)每個(gè)粒子的T個(gè)位置進(jìn)行更新.這樣，粒子在迭代更新過程中可以比較某個(gè)位置的更新是否比不更新前的位置更具有優(yōu)勢(shì)，優(yōu)化的過程更加具有針對(duì)性，粒子的位置也是部分的、慢慢的向最優(yōu)個(gè)體靠攏.

2.2保持種群的多樣性

將更新公式（3）改為：

對(duì)于式中u的數(shù)學(xué)描述如下：

其中，η＝1－0.9*（max＿iter-iter）/max＿iter為0.1～1線性遞增；pneighbour個(gè)體neighbour的極值，且i≠neighbour；這樣可以在種群搜索的初始階段，算法注重種群搜索的速度，而到了搜索的后半程，算法則更注重種群的多樣性，避免“早熟”.

2.3添加控制參數(shù)“l(fā)imit”

用于記錄某個(gè)粒子被更新的次數(shù)，若某個(gè)粒子連續(xù)經(jīng)過limit次迭代更新之后，其個(gè)體極值依然沒有得到改善，表明該粒子（解）已經(jīng)陷入局部最優(yōu)，那么就要放棄這個(gè)解，并重新隨機(jī)生成一個(gè)新解來代替χi，這樣使粒子在迭代進(jìn)化過程中完成“自救”，并能增加種群的多樣性.其中

改進(jìn)算法的具體實(shí)現(xiàn)步驟如下：

1）給定算法的參數(shù)：種群規(guī)模m；記憶因子c1，c2；影響參數(shù)ω以及最大迭代次數(shù)Gmax.

2）在待解決問題的搜索范圍內(nèi)隨機(jī)生成m個(gè)粒子的初始位置（每個(gè)粒子有n維）；

3）根據(jù)適應(yīng)度函數(shù)公式，計(jì)算每個(gè)粒子的適應(yīng)值；

4）以當(dāng)前每個(gè)粒子的位置作為該粒子經(jīng)歷的最好位置P，并求出整個(gè)種群的最優(yōu)位置Pg；

5）對(duì)于種群的所有粒子（for i＝1to m）；

6）對(duì)于粒子i，在1到n個(gè)位置間隨機(jī)生成T個(gè)位置，并按公式（5）對(duì)該粒子的T個(gè)位置進(jìn)行更新，并記sol為粒子i更新前的位置，sne為粒子i更新后的位置；

7）對(duì)于粒子i，計(jì)算其適應(yīng)值，并與更新前的適應(yīng)值進(jìn)行比較，若它的適應(yīng)值更好，就以更新后的位置sne作為粒子i這一輪迭代的位置，同時(shí)粒子i的控制參數(shù)“l(fā)imit”歸0；否則，以更新前的位置sol作為粒子i這一輪迭代的位置，同時(shí)粒子i的控制參數(shù)“l(fā)imit”加1；

8）對(duì)于粒子i，將其適應(yīng)值與它經(jīng)歷過的最好位置P的適應(yīng)值進(jìn)行比較，若較好，則將其更新位置P；

9）對(duì)于粒子i，比較其適應(yīng)值和種群中的最好位置Pg的適應(yīng)值，如果它的適應(yīng)值更好，更新Pg；

10）每完成一輪迭代，判斷是否有粒子的控制參數(shù)“l(fā)imit”達(dá)到上限，若存在，則根據(jù)（6）式生成一個(gè)新的解代替它，并將其對(duì)應(yīng)的控制參數(shù)歸0；

11）判斷是否滿足停止條件，若滿足，則輸出最優(yōu)值，否則轉(zhuǎn)到5）.

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

為了驗(yàn)證筆者提出的改進(jìn)粒子群算法的性能，選取了多個(gè)經(jīng)典測(cè)試函數(shù)對(duì)新算法進(jìn)行測(cè)試，其表達(dá)式如下，并將之與幾種有名的改進(jìn)算法：CLPSO、IPSO[5]、HPSO[6]的結(jié)果進(jìn)行比較.所用的測(cè)試函數(shù)及其搜索范圍、最優(yōu)點(diǎn)、初始化范圍等信息見表1：

表1　測(cè)試函數(shù)的全局最優(yōu)點(diǎn)、搜索范圍以及初始化范圍Tab.1　Test global optimum function，search range and initializing range

在改進(jìn)算法中，實(shí)驗(yàn)計(jì)算需要確定的參數(shù)c1＝c2＝2；種群規(guī)模m＝50；最大迭代次數(shù)3500次；每個(gè)函數(shù)獨(dú)立運(yùn)行20次；測(cè)試函數(shù)的維數(shù)是30維.對(duì)于CLPSO、IPSO、HPSO等算法均采用各自文獻(xiàn)中的默認(rèn)參數(shù)，其中他們的最大迭代次數(shù)分別是5000次，4000次和200000次.其比較結(jié)果見表2：

表2　函數(shù)為30維的測(cè)試結(jié)果Tab.2　30－dimensional function test results

從表2可以看出，筆者提出的NSPSO算法對(duì)絕大部分函數(shù)的收斂精度遠(yuǎn)高于CLPSO、HPSO和IPSO算法，而且在15個(gè)測(cè)試函數(shù)中，筆者提出的NSPSO算法有9個(gè)函數(shù)搜索到理論優(yōu)解，還有一個(gè)函數(shù)（Sphere函數(shù)）其精度也幾乎達(dá)到了理論值，從而證明該算法穩(wěn)定性和有效性.而HPSO算法只有在第3個(gè)測(cè)試函數(shù)Ackley上測(cè)試精度最好，但其耗費(fèi)的迭代次數(shù)太大.

進(jìn)一步地，為了觀察該算法在迭代過程中適應(yīng)度值的變化情況，將NSPSO算法和CLPSO在300維的Rastrigin函數(shù)、Ackley函數(shù)、Weierstrass函數(shù)以及Griewank函數(shù)上收斂過程進(jìn)行對(duì)比.見圖1～4.

從圖1～4的收斂曲線對(duì)比可以看出，對(duì)更高維的測(cè)試函數(shù)進(jìn)行全局尋優(yōu)時(shí)，NSPSO算法的收斂曲線在搜索開始后就迅速下降，隨著搜索的進(jìn)一步深入，筆者提出的NSPSO算法與CLPSO算法的收斂曲線的距離也越來越大（即兩種算法收斂精度差距越來越大：NSPSO算法收斂速度明顯快于CLPSO算法）.進(jìn)一步地，從圖中我們還可以看出，NSPSO算法的曲線是一直平滑的，而CLPSO的收斂曲線則在搜索的初始階段和搜索的中期均出現(xiàn)一定的不規(guī)則階梯型，即搜索出現(xiàn)停滯現(xiàn)象，這說明該算法在搜索過程中在不停的陷入局部最優(yōu)解，為此，算法不得不花費(fèi)一定的搜索時(shí)間逃出局部最優(yōu)解，因此該算法的收斂速度和收斂精度均遜于提出的NSPSO算法.

圖1　NSPSO和CLPSO對(duì)300維Rastrigin函數(shù)的收斂曲線對(duì)比圖Fig.1　NSPSO and CLPSO convergence curve 300 Victoria Rastrigin function comparison chart

圖2　NSPSO和CLPSO對(duì)300維Ackley函數(shù)的收斂曲線對(duì)Fig.2　NSPSO and CLPSO convergence curve dimensional Ackley function 300Comparison Chart

圖3　NSPSO和CLPSO對(duì)300維Griewank函數(shù)的收斂曲線對(duì)比圖Fig.3　NSPSO and CLPSO convergence curve 300 Victoria Griewank function comparison chart

圖4　NSPSO和CLPSO對(duì)300維Weierstrass函數(shù)的收斂曲線對(duì)比圖Fig.4　NSPSO and CLPSO convergence curve 300 Victoria Weierstrass function comparison chart

4　結(jié)論

筆者提出了一種簡(jiǎn)化的粒子群改進(jìn)算法（NSPSO算法），該算法不僅去掉了標(biāo)準(zhǔn)PSO算法中的粒子飛行速度項(xiàng)V部分，而且也拋棄了標(biāo)準(zhǔn)PSO算法中的向個(gè)體極值靠攏和向種群極值靠攏的部分，取而代之的是論文提出的粒子更新方法：粒子以一定概率選擇向其他粒子或種群極值進(jìn)行部分維數(shù)鄰域搜索新的位置，若搜索到的位置更好則更新粒子的位置，否則粒子的位置不更新.同時(shí)，論文還添加一個(gè)控制參數(shù)用以判斷是否放棄粒子目前的位置而重新生成新的位置.實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法的全局尋優(yōu)能力與其他改進(jìn)算法相比具有較大優(yōu)勢(shì)，而且筆者的改進(jìn)算法NSPSO收斂速度也快、精度也高，對(duì)于高、低維的復(fù)雜函數(shù)優(yōu)化問題均可行.

[1]Kennedy J，Eberhart R.Particle Swarm optimization[C].In：IEEE Int 1Conf on Neural Networks.Perth，Austraial，1995：1942－1948.

[2]Omranpour H.，Ebadzadeh M.，Shiry S.et al.，Dynamic Particle Swarm Optimization for Multimodal Function[J].Artificial Intelligence，2012，1（1）：1－10.

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

[4]任小波，楊忠秀.粒子群優(yōu)化算法的改進(jìn)[J].計(jì)算機(jī)工程.2010，36（7）：205－207.

[5]Liang J J，Qin A K，Suganthan P N，et al.Comprehensive learning particle swarm optimizer for global optimization of multimodal functions [C].IEEE Transactions on Evolutionary Computation，2006，10（3）：281－295.

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

[7]Chen Chia－Chong.Hierarchical Particle Swarm Optimization for Optimization Problems[J].Tamkang Journal of Science and Engineering，2009，12（3）：289－298.

[8]劉愛軍，楊育，李斐，等.混沌模擬退火粒子群優(yōu)化算法研究及應(yīng)用[J].浙江大學(xué)學(xué)報(bào)：工學(xué)版，2013，47（10）：1722－1730.

[9]Clerc M.The swarm and the queen：Towards a deterministic and adaptive particle swarm optimization[C].Proc.The Congress on Evolutionary Computation.Washington，1999：1951－1957.

[責(zé)任編輯 蘇 琴][責(zé)任校對(duì) 黃招揚(yáng)]

A New Simplified Particle Swarm Optimization

LI Xiao-jing
（Guangχi College for Preschool Education，Nanning530022，China）

Concerning the problems of premature and low convergence accuracy for the particle？swarm？algorithm in search of optimization，update strategy and formula of the particle position have been made improvements in this paper，and a new simple particle swarm optimization（NSPSO）is proposed. Through global optimization tests in 15multiple maximum benchmark functions，the experimental results show the convergence accuracy of NSPSO has improved greatly and the rate of convergence become faster，which can be applied in the optimization for high and low dimensional complicated functions.

particle swarm optimization；Simplified formula；swarm intelligence；global optimality

TP18

A

1673－8462（2015）01－0083－07

2014-09-10.

廣西青年基金項(xiàng)目（2013GXNSFBA019227）；國家自然科學(xué)基金項(xiàng)目（41065002）.

李曉靜（1982-），女，河南許昌人，碩士，廣西幼兒師范高等?？茖W(xué)校講師，研究方向：數(shù)據(jù)挖掘、應(yīng)用數(shù)學(xué).