基于鄰域極值數(shù)的協(xié)同粒子群優(yōu)化算法

曾毅，朱旭生，廖國(guó)勇

（華東交通大學(xué)理學(xué)院，江西南昌330013）

基于鄰域極值數(shù)的協(xié)同粒子群優(yōu)化算法

曾毅，朱旭生，廖國(guó)勇

（華東交通大學(xué)理學(xué)院，江西南昌330013）

提出了一種基于鄰域極值數(shù)的協(xié)同粒子群優(yōu)化算法。該算法將種群分為若干個(gè)獨(dú)立進(jìn)化的子種群。根據(jù)鄰域極值數(shù)確定各子種群的生存狀態(tài)。根據(jù)子種群的生存狀態(tài)對(duì)子種群實(shí)施相應(yīng)的控制操作，提高子種群的搜索能力，實(shí)現(xiàn)子種群之間的信息共享，共同進(jìn)化。測(cè)試結(jié)果表明基于鄰域極值數(shù)的協(xié)同粒子群優(yōu)化算法是一種高效穩(wěn)健的全局優(yōu)化算法。

粒子群優(yōu)化算法；協(xié)同進(jìn)化；鄰域極值數(shù)

粒子群優(yōu)化（particle swarm optimization，PSO）算法是由Kennedy和Eberhart等人于1995年提出的一種基于群體智能的演化計(jì)算技術(shù)［1］。算法基本思想源于對(duì)鳥(niǎo)群撲食行為的研究，是對(duì)簡(jiǎn)單社會(huì)系統(tǒng)的模擬。由于PSO算法具有很好的生物社會(huì)背景而易理解、結(jié)構(gòu)簡(jiǎn)單、參數(shù)少而易實(shí)現(xiàn)，算法提出后受到了學(xué)者的重視和研究。目前，已經(jīng)廣泛應(yīng)用于許多領(lǐng)域［2］。

粒子群優(yōu)化算法通過(guò)種群粒子之間的合作與競(jìng)爭(zhēng)實(shí)現(xiàn)對(duì)問(wèn)題最優(yōu)解的搜索，可用于解決大量非線性、不可微和多峰值等優(yōu)化問(wèn)題。但在求解高維復(fù)雜函數(shù)優(yōu)化問(wèn)題時(shí)，進(jìn)化前期收斂速度快，進(jìn)化后期極易陷入局部最優(yōu)解，收斂速度和解的精度也不理想。針對(duì)這一問(wèn)題，文獻(xiàn)［3］提出基于高斯變異的粒子群算法，算法按預(yù)先設(shè)置的概率對(duì)粒子進(jìn)行高斯變異操作，改善了種群的多樣性，有利于變異粒子跳出局部極值點(diǎn)進(jìn)行全局搜索，收斂速度和精度也有一定程度的提高。文獻(xiàn)［4］分析了不同的種群拓?fù)浣Y(jié)構(gòu)對(duì)PSO算法效能的影響，提出了構(gòu)造種群拓?fù)浣Y(jié)構(gòu)的基本原則。文獻(xiàn)［5-6］提出多種群協(xié)同粒子群優(yōu)化算法，測(cè)試結(jié)果表明能提高算法的收斂性。本文提出了一種基于鄰域極值數(shù)的協(xié)同粒子群優(yōu)化算法。測(cè)試結(jié)果表明基于鄰域極值數(shù)的協(xié)同粒子群優(yōu)化算法的有效性。

1 標(biāo)準(zhǔn)粒子群優(yōu)化算法

本文討論如下數(shù)值優(yōu)化問(wèn)題

其中：N為搜索空間的維數(shù)。

標(biāo)準(zhǔn)粒子群優(yōu)化算法將每個(gè)個(gè)體看成N維搜索空間中的一個(gè)沒(méi)有質(zhì)量和體積的粒子，并以一定的速度飛行。飛行速度由個(gè)體的飛行經(jīng)驗(yàn)和群體的飛行經(jīng)驗(yàn)進(jìn)行動(dòng)態(tài)調(diào)整。標(biāo)準(zhǔn)粒子群優(yōu)化算法根據(jù)式（1）

（2）更新粒子速度和位置。

