謝紅俠　馬曉偉　陳曉曉　邢強(qiáng)

摘要：

針對(duì)多模態(tài)函數(shù)尋優(yōu)過程中開發(fā)與探索能力難以平衡的問題，提出一種基于多種群的改進(jìn)粒子群算法（EMSPSO）。該算法在基于種群的粒子群算法（SPSO）的基礎(chǔ)上改進(jìn)了種群生成策略，通過在個(gè)體最優(yōu)值中選擇種子，將粒子群分為若干獨(dú)立進(jìn)化的種群，增強(qiáng)了算法收斂的穩(wěn)定性；為了提高粒子的利用率、算法的全局搜索能力和搜索效率，引入冗余粒子重新初始化策略；同時(shí)為了防止算法在尋優(yōu)的過程中遺漏適應(yīng)度較優(yōu)的極值點(diǎn)，對(duì)速度更新公式進(jìn)行改進(jìn)，使算法的開發(fā)與探索能力得到了有效的均衡。最后選用6個(gè)典型的測(cè)試函數(shù)進(jìn)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，EMSPSO具有較高的多模態(tài)尋優(yōu)成功率與較優(yōu)的全局極值搜索性能。

關(guān)鍵詞：

多模態(tài)函數(shù)優(yōu)化；粒子群算法；小生境技術(shù)；多種群；冗余粒子

中圖分類號(hào)：

TP18

文獻(xiàn)標(biāo)志碼：A

Abstract：

It is difficult to balance local development and global exploration in a multimodal function optimization process， therefore， an Enhanced MultiSpeciesbased Particle Swarm Optimization （EMSPSO） was proposed. An improved multispecies evolution strategy was introduced to Speciesbased Particle Swarm Optimization （SPSO）. Several species which evolved independently were established by selecting seed in the individual optimal values to improve the stability of algorithm convergence. A redundant particle reinitialization strategy was introduced to the algorithm in order to improve the utilization of the particles， and enhance global search capability and search efficiency of the algorithm. Meanwhile， in order to prevent missing optimal extreme points in the optimization process， the rate update formula was also improved to effectively balance the local development and global exploration capability of the algorithm. Finally， six typical test functions were selected to test the performance of EMSPSO. The experimental results show that， EMSPSO has high multimodal optimization success rate and optimal performance of global extremum search.

英文關(guān)鍵詞Key words：

multimodal function optimization； Particle Swarm Optimization （PSO） algorithm； niche technology； multispecies； redundant particle

0引言

在現(xiàn)實(shí)生活中很多實(shí)際問題都可以抽象為數(shù)值函數(shù)尋優(yōu)問題，有一些問題如神經(jīng)網(wǎng)絡(luò)集成、組合投資等，不僅要在解空間中找出全局最優(yōu)解，還要盡可能多地找出有意義的局部最優(yōu)解，為問題的解決提供足夠的信息，此類問題被稱為多模態(tài)優(yōu)化問題[1-2]，抽象出的函數(shù)為多模態(tài)函數(shù)（multimodal function），而解決此類問題的過程便是多模態(tài)函數(shù)的尋優(yōu)。

