骨干粒子群算法兩種不同實(shí)現(xiàn)的優(yōu)化特性

張 震,潘再平,潘曉弘

（浙江大學(xué)工學(xué)部,浙江杭州310027）

骨干粒子群算法兩種不同實(shí)現(xiàn)的優(yōu)化特性

張 震,潘再平,潘曉弘

（浙江大學(xué)工學(xué)部,浙江杭州310027）

總結(jié)了骨干粒子群算法（BBPSO）的一般形式,指出決定BBPSO算法本質(zhì)的4個要素.BBPSO在實(shí)施中,粒子不同維度采用的隨機(jī)變量值相同或不同,這將導(dǎo)致算法的特性及適合的優(yōu)化對象不同.記相同的為I型實(shí)現(xiàn),不同的為II型實(shí)現(xiàn),通過實(shí)驗(yàn)指出2種實(shí)現(xiàn)的差別：I型實(shí)現(xiàn)有各向同性的優(yōu)點(diǎn),但是粒子多樣性差；II型粒子多樣性更優(yōu),但各向異性,使用高斯、柯西、指數(shù)和均勻分布形式的II型BBPSO都傾向于沿坐標(biāo)軸尋解.從理論上分析了這些差別的成因,指出I型實(shí)現(xiàn)總體性能較差,只適合優(yōu)化梯度變化明顯的單峰函數(shù)；II型實(shí)現(xiàn)總體性能較好,擅長求解峰的方向平行于坐標(biāo)軸的單峰或多峰函數(shù).

骨干粒子群算法（BBPSO）；量子粒子群算法（QPSO）；粒子多樣性；各向異性算法

骨干粒子群（bare-bone PSO,BBPSO）是一種精簡的粒子群算法,取消了粒子的速度屬性,以隨機(jī)分布的形式完成進(jìn)化.第一種BBPSO由Kennedy［1］提出,用高斯分布控制粒子進(jìn)化,本文記為GBBPSO.隨后,Sun等［2］在量子空間內(nèi)考慮粒子行為,得出一個帶指數(shù)分布的BBPSO進(jìn)化方程.這一改進(jìn)算法即量子粒子群算法（QPSO）,Sun等［3］對控制參數(shù)、粒子行為和算法性能作了詳細(xì)研究.近年來對QPSO的算法改進(jìn)、分析與應(yīng)用是最高產(chǎn)的骨干粒子群研究領(lǐng)域［4］.GBBPSO和QPSO是影響最大的2類基本骨干粒子群形式,本文重點(diǎn)分析這2類BBPSO.

在PSO中,粒子以鄰域內(nèi)粒子的最優(yōu)解為引導(dǎo)決定移動位置,鄰域選擇形式稱為拓?fù)浣Y(jié)構(gòu).骨干粒子群中保留了這些概念,Zhang等［5-6］考察了不同拓?fù)浣Y(jié)構(gòu)對BBPSO的影響,結(jié)果表明拓?fù)浣Y(jié)構(gòu)的優(yōu)化能進(jìn)一步改進(jìn)算法性能.基于此,本文將拓?fù)湫问降牟煌鳛榉治鲋械囊粋€變量.

英國學(xué)者Blackwell對BBPSO研究作出了比較突出的貢獻(xiàn),與Richer［7］共同提出了Levy BBPSO（LBBPSO）,使用更長尾的Levy分布替代高斯分布,從而算法有可能在群體集中時產(chǎn)生較大的標(biāo)準(zhǔn)差讓粒子分散,這一改進(jìn)在測試函數(shù)中獲得了較好的改進(jìn)效果.針對BBPSO的坍塌問題,Blackwell等［8］提出基于高斯或柯西分布的跳躍機(jī)制.從理論上研究了GBBPSO坍塌的機(jī)理［9］,指出BBPSO還有更多的改善空間.

國內(nèi)外學(xué)者從多方面對BBPSO進(jìn)行了改進(jìn),近幾年的主要改進(jìn)如下：Hsieh等［10］在GBBPSO的基礎(chǔ)上,對平均值和標(biāo)準(zhǔn)差各自增加了一個調(diào)節(jié)系數(shù)；Li等［11］在QPSO的基礎(chǔ)上引入合作機(jī)制,利用若干臨時個體的協(xié)作完成粒子的進(jìn)化；Zhang等［12］在GBBPSO的標(biāo)準(zhǔn)差中引入一個帶參數(shù)的變異項并分析了其對算法收斂性的影響,隨后在算法中引入定向混合搜索方法［13］.由于算法簡潔、調(diào)節(jié)參數(shù)少（甚至沒有）、優(yōu)化性能良好,BBPSO近兩年來成功應(yīng)用于經(jīng)濟(jì)調(diào)度［13］、故障診斷［14］、工程優(yōu)化［6,15］等領(lǐng)域.