其中：vi(k)為粒子i在第k代的速度；xi(k)為粒子i在第k代的位置；ω為慣性權(quán)重；rand()為分布于[0,1]之間的隨機(jī)數(shù)；c1為認(rèn)知系數(shù)；c2為社會(huì)系數(shù)；pi(k)為粒子i個(gè)體歷史最優(yōu)位置，也稱為個(gè)體極值；pg(k)為群體歷史最優(yōu)位置，也稱為全局極值。為保證算法的穩(wěn)定性，算法定義了一個(gè)最大速度上限vmax，用以限制粒子速度的大小，即

粒子在搜索空間內(nèi)不斷跟蹤個(gè)體極值及全局極值進(jìn)行搜索，直到達(dá)到規(guī)定的迭代次數(shù)或滿足規(guī)定的誤差標(biāo)準(zhǔn)為止。

2 種群的生存狀態(tài)［7］

在一次優(yōu)化搜索中，一個(gè)種群從初始化直至最終成熟的整個(gè)過(guò)程定義為該種群的生命周期。一般來(lái)說(shuō)，在搜索初期，種群的分布最分散，多樣性最好，搜索能力最強(qiáng)；在搜索中期，種群的多樣性和搜索能力會(huì)逐漸降低，但依然會(huì)保持在相對(duì)較高水平；進(jìn)入搜索后期，種群的多樣性和搜索能力會(huì)降低至一個(gè)相對(duì)較低水平，變化速度趨緩。為了能夠準(zhǔn)確地引導(dǎo)種群的尋優(yōu)過(guò)程，根據(jù)種群的搜索特征將種群的生存狀態(tài)劃分為成長(zhǎng)初期、成長(zhǎng)中期和成熟期3個(gè)時(shí)期。為此，給出鄰域空間、鄰域極值和鄰域極值數(shù)的定義，并根據(jù)鄰域極值數(shù)確定種群的生存狀態(tài)。

定義1在第k代種群中，與粒子i歐氏距離最近的num個(gè)粒子的集合稱為粒子i的鄰域空間［8］。

定義2在第k代種群中，粒子i的鄰域空間最優(yōu)粒子的位置，稱為粒子i的第k代的鄰域極值。每個(gè)粒子都有鄰域極值，且不同的粒子的鄰域極值可能相同。

定義3在第k代種群中，若粒子j的位置xj(k)為種群中mj(k)個(gè)粒子的第k代鄰域極值，稱mj(k)為粒子j的鄰域極值數(shù)。記

并稱m(k)為第k代種群的鄰域極值數(shù)。因?yàn)閙(k)的大小反映了種群多樣性和搜索能力，所以可利用m(k)的大小來(lái)確定種群的生存狀態(tài)。

定義4若m(k)＜K1，K1的經(jīng)驗(yàn)取值為，其中n為種群規(guī)模，則認(rèn)為種群的生存狀態(tài)為成長(zhǎng)初期；若K1≤m(k)＜K2，K2的經(jīng)驗(yàn)取值為，則認(rèn)為種群的生存狀態(tài)為成長(zhǎng)中期；若m(k)≥K2，則認(rèn)為種群的生存狀態(tài)為成熟期。

3 控制操作

根據(jù)種群所處的生存狀態(tài)，對(duì)種群實(shí)施相應(yīng)的控制操作，更有利于調(diào)控種群的局部搜索和全局搜索的平衡，進(jìn)而提升算法的性能。

1）當(dāng)種群處于成長(zhǎng)初期時(shí)，為了使種群有較好的多樣性和搜索能力，此時(shí)應(yīng)減少種群最優(yōu)粒子的對(duì)種群粒子的影響，增加鄰域空間最優(yōu)粒子對(duì)種群粒子的影響，防止粒子迅速地向種群最優(yōu)位置聚集，能有效地提高種群局部搜索能力，在一定程度上避免早熟現(xiàn)象的發(fā)生［9］。為此，本文根據(jù)式（5）（6）更新粒子速度和位置

其中：pli(k)為粒子i的歷史最優(yōu)鄰域極值，其余記號(hào)與式（1）（2）中的意義相同。

