何 莉，王 淼，李 博

(河南工程學(xué)院 計算機(jī)學(xué)院, 鄭州 451191)

面向單目標(biāo)優(yōu)化的集成粒子群算法

何 莉，王 淼，李 博

(河南工程學(xué)院 計算機(jī)學(xué)院, 鄭州 451191)

串行粒子群算法廣泛應(yīng)用于多個領(lǐng)域，出現(xiàn)了多個變種，但解決不同種類的優(yōu)化問題時性能有差異。為提高串行粒子群算法對各種優(yōu)化問題的適應(yīng)能力，提出一種集成粒子群優(yōu)化算法。新算法使用Matlab的單程序多數(shù)據(jù)并行結(jié)構(gòu)發(fā)揮單節(jié)點多核計算能力，通過設(shè)置外部檔案分享不同粒子群的全局最佳位置，促進(jìn)不同串行粒子群算法之間的信息交流，綜合利用不同串行粒子群算法在解決不同類型優(yōu)化問題的優(yōu)勢。在廣泛使用的測試函數(shù)集上開展仿真實驗，結(jié)果驗證了新算法的有效性，與多個知名的串行粒子群算法相比，新算法在尋優(yōu)性能上優(yōu)勢明顯。新算法不僅能夠提高粒子群算法的適應(yīng)能力，而且，所采用的算法框架也適應(yīng)于其他群智能算法，改善了算法的性能。

單程序多數(shù)據(jù)；集成粒子群算法；全局?jǐn)?shù)值優(yōu)化；粒子群優(yōu)化；并行計算

0 引 言

現(xiàn)實世界中工程和科學(xué)問題很多可以抽象為單目標(biāo)優(yōu)化問題。如果目標(biāo)函數(shù)和約束條件是決策變量的線性組合，可以用經(jīng)典的線性規(guī)劃、動態(tài)規(guī)劃等方法解決。然而，現(xiàn)實世界的優(yōu)化問題經(jīng)常是非線性的，維數(shù)比較高，用經(jīng)典方法并不能取得較好的效果。啟發(fā)式算法借鑒自然進(jìn)化思想，在解決復(fù)雜優(yōu)化問題時取得顯著成效，也受到學(xué)術(shù)界高度關(guān)注和追蹤[1]。典型的啟發(fā)式算法包括粒子群算法[2]、蟻群算法[3]、人工蜂群算法[4]、螢火蟲算法[5]等。

粒子群算法(particle swarm optimizer，PSO)出現(xiàn)于1995年[2]，受到鳥類覓食群體行為的啟發(fā)。粒子群算法包括多個粒子，每個粒子對應(yīng)優(yōu)化問題的一個解。粒子的位置初始化后，其移動軌跡受到粒子自身最佳位置以及鄰域中粒子最佳位置的影響，粒子的行為決定于自身的慣性和社會行為。PSO算法最早應(yīng)用于神經(jīng)網(wǎng)絡(luò)的參數(shù)優(yōu)化。由于PSO算法的簡潔性和方便處理高維優(yōu)化問題的能力，PSO算法已廣泛應(yīng)用于多個領(lǐng)域[6-8]。

現(xiàn)有多數(shù)PSO算法的代碼以串行方式執(zhí)行，稱這類PSO為串行粒子群算法(serial particle Swarm optimizer，SPSO)。SPSO在處理優(yōu)化問題中取得顯著成績，但依然存在多個問題需要解決，比如迭代尋優(yōu)的耗時問題，大數(shù)量級數(shù)據(jù)處理問題，自身行為與社會行為的主導(dǎo)性問題，探索與挖掘矛盾的處理?，F(xiàn)已提出多種并行與分布式PSO[9-11]用于解決前2個問題。粒子的行為軌跡受到自身歷史最佳位置和鄰域粒子的影響，如何更有效地引導(dǎo)粒子下一步動作值得進(jìn)一步研究。粒子的通信拓?fù)浔徽J(rèn)為是刻畫粒子與鄰域關(guān)系的有效方法，被廣泛使用的拓?fù)浣Y(jié)構(gòu)有全連接[12]和環(huán)型拓?fù)浣Y(jié)構(gòu)[13]。文獻(xiàn)[14-15]認(rèn)為粒子的行為受到其鄰域中所有粒子的影響，粒子群進(jìn)行探索的目的是跳出局部最優(yōu)解，在更大的區(qū)域?qū)ふ胰肿顑?yōu)解，粒子群進(jìn)行挖掘的目的是對局部區(qū)域進(jìn)行細(xì)粒度搜索更優(yōu)解。反向?qū)W習(xí)機(jī)制被引入提高粒子的學(xué)習(xí)能力[16-17]，核矩陣被用于改善粒子的多樣性[18]。多種參數(shù)約束的SPSO算法已提出用于折衷探索與挖掘的關(guān)系[12, 19-22]，每種SPSO算法在解決特定優(yōu)化問題時都有較好的表現(xiàn)。