盡管國內(nèi)外學(xué)者對BBPSO的改進(jìn)和應(yīng)用進(jìn)行了大量研究,但在算法特性方面,除了Blackwell［9］分析了求解坍塌機(jī)理、Zhang等［12］分析了引入的變異項對算法收斂性的影響之外,較少出現(xiàn)相關(guān)工作.本文首次系統(tǒng)地對BBPSO的尋解特性進(jìn)行分析.

BBPSO在實(shí)現(xiàn)中,針對粒子不同維度采用的隨機(jī)變量值是否相同有兩種實(shí)現(xiàn),記相同的為I型實(shí)現(xiàn),不同的為II型實(shí)現(xiàn).為了分析2種實(shí)現(xiàn)的不同特性,本文開展以下工作.首先提出BBPSO的一般形式,指出算法的4個核心因素.結(jié)合實(shí)驗(yàn)指出BBPSO 2種不同實(shí)現(xiàn)的特性：I型實(shí)現(xiàn)將導(dǎo)致粒子多樣性較差,而使用所有主流分布（高斯、柯西、指數(shù)和均勻分布）的II型實(shí)現(xiàn)都將導(dǎo)致粒子傾向于沿著坐標(biāo)軸方向?qū)そ?本文首次提出并從理論上論證了這BBPSO的這2個特性.基于這些結(jié)論,指出2種實(shí)現(xiàn)各自的優(yōu)缺點(diǎn)及適合求解的問題.

1 BBPSO算法模型

1.1 基本GBBPSO及其改進(jìn)簡述

在經(jīng)典粒子群算法中,粒子i將收斂于歷史最優(yōu)點(diǎn)Pi和鄰域最優(yōu)點(diǎn)Gi中間的某一點(diǎn).受此啟發(fā),Kennedy提出的最初GBBPSO形式如下：

式中：xid表示點(diǎn)Xi第d維的位置；pid和gid分別為Pi和Gi第d維的值,以Pi和Gi的平均值為中心、差絕對值為標(biāo)準(zhǔn)差的高斯分布變量為基礎(chǔ)完成位置進(jìn)化.

除取消了速度項之外,GBBPSO與經(jīng)典粒子群的最大的區(qū)別是,下一移動位置不取決于當(dāng)前粒子位置,而是當(dāng)前的粒子歷史最優(yōu)位置.這一改變使得PSO的差分方程模型不能用于此處,從而增加了算法特性分析的困難.針對GBBPSO基本模型的改進(jìn)主要有以下兩方面.

1）鄰域拓?fù)涞母倪M(jìn).Zhang等［5］分析了全鄰域和局部鄰域下BBPSO的不同性能和特征.Chang等［16］研究通過增加鄰域內(nèi)的粒子最優(yōu)位置信息來改進(jìn)高斯分布平均值,得到更好的總體性能.

2）高斯分布標(biāo)準(zhǔn)差的控制.在式（1）中,算法是不帶控制參數(shù)的.Rifaie等［8,10］增加了一個系數(shù)α來控制標(biāo)準(zhǔn)差.引進(jìn)系數(shù)的優(yōu)點(diǎn)是顯然的,對不同函數(shù)、不同進(jìn)化階段都可以用來調(diào)節(jié)粒子移動幅度,從而改進(jìn)算法性能.

式中：K為鄰域內(nèi)粒子數(shù)量,α為標(biāo)準(zhǔn)差調(diào)節(jié)系數(shù).結(jié)合這兩點(diǎn)改進(jìn)之后的BBPSO如式（2）所示.

1.2 鄰域模型的表示

本文用集合的方式來表示不同的BBPSO鄰域模型.對于一個由N個粒子組成的群體,以Pi表示第i個粒子的歷史最優(yōu)位置,則所有粒子最優(yōu)位置的全鄰域模型可以表示為集合S：

于是粒子i的鄰域Li為S的一個子集,對于局部環(huán)狀拓?fù)?Li＝｛Pi－1,Pi,Pi＋1｝；對于全鄰域拓?fù)銵i＝S.粒子鄰域最優(yōu)位置Gi即Li的最優(yōu)元素.

1.3 BBPSO算法一般模型的建立