2）當(dāng)種群處于成長(zhǎng)中期時(shí)，此時(shí)種群所在的搜索區(qū)域還沒(méi)有完全被開(kāi)發(fā)。為進(jìn)一步開(kāi)發(fā)搜索區(qū)域，對(duì)鄰域極值數(shù)大于K1，小于K2的粒子實(shí)施單變量高斯變異操作。

設(shè)第k代的粒子j鄰域極值數(shù)mj(k)滿足：K1≤mj(k)＜K2，且粒子j位置為xj=(xj1,xj2,…xjN)，則可按下述過(guò)程對(duì)粒子j實(shí)施單變量高斯變異操作。

單變量高斯變異操的目的是依次對(duì)粒子j的位置向量xj的每一維分量進(jìn)行擾動(dòng)，以提高當(dāng)前解的精度或找到比當(dāng)前解更優(yōu)的解。

3）當(dāng)種群處于成熟期時(shí)，種群多樣性和搜索能力均已喪失殆盡，此時(shí)種群中的粒子應(yīng)逃逸種群，搜索新的可行區(qū)域。為此若粒子群中的粒子j的鄰域極值數(shù)mj(k)＞K2，則對(duì)粒子j實(shí)施協(xié)同操作（協(xié)同操作將在下一節(jié)介紹），同時(shí)將以粒子j的位置為鄰域極值的粒子初始化，使粒子具有新的動(dòng)量對(duì)搜索空間進(jìn)行新的搜索。

4 基于鄰域極值數(shù)的協(xié)同粒子群優(yōu)化算法及協(xié)同操作

基于鄰域極值數(shù)的協(xié)同粒子群優(yōu)化算法是將整個(gè)種群分為若干個(gè)獨(dú)立進(jìn)化子種群，并通過(guò)協(xié)同操作實(shí)現(xiàn)子種群間的信息交流共享、共同進(jìn)化。協(xié)同操作借助基因庫(kù)平臺(tái)實(shí)現(xiàn)的?；驇?kù)可由每個(gè)子種群的第一代的最優(yōu)粒子構(gòu)成，也可以由各子種群進(jìn)化一定代數(shù)后，每個(gè)種群最優(yōu)粒子構(gòu)成。協(xié)同操作過(guò)程如下。

設(shè)粒子群處于成熟期，粒子j的鄰域極值數(shù)mj(k)＞K2，粒子j位置為xj=(x1,x2,…xN)，從基因庫(kù)中隨機(jī)地選取一個(gè)粒子，不妨選出粒子為t，其位置為yt=(y1,y2,…,yN)。

首先，由粒子j和選取的粒子t生成兩個(gè)新粒子new1,new2，且新粒子new1，new2的位置xnew1,xnew2由式（7）確定

其中：l1,l2為1～N之間的隨機(jī)整數(shù)，且l1＜l2。

當(dāng)min{fitness(xnew1),fitness(xnew2)}＜fitness(xj)時(shí)，粒子j的位置xj用new1,new2中較優(yōu)的粒子的位置替換；否則，粒子j的位置不變。上述操作可連續(xù)實(shí)施若干次，具體次數(shù)可由用戶設(shè)定。

其次，基因庫(kù)更新。為方便敘述基因庫(kù)更新的過(guò)程，先給出粒子相似的定義。

定義5設(shè)粒子j的位置為xj=(x1,x2,…xN)，粒子t的位置為yt=(y1,y2,…,yN)，若位置向量的分量滿足

其中：δ為一個(gè)很小的正數(shù)，則稱粒子j,t相似。

將上一步操作得到的粒子j與基因庫(kù)中的粒子逐一進(jìn)行相似判斷。若滿足下面的條件①或②時(shí)，則對(duì)基因庫(kù)進(jìn)行更新；否則基因庫(kù)不變。

①若粒子j與基因庫(kù)的粒子t相似，且粒子j好于粒子t，則將粒子j替換基因庫(kù)中的粒子t；

②若粒子j與基因庫(kù)中粒子都不相似，且粒子j好于基因庫(kù)中的最差粒子，則用粒子j替換基因庫(kù)中最差的粒子。

基于以上的分析，基于鄰域極值數(shù)的協(xié)同粒子群優(yōu)化算法流程如下：