為融合各種SPSO算法在解決不同類型問題的優(yōu)勢，提出一種集成粒子群算法(ensemble particle swarm optimizer, EPSO)。EPSO采用Matlab單程序多數(shù)據(jù)(single program multiple data，SPMD)并行結(jié)構(gòu)，利用單節(jié)點多核的并發(fā)處理能力，用多個內(nèi)核分別運(yùn)行全局粒子群算法(global PSO，GPSO)[12]，本地粒子群算法(local PSO，LPSO)[13]，裸骨粒子群算法(bare bones particle swarms，BBPSO)[23]和全信息粒子群算法(fully informed particle swarm，F(xiàn)IPS)[14-15]，然后，通過信息共享機(jī)制促進(jìn)粒子群全局最佳位置的共享，提高PSO算法的準(zhǔn)確性。

EPSO算法提出的主要思想：通過并行化方式不僅實現(xiàn)不同粒子群算法的協(xié)同進(jìn)化，而且，還融合了各自算法的優(yōu)勢，是提高粒子群算法性能的新方法。

1 串行粒子群算法

一個粒子群由S個粒子構(gòu)成。每個粒子用序號表示，第k個粒子用粒子k表示。粒子k的狀態(tài)由位置向量Xk和速度向量Vk來表示。在D維空間中，Xk=[xk1,xk2,…,xkD]，Vk=[vk1,vk2,…,vkD]。粒子k的個體最佳位置和鄰域最佳位置分別用Pk和Lk表示，即Pk=[pk1,pk2,…,pkD]，Lk=[lk1,lk2,…,lkD]。粒子群全局最佳位置用G表示，即G=[g1,g2,…,gD]。對于最小化問題，最佳位置意味著在指定的范圍該位置的適應(yīng)度最低。粒子k的鄰域Nk由粒子群的通信拓?fù)錄Q定，對于環(huán)型通信拓?fù)浣Y(jié)構(gòu)，粒子k的鄰域包括粒子k-1，k和k+1，即Nk={k-1,k,k+1}。

LPSO[13]中Xk和Vk在隨機(jī)初始化后，分別按照(1)和(2)式進(jìn)行更新。

(1)

(2)

(1)—(2)式中：ω表示慣性系數(shù)，通常被設(shè)置為隨迭代次數(shù)逐漸減少的值，比如文獻(xiàn)[12]建議ω由0.9降低到0.4；c1和c2分別表示界定認(rèn)知部分與社會部分貢獻(xiàn)的加速系數(shù)，在不同SPSO算法中，c1和c2取值有所不同，比如文獻(xiàn)[12-13]中，c1和c2被設(shè)置為2.0；r1d和r2d是[0, 1]上的隨機(jī)數(shù)，服從均勻分布，為粒子的速度更新帶來一定的隨機(jī)性。

GPSO[12]中粒子的鄰域包含粒子群中所有粒子，粒子的位置根據(jù)(2)式進(jìn)行更新，但是粒子的速度根據(jù)(3)式進(jìn)行更新。因此，GPSO可以看成是LPSO的一個特例。

(3)

為解決SPSO在求解多模優(yōu)化問題容易陷入局部最優(yōu)而導(dǎo)致過早收斂的問題，算法CLPSO[24]提出了一種深度學(xué)習(xí)策略，即粒子每維速度的更新受到其他所有粒子個體歷史最佳位置的影響，粒子速度的更新公式為

(4)

(4)式中，f(k)表示引導(dǎo)粒子k在第d維運(yùn)動的粒子的序號。

FIPS[14-15]認(rèn)為粒子位置的變化受到鄰域所有粒子歷史最佳位置的影響，其速度更新采用的公式為

(5)

(5)式中：rd表示區(qū)間(0,φ)上的隨機(jī)數(shù)，服從均勻分布，參數(shù)φ通常被設(shè)置為4.1；此時，χ≈0.729 8[15]。FIPS[15]可以看成是文獻(xiàn)[19]提出的PSO算法的通用版。

標(biāo)準(zhǔn)的粒子群算法存在多個參數(shù)，參數(shù)的設(shè)置會影響到算法執(zhí)行的效果。算法BBPSO[23]去掉了速度更新公式，粒子位置的更新公式為

(6)

(6)式中：μkd←0.5(pkd+lkd)；σkd←|pkd-lkd|；N(μkd,σkd)是以μkd為均值和σkd為方差的高斯分布的一個值。BBPSO以其簡潔性受到關(guān)注，在此基礎(chǔ)上又發(fā)展了文獻(xiàn)[25]提出的算法。