引入鄰域模型后,GBBPSO進(jìn)化方程（式（2））可以表示為

記ξ為標(biāo)準(zhǔn)正態(tài)分布變量,即ξ＝N（0,1）,可將進(jìn)化方程進(jìn)一步轉(zhuǎn)換為

式（5）為BBPSO的一般模型.應(yīng)該說明的是,式（5）雖然是從高斯骨干粒子群推導(dǎo)而來,但適用于所有的主流骨干粒子群形式.可以看出,骨干粒子群的一般模型中只有一個控制參數(shù)α,位置進(jìn)化由4個因素決定：一是鄰域Li,二是進(jìn)化中心位置μ（Li）,三是離散控制項σ（Li）,四是隨機(jī)分布變量ξ.對其中每一項的不同選擇都將產(chǎn)生不同的變異形式,原始GBBPSO［1］、LBBPSO［7］、QPSO_Type 1［2］這3種算法,與一般模型的各項對應(yīng)關(guān)系如表1所示.

表1 3種BBPSO一般模型中的參數(shù)值Tab.1 Parameter mapping of three BBPSO to general model

LBBPSO把項Pi-Gi作為范圍調(diào)節(jié)參數(shù)內(nèi)置于Levy分布中；QPSO中參數(shù)φ1和φ2為服從［0,1］均勻分布的隨機(jī)變量,鄰域中除了所有粒子的歷史最優(yōu)位置,還增加了粒子當(dāng)前位置.值得說明的是,研究者們提出的大量不同BBPSO的變異形式,主要都是對模型中的一項或幾項的改進(jìn).

1.4 BBPSO算法的兩種實(shí)現(xiàn)形式

觀察一般進(jìn)化方程（5）可知,Xi、μ（Li）和σ（Li）都為向量,每個維度下的值互相獨(dú)立.在算法實(shí)施中,ξ有2種處理方式：1）將ξ視為標(biāo)量,即每個維度進(jìn)化時選用相同的值；2）將ξ視為向量,即每個維度進(jìn)化時用獨(dú)立的值.這2種實(shí)現(xiàn)的偽代碼如下.

其中,變量D為粒子維度.

2 I型實(shí)現(xiàn)特性分析

在I型實(shí)現(xiàn)中,ξ為標(biāo)量.由式（5）可知,粒子位置由向量μ（Li）和σ（Li）線性疊加得到,這一過程不依賴于具體的坐標(biāo)系,因此算法具有平移不變和各項同性的特點(diǎn).

在粒子群“駐態(tài)”情況下進(jìn)行分析.駐態(tài)（stagnation）是指粒子的歷史最優(yōu)位置Pi和鄰域最優(yōu)位置Gi都保持不變的進(jìn)化狀態(tài).

粒子多樣性是衡量粒子群算法的一個重要指標(biāo).若粒子多樣性較好,則算法有更大的可能尋找到全局最優(yōu)解,因而對多峰函數(shù)的優(yōu)化性能更好.從運(yùn)動自由度角度來考慮,各個維度使用相同的ξ導(dǎo)致粒子自由度降低,這必然導(dǎo)致粒子多樣性較差.分析GBBPSO和QPSO這2類形式在這種低粒子自由度下的表現(xiàn).從粒子多樣性分析出發(fā),首先通過對實(shí)驗(yàn)說明GBBPSO和QPSO的I型實(shí)現(xiàn)將導(dǎo)致粒子沿著（或經(jīng)過若干次迭代之后沿著）一條直線運(yùn)動,然后從理論上說明這一現(xiàn)象的必然性.

2.1 粒子多樣性實(shí)驗(yàn)

圖1 II型實(shí)現(xiàn)在二維下粒子的運(yùn)動軌跡Fig.1 Particle trajectory of BBPSO-I in two-dimensional space

實(shí)驗(yàn)1 選取算法形式為GBBPSO和QPSO的I型實(shí)現(xiàn)（算法詳情見表1）,系數(shù)α設(shè)為1,維度為2,固定Pi坐標(biāo)為（30,60）,Gi為（60,－30）.粒子迭代100次,記錄運(yùn)動軌跡.

實(shí)驗(yàn)結(jié)果如圖1所示.可見,GBBPSO粒子運(yùn)動完全沿著直線PG運(yùn)動；QPSO粒子在經(jīng)過10次左右迭代之后,軌跡完全進(jìn)入直線PG.

2.2 理論分析