粒子群算法（Particle Swarm Optimization， PSO）[3]是Kennedy與Eberhard觀察模仿鳥類遷徙覓食的群體行為，于1995年提出的一種群體智能優(yōu)化技術(shù)。標(biāo)準(zhǔn)的PSO是單極值搜索的算法，一次只能搜索到一個(gè)極值點(diǎn)，對(duì)多模態(tài)問題并不適用。小生境（niche）技術(shù)[4]是一種仿生技術(shù)，將自然界中種群的概念與群體智能算法相結(jié)合，通過一定的方法，將整個(gè)種群劃分為許多個(gè)獨(dú)立的子種群，每個(gè)子種群可以獨(dú)立地進(jìn)化。近幾年，將小生境技術(shù)與群體智能算法相結(jié)合，提出了一些適用于多模態(tài)優(yōu)化問題的尋優(yōu)方法。將小生境技術(shù)與遺傳算法（Genetic Algorithm， GA）相結(jié)合提出了小生境遺傳算法（Niche Genetic Algorithm， NGA）[5]與種群保護(hù)遺傳算法（Species Conserving Genetic Algorithm， SCGA）[6]等多模態(tài)優(yōu)化算法，但這些基于遺傳算法的多模態(tài)優(yōu)化方法大多存在計(jì)算開銷大、收斂速度慢、局部搜索精度低的缺陷[7]。將小生境技術(shù)與粒子群相結(jié)合，文獻(xiàn)[8]提出了基于種群的粒子群算法（Speciesbased PSO， SPSO），將粒子群劃分為個(gè)數(shù)自適應(yīng)的種群各自獨(dú)立進(jìn)化將粒子群劃分為數(shù)個(gè)種群各自獨(dú)立進(jìn)化，種群的數(shù)目在進(jìn)化過程中不斷變化，但是在極值點(diǎn)分布較分散的情況下有可能會(huì)漏掉某些較優(yōu)的解；并且SPSO在每一代的粒子中生成種群種子，這使得粒子在收斂過程中抖動(dòng)，導(dǎo)致算法穩(wěn)定性降低。文獻(xiàn)[9]提出了一種基于k均值聚類算法的粒子群算法（kmeansbased PSO， kPSO），使用貝葉斯信息規(guī)則和標(biāo)準(zhǔn)k均值聚類算法自動(dòng)識(shí)別聚類數(shù)

目；但是該算法需要預(yù)先設(shè)置參數(shù)c與集群之間的步數(shù)，降低了該算法的實(shí)用價(jià)值。文獻(xiàn)[10]提出了多分組粒子群算法（MultiGrouped PSO， MGPSO），為搜索到的每一個(gè)極值分配一個(gè)隨進(jìn)化代數(shù)增加不斷減小的區(qū)域來避免最優(yōu)解重疊；但是如果在種群沒有足夠收斂之前極值范圍變得太小，那么很可能會(huì)導(dǎo)致某些種群找不到極值點(diǎn)。

為了提高多模態(tài)粒子群算法的搜索性能，在SPSO的基礎(chǔ)上提出了一種基于多種群的改進(jìn)粒子群算法（Enhanced MultiSpeciesbased Particle Swarm Optimization， EMSPSO）。該算法一方面改進(jìn)了種群生成策略，通過在個(gè)體最優(yōu)值中選擇種群種子，減少了粒子在搜索過程中的抖動(dòng)，使得算法更加穩(wěn)定；另一方面引入了冗余粒子重新初始化策略，提高了粒子的利用率，增強(qiáng)了算法的全局搜索能力；此外對(duì)速度更新公式進(jìn)行了改進(jìn)，使算法在收斂速度與全局搜索能力之間取得平衡。

在1維測(cè)試函數(shù)中，F(xiàn)1、F3為等峰函數(shù)，各有5個(gè)適應(yīng)度為1.0的極大值，F(xiàn)1的極大值是均勻分布的，而F3的極大值不是均勻分布；F2為變峰函數(shù)，有5個(gè)適應(yīng)度不同的極大值，最大適應(yīng)度為1.0。在2維測(cè)試函數(shù)中，F(xiàn)4具有4個(gè)適應(yīng)度為200的極大值，在解空間中分布較均勻。F5在解空間中含有若干極小值，在[0， 0]處存在全局最小值0，其余極小值在最小值周圍對(duì)稱分布，任意兩個(gè)相鄰極值之間距離相等，測(cè)試中只關(guān)心前13個(gè)極小值。F6是比較困難的多模態(tài)測(cè)試函數(shù)，在解空間中同樣存在若干極小值，這里只關(guān)心其中8個(gè)全局最小值與8個(gè)全局次小值。兩個(gè)全局最小值與兩個(gè)全局次小值為一組，整個(gè)解空間中存在4組極值，每組內(nèi)的極值間距只有0.98，而兩組間的距離遠(yuǎn)大于0.98，極值的不均勻分布與數(shù)量眾多的局部極值點(diǎn)給算法的搜索帶來很大挑戰(zhàn)。

