PSO的改進(jìn)
——跳蚤算法

黃志鋼，趙曉寒，孫 泰

(1.沈陽(yáng)理工大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 沈陽(yáng) 110159；2.香港中文大學(xué)，香港 新界 沙田)

PSO的改進(jìn)
——跳蚤算法

黃志鋼1，趙曉寒1，孫 泰2

(1.沈陽(yáng)理工大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 沈陽(yáng) 110159；2.香港中文大學(xué)，香港 新界 沙田)

PSO;斥力；跳蚤算法

粒子群算法(PSO)是由kennedy James和Eberhart Russell在1995年提出的一種模擬鳥類捕食行為的全局優(yōu)化算法[1]。PSO算法的提出引起了演化計(jì)算領(lǐng)域國(guó)內(nèi)外眾多專家的興趣，經(jīng)過(guò)幾十年的發(fā)展，PSO算法被廣泛應(yīng)用于優(yōu)化和一些工程領(lǐng)域[2-3]。但PSO算法本身也存在一些固有缺陷，其中最主要的是容易產(chǎn)生早熟，在迭代后期，收斂速度慢、全局搜索能力差、粒子出現(xiàn)“趨同性”。提高算法的性能以及避免陷入局部最優(yōu)點(diǎn)已經(jīng)成為研究的熱點(diǎn)。

1 PSO的早熟與斥力改進(jìn)

1.1 PSO的早熟

文中，第i個(gè)粒子的當(dāng)前函數(shù)值、位置，記為f(xi)、xi；第i個(gè)粒子的最優(yōu)函數(shù)值及其位置，記為pibestF、pibestX，稱為局部最優(yōu)解；pibestF中的最優(yōu)值及其位置，記為GbestF、GbestX，稱為全局最優(yōu)解；函數(shù)的全局最優(yōu)值及其位置記為FbestF、GbestX，稱為函數(shù)最優(yōu)解。同時(shí)指代位置X和函數(shù)值F時(shí)不加后綴。

vi(t+1)=wvi(t)+c1×r1(0,1)×(PibestX(t)-xi(t)+c2×r2(0,1)×(GbestX(t)-xi(t))

x1(t+1)=xi(t)+vi(t+1)

根據(jù)上述標(biāo)準(zhǔn)PSO算法的迭代公式可知粒子總是受到PibestX和GbestX的吸引，此種只設(shè)計(jì)了引力沒(méi)有設(shè)計(jì)斥力的尋優(yōu)方法使得粒子一旦陷入局部最優(yōu)解時(shí)，沒(méi)有斥力把陷入早熟的粒子分散開。另外，PSO算法假設(shè)函數(shù)最優(yōu)解在粒子群的運(yùn)動(dòng)軌跡包絡(luò)體中，當(dāng)函數(shù)最優(yōu)解不在這個(gè)包絡(luò)體中時(shí)，粒子有可能無(wú)法找到函數(shù)最優(yōu)解。

1.2 R斥力改進(jìn)

針對(duì)早熟問(wèn)題，研究者們基于參數(shù)、位置公式、速度公式等角度對(duì)單一的引力進(jìn)行了各種改進(jìn)[4]。其中特別引起筆者注意的是范超贊等人[4]，在PSO算法中引進(jìn)的r斥力，即引入排斥半徑r和排斥因子，以最優(yōu)粒子位置為超圓心設(shè)定一個(gè)排斥半徑r，將進(jìn)入r區(qū)域的粒子依照排斥因子參數(shù)排斥出去。

R斥力算法的思路與問(wèn)題：

(1)如果最優(yōu)粒子的r范圍內(nèi)僅有一個(gè)峰值即函數(shù)最優(yōu)解，沒(méi)有谷值，則該粒子可以尋優(yōu)到這個(gè)峰值。而且有一個(gè)粒子逼近最優(yōu)解就足夠，所以可以驅(qū)動(dòng)其余粒子離開r范圍去尋找其他可能的更優(yōu)解，以此來(lái)避免趨同和早熟問(wèn)題。

(2)但是，如果最優(yōu)粒子的r范圍內(nèi)有多個(gè)峰值和谷值，則該粒子可能早熟于某個(gè)峰值，而無(wú)法到達(dá)函數(shù)最優(yōu)解。同時(shí)r斥力阻止其它粒子進(jìn)入r范圍尋找函數(shù)最優(yōu)解。

(3)如果Fbest不在Gbest的r范圍內(nèi)，那么斥力PSO僅僅是把其他粒子排斥離開Gbest。

(4)但是并沒(méi)有在其余粒子之間設(shè)置斥力，其余粒子有可能聚集在一個(gè)局部范圍內(nèi)，依然處于早熟趨同狀態(tài)。例如聚集在Gbest的R邊界處，這時(shí)的r太小。

(5)若r過(guò)大，則可能把FbestX包括進(jìn)來(lái)，這時(shí)最優(yōu)粒子有可能早熟于Gbest，并阻止其他粒子進(jìn)入FbestX的附近尋優(yōu)，從而沒(méi)有粒子去尋找Fbest。

2 尋優(yōu)算法改進(jìn)分析

2.1 多峰值函數(shù)的特征鄰域與可尋優(yōu)性

2.2 尋優(yōu)算法對(duì)特征鄰域的遍歷性、粘著性和脫離性

Fbest的特征鄰域?yàn)榭占暮瘮?shù)是不可尋優(yōu)函數(shù)，只有尋優(yōu)算法恰好取到這個(gè)孤立位置才能求得Fbest，因此任何尋優(yōu)算法只能以零概率求得這種函數(shù)的Fbest。