BBPSO一般模型中的離散控制項σ（Li）有2種情況：一種是只由鄰域內(nèi)的粒子歷史最優(yōu)位置Pi決定,如GBBPSO；另一種還將受粒子當(dāng)前（或更早）位置Xi決定,如QPSO.圖2的2種粒子運(yùn)動軌跡顯示了這兩種情況的區(qū)別,下面分析這兩種情況下的粒子特性.

定理1 對于I型實(shí)現(xiàn),若BBPSO的離散控制項只由Li決定,則在鄰域狀態(tài)為的駐態(tài)中,粒子將只沿著經(jīng)過點(diǎn)μ）、方向?yàn)棣遥ǎ┑闹本€運(yùn)動.

這一結(jié)果是顯然的,將隨機(jī)變量ξ視為自變量,由式（5）可得粒子的運(yùn)動軌跡為

對于QPSO,進(jìn)化中心μ（Li）實(shí)際上是由一個均勻分布變量產(chǎn)生的直線分布.此外,在離散控制項中加入了當(dāng)前位置,對該類變異形式有以下結(jié)論.

定理2 對于I型實(shí)現(xiàn),如果BBPSO符合2個條件：1）σ（Li）與μ（Li）具有相同的位置分布；2）離散控制項形式為σ（Li）－Xi,即粒子的當(dāng)前位置會影響下一時刻的位置.在駐態(tài)中,粒子隨著迭代的進(jìn)行將以概率1落入由σ（Li）概率分布所在的直線中.

證明：包含Xi項之后,離散控制項在駐態(tài)中并非為固定值,進(jìn)化方程轉(zhuǎn)變?yōu)?/p>

對t取極限,再對式（7）兩邊求期望值,可得

由于ξ和Xi、ξ和μ（Li）之間都相互獨(dú)立,結(jié)合條件1）,從式（7）可得

即粒子位置的期望在μ（Li）的分布中心.若μ（Li）的分布為直線PG,則隨著迭代進(jìn)行粒子落在PG上的概率為1.一旦落入PG上的任意一點(diǎn),從式（7）可知,粒子將再不能逃離出直線PG.定理2得證.

QPSO中μ（Li）的分布即為連接Pi和Gi的直線PG,由定理2可知,實(shí)驗(yàn)1中QPSO粒子在迭代若干次之后進(jìn)入直線PG是必然的.孫俊在改進(jìn)算法QPSO_Type 2中創(chuàng)造性地在σ（Li）項中引入“平均最優(yōu)位置”,本質(zhì)是使算法的σ（Li）與μ（Li）不相等,算法不再滿足條件1,粒子多樣性得到增強(qiáng),從而獲得更好的總體性能.

3 II型實(shí)現(xiàn)特性分析

在II型實(shí)現(xiàn)中,ξ為矢量,每一個維度互相獨(dú)立,對σ（Li）各個維度的值根據(jù)其離坐標(biāo)原點(diǎn)的遠(yuǎn)近進(jìn)行不同程度的放大（或縮?。?因此算法求解過程受坐標(biāo)系選取的影響.

首先通過對GBBPSO和QPSO 2種骨干粒子群的II型實(shí)現(xiàn)進(jìn)行實(shí)驗(yàn)分析,指出II型實(shí)現(xiàn)粒子多樣性優(yōu)于I型,但是有傾向于沿著坐標(biāo)軸尋解的現(xiàn)象,隨后從理論上分析了該現(xiàn)象的產(chǎn)生.

3.1 粒子多樣性實(shí)驗(yàn)

實(shí)驗(yàn)2 選取算法形式為GBBPSO的II型實(shí)現(xiàn),設(shè)置維度為2,固定Pi坐標(biāo)為（30,60）,Gi為（60,－30）.粒子迭代100次,記錄運(yùn)動軌跡.

實(shí)驗(yàn)結(jié)果如圖2所示,可見粒子不再像I型實(shí)現(xiàn)一樣陷入一條直線,而是擴(kuò)展到了全空間.這意味該粒子的空間多樣性優(yōu)于I型實(shí)現(xiàn),從而對多峰函數(shù)的優(yōu)化性能更好,這是算法提出者使用II型實(shí)現(xiàn)的原因.

圖2 II型GBBPSO實(shí)現(xiàn)在二維下粒子的運(yùn)動軌跡Fig.2 Particle trajectory of GBBPSO-II in two-dimensional space

3.2 坐標(biāo)軸偏向?qū)嶒?yàn)

