摘  要： 提出了一種改進(jìn)的多群協(xié)作粒子群優(yōu)化算法，該算法整個(gè)種群采用主從模式,，分為一個(gè)主群和多個(gè)從群,，多個(gè)從群粒子統(tǒng)一地進(jìn)行初始化操作，從而避免了多個(gè)粒子群重復(fù)搜索現(xiàn)象,。同時(shí),，算法采取了一種擾動(dòng)策略,，即當(dāng)前全局最優(yōu)解在擾動(dòng)因子的迭代周期內(nèi)保持不變時(shí)，就重置粒子的速度,，迫使粒子群擺脫局部極小,。該算法不僅增加了種群的多樣性，擴(kuò)大了搜索范圍,，而且還改善整個(gè)種群易陷入局部極小值的缺陷,。通過(guò)9個(gè)基準(zhǔn)函數(shù)進(jìn)行測(cè)試,，實(shí)驗(yàn)結(jié)果表明,，IMCPSO與MCPSO算法相比具有明顯的優(yōu)越性。

　　關(guān)鍵詞： 多群協(xié)作,；粒子群優(yōu)化,；函數(shù)優(yōu)化

　　粒子群優(yōu)化PSO（Particle Swarm Optimization）算法，由KENNEDY J和EBERHART R C[1-2]于1995年提出,，成為智能計(jì)算領(lǐng)域的研究熱點(diǎn)之一,。PSO算法是一種模擬自然生物界鳥(niǎo)群或魚(yú)群行為的隨機(jī)智能優(yōu)化算法，其全局搜索能力較強(qiáng),，對(duì)一些粒子進(jìn)行迭代計(jì)算獲取全局最優(yōu)解,。PSO算法是一種模擬自然界鳥(niǎo)群或魚(yú)群行為的隨機(jī)智能優(yōu)化算法。不少學(xué)者們也研究了一些改進(jìn)算法來(lái)改善PSO算法的性能和收斂速度,。牛奔[3]等基于種群共生關(guān)系提出了多群協(xié)作粒子群優(yōu)化MCPSO（Multi-swarm Cooperative Particle Swarm Optimizer）算法的兩種進(jìn)化結(jié)構(gòu),。而ZHAO S Z等[4]在2011年提出了關(guān)于動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)的多粒子群協(xié)同優(yōu)化算法。KONSTANTINOS E P[5]提出了主-從模式的并行微型結(jié)構(gòu)的多粒子群協(xié)同優(yōu)化算法,。

　　但是這些多粒子群優(yōu)化算法可能存在重復(fù)搜索,，造成粒子數(shù)目的浪費(fèi)，同時(shí)又在多維數(shù),、多峰值優(yōu)化函數(shù)存在算法求解精度低及收斂度差等不足,，為此本文提出一種改進(jìn)的多群協(xié)作粒子群協(xié)同粒子群優(yōu)化（IMCPSO）算法。該算法對(duì)從群粒子采取統(tǒng)一初始化操作,，避免在搜索初期造成的重復(fù)搜索現(xiàn)象,。同時(shí)，引入粒子擾動(dòng)策略,，即當(dāng)粒子陷入局部極小值時(shí)能夠重新設(shè)置粒子速度,，強(qiáng)制粒子擺脫陷入局部極小值的可能。

　　實(shí)驗(yàn)仿真結(jié)果表明,，IMCPSO算法比MCPSO和PSO算法在尋優(yōu)精度和收斂速度都有大幅度的提高,，并且具有較強(qiáng)的魯棒性。

1 基本粒子群優(yōu)化算法