4.2實(shí)驗(yàn)與結(jié)果分析

實(shí)驗(yàn)選用精度、成功率與收斂速度三個(gè)評(píng)價(jià)標(biāo)準(zhǔn)對(duì)算法的性能進(jìn)行對(duì)比。對(duì)某一極值點(diǎn)的尋優(yōu)精度用可使用找到的極值點(diǎn)pi與實(shí)際的極值點(diǎn)opti適應(yīng)度差值的絕對(duì)值來表示，其計(jì)算公式如式（9）。

acci=f（pi）-f（opti）（9）

在實(shí)驗(yàn)中規(guī)定單峰誤差ε=0.001，當(dāng)某一極值點(diǎn)的acci≤ε，才認(rèn)為此極值點(diǎn)被搜索到。式（10）定義了算法的平均誤差（Average ErrorS， AES）[15]，N為適應(yīng)度函數(shù)極值點(diǎn)的個(gè)數(shù)。AES體現(xiàn)了算法的全局平均精度，在一定的迭代次數(shù)下，平均誤差越小，算法精度越高。

AES=1N∑Ni=1acci=1N∑Ni=1f（pi）-f（opti）（10）

成功率指的是在進(jìn)行多次實(shí)驗(yàn)后，能成功找到所有期望極值點(diǎn)的實(shí)驗(yàn)次數(shù)與實(shí)驗(yàn)總的次數(shù)的比值，是評(píng)價(jià)多模態(tài)尋優(yōu)算法搜索性能的重要指標(biāo)。

收斂速度通過計(jì)算搜索到所有期望的極值點(diǎn)所需要的平均評(píng)價(jià)次數(shù)與運(yùn)行時(shí)間來確定。在一次運(yùn)行中，搜索到一定精度的解所需要的評(píng)價(jià)次數(shù)與運(yùn)行時(shí)間減少，收斂速度越高。

SCGA的交叉概率Pc=0.6，變異概率Pm=0.05[6]；SPSO采用收縮因子PSO，收縮因子χ=0.7298，c1=c2=2.05[8]；EMSPSO使用與SPSO等價(jià)的參數(shù)，ω=χ，c1=c2=1.4961，c3采用雙曲正切函數(shù)tanh加速。

c3=c3min+（c3max-c3min） 1-tanh（k-0.2Ngmax）2（11）

其中：c3min=0，c3max=0.15，Ngmax為最大迭代次數(shù)，k為當(dāng)前迭代次數(shù)。種群距離σS、種群規(guī)模n和Ngmax是與測(cè)試函數(shù)相關(guān)的參數(shù)，參考文獻(xiàn)[1，8]中參數(shù)的設(shè)置，其具體取值見表2。

在對(duì)比算法成功率的實(shí)驗(yàn)中，每一個(gè)測(cè)試函數(shù)都經(jīng)過三種算法50次尋優(yōu)，記錄成功率如表3的成功率。SCGA局部搜索能力較弱，容易出現(xiàn)個(gè)別極值點(diǎn)搜索精度較低的情況，所以對(duì)每一個(gè)測(cè)試函數(shù)的搜索成功率都沒有達(dá)到100%。SPSO的局部搜索能力比SCGA要強(qiáng)，但是全局搜索能力較弱，對(duì)于一維函數(shù)與簡(jiǎn)單的二維函數(shù)F4，能保持100%的成功率；但對(duì)于極值點(diǎn)較多分布較復(fù)雜的F5、F6，成功率就會(huì)嚴(yán)重下降。而EMSPSO由于改進(jìn)了速度更新公式，增加了冗余粒子初始化策略，提高了算法的搜索能力，對(duì)復(fù)雜函數(shù)的尋優(yōu)成功率要高于SPSO。