前文已指出算法求解過程受坐標(biāo)系選取的影響,筆者通過BBPSO的II型實(shí)現(xiàn)對函數(shù)優(yōu)化時的粒子特性來進(jìn)一步觀察這一點(diǎn).

實(shí)驗(yàn)3 選取算法形式為GBBPSO和QPSO的II型實(shí)現(xiàn),優(yōu)化目標(biāo)函數(shù)為坐標(biāo)距離原點(diǎn)偏離（100,200）的二維Sphere函數(shù),即

設(shè)置系數(shù)α為1,粒子數(shù)量為10 000,初始化位置為［－100,100］范圍均勻分布.迭代10次后,記錄所有粒子的位置,粒子散點(diǎn)圖如圖3所示.

圖3 II型實(shí)現(xiàn)迭代10次后粒子分布Fig.3 Particles distribution of BBPSO II after 10 iterations

從圖3可以看出,不論是GBBPSO還是QPSO的粒子在迭代10次后,都以點(diǎn)（100,200）為中心,沿著坐標(biāo)軸方向呈十字形分布.

為了進(jìn)一步分析該現(xiàn)象,引入粒子“速度”的概念,即

重新以GBBPSO運(yùn)行一次實(shí)驗(yàn)3,每次迭代中保存粒子群的當(dāng)前位置以及上一次位置,用以計算粒子“速度”.在第10次迭代時記錄所有粒子的速度,統(tǒng)計速度與x軸夾角θ的分布,結(jié)果如圖4所示.圖中,N為分布在θ角度的粒子數(shù).可以看出,大部分粒子都沿著與x軸夾角為－90°、0°和90°的方向運(yùn)動,即坐標(biāo)軸方向.這一結(jié)果進(jìn)一步確認(rèn)了粒子的坐標(biāo)軸偏向現(xiàn)象.

圖4 GBBPSO II型實(shí)現(xiàn)粒子移動速度的角度分布Fig.4 Velocity angle distribution of GBBPSO II

該現(xiàn)象不是實(shí)驗(yàn)3中的設(shè)置導(dǎo)致的,使用其他目標(biāo)函數(shù)、在更高維度下,也有坐標(biāo)軸偏向的問題.

3.3 理論分析

Spears等［17］分析了標(biāo)準(zhǔn)粒子群中的坐標(biāo)軸偏向問題,實(shí)驗(yàn)3說明BBPSO的II型實(shí)現(xiàn)有坐標(biāo)軸偏向問題.以下將說明II型實(shí)現(xiàn)中使用的隨機(jī)分布與這一現(xiàn)象之間的內(nèi)在關(guān)系.

為了方便敘述,分析中略去粒子下標(biāo)i.設(shè)在t時刻粒子位置為X,迭代一次之后位置為X′,則由式（5）有

二維下,速度V＝X′－X表示為

記ai＝μi（L′）－μi（L）,bi＝α·σi（L′）,ci＝－α·σi（L）,則速度V及其夾角θ簡化為

無論ξ取何種分布,取值多少,θ都有一個伴隨角度,記為θ*：

通過實(shí)驗(yàn)4來分析θ隨θ*的變化情況.

實(shí)驗(yàn)4 a1、a2、b1、b2、c1和c2這6個參數(shù)以高斯分布N（0,1 000）隨機(jī)取值,按照式（15）、（16）計算θ和θ*.分別取ξ為標(biāo)準(zhǔn)高斯、柯西、指數(shù)和［0,1］均勻分布,在每種分布下重復(fù)計算θ和θ*共1.8×107次；然后將θ*按照角度離散為180個區(qū)間,計算每個區(qū)間中θ的平均值和方差,結(jié)果如圖5所示.

由圖5可知,柯西分布與高斯分布的結(jié)果類似,指數(shù)分布和均勻分布的結(jié)果類似.觀察高斯分布的結(jié)果可知,θ的平均值都為0,但各個角度的θ的標(biāo)準(zhǔn)差呈現(xiàn)出一種規(guī)則的變化.當(dāng)θ*為0°時,標(biāo)準(zhǔn)差為0,此時為一個穩(wěn)定的狀態(tài)；當(dāng)θ*遠(yuǎn)離0°時,標(biāo)準(zhǔn)差不斷擴(kuò)大,有一種將角度推向坐標(biāo)軸方向的趨勢.當(dāng)θ*為90°時,標(biāo)準(zhǔn)差為90,由于θ最大值為180°,可知此時θ只有0°和180°兩種狀態(tài),即粒子速度都沿坐標(biāo)軸方向.

