基于多種群的改進粒子群算法多模態(tài)優(yōu)化

謝紅俠　馬曉偉　陳曉曉　邢強

摘要：

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

關(guān)鍵詞：

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

中圖分類號：

TP18

文獻標志碼：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ù)尋優(yōu)問題，有一些問題如神經(jīng)網(wǎng)絡集成、組合投資等，不僅要在解空間中找出全局最優(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ù)。標準的PSO是單極值搜索的算法，一次只能搜索到一個極值點，對多模態(tài)問題并不適用。小生境（niche）技術(shù)[4]是一種仿生技術(shù)，將自然界中種群的概念與群體智能算法相結(jié)合，通過一定的方法，將整個種群劃分為許多個獨立的子種群，每個子種群可以獨立地進化。近幾年，將小生境技術(shù)與群體智能算法相結(jié)合，提出了一些適用于多模態(tài)優(yōu)化問題的尋優(yōu)方法。將小生境技術(shù)與遺傳算法（Genetic Algorithm， GA）相結(jié)合提出了小生境遺傳算法（Niche Genetic Algorithm， NGA）[5]與種群保護遺傳算法（Species Conserving Genetic Algorithm， SCGA）[6]等多模態(tài)優(yōu)化算法，但這些基于遺傳算法的多模態(tài)優(yōu)化方法大多存在計算開銷大、收斂速度慢、局部搜索精度低的缺陷[7]。將小生境技術(shù)與粒子群相結(jié)合，文獻[8]提出了基于種群的粒子群算法（Speciesbased PSO， SPSO），將粒子群劃分為個數(shù)自適應的種群各自獨立進化將粒子群劃分為數(shù)個種群各自獨立進化，種群的數(shù)目在進化過程中不斷變化，但是在極值點分布較分散的情況下有可能會漏掉某些較優(yōu)的解；并且SPSO在每一代的粒子中生成種群種子，這使得粒子在收斂過程中抖動，導致算法穩(wěn)定性降低。文獻[9]提出了一種基于k均值聚類算法的粒子群算法（kmeansbased PSO， kPSO），使用貝葉斯信息規(guī)則和標準k均值聚類算法自動識別聚類數(shù)

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

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

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

4.2實驗與結(jié)果分析

實驗選用精度、成功率與收斂速度三個評價標準對算法的性能進行對比。對某一極值點的尋優(yōu)精度用可使用找到的極值點pi與實際的極值點opti適應度差值的絕對值來表示，其計算公式如式（9）。

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

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

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

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

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

SCGA的交叉概率Pc=0.6，變異概率Pm=0.05[6]；SPSO采用收縮因子PSO，收縮因子χ=0.7298，c1=c2=2.05[8]；EMSPSO使用與SPSO等價的參數(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為當前迭代次數(shù)。種群距離σS、種群規(guī)模n和Ngmax是與測試函數(shù)相關(guān)的參數(shù)，參考文獻[1，8]中參數(shù)的設置，其具體取值見表2。

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

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

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

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

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

5結(jié)語

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

參考文獻：

[1]

呂明偉.基于相似度模型的多模態(tài)粒子群優(yōu)化算法研究[D].大連：大連理工大學，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]

劉宇，呂明偉，李維佳，等.基于物種的自適應多模態(tài)粒子群優(yōu)化算法[J].山東大學學報（理學版），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]

陳娟，徐立鴻.動態(tài)小生境遺傳算法在多模函數(shù)優(yōu)化中的應用[J].同濟大學學報（自然科學版），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ōu)算法[J].計算機應用研究，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.）