在算法精度的對(duì)比實(shí)驗(yàn)中，對(duì)每個(gè)測(cè)試函數(shù)都進(jìn)行50次尋優(yōu)，每次尋優(yōu)都運(yùn)行到此測(cè)試函數(shù)對(duì)應(yīng)的最大迭代次數(shù)Ngmax，對(duì)50次實(shí)驗(yàn)的AES取平均值得到最終結(jié)果。由表3平均誤差A(yù)ES可以看出，對(duì)每個(gè)測(cè)試函數(shù)，EMSPSO的平均誤差A(yù)ES遠(yuǎn)小于SCGA與SPSO。這說明，在相同迭代次數(shù)下，EMSPSO解的精度遠(yuǎn)高于其余兩種算法，EMSPSO具有更強(qiáng)的局部搜索能力與較快的收斂速度。

在收斂速度的對(duì)比實(shí)驗(yàn)中，同樣對(duì)每個(gè)測(cè)試函數(shù)進(jìn)行50次尋優(yōu)。規(guī)定平均誤差的閾值εg = 1E-4，在每次尋優(yōu)時(shí)，當(dāng)AES<εg時(shí)便停止迭代，記錄此時(shí)的評(píng)價(jià)次數(shù)與運(yùn)行時(shí)間，最后計(jì)算50次實(shí)驗(yàn)的平均值記錄于表3。實(shí)驗(yàn)結(jié)果表明，雖然增加了冗余粒子初始化策略，在一次迭代中的評(píng)價(jià)次數(shù)可能比其他兩種算法更多，但EMSPSO的評(píng)價(jià)次數(shù)與運(yùn)行時(shí)間在大部分情況下要少于SCGA與SPSO。這是由于EMSPSO具有更快的收斂速度，能在較少的迭代次數(shù)下搜索

到平均誤差小于εg的解。

在圖2中，圖（a）顯示了一維函數(shù)F2的AES收斂曲線，圖（b）顯示了二維函數(shù)F5的AES收斂曲線。可以看出，無論是一維函數(shù)還是二維函數(shù)，EMSPSO的收斂速度要高于SCGA與SPSO。尤其是在進(jìn)化后期，EMSPSO的搜索精度會(huì)快速提高，說明算法具有較好的局部搜索能力；而且，EMSPSO的收斂曲線幾乎沒有抖動(dòng)，而SPSO有很大波動(dòng)，這表明EMSPSO具有更好的穩(wěn)定性。

5結(jié)語(yǔ)

為了提高多模態(tài)粒子群優(yōu)化算法的搜索性能，平衡算法的開發(fā)與探索能力，提出了一種基于多種群的改進(jìn)粒子群算法。該算法在SPSO的基礎(chǔ)上改進(jìn)了種群生成策略，提高了算法收斂的穩(wěn)定性。并在迭代尋優(yōu)的過程中引入了冗余粒子重新初始化策略，提高了粒子的利用率和算法的搜索效率。同時(shí)改進(jìn)了速度更新公式，有效地避免遺漏適應(yīng)度較優(yōu)的極值點(diǎn)，使算法的開發(fā)與探索能力得到均衡。文章對(duì)EMSPSO算法的計(jì)算復(fù)雜度進(jìn)行分析，并將其與SCGA和SPSO進(jìn)行了對(duì)比實(shí)驗(yàn)。理論分析與實(shí)驗(yàn)結(jié)果表明，EMSPSO具有更好的多模態(tài)尋優(yōu)性能，對(duì)于解決多模態(tài)函數(shù)優(yōu)化問題具有收斂速度快、搜索精度高、穩(wěn)定性好的優(yōu)點(diǎn)。

參考文獻(xiàn)：

[1]