指數(shù)分布和高斯分布的實(shí)驗(yàn)結(jié)果稍有區(qū)別.當(dāng)θ為－90°、0°、90°時,標(biāo)準(zhǔn)差都為0,穩(wěn)定地沿著坐標(biāo)軸方向.當(dāng)角度偏離時,標(biāo)準(zhǔn)差增大,有將角度推向坐標(biāo)軸方向的趨勢.

圖5 實(shí)現(xiàn)II中ξ取不同分布時θ的平均值和方差分布Fig.5 Expectation and deviation ofθin BBPSO II under different distribution ofξ

實(shí)現(xiàn)II的坐標(biāo)軸偏向現(xiàn)象本質(zhì)上是由采用的隨機(jī)分布導(dǎo)致的,各個分布的表現(xiàn)略有不同,但都導(dǎo)致同樣的偏向現(xiàn)象.

對于實(shí)現(xiàn)I,各個方向的ξ相同,即

圖6 實(shí)現(xiàn)I中取高斯分布時θ的平均值和方差分布Fig.6 Expectation and deviation ofθin BBPSO I

用高斯分布形式的實(shí)現(xiàn)I重復(fù)試驗(yàn)4,可得相應(yīng)的結(jié)果如圖6所示.與實(shí)現(xiàn)II不同,此時θ隨θ*均勻變化,方差恒為0.這進(jìn)一步說明實(shí)現(xiàn)I是各項同性的.

上述說明了BBPSO實(shí)現(xiàn)II中若采用上述4種分布,都將導(dǎo)致粒子傾向于沿著坐標(biāo)軸運(yùn)動.GBBPSO采用的是高斯分布,QPSO采用的是指數(shù)分布,LBBPSO中的Levy分布實(shí)際上是高斯分布和柯西分布的混合,因此這3種算法都是各向異性的,且有坐標(biāo)軸偏向現(xiàn)象.注意到論證過程中未使用駐態(tài)假設(shè),此外與目標(biāo)函數(shù)、算法參數(shù)設(shè)置都無關(guān),因此坐標(biāo)軸偏向是實(shí)現(xiàn)II導(dǎo)致的BBPSO的本質(zhì)特點(diǎn).

4 求解性能分析

由于2種實(shí)現(xiàn)具有不同的粒子運(yùn)動特點(diǎn),這必然導(dǎo)致不同的優(yōu)化特性.本節(jié)分析2種實(shí)現(xiàn)的不同求解性能.

對于實(shí)現(xiàn)I,由于粒子易沿著直線尋解,在迭代早期將更快速地收斂.隨著迭代的進(jìn)行,對多峰函數(shù)的求解非常容易陷入局部最優(yōu),對梯度變化不明顯的單峰函數(shù)則容易求解收斂于并非全局最優(yōu)解的某一點(diǎn).只有對梯度明顯的單峰函數(shù)才能獲得較好的優(yōu)化性能.

對于實(shí)現(xiàn)II,粒子多樣性增強(qiáng),因而總體求解性能較好.由于各向異性的特點(diǎn),對同一函數(shù)在某些旋轉(zhuǎn)角度下優(yōu)化性能較差.由坐標(biāo)軸偏向現(xiàn)象可知,若“峰”的形狀不平行于坐標(biāo)軸,則將導(dǎo)致求解困難；當(dāng)峰形狀平行于坐標(biāo)軸時,求解將非常高效.

采用2組實(shí)驗(yàn)來驗(yàn)證上述分析.優(yōu)化對象為畸變的2維Sphere（F1）和Rastrigin（F2）函數(shù)、30維Rosenbrock（F3）和Rastrigin（F4）函數(shù),最小值都為0,初始化和求解范圍統(tǒng)一設(shè)置為［－100,100］.

實(shí)驗(yàn)5 分別選用GBBPSO的I型和II型實(shí)現(xiàn),對函數(shù)F1和F2在各個旋轉(zhuǎn)角度下進(jìn)行優(yōu)化.設(shè)置粒子數(shù)為40,迭代次數(shù)為500.在每個旋轉(zhuǎn)角度下,計算重復(fù)10次,記錄最優(yōu)目標(biāo)函數(shù)值的平均值,結(jié)果如圖7所示.