Fbest的特征鄰域非空的函數(shù)是可尋優(yōu)函數(shù)，某些尋優(yōu)算法能以正概率進(jìn)入這個(gè)特征鄰域并由此尋優(yōu)到Fbest。

若每個(gè)特征鄰域內(nèi)都粘著一個(gè)粒子進(jìn)行尋優(yōu)，則必然能尋得Fbest[6]。

一個(gè)尋優(yōu)算法如果能按概率遍歷所有特征鄰域并粘著尋優(yōu)，則它能按概率尋到Fbest。

粒子群尋優(yōu)計(jì)算時(shí)，如果粒子數(shù)少于特征鄰域數(shù)，則尋優(yōu)算法必須具備脫離性才有可能遍歷所有特征鄰域。

因此，尋優(yōu)算法應(yīng)該具有對(duì)特征鄰域的遍歷性、粘著性和脫離性。

遍歷性的作用是防止漏掉Fbest的鄰域，粘著性的作用是保障粒子能停留在特征領(lǐng)域內(nèi)逼近最優(yōu)點(diǎn)，脫離性的作用是預(yù)防和克服趨同現(xiàn)象。

從標(biāo)準(zhǔn)PSO的迭代公式可知，其遍歷性、脫離性都不夠好，一旦陷入局部最優(yōu)，粒子群就可能會(huì)趨同早熟，導(dǎo)致粒子群無(wú)法遍歷整個(gè)求解域，漏掉Fbest。

3 跳蚤算法

3.1 跳蚤算法的原理

針對(duì)標(biāo)準(zhǔn)PSO存在的早熟和趨同性等缺點(diǎn)，提出一種新的優(yōu)化方法—跳蚤算法。此種算法模擬跳蚤的運(yùn)動(dòng)模式，跳蚤體重越大，跳距越短，體重越小，跳距越長(zhǎng)，跳蚤對(duì)應(yīng)粒子，體重對(duì)應(yīng)函數(shù)值，根據(jù)函數(shù)值的優(yōu)劣按一定的關(guān)系式動(dòng)態(tài)分配各個(gè)粒子的步長(zhǎng)，最優(yōu)粒子分配最小步長(zhǎng)細(xì)致地尋找最優(yōu)解，最劣粒子分配最大步長(zhǎng)按概率去遍歷真優(yōu)解的特征鄰域。每個(gè)粒子根據(jù)算法規(guī)則分配的步長(zhǎng)進(jìn)行尋優(yōu)操作，使得每個(gè)粒子都無(wú)法聚集在同一點(diǎn)上，從而使整個(gè)粒子群不會(huì)出現(xiàn)趨同于局部最優(yōu)解的現(xiàn)象[7]。

3.2 步長(zhǎng)的設(shè)定

步長(zhǎng)是人為設(shè)定的，在本文的算例中，第top(k)個(gè)粒子的步長(zhǎng)為A·αk，A的值決定了精度，αn(n粒子總數(shù))決定最大步長(zhǎng)即穿越谷區(qū)的寬度，取1.1～1.5，其中，k代表粒子號(hào)。例如：當(dāng)取α=1.4時(shí)，通過(guò)對(duì)步長(zhǎng)的數(shù)學(xué)表達(dá)式的分析可知，若取步長(zhǎng)最小為0.01，當(dāng)粒子的個(gè)數(shù)為20時(shí)，最大步長(zhǎng)為10，步長(zhǎng)倍數(shù)為1000。

3.3 跳蚤算法迭代公式

跳蚤算法的更新迭代公式為

若f(xi)>PibestF則更新Pibest

若有PibestF>GbestF則更新Gbest

stepi=step0·αtop(f(xi))

topi：從小到大的排序；

Pibest：第i個(gè)粒子已走過(guò)的最優(yōu)解；

Gbest：全局最優(yōu)解；