step1設(shè)定子種群數(shù)量及子種群規(guī)模，設(shè)置算法的最大迭代次數(shù)、優(yōu)化精度；確定各子種群的粒子的初始位置及速度，鄰域極值、全局極值；確定基因庫(kù)，置迭代次數(shù)t:=0；

step2從第一個(gè)子種群開(kāi)始直到最后一個(gè)子種群結(jié)束，各子種群依次完成step2.1、step2.2、step2.3三個(gè)步驟；

step2.1各子種群根據(jù)式（5）（6）對(duì)粒子進(jìn)行速度和位置的更新，并更新粒子的鄰域極值、全局極值；

step2.2對(duì)鄰域極值數(shù)大于K1，小于K2的粒子進(jìn)行單變量高斯變異操作，若變異后的粒子更優(yōu)，則將變異后的粒子替換操作前的粒子，并更新以變異粒子的位置為鄰域極值的粒子的鄰域極值；

step2.3對(duì)鄰域極值數(shù)大于K2的粒子實(shí)施協(xié)同操作，更新基因庫(kù)，并將以該粒子為鄰域極值的粒子初始化；

step3若算法的迭代次數(shù)t小于設(shè)定的次數(shù)，置t:=t+1，轉(zhuǎn)step2；否則，輸出基因庫(kù)中的最好粒子的位置為所求問(wèn)題的解。

5 仿真實(shí)驗(yàn)

5.1 測(cè)試函數(shù)

擬用4個(gè)經(jīng)典的測(cè)試函數(shù)對(duì)算法的性能進(jìn)行測(cè)試研究。測(cè)試函數(shù)如表1所示，其中函數(shù)f1,f2為單峰函數(shù)，函數(shù)f3,f4為多峰函數(shù)，4個(gè)測(cè)試函數(shù)的優(yōu)化精度分別取0.05，100，0.5和100。

表1 測(cè)試函數(shù)Tab.1 Test functions

5.2 測(cè)試結(jié)果和性能分析

采用Matlab7.1實(shí)驗(yàn)平臺(tái)進(jìn)行仿真測(cè)試。算法1為本文提出的算法，算法2為文獻(xiàn)［5］提出的CEPSO2算法。算法1參數(shù)的取值如表2所示。為了使測(cè)試數(shù)據(jù)的公平可信，算法2參數(shù)的取值盡可能與算法1保持一致?？紤]到更新周期R是算法2的很重要的一個(gè)參數(shù)，當(dāng)選取合適時(shí)，可大幅度提高算法2的收斂性。為此，更新周期采用文獻(xiàn)［5］推薦的更新周期：R=30，且每隔一個(gè)更新周期記錄全局最優(yōu)值解。為了便于比較，算法1也每隔一個(gè)更新周期記錄全局最優(yōu)解。測(cè)試結(jié)果如表3所示，表中的MEAN、BEST、WORST、SD分別表示測(cè)試函數(shù)獨(dú)立運(yùn)行30次的實(shí)驗(yàn)結(jié)果的平均值、最好值、最差值和方差，SR表示達(dá)到優(yōu)化精度的實(shí)驗(yàn)次數(shù)占總實(shí)驗(yàn)次數(shù)的比例。圖1為各測(cè)試函數(shù)的收斂曲線。

表2 實(shí)驗(yàn)參數(shù)Tab.2 Parameter setting

表3 2種算法仿真實(shí)驗(yàn)結(jié)果Tab.3 Two kinds of algorithm simulation results

圖1 測(cè)試函數(shù)收斂曲線Fig.1 Convergence curves of test function

從表3可以清楚地看出，算法1不僅實(shí)驗(yàn)結(jié)果的平均值好于算法2的，而且實(shí)驗(yàn)結(jié)果方差遠(yuǎn)比算法2的小，這表明算法1有較好魯棒性。從圖1的收斂曲線可明顯地看出算法1有較快的收斂速度和較好的求解質(zhì)量。另外，從兩個(gè)多峰函數(shù)的收斂曲線看到，當(dāng)算法2停滯不前進(jìn)展緩慢時(shí)，而算法1卻能持續(xù)進(jìn)化獲得滿意解，這表明算法1不僅全局收斂速度快，而且收斂到全局最優(yōu)解。

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