　　基本PSO算法利用單個(gè)粒子間的協(xié)作和競(jìng)爭(zhēng)來(lái)搜索優(yōu)化問(wèn)題的最優(yōu)解,。算法起初通過(guò)隨機(jī)生成初始化種群粒子,，其中每個(gè)粒子作為優(yōu)化問(wèn)題的一個(gè)候選方案,，并由目標(biāo)函數(shù)計(jì)算出粒子適應(yīng)值。種群粒子在搜索空間里運(yùn)動(dòng),，通過(guò)自身速度向量來(lái)判定其運(yùn)動(dòng)的方向和長(zhǎng)度,。每個(gè)粒子跟隨當(dāng)前自身最優(yōu)位置和種群的最優(yōu)位置而運(yùn)動(dòng)，最后經(jīng)過(guò)多次搜索得到優(yōu)化問(wèn)題的最優(yōu)解,。

　　假設(shè)在D維搜索空間里,，粒子搜索空間的上、下界分別為xmax,、xmin,。第i個(gè)粒子的位置和速度矢量分別為xi=（xi1，xi2,，…,，xiD），vi=（vi1,，vi2,，…，viD）,，其中xiD∈（xmax,，xmin），d∈[1,，D],。Pi=（pi1，pi2,，…,，piD）表示為第i個(gè)粒子的當(dāng)前最優(yōu)位置矢量，Pg=（pg1,，pg2,，…，pgD）是種群的全局最優(yōu)位置矢量,。每次迭代過(guò)程中,，粒子的速度和位置的更新公式為：

　　Vid（t+1）=wvid（t）+c1R1（pid-xid（t））+c2R2（pgd-xgd（t））（1）

　　xid（t+1）=xid（t）+vid（t）（2）

　　其中，w為慣性權(quán)重,，c1,、c2為加速因子，R1,、R2為[0,，1]之間的隨機(jī)數(shù)[1]。

　　通過(guò)解析式（1）和（2）可以發(fā)現(xiàn),，經(jīng)典的PSO算法的種群粒子在不斷的搜索過(guò)程中,，常常跟蹤當(dāng)前全局最優(yōu)位置及自己目前搜索到的歷史最優(yōu)位置,。因此，粒子速度比較快地下降接近為0,，造成種群粒子陷入局部極小值而無(wú)法擺脫,。這種“趨同性”局限了粒子的搜索空間，若實(shí)現(xiàn)搜索空間的擴(kuò)大,，必須要加大種群的粒子數(shù),，或降低種群粒子對(duì)全局最優(yōu)位置的追蹤。加大粒子數(shù)會(huì)造成優(yōu)化問(wèn)題的計(jì)算復(fù)雜度的增加,，降低種群粒子對(duì)全局最優(yōu)位置的追蹤又造成算法收斂性能較差的不足,。

2 一種改進(jìn)的多群協(xié)作粒子群優(yōu)化算法

　　2.1 MCPSO算法

　　牛奔[3]等人提出的基本MCPSO算法，借鑒了生物系統(tǒng)中的共生現(xiàn)象,，反映了種群個(gè)體之間的相互關(guān)系,。該算法將種群均分成具有主從模式的一個(gè)主群和多個(gè)從群,，利用主,、從群間的共生關(guān)系，兩者進(jìn)行信息的交流與傳遞,，某種程度上克服了粒子陷入局部最優(yōu)的危險(xiǎn),。根據(jù)不同的共生關(guān)系，算法可分為合作（COL_MCPSO）和競(jìng)爭(zhēng)（COM_MCPSO）兩種形式,，算法中每個(gè)從群都獨(dú)立并行地執(zhí)行基本PSO算法或其變體,，更新粒子的位置和速度。當(dāng)所有從群更新完成,，再將局部最優(yōu)值傳給主群,。

　　（1）COL_MCPSO算法主群粒子位置,、速度更新公式為：

　　2.2 IMPSCO算法