呂明偉.基于相似度模型的多模態(tài)粒子群優(yōu)化算法研究[D].大連：大連理工大學(xué)，2013：10-13.（LYU M W. Research on multimodal particle swarm optimization algorithm based on similarity model [D]. Dalian： Dalian University of Technology， 2013， 10-13.）

[2]

劉宇，呂明偉，李維佳，等.基于物種的自適應(yīng)多模態(tài)粒子群優(yōu)化算法[J].山東大學(xué)學(xué)報(bào)（理學(xué)版），2011，46（5）：91-96.（LIU Y， LYU M W， LI W J， et al. Adaptively speciesbased multimodal particle swarm optimization [J]. Journal of Shandong University （Natural Science）， 2011， 46（5）： 91-96.）

[3]

KENNEDY J， EBERHART R. Particle swarm optimization [C]// Proceedings of the 1995 IEEE International Conference on Neural Networks. Piscataway， NJ： IEEE， 1995， 4： 1942-1948.

[4]

HORN J. The nature of niching： genetic algorithm and the evolution of optimal， cooperative population [D]. UrbanaChampaign： University of Illinois at UrbanaChampaign， 1997： 17-21.

[5]

WEI L， ZHAO M. A niche hybrid genetic algorithm for global optimization of continuous multimodal functions [J]. Applied Mathematics and Computation， 2005， 160（3）： 649-661.

[6]

LI J P， BALAZS M E， PARKS G T， et al. A species conserving genetic algorithm for multimodal function optimization [J]. Evolutionary Computation， 2002， 10（3）： 207-234.

[7]

陳娟，徐立鴻.動(dòng)態(tài)小生境遺傳算法在多模函數(shù)優(yōu)化中的應(yīng)用[J].同濟(jì)大學(xué)學(xué)報(bào)（自然科學(xué)版），2006，34（5）：684-688.（CHEN J， XU L H. A dynamic niche genetic algorithm for multimodal function optimization [J]. Journal of Tongji University （Natural Science）， 2006， 34（5）： 684-688.）

[8]

LI X. Adaptively choosing neighbourhood bests using species in a particle swarm optimizer for multimodal function optimization [M]// DEB K. Genetic and Evolutionary Computation—GECCO 2004， LNCS 3102. Berlin： Springer， 2004：105-116.

[9]

PASSARO A， STARITA A. Particle swarm optimization for multimodal function： a clustering approach [J]. Journal of Artificial Evolution and Application， 2008， 2008（2）：Article No. 8.

[10]

SEO J H， IM C H， HEO C G， et al. Multimodal function optimization based on particle swarm optimization [J]. IEEE Transactions on Magnetics， 2006， 42（4）： 1095-1098.

[11]

CLERC M， KENNEDY J. The particle swarmexplosion， stability， and convergence in a multidimensional complex space [J]. IEEE Transactions on Evolutionary Computation， 2002， 6（1）： 58-73.

[12]

GOLDBERG D E， RICHARDSON J. Genetic algorithms with sharing for multimodal function optimization [C]// Genetic algorithms and their applications： Proceedings of the 2nd International Conference on Genetic Algorithms. Hillsdale， NJ： Lawrence Erlbaum Associates， 1987： 41-49.

[13]

IWAMATSU M. Multispecies particle swarm optimizer for multimodal function optimization [J]. IEICE Transactions on Information and Systems， 2006， E89D（3）：1181-1187.

[14]

PARROTT D， LI X. Locating and tracking multiple dynamic optima by a particle swarm model using speciation [J]. IEEE Transactions on Evolutionary Computation， 2006， 10（4）： 440-458.

[15]

吳江，胡捍英，吳瑛.面向應(yīng)用的快速多峰尋優(yōu)算法[J].計(jì)算機(jī)應(yīng)用研究，2008，25（12）：3617-3620.（WU J， HU H Y， WU Y. Applicationoriented fast optimizer for multipeak searching [J]. Application Research of Computers， 2008， 25（12）： 3617-3620.）