圖7中,ln f為目標(biāo)函數(shù)值的自然底數(shù)對數(shù),由于計算精度表達(dá)限制,當(dāng)函數(shù)值為0時,縱坐標(biāo)記為－300.可見,實(shí)現(xiàn)II在不同旋轉(zhuǎn)角度下性能差別巨大,當(dāng)旋轉(zhuǎn)角度在0°、90°和180°附近時效果最好.實(shí)現(xiàn)I則保持穩(wěn)定的求解性能,對單峰函數(shù)F1的任意旋轉(zhuǎn)角度能都找到最優(yōu)解,但是對多峰函數(shù)F2的表現(xiàn)遠(yuǎn)不如實(shí)現(xiàn)II.

實(shí)驗(yàn)6 分別以I型和II型GBBPSO求解F3和F4,粒子數(shù)為20,迭代200次,結(jié)果如圖8、9所示.圖中,ni為迭代次數(shù).

I型實(shí)現(xiàn)在最初的迭代中性能遠(yuǎn)遠(yuǎn)優(yōu)于II型,但是求解過程容易塌陷,過早收斂.II型實(shí)現(xiàn)則保持穩(wěn)定良好的求解勢頭,在長期的迭代中性能遠(yuǎn)優(yōu)于I型,這進(jìn)一步驗(yàn)證了分析結(jié)果.

圖7 2種不同實(shí)現(xiàn)在函數(shù)旋轉(zhuǎn)時的性能區(qū)別Fig.7 Performance comparisons on rotated functions

圖8 2種不同實(shí)現(xiàn)在Rosenbrock函數(shù)上的對比Fig.8 Performance comparisons on Rosenbrock function

圖9 2種不同實(shí)現(xiàn)在Rastrigin函數(shù)上的對比Fig.9 Performance comparisons on Rastrigin function

5 結(jié) 語

本文首先提出了骨干粒子群算法的一般模型.該模型包含1個控制參數(shù)α以及4個核心因素：鄰域選擇、進(jìn)化中心位置、離散控制方式以及隨機(jī)分布的類型.采用該模型分析算法的2種不同實(shí)現(xiàn),可得以下結(jié)論.

（1）I型實(shí)現(xiàn)是各項同性的,但是由于各個維度使用同一個隨機(jī)變量,導(dǎo)致粒子自由度降低,粒子多樣性差.對于GBBPSO和QPSO這2種基本形式來說,在駐態(tài)時,粒子將沿著（或趨向于沿著）一條直線運(yùn)動；當(dāng)群體進(jìn)化到另一個駐態(tài)時,粒子只是切換一條直線尋解.

（2）II型實(shí)現(xiàn)粒子多樣性較好,但是對于目前使用的4種主流隨機(jī)分布（高斯、柯西、指數(shù)及均勻分布）,粒子都有趨向于沿著坐標(biāo)軸尋解的趨勢.

根據(jù)沒有免費(fèi)午餐理論［18］可知,不可能找到對所有優(yōu)化函數(shù)都能取得最優(yōu)結(jié)果的隨機(jī)算法.每種算法都具有特定的優(yōu)點(diǎn)和缺點(diǎn),在應(yīng)用中應(yīng)該根據(jù)優(yōu)化問題的特性來選擇合適的算法.本文工作的目標(biāo)是討論BBPSO算法的特點(diǎn),分析2種實(shí)現(xiàn)各自擅長的求解問題.在應(yīng)用中,若求解目標(biāo)是簡單單峰函數(shù),則可用實(shí)現(xiàn)I求解；若不是,則應(yīng)該用實(shí)現(xiàn)II求解.若了解函數(shù)的特征,則可以考慮將坐標(biāo)系旋轉(zhuǎn)到合適的角度再進(jìn)行求解.

［1］KENNEDY J.Bare bones particle swarms［C］//Proceedings of the Swarm Intelligence Symposium.Indiana：IEEE,2003：80- 87.

［2］SUN J,XU W B,FENG B.A global search strategy of quantum-behaved particle swarm optimization［C］//Conference on Cybernetics and Intelligent Systems.Singapore：IEEE,2004：111- 116.

［3］SUN J,FANG W,WU X,et al.Quantum-behaved particle swarm optimization：analysis of individual particle behavior and parameter selection［J］.Evolutionary Computation,2012,20（3）：349- 393.

［4］FANG W,SUN J,DING Y,et al.A review of quantum-behaved particle swarm optimization［J］.IETE Technical Review,2010,27（4）：336- 348.

［5］ZHANG H,FERNáNDEZ-VARGAS J A,RANGAIAH G P,et al.Evaluation of integrated differential evolution and unified bare-bones particle swarm optimization for phase equilibrium and stability problems［J］.Fluid Phase Equilibria,2011,310（1）：129- 141.