　　面對(duì)高維,、多峰值的復(fù)雜優(yōu)化問(wèn)題，為了獲得更好的全局最優(yōu)值,，基本MCPSO算法通過(guò)犧牲收斂速度來(lái)增加種群多樣性,，以達(dá)到降低種群陷入局部極小值的可能。但是同時(shí)保持種群多樣性和較快的收斂速度,，仍然是目前優(yōu)化算法面臨的一個(gè)挑戰(zhàn),，并且在搜索初期，多種群并行獨(dú)立搜索解空間,，造成部分粒子的重復(fù)搜索現(xiàn)象,，且種群搜索初期容易陷入局部最優(yōu)解。

　　2.3 改進(jìn)算法

　　針對(duì)上述算法不足之處,，本文通過(guò)基本MCPSO算法中競(jìng)爭(zhēng)結(jié)果,，即以COM_MCPSO算法為主要研究算法,，提出了一種改進(jìn)的多群協(xié)作粒子群優(yōu)化算法。該算法利用一個(gè)主群和多個(gè)從群結(jié)構(gòu)協(xié)作進(jìn)化,，其中從群粒子根據(jù)本粒子群迄今搜索到的最優(yōu)位置來(lái)更新種群中粒子速度,，而主群是由所有從群的當(dāng)前全局最優(yōu)位置來(lái)更新主群中的粒子速度。多個(gè)從群改善了尋優(yōu)搜索過(guò)程中,，提高種群多樣性,，擴(kuò)大了解空間內(nèi)的搜索范圍。同時(shí),，主群粒子追逐當(dāng)前的全局最優(yōu)位置來(lái)提高該算法的收斂速度,，從而兼顧優(yōu)化過(guò)程的精度和效率。這種算法各從群粒子數(shù)目并不要求相同,，每個(gè)子群的粒子位置和速度的更新策略也可以不同,。當(dāng)粒子數(shù)目相等的情況下，IMCPSO與基本MCPSO算法的計(jì)算復(fù)雜度是相同的,。

　　該算法提出增加擾動(dòng)因子的策略,，即假設(shè)目前尋優(yōu)得到的全局最優(yōu)位置在連續(xù)的l次迭代都沒(méi)有更新，則在搜索空間內(nèi)重新賦值粒子速度,。l為自然數(shù),，本文中稱作擾動(dòng)因子。其擾動(dòng)策略的更新公式為：

　　if t-tl>l then reset v,；

　　其中tl表示為主群當(dāng)前更新到全局最優(yōu)位置的迭代步數(shù),。

　　擾動(dòng)策略的原理為：假如種群陷入局部極小值時(shí)，重新隨機(jī)化粒子速度,，迫使種群粒子跳出局部極小值,，進(jìn)而進(jìn)行下一迭代的新的搜索過(guò)程。IMCPSO算法利用擾動(dòng)因子的策略,，能夠進(jìn)一步提高M(jìn)CPSO算法的性能,。

　　IMCPSO算法的步驟：（1）設(shè)置算法參數(shù)大小，初始化主群和從群粒子的位置和速度,。（2）評(píng)估主群和從群中每個(gè)粒子的適應(yīng)值,，求解各從群的全局最優(yōu)值及整個(gè)種群的全局最優(yōu)位置。（3）利用式（1）,、（2）,，更新全部從群粒子，并評(píng)估從群的各粒子的適應(yīng)值,。（4）將從群的全局最優(yōu)位置傳給主群,，并根據(jù)式（5）、（6）更新主群的各個(gè)粒子，然后評(píng)估主群各粒子的適應(yīng)值,。（5）假如t-tl>l1主群全局最優(yōu)位置未更新則執(zhí)行步驟（6）,，否則執(zhí)行步驟（7）。（6）在搜索空間內(nèi)重置主群粒子速度,。（7）若滿足終止條件（達(dá)到最大迭代步數(shù)）終止,，返回主群的全局最優(yōu)值及適應(yīng)值；否則返回步驟（3）,。

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

　　3.1 基準(zhǔn)函數(shù)