粒子群的變種還有很多，文獻(xiàn)[6]綜述了粒子群算法的各個變種以及應(yīng)用。不同粒子群算法各具有優(yōu)勢。GPSO[12]和LPSO[13]運(yùn)行速度比較快，在單模優(yōu)化問題上有優(yōu)勢，而FIPS[14-15]和BBPSO[23]在解決多模優(yōu)化問題時取得良好的結(jié)果。

2 集成粒子群算法(EPSO)

每種SPSO算法在解決某一類優(yōu)化問題有優(yōu)勢，比如GPSO[12]適合解決單模單目標(biāo)優(yōu)化問題；綜合學(xué)習(xí)粒子群算法(comprehensive learning，CLPSO)[24]在解決多模單目標(biāo)優(yōu)化問題時比其他PSO算法表現(xiàn)更好。沒有免費(fèi)午餐(no free lunch，NFL)理論[14]表明，沒有一種算法在評測所有可能的優(yōu)化函數(shù)時都優(yōu)于其他算法。為了提高SPSO算法對不同優(yōu)化問題的適應(yīng)能力，有必要綜合各種算法的優(yōu)勢。

2.1 Matlab SPMD并行結(jié)構(gòu)

在單核CPU時代，多線程技術(shù)用于減少CPU的等待時間，提高CPU的利用效率。由于CPU同一時刻只能執(zhí)行一個線程，單核多線程并不是真正意義上的并行計算。進(jìn)入多核時代，多個線程可以分配給多個內(nèi)核同時運(yùn)算，實現(xiàn)并行計算，此時，多線程編程也稱為多核編程。

Matlab提供2種方式利用多核計算能力：①內(nèi)置多線程，快速傅立葉變換(fast Fourier transform，F(xiàn)FT)、矩陣特征值和特征向量函數(shù)eig、奇異值分解函數(shù)svd、排序函數(shù)sort等線性代數(shù)和數(shù)值函數(shù)在Matlab上執(zhí)行時默認(rèn)啟用多線程，圖像處理工具箱中許多函數(shù)也默認(rèn)啟用多線程；②基于Matlab工作單元(worker)的并行計算，Matlab啟用多個工作單元實現(xiàn)應(yīng)用的并行執(zhí)行。②相對于①的優(yōu)勢是對并行計算有更多的控制，可以將并行應(yīng)用由單個節(jié)點擴(kuò)展到集群。②通常采用2種編程結(jié)構(gòu)：parfor和SPMD[26]。parfor主要實現(xiàn)for循環(huán)的并行運(yùn)算，SPMD并行結(jié)構(gòu)比parfor并行結(jié)構(gòu)更靈活，但也引入更加復(fù)雜的數(shù)據(jù)類型和操作方法。

Matlab SPMD并行結(jié)構(gòu)如圖1所示。客戶端(client)完成所有的用戶交互操作，并提交任務(wù)給調(diào)度器(scheduler)；調(diào)度器負(fù)責(zé)Matlab工作單元的管理，并將任務(wù)分解為多個作業(yè)，每個作業(yè)由調(diào)度器分配給工作單元執(zhí)行；工作單元執(zhí)行作業(yè)，并將執(zhí)行結(jié)果返回。客戶端、調(diào)度器、工作單元既可以運(yùn)行在單個節(jié)點，也可以運(yùn)行在多個節(jié)點。本文側(cè)重于單節(jié)點多核計算。

圖1 Matlab SPMD并行結(jié)構(gòu)Fig.1 Matlab SPMD parallel structure

2.2 并行策略與信息共享

在異構(gòu)分布式計算環(huán)境時，計算效率的提升除了與節(jié)點自身計算資源相關(guān)外，也受到節(jié)點之間通信資源的影響。在單節(jié)點多核并行計算環(huán)境中，多個內(nèi)核之間通信速率通常遠(yuǎn)高于節(jié)點之間通信速率，所以多核計算效率的提升主要與自身的計算資源關(guān)系密切。

EPSO算法中，客戶端主要負(fù)責(zé)參數(shù)初始化、并行任務(wù)的啟動、結(jié)果匯總等工作。一個工作單元對應(yīng)一個內(nèi)核，執(zhí)行單個SPSO算法，維護(hù)一個粒子群的狀態(tài)信息，算法開始后每隔一定迭代次數(shù)，通過工作單元間通信機(jī)制將各個SPSO的最佳位置存放在檔案中。各個SPSO的粒子群構(gòu)成一個粒子群集合。