提出了基于鄰域極值數(shù)的協(xié)同粒子群優(yōu)化算法。該算法與同類的多種群協(xié)同粒子群優(yōu)化算法有2個(gè)不同點(diǎn)：

1）利用種群鄰域極值數(shù)確定種群的生存狀態(tài)，根據(jù)子種群的生存狀態(tài)對(duì)子種群實(shí)施相應(yīng)的控制操作來(lái)提高子種群的搜索能力。這與以往利用種群多樣性或搜索能力來(lái)判定種群的生存狀態(tài)不同，是一種新的思路。

2）采用協(xié)同操作實(shí)現(xiàn)多種群的信息共享、共同進(jìn)化。這與“孤島模型”、“鄰域模型”直接將搜索到的最優(yōu)粒子“遷移”到子種群的方式不同。這保證了各子種群的獨(dú)立進(jìn)化，同時(shí)一定程度上避免了算法早熟收斂。

基本測(cè)試函數(shù)的測(cè)試結(jié)果表明基于鄰域極值數(shù)的協(xié)同粒子群優(yōu)化算法是一種高效穩(wěn)健的全局優(yōu)化算法，但在測(cè)試過(guò)程中發(fā)現(xiàn)參數(shù)K1,K2選擇、單變量高斯變異次數(shù)和協(xié)同操作的次數(shù)都會(huì)對(duì)算法的性能產(chǎn)生一定的影響。

[1]KENNEDY J,EBERHART R.Particle swarm optimization[C]//Proc of the IEEE Int Conf Neural Networks,Piscataway,NJ,USA, 1995:1942-1948.

[2]倪慶劍,邢漢承,張志政.粒子群優(yōu)化算法研究進(jìn)展[J].模式識(shí)別與人工智能,2007,20(3):349-357.

[3]HIGASHI N,IBA H.Particle swarm optimization with gaussianmutation[C]//Proc of IEEE Swarm Intelligence Symposium(SIS), 2003:71-79.

[4]KUMAR J,ALMAGEED W A,DOERMANN D.Handwritten arabic text line segmentation using affinity propagation[C]//Proc.of the 9th IAPR International Workshop on Document Analysis Systems,New York,USA,2010:135-142.

[5]王元元,曾建潮,譚瑛.多種群協(xié)同進(jìn)化的微粒群算法[J].計(jì)算機(jī)工程與設(shè)計(jì)2007,28(15):3661-3664.

[6]徐冰純,葛洪偉,王燕燕.基于多種群多模型協(xié)同進(jìn)化的粒子群優(yōu)化算法[J].計(jì)算機(jī)工程2013(39):200-208.

[7]崔志華,曾建潮.微粒群優(yōu)化算法[M].北京:科學(xué)出版社,2011:150-151.

[8]曾毅,朱旭生,廖國(guó)勇.一種基于鄰域空間的混合粒子群優(yōu)化算法[J].華東交通大學(xué)學(xué)報(bào),2013,30(3):44-49.

[9]KENNEDY J,MENDES R.Population structure and performance[C]//Cec'02:Proceedings of the 2002 Congress on Evolutionary Computation,IEEE,Piscataway,NJ,USA,2002:1671-1676.

Cooperative Particle Swarm Optimization Based on Neighborhood Extremum Number

Zeng Yi,Zhu Xusheng,Liao Guoyong
(School of Basic Sciences,East China Jiaotong University,Nanchang 330013,China)

A cooperative particle swarm optimization based on the neighborhood extremum number is proposed.In this algorithm,the whole population is divided into several sub-populations evolving independently.The survival state of each sub-population is determined in terms of the neighborhood extremum number.Based on the survival state of each sub-population,corresponding control operation is implemented so as to improve the search ability of each sub-population and realize information sharing so that the sub-populations coevolve.The experimental re?sults show that the cooperative particle swarm optimization based on the neighborhood extremum number is an ef?fective and steady global optimization algorithm.

PSO;cooperative coevolution;the neighborhood extremum number

TP18

A

2014-04-07

國(guó)家自然科學(xué)基金項(xiàng)目（11161021）；華東交通大學(xué)校立科研項(xiàng)目（09111114）

曾毅（1965—），男，副教授，研究方向?yàn)橹悄苡?jì)算。

1005-0523（2014）04-0071-06