　　為了保證實(shí)驗(yàn)對(duì)比的準(zhǔn)確性,，IMCPSO和MCPSO算法參數(shù)設(shè)置為一個(gè)主群和4個(gè)從群，每個(gè)子群粒子個(gè)數(shù)為5,，c1=c2=c3=1.494 45,，wmin=0.4，wmax=0.9,，其中vmax限制為搜索范圍的20%,。擾動(dòng)因子l=10。

　　本文比較了IMCPSO與經(jīng)典PSO算法,、基本MCPSO算法,，使用9個(gè)經(jīng)典的基準(zhǔn)函數(shù)評(píng)估所提算法的性能。測(cè)試基準(zhǔn)函數(shù)與搜索范圍如下,。

　　每個(gè)算法分別在維數(shù)為10,、50的基準(zhǔn)函數(shù)上測(cè)試,，迭代次數(shù)為1 000次,，運(yùn)行100次。如表1,、表2中實(shí)驗(yàn)結(jié)果為種群全局最優(yōu)值的均值和標(biāo)準(zhǔn)差,，IMCPSO和MCPSO-HS列代表函數(shù)相應(yīng)的全局最佳適應(yīng)值，所有結(jié)果的表達(dá)形式為“0.0000e+00”,。IMCPSO算法的最佳適應(yīng)值平均值與標(biāo)準(zhǔn)差要好于PSO和MCPSO算法,，說(shuō)明所提算法具有較好的穩(wěn)定性。

　　為表明算法的收斂速度,，在Windows7系統(tǒng),、Intel（R）4 3.20 GHz CPU、2 GB RAM,、軟件為MATLAB 2012a的環(huán)境下運(yùn)行所提算法,，并得出在維數(shù)為10下各基準(zhǔn)函數(shù)的迭代過(guò)程，如圖1所示,?？芍狪MPSCO算法的收斂速度和最優(yōu)值明顯優(yōu)于PSO和MCPSO算法。

　　本文中IMCPSO算法通過(guò)多個(gè)從群改善種群多樣性,，擴(kuò)大了搜索范圍,，通過(guò)統(tǒng)一的初始化操作,，避免了搜索空間的重復(fù)搜索。該算法引入擾動(dòng)策略,，進(jìn)一步避免了種群粒子陷入局部最優(yōu)點(diǎn)的危險(xiǎn),。實(shí)驗(yàn)結(jié)果表明，與PSO和MCPSO算法相比,，IMCPSO算法更有效地使用了以往的解決方案,，以便獲取較好的全局最優(yōu)位置。通過(guò)測(cè)試的9個(gè)基準(zhǔn)函數(shù),，可以得出IMCPSO算法在解決高維,、多峰值復(fù)雜優(yōu)化函數(shù)改善了PSO和MCPSO算法的尋優(yōu)性能和求解精度，且具有較強(qiáng)的魯棒性,。

　　參考文獻(xiàn)

　　[1] KENNEDY J,， EBERHART R C. Particle swarm optimization[C]. Proceedings of IEEE International Conference on Neural Networks， piscataway,， 1995： 1942-1948.

　　[2] EBERHART R C,， KENNEDY J. A new optimizer using particle swarm theory[C]. Proceedings of the Sixth International Symposium on Micro Machine and Human Science. 1995（1）： 39-43.

　　[3] Niu Ben， Zhu Yunlong,， He Xiaoxian,， et al. MCPSO： A multi-swarm cooperative particle swarm optimizer[J]. Applied Mathematics and Computation， 2007,， 185（2）： 1050-1062.

　　[4] ZHAO S Z,， SUGANTHAN P N， PAN QUAN-KE,， et al. Dynamic multi-swarm particle swarm optimizer with harmony search[J]. Expert Systems with Applications,， 2011， 38（4）： 3735-3742.

　　[5] KONSTANTINOS E P. Parallel cooperative micro-particle swarm optimization： A master-slave model[J]. Applied Soft Computing,， 2012,， 12（11）： 3552-3579.