粒子群信息的交流已被證明能夠有效提高粒子的多樣性和增強(qiáng)避免陷入局部最優(yōu)解的能力[27-28]。在EPSO算法中，每個工作單元設(shè)置并維護(hù)一個檔案，用于存放并行執(zhí)行階段各個SPSO算法的粒子群全局最佳位置，適應(yīng)度最小(對于最小優(yōu)化問題)的粒子群全局最佳位置將作為粒子群集合的最佳位置best_G。因為進(jìn)入并發(fā)執(zhí)行階段，不同的SPSO算法執(zhí)行的速度有快有慢，所以各個SPSO經(jīng)過相同的迭代次數(shù)，計算的best_G可能不一樣。這體現(xiàn)了EPSO同一個粒子群內(nèi)同步通信而不同粒子群間異步通信的特點。通過信息共享，實現(xiàn)最佳位置在多個粒子群中共享。通過檔案傳遞粒子群的最佳位置的速度高于文獻(xiàn)[29]提到島嶼模型(island model)。在島嶼模型中，多個粒子群按序排列，逐個向下一個粒子群傳遞最佳位置。

EPSO算法采用隨機(jī)替換策略實現(xiàn)SPSO的粒子群與粒子群集合的最佳位置的交流。SPSO計算best_G后，產(chǎn)生一個服從均勻分布的序號，然后將序號對應(yīng)的粒子的個體最佳位置替換為best_G，使得粒子群受到best_G的影響，提高找到更優(yōu)解的可能性。這種替換策略簡單有效，不會改變SPSO原有的粒子速度和位置的更新公式。

2.3 EPSO的實現(xiàn)流程

目前，楚雄市漢語公示語英譯的數(shù)量遠(yuǎn)遠(yuǎn)不夠，很多對外交流頻繁的地方還缺少公示語的翻譯，例如公共汽車站，火車站售票窗口，彝族文化活動場所，市區(qū)主干道的景區(qū)標(biāo)識牌，還有一些功能性建筑物都缺少規(guī)范的公示語翻譯，城市的對外文明形象也大大削弱了。

EPSO的實現(xiàn)流程如圖2所示，程序分為3個階段進(jìn)行。

圖2 EPSO算法流程Fig.2 Flow chart of EPSO algorithm

1)程序采用串行執(zhí)行方式，即由系統(tǒng)選擇一個內(nèi)核順序執(zhí)行指令，客戶端完成粒子群粒子數(shù)量，加權(quán)系數(shù)ω，控制系數(shù)c1，c2，迭代次數(shù)等算法參數(shù)的初始化，以及啟動4個內(nèi)核作為并行工作單元。

2)程序采用并行執(zhí)行方式。4個并行工作單元分別執(zhí)行SPSO算法GPSO[12]，LPSO[13]，BBPSO[23]和FIPS[15]，對應(yīng)的粒子群全局最佳位置分別用GPSO_G，LPSO_G，BBPSO_G，F(xiàn)IPS_G表示。每種SPSO算法每經(jīng)過step次迭代，通過工作單元間的通信機(jī)制收集4個粒子群的全局最佳位置，并計算best_G，然后，從自身粒子群中隨機(jī)選取一個粒子，將其個體最佳位置替換為best_G。

進(jìn)入并行執(zhí)行階段后，Matlab調(diào)度器負(fù)責(zé)工作單元的管理和作業(yè)的分配。

3)程序采用串行執(zhí)行方式。當(dāng)所有作業(yè)完成后，進(jìn)入串行執(zhí)行階段?？蛻舳耸占鱾€算法的最佳位置，并計算best_G，作為優(yōu)化問題的最終解。

3 實驗與討論

3.1 評測函數(shù)

實驗采用CES’15[30]評測集。評測集共有15個單目標(biāo)最小優(yōu)化函數(shù)，分為4種類型，其中，F(xiàn)1(x)和F2(x)是單模函數(shù)，F(xiàn)3(x)～F5(x)為簡單多模函數(shù)，F(xiàn)6(x)～F8(x)為混合函數(shù)(hybrid functions)，F(xiàn)9(x)～F15(x)為構(gòu)造函數(shù)(composition functions)?；旌虾瘮?shù)將函數(shù)變量分為多個子分量，每個子分量分別受到基本的單模函數(shù)或多模函數(shù)的影響，所以混合函數(shù)是否屬于單模或多模函數(shù)取決于作用在子變量的基本函數(shù)。構(gòu)造函數(shù)是由多個基本函數(shù)組合而成。函數(shù)的具體描述可參見文獻(xiàn)[30]。