由公式可知跳蚤算法中，粒子的更新迭代是和粒子的當(dāng)前位置、全局的最優(yōu)位置有關(guān)，并與函數(shù)優(yōu)性有關(guān)的步長(zhǎng)量。

變步長(zhǎng)主要體現(xiàn)粒子間的排斥力，使粒子不能陷入早熟困境，并且粒子的下次方向依據(jù)當(dāng)代方向信息而定。另一方面，在粒子群中加入Gbest的吸引力，暫定其作用強(qiáng)度是Pibest的十分之一。

從兩個(gè)過(guò)程的比較可知，標(biāo)準(zhǔn)PSO的迭代過(guò)程只和引力有關(guān)，粒子的飛行是被Pibest和Gbest吸引著，而沒(méi)有排斥力，從而容易陷入局部最優(yōu)點(diǎn)的早熟困境。相比之下，跳蚤算法，在更新迭代的過(guò)程當(dāng)中，不但存在著吸引力，而且最主要的是存在著排斥力，正是由于這種排斥力，即使所有粒子已經(jīng)落在一個(gè)點(diǎn)上，也能夠由于各個(gè)粒子不同的步長(zhǎng)而分散開，退出局部早熟。

4 算例

其峰谷阻礙尋優(yōu)算法向函數(shù)最優(yōu)值移動(dòng)。

圖1為二維函數(shù)y=r·cosr進(jìn)行尋優(yōu)處理的結(jié)果，所有粒子的初始位置都在(10，10)處。

圖1 二維測(cè)試函數(shù)時(shí)優(yōu)化算法的算例1

由圖1可以清晰地看出，粒子的蹤跡比較集中于Gbest的峰值圈，而在其它位置上，粒子基本都是以較大的步長(zhǎng)進(jìn)行搜索，所以密度較小，會(huì)顯得比較疏散。

圖2 二維測(cè)試函數(shù)時(shí)優(yōu)化算法的算例2

5 結(jié)束語(yǔ)

由算例可知，即使粒子全部初始于同一點(diǎn)時(shí)，由于步長(zhǎng)的不同使得某些粒子可以擺脫局部最優(yōu)點(diǎn)去尋找更好的點(diǎn)，所以，跳蚤算法可以有效克服早熟問(wèn)題，特別是對(duì)于一些多峰值函數(shù)，跳蚤算法能夠克服標(biāo)準(zhǔn)PSO算法的不足之處。

但是，跳蚤算法還存在一些缺陷。當(dāng)步長(zhǎng)分配不合理時(shí)，比如步長(zhǎng)比較小，則很可能粒子無(wú)法跳躍“峰谷”到達(dá)對(duì)面特征鄰域。另外，跳蚤算法的精度受限于最小步長(zhǎng)step0。在后續(xù)的研究中，主要方向是如何預(yù)先確定step0或運(yùn)算中修改最大步長(zhǎng)和最小步長(zhǎng)來(lái)改善整個(gè)算法的效果。

[1]Kennedy J，Eberhart R.Particle Swarm Optimization[C].Proceeding of IEEE international conference on neutral networks，Perth，Australia，1995：1942-1948.

[2]譚皓，沈春林，李錦.混合粒子群算法在高維復(fù)雜函數(shù)尋優(yōu)中的應(yīng)用[J].系統(tǒng)工程與電子技術(shù)，2005，27(8)：1471-1474.

[3]FAN K S，LIANG Y C，ZAHARA E.Hybrid simplex search and particle swarm optimization for the global optimization of multimodal functions[J].Engineering Optimization，2004，36(4)：401-418.

[4]李寧.粒子群優(yōu)化算法的理論分析與應(yīng)用研究[D].武漢：華中科技大學(xué)，2007：24-67.

[5]張杰，范超贊.改進(jìn)粒子群算法研究[D].北京：北方工業(yè)大學(xué)，2010：11-17.

[6]倪勤.最優(yōu)化方法與程序設(shè)計(jì)[M].北京：科學(xué)出版社，2009：1-15.

[7]張曉清，張建科，方敏.多峰搜索的動(dòng)態(tài)微粒群算法[J].計(jì)算機(jī)應(yīng)用，2005，25(1)：266-267.

(責(zé)任編輯：馬金發(fā))

Flea Algorithm Based on An Improved Particle Swarm Optimization

HUANG Zhigang1，ZHAO Xiaohan1，SUN Tai2

(1.Shenyang Ligong University，Shenyang 110159，China;2.Chinese University of Hong Kong，Shatin，New Territories，Hong Kong)

PSO;repelling force;flea algorithm

2014-09-28

黃志鋼(1960—)，男，副教授；研究方向：計(jì)算機(jī)控制系統(tǒng)，嵌入式系統(tǒng).

1003-1251(2015)04-0080-04

TP301.6

A