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

何 莉，王 淼，李 博

(河南工程學院 計算機學院, 鄭州 451191)

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

何 莉，王 淼，李 博

(河南工程學院 計算機學院, 鄭州 451191)

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

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

0 引 言

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

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

現(xiàn)有多數(shù)PSO算法的代碼以串行方式執(zhí)行，稱這類PSO為串行粒子群算法(serial particle Swarm optimizer，SPSO)。SPSO在處理優(yōu)化問題中取得顯著成績，但依然存在多個問題需要解決，比如迭代尋優(yōu)的耗時問題，大數(shù)量級數(shù)據(jù)處理問題，自身行為與社會行為的主導性問題，探索與挖掘矛盾的處理?，F(xiàn)已提出多種并行與分布式PSO[9-11]用于解決前2個問題。粒子的行為軌跡受到自身歷史最佳位置和鄰域粒子的影響，如何更有效地引導粒子下一步動作值得進一步研究。粒子的通信拓撲被認為是刻畫粒子與鄰域關系的有效方法，被廣泛使用的拓撲結構有全連接[12]和環(huán)型拓撲結構[13]。文獻[14-15]認為粒子的行為受到其鄰域中所有粒子的影響，粒子群進行探索的目的是跳出局部最優(yōu)解，在更大的區(qū)域?qū)ふ胰肿顑?yōu)解，粒子群進行挖掘的目的是對局部區(qū)域進行細粒度搜索更優(yōu)解。反向?qū)W習機制被引入提高粒子的學習能力[16-17]，核矩陣被用于改善粒子的多樣性[18]。多種參數(shù)約束的SPSO算法已提出用于折衷探索與挖掘的關系[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é)點多核的并發(fā)處理能力，用多個內(nèi)核分別運行全局粒子群算法(global PSO，GPSO)[12]，本地粒子群算法(local PSO，LPSO)[13]，裸骨粒子群算法(bare bones particle swarms，BBPSO)[23]和全信息粒子群算法(fully informed particle swarm，F(xiàn)IPS)[14-15]，然后，通過信息共享機制促進粒子群全局最佳位置的共享，提高PSO算法的準確性。

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

1 串行粒子群算法

一個粒子群由S個粒子構成。每個粒子用序號表示，第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]。對于最小化問題，最佳位置意味著在指定的范圍該位置的適應度最低。粒子k的鄰域Nk由粒子群的通信拓撲決定，對于環(huán)型通信拓撲結構，粒子k的鄰域包括粒子k-1，k和k+1，即Nk={k-1,k,k+1}。

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

(1)

(2)

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

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

(3)

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

(4)

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

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

(5)

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

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

(6)

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

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

2 集成粒子群算法(EPSO)

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

2.1 Matlab SPMD并行結構

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

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

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

圖1 Matlab SPMD并行結構Fig.1 Matlab SPMD parallel structure

2.2 并行策略與信息共享

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗與討論

3.1 評測函數(shù)

實驗采用CES’15[30]評測集。評測集共有15個單目標最小優(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)為構造函數(shù)(composition functions)?；旌虾瘮?shù)將函數(shù)變量分為多個子分量，每個子分量分別受到基本的單模函數(shù)或多模函數(shù)的影響，所以混合函數(shù)是否屬于單模或多模函數(shù)取決于作用在子變量的基本函數(shù)。構造函數(shù)是由多個基本函數(shù)組合而成。函數(shù)的具體描述可參見文獻[30]。

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

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

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

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

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

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

3.3 實驗結果分析

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

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

備注：每行最小均值和最小均方差用#標明。

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

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

表3 各對比算法的Friedman測試結果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)的類型分別對應單峰函數(shù)、簡單多模函數(shù)、混合函數(shù)、構造函數(shù)。從圖3可知，EPSO的收斂速度是最快的，主要是由于EPSO在運算過程中結合了不同算法尋找的最優(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種算法的運行時間對比如表 4所示。從表4中可以看出，5種SPSO中GPSO的運行時間最短，主要原因是算法最簡單；其次是LPSO，增加了鄰域計算；而CLPSO和BBPSO運行時間相對較長，主要原因是CLPSO的學習策略較復雜，BBPSO的多元分布計算消耗較多時間；EPSO是6種算法中最長的，主要原因是除了基本的迭代運算，工作單元管理、任務分配、工作單元之間通信都會耗費時間。表4中的增量表示EPSO與5種SPSO的最大運行時間均值之差。結果顯示，EPSO的運行時間增加量在[2,8]s，并不多，EPSO運行時間的均方差比其余幾種算法稍大，但相差大約0.2s，說明算法比較穩(wěn)定。

表4 運行時間比較Tab.4 Runtime comparisons

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

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

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

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

4 結 論

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

[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] 侯燕, 郭慧玲. 關聯(lián)規(guī)則挖掘結合簡化粒子群優(yōu)化的哈?；厮葑粉檯f(xié)議[J].重慶郵電大學學報：自然科學版，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].重慶郵電大學學報：自然科學版，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習粒子群優(yōu)化算法[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] 趙嘉, 付平, 李崇俠, 等. 基于不同學習模型的精英反向粒子群優(yōu)化算法[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] 戴月明, 朱達祥, 吳定會. 核矩陣協(xié)同進化的震蕩搜索粒子群優(yōu)化算法[J].重慶郵電大學學報：自然科學版，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ōu)化在無約束優(yōu)化問題中的應用[J].計算機應用，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ì)心和自適應指數(shù)慣性權重改進的粒子群算法[J]. 計算機應用，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].計算機應用，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

國家自然科學基金青年項目(61301232，61501174)；河南省高等學校重點科研項目(17A520026)；河南工程學院博士基金(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-)，男，河南南陽人，副教授，博士，研究方向為空間關系數(shù)據(jù)庫。E-mail：506872858@qq.com。 李 博(1982-)，男，河南許昌人，講師，博士，研究方向為群智能和圖像處理。E-mail：422873809@qq.com。

HE Li, WANG Miao, LI Bo