15個函數(shù)的搜索空間為[-100, 100]D，其中，D是空間的維數(shù)，x*表示函數(shù)的全局最佳位置，x*被設(shè)置為[-80, 80]D的隨機(jī)數(shù)，有效避免優(yōu)化算法受變量初值的影響。函數(shù)的最優(yōu)值(最小值)被設(shè)置為函數(shù)序號×100，即F1(x*)=100，F(xiàn)2(x*)=200，…，F(xiàn)15(x*)=1 500。函數(shù)的維數(shù)設(shè)置為30。

3.2 實驗環(huán)境設(shè)置

基于算法對應(yīng)文獻(xiàn)的推薦配置，實驗所應(yīng)用的算法的參數(shù)設(shè)置如表1所示，其中，Vmaxd表示粒子第d維速度的最大值，即粒子速度vkd限制在[-Vmaxd,Vmaxd]中；Range表示粒子位置各維的變化范圍，由于函數(shù)搜索空間為[-100, 100]D，所以Range=200。為驗證算法的有效性，EPSO不僅與基礎(chǔ)算法GPSO[12]，LPSO[13]，BBPSO[23]和FIPS[15]進(jìn)行比較，還與知名的CLPSO[24]進(jìn)行比較。

表1 參數(shù)設(shè)置Tab.1 Parameter configurations

為反映環(huán)境的隨機(jī)性對實驗結(jié)果的影響，對于每個測試函數(shù)，實驗運(yùn)行51次[30]。各串行算法的粒子群中粒子數(shù)量為40，根據(jù)文獻(xiàn)[30]，最大迭代次數(shù)MaxFES設(shè)置為40×104=4×105。本文的EPSO算法的參數(shù)設(shè)置為step=MaxFES/10=4×104，即各串行算法運(yùn)行過程中進(jìn)行10次信息共享；各串行算法的粒子群的粒子數(shù)量為40，算法的收斂條件是迭代次數(shù)達(dá)到MaxFES。由于各串行算法的計算復(fù)雜度不同，因此，EPSO需要等待最慢的串行算法達(dá)到MaxFES后才結(jié)束。

實驗的計算機(jī)配置為CPU AMD 6核Fx-6300，內(nèi)存8 GByte，固態(tài)硬盤120 GByte，計算機(jī)最大能開啟6個工作單元。

3.3 實驗結(jié)果分析

本文采用51次實驗結(jié)果的均值和均方差作為統(tǒng)計指標(biāo)。均值越接近于最優(yōu)值，說明算法的準(zhǔn)確度越高；若均方差越小，說明算法的穩(wěn)定度越高。表2列出了6種算法在15個函數(shù)上尋優(yōu)結(jié)果，其中，最小均值和最小均方差用#標(biāo)明,表示6種算法測試值中的最好值。

表2 統(tǒng)計結(jié)果比較Tab.2 Statistical results comparison

備注：每行最小均值和最小均方差用#標(biāo)明。

從表2可知，GPSO和CLPSO分別在F9(x)和F12(x)上取得最優(yōu)均值，而EPSO在剩余的13個函數(shù)上取得較好的均值。EPSO在7個函數(shù)上取得最優(yōu)均方差，EPSO在其余函數(shù)上的均方差接近于6種算法的最優(yōu)均方差。

表3列出了各算法的Friedman測試結(jié)果，EPSO排名第1，位列第2的是CLPSO，這表明EPSO的綜合性能最好。雖然GPSO，LPSO，BBPSO和FIPS測試排名不如CLPSO，但這4種算法集成為EPSO后，性能優(yōu)于CLPSO，顯示集成策略的有效性。

表3 各對比算法的Friedman測試結(jié)果Tab.3 Friedman test results of the comparison algorithms

圖3顯示的是EPSO和其他5種算法在函數(shù)F2(x)，F(xiàn)3(x)，F(xiàn)7(x)，F(xiàn)12(x)上的收斂曲線。F2(x)，F(xiàn)3(x)，F(xiàn)7(x)，F(xiàn)12(x)的類型分別對應(yīng)單峰函數(shù)、簡單多模函數(shù)、混合函數(shù)、構(gòu)造函數(shù)。從圖3可知，EPSO的收斂速度是最快的，主要是由于EPSO在運(yùn)算過程中結(jié)合了不同算法尋找的最優(yōu)值。

圖3 6種算法在F2(x)，F(xiàn)3(x)，F(xiàn)7(x)，F(xiàn)12(x)上的收斂曲線Fig.3 Convergence curve of six algorithms on functions F2(x),F3(x),F7(x),F12(x)