［6］YAO J,HAN D.Improved barebones particle swarm optimization with neighborhood search and its application on ship design［J］.Mathematical Problems in Engineering,2013,2013（1）：1- 13.

［7］RICHER T J,BLACKWELL T.The Lévy particle swarm［C］//IEEE Congress on Evolutionary Computation.Vancouver：IEEE,2006：808- 815.

［8］AL-RIFAIE M M,BLACKWELL T.Bare bones particle swarms with jumps［C］//Algorithmic Number Theory Symposium.Brussels：Springer,2012：49- 60.

［9］BLACKWELL T.A study of collapse in bare bones particle swarm optimization［J］.IEEE Transactions on Evolutionary Computation,2012,16（3）：354- 372.

［10］HSIEH H,LEE T.A modified algorithm of bare bones particle swarm optimization［J］.International Journal of Computer Science Issues,2010,7（6）：12- 17.

［11］LI Y,XIANG R,JIAO L,et al.An improved cooperative quantum-behaved particle swarm optimization［J］.Soft Computing,2012,16（6）：1061- 1069.

［12］ZHANG Y,GONG D,SUN X,et al.Adaptive barebones particle swarm optimization algorithm and its convergence analysis［J］.Soft Computing,2013, 18（7）：1- 16.

［13］ZHANG Y,GONG D,GENG N,et al.Hybrid barebones PSO for dynamic economic dispatch with valvepoint effects［J］.Applied Soft Computing,2014, 5（18）：248- 260.

［14］史麗萍,王攀攀,胡泳軍,等.基于骨干微粒群算法和支持向量機(jī)的電機(jī)轉(zhuǎn)子斷條故障診斷［J］.電工技術(shù)學(xué)報,2014,29（1）：147- 155.

SHI Li-ping,WANG Pan-pan,HU Yong-jun,et al.Broken rotor bar fault diagnosis of induction motors based on bare-bone particle swarm optimization［J］.Transactions of China Electricotechnical Society,2014, 29（1）：147- 155.

［15］CAMPOS M,KROHLING R A.Hierarchical bare bones particle swarm for solving constrained optimization problems［C］//IEEE Congress on Evolutionary Computation.Cancun：IEEE,2013：805- 812.

［16］CHANG Y,CHUEH C,XU Y,et al.Bare bones particle swarm optimization with considering more local best particles［C］//International Symposium on Instrumentation and Measurement,Sensor Network and Automation.Toronto：IEEE,2013：1105- 1108.

［17］SPEARS W M,GREEN D T,SPEARS D F.Biases in particle swarm optimization［J］.International Journal of Swarm Intelligence Research,2010,1（2）：34- 57.

［18］WOLPERT D H,MACREADY W G.No free lunch theorems for optimization［J］.IEEE Transactions on Evolutionary Computation,1997,1（1）：67- 82.

Different implementations of bare bones particle swarm optimization

ZHANG Zhen,PAN Zai-ping,PAN Xiao-hong
（Faculty of Engineering,Zhejiang University,Hangzhou 310027,China）

A general bare bones particle swarm optimization（BBPSO）form was presented,which consists of four key elements.In the implementation of BBPSO,whether the different dimensions of a particle use the same random variable or not conduct to two different algorithms.Denote the former as BBPSO-I,and the latter as BBPSO-II.Experimental results indicate that BBPSO-I is a rotational invariant algorithm with poor swarm diversity,while BBPSO-II is rotational variant with better swarm diversity and general performance.The using of Gaussian,Cauchy,Exponential or Uniform distribution makes particles of BBPSO-II tend to move along the axes.These features were clarified by theoretical analysis.Some advice on the application of BBPSO was given.BBPSO-I is suitable for unimodal functions with obvious gradient descent,while BBPSO-II obtains generally better performance,especially on optimizing functions with peaks along axes.

bare bones particle swarm optimization（BBPSO）；quantum particle swarm optimization（QPSO）；swarm diversity；rotational variant algorithm

10.3785／j.issn.1008-973X.2015.07.021

TP 301

A

1008- 973X（2015）07- 1350- 08

2014- 04- 24. 浙江大學(xué)學(xué)報(工學(xué)版)網(wǎng)址：www.journals.zju.edu.cn／eng

張震（1986－）,男,博士,從事算法分析、變壓器設(shè)計的研究.ORCID：0000-0002-6437-7195.E-mail：colabh＠hotmail.com

潘再平,男,教授.E-mail：panzaiping＠zju.edu.cn