6種算法的運(yùn)行時間對比如表 4所示。從表4中可以看出，5種SPSO中GPSO的運(yùn)行時間最短，主要原因是算法最簡單；其次是LPSO，增加了鄰域計算；而CLPSO和BBPSO運(yùn)行時間相對較長，主要原因是CLPSO的學(xué)習(xí)策略較復(fù)雜，BBPSO的多元分布計算消耗較多時間；EPSO是6種算法中最長的，主要原因是除了基本的迭代運(yùn)算，工作單元管理、任務(wù)分配、工作單元之間通信都會耗費(fèi)時間。表4中的增量表示EPSO與5種SPSO的最大運(yùn)行時間均值之差。結(jié)果顯示，EPSO的運(yùn)行時間增加量在[2,8]s，并不多，EPSO運(yùn)行時間的均方差比其余幾種算法稍大，但相差大約0.2s，說明算法比較穩(wěn)定。

表4 運(yùn)行時間比較Tab.4 Runtime comparisons

備注：每行最大的前2個均值用#標(biāo)明，增量表示EPSO算法與5種串行PSO的最大均值之差。

由于BBPSO的多元分布計算比較復(fù)雜，其時間復(fù)雜度高于GPSO，LPSO，F(xiàn)IPS。EPSO的時間復(fù)雜度主要取決于BBPSO，從表4可以看出，EPSO的運(yùn)行時間與BBPSO相當(dāng)。

當(dāng)每種算法選取的粒子數(shù)量是一樣時，EPSO的空間需求量是GPSO，LPSO，F(xiàn)IPS，BBPSO的4倍多。當(dāng)每個串行算法采用40個粒子，采用雙精度浮點數(shù)存儲每個粒子的速度、位置、個體最佳位置，EPSO用于存儲粒子需要的空間為40×8 Byte×3×4=3 840 Byte，因為EPSO是并行的，需要額外的空間存儲臨時變量，所以實際的空間需求量會高于3 840 Byte?，F(xiàn)在的計算機(jī)內(nèi)存一般配置2 GByte以上，所以EPSO的空間需求量并不會給計算機(jī)帶來壓力。

實驗結(jié)果表明，通過并行計算和信息共享，EPSO的測試準(zhǔn)確度不僅優(yōu)于集成的4種SPSO算法，還優(yōu)于知名的CLPSO算法的最好測試結(jié)果，并且其標(biāo)準(zhǔn)差與5種SPSO的最小標(biāo)準(zhǔn)差比較接近。同時，EPSO運(yùn)行時間增加并不多。

4 結(jié) 論

SPSO算法已在多個領(lǐng)域發(fā)揮重要的作用。提出的集成粒子群算法EPSO使用Matlab SPMD并行結(jié)構(gòu)發(fā)揮單節(jié)點多核計算能力，實現(xiàn)4種SPSO算法的并行計算，充分發(fā)揮不同SPSO的優(yōu)勢，設(shè)置檔案收集不同粒子群的最佳位置，通過粒子的隨機(jī)替換，促進(jìn)不同粒子群之間的信息共享。在廣泛使用的測試集上進(jìn)行仿真實驗，實驗結(jié)果表明，EPSO在保持較好的穩(wěn)定度以及運(yùn)行時間增加不多的前提下，準(zhǔn)確度優(yōu)于知名的SPSO算法。EPSO的算法框架是靈活的，可以進(jìn)行擴(kuò)展，通過集成多種各具特色的粒子群算法，使得粒子群算法能夠適應(yīng)更多場合。

[1] ZHANG J, ZHAN Z, LIN Y, et al. Evolutionary computation meets machine learning: A survey[J]. IEEE Computational Intelligence Magazine, 2011, 6(4): 68-75.

[2] KENNEDY J, EBERHART R. Particle swarm optimization[C]// IEEE Proceedings of the International Conference on Neural Networks. Piscataway: IEEE Press,1995: 1942-1948.

[3] DORIGO M, BIRATTARI M, STUTZLE T. Ant colony optimization[J].IEEE Computational Intelligence Magazine, 2006, 1(4): 28-39.

[4] KARABOGA D, GORKEMLI B, OZTURK C, et al. A comprehensive survey: Artificial bee colony (ABC) algorithm and applications[J].Artificial Intelligence Review, 2014, 42(1): 21-57.

[5] YANG X. Firefly algorithms for multimodal optimization[M].Watanabe O, Zeugmann T：Springer Berlin Heidelberg,2009, 169-178.

[6] ZHANG Y, WANG S, JI G.A comprehensive survey on particle swarm optimization algorithm and its applications[EB/OL].(2015-02-12)[2016-06-01].http://www.hindawi.com/journals/mpe/aa/931256/.

[7] 侯燕, 郭慧玲. 關(guān)聯(lián)規(guī)則挖掘結(jié)合簡化粒子群優(yōu)化的哈希回溯追蹤協(xié)議[J].重慶郵電大學(xué)學(xué)報：自然科學(xué)版，2016, 28(02): 239-246. HOU Yan,GUO Huiling. Hash IP trace-back protocol based on association rule mining and simplified particle swarm optimization[J].Journal of Chongqing University of Posts and Telecommunications：Natural Science Edition, 2016, 28(02): 239-246.

[8] 孫延維, 彭智明, 李健波. 基于粒子群優(yōu)化與模糊聚類的社區(qū)發(fā)現(xiàn)算法[J].重慶郵電大學(xué)學(xué)報：自然科學(xué)版，2015, 27(05): 660-666. SUN Yanwei, PENG Zhiming, LI Jianbo. Community detection algorithm based on particle swarm optimization and fuzzy clustering[J].Journal of Chongqing University of Posts and Telecommunications：Natural Science Edition, 2015, 27(05): 660-666.

[9] WAINTRAUB M, SCHIRRU R, PEREIRA C M N A. Multiprocessor modeling of parallel Particle Swarm Optimization applied to nuclear engineering problems[J]. Progress in Nuclear Energy, 2009, 51(6-7): 680-688.

[10] MUSSI L, DAOLIO F, CAGNONI S. Evaluation of parallel particle swarm optimization algorithms within the CUDA? architecture[J]. Information Sciences, 2011, 181(20): 4642-4657.

[11] TU K,LIANG Z.Parallel computation models of particle swarm optimization implemented by multiple threads[J].Expert Systems with Applications,2011,38(5):5858-5866.

[12] SHI Y, EBERHART R. A modified particle swarm optimizer[C]//IEEE.Proceedings of the IEEE Congress on Evolutionary Computation.Piscataway:IEEE Press，1998:69-73.

[13] KENNEDY J, MENDES R. Population structure and particle swarm performance[C]//IEEE.Proceedings of the IEEE Congress on Evolutionary Computation.Piscataway: IEEE Press, 2002: 1671-1676.

[14] MENDES R, KENNEDY J, NEVES J. The fully informed particle swarm: Simpler, maybe better[J].IEEE Transactions on Evolutionary Computation,2004,8(3): 204-210.

[15] KENNEDY J, MENDES R. Neighborhood topologies in fully informed and best-of-neighborhood particle swarms[J]. IEEE Transactions on Systems Man and Cybernetics Part C Applications and Reviews,2006,36(4):515-519.

[16] 占棟輝, 盧厚清, 郝文寧, 等. 一種高斯反向?qū)W習(xí)粒子群優(yōu)化算法[J].小型微型計算機(jī)系統(tǒng)， 2015, 36(5): 1064-1068. ZHAN Donghui, LU Houqing, HAO Wenning, et al.Particle Swarm Optimization Algorithm with Gaussian Opposition-based Learning[J].Journal of Chinese Computer Systems,2015,36(5):1064-1068.

[17] 趙嘉, 付平, 李崇俠, 等. 基于不同學(xué)習(xí)模型的精英反向粒子群優(yōu)化算法[J].小型微型計算機(jī)系統(tǒng)，2015,36(6): 1368-1372. ZHAO Jia, FU Ping, LI Chongxia, et al. Particle Swarm Optimization Based on Elite Opposition Learning Using Different Learning Models[J].Journal of Chinese Computer Systems, 2015,36(6): 1368-1372.

[18] 戴月明, 朱達(dá)祥, 吳定會. 核矩陣協(xié)同進(jìn)化的震蕩搜索粒子群優(yōu)化算法[J].重慶郵電大學(xué)學(xué)報：自然科學(xué)版，2016, 28(02): 247-253. DAI Yueming,ZHU Daxiang,WU Dinghui.Shock search particle swarm optimization algorithm based on kernel matrix synergistic evolution[J].Journal of Chongqing University of Posts and Telecommunications：Natural Science Edition, 2016, 28(02): 247-253.

[19] CLERC M, KENNEDY J.The particle swarm-explosion, stability, and convergence in a multidimensional complex space[J].IEEE Transactions on Evolutionary Computation,2002,6(1): 58-73.

[20] 許君, 魯海燕, 石桂娟. 限制速度粒子群優(yōu)化和自適應(yīng)速度粒子群優(yōu)化在無約束優(yōu)化問題中的應(yīng)用[J].計算機(jī)應(yīng)用，2015, 35(3): 668-674. XU Jun,LU Haiyan,SHI Guijuan.Application of restricted velocity particle swarm optimization and self-adaptive velocity particle swarm optimization to unconstrained optimization problem[J].Journal of Computer Applications, 2015, 35(3): 668-674.

[21] 陳壽文. 基于質(zhì)心和自適應(yīng)指數(shù)慣性權(quán)重改進(jìn)的粒子群算法[J]. 計算機(jī)應(yīng)用，2015, 35(3): 675-679. CHEN Shouwen.Improved particle swarm optimization algorithm based on centroid and self-adaptive exponential inertia weight[J].Journal of Computer Applications, 2015, 35(3): 675-679.

[22] 奚茂龍,盛歆漪,孫俊.基于多維問題的交叉算子量子粒子群優(yōu)化算法[J].計算機(jī)應(yīng)用，2015,35(3):680-684. XI Maolong,SHENG Xinyi,SUN Jun. Quantum-behaved particle swarm optimization algorithm with crossover operator to multi-dimension problems[J]. Journal of Computer Applications, 2015, 35(3): 680-684.

[23] KENNEDY J. Bare bones particle swarms[C]//IEEE.Proceedings of the IEEE Swarm Intelligence Symposium. Piscataway: IEEE Press, 2003: 80-87.

[24] LIANG J J, QIN A K, SUGANTHAN P N, et al. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(3): 281-295.

[25] CAMPOS M, KROHLING R A, ENRIQUEZ I. Bare bones particle swarm optimization with scale matrix adaptation[J]. IEEE Transactions on Cybernetics, 2014, 44(9): 1567-1578.

[26] MathWorks, Inc. Parallel computing toolbox[EB/OL]. (2015-09-01)[2016-06-01].http://cn.mathworks.com/help/distcomp/.

[27] GOH C K, TAN K C, LIU D S, et al. A competitive and cooperative co-evolutionary approach to multi-objective particle swarm optimization algorithm design[J]. European Journal of Operational Research,2010,202(1):42-54.

[28] ZHANG G, ZHAN Z, DU K, et al. Parallel particle swarm optimization using message passing interface[C]//Proceedings of the 18th Asia Pacific Symposium on Intelligent and Evolutionary Systems.Cham, Switzerland:Springer International Publishing, 2015: 55-64.

[29] ALBA E, TOMASSINI M. Parallelism and evolutionary algorithms[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(5): 443-462.

[30] LIANG J J, QU B Y, SUGANTHAN P N, et al. Problem Definitions and Evaluation Criteria for the CEC 2015 Competition on Learning-based Real-Parameter Single Objective Optimization[R].Zhengzhou, China: Computational Intelligence Laboratory, 2014.

(編輯：王敏琦)

s：The National Science Fund for Young Scholars of China(61301232, 61501174); The Key Scientific Research projects of Higher Education of Henan Province of China(17A520026); The Doctoral Program of Henan Institute of Engineering(D2012016)

Serial particle swarm optimizer (SPSO) is popularly applied in many areas. SPSO variants are proposed to solve different kinds of optimization problems，but there are differences between the performances. Therefore, an ensemble particle swarm optimizer (EPSO) was proposed to improve SPSO’s ability to adapt to problems. The parallel structure single program multiple data (SPMD) in Matlab was utilized to play single node multicore computing power. An outside archive was set to share the global best positions of different particle swarms and further facilitate information exchange of different SPSOs. SPSOs’ advantages to solve different kinds of optimization problems were synthesized by the new algorithm. Simulation experiments conducted on a set of widely used benchmark functions verify the effectiveness of the new algorithm. Compared with several well-known SPSO variants, the new algorithm has a significant advantage in optimizing performance. The new algorithm can not only improve the adaptability of PSO, but also adapt to the other swarm intelligent algorithms to improve the algorithm performance.

single program multiple data; ensemble particle swarm optimizer; global numerical optimization; particle swarm optimizer; parallel computing

10.3979/j.issn.1673-825X.2017.04.016

2016-10-07

2017-02-26 通訊作者：何 莉 engineerheli@126.com

國家自然科學(xué)基金青年項目(61301232，61501174)；河南省高等學(xué)校重點科研項目(17A520026)；河南工程學(xué)院博士基金(D2012016)

TP393

A

1673-825X(2017)04-0527-08

Ensemble particle swarm optimizer for single objective optimization

(School of Computer, Henan Institute of Engineering, Zhengzhou 451191, P. R. China)

何 莉(1982-)，男，江西萍鄉(xiāng)人，講師，博士，研究方向為智能計算、物聯(lián)網(wǎng)。E-mail：engineerheli@126.com。 王 淼(1981-)，男，河南南陽人，副教授，博士，研究方向為空間關(guān)系數(shù)據(jù)庫。E-mail：506872858@qq.com。 李 博(1982-)，男，河南許昌人，講師，博士，研究方向為群智能和圖像處理。E-mail：422873809@qq.com。

HE Li, WANG Miao, LI Bo