基于模擬退火算法的可逃逸粒子群算法

摘要：通過引入模擬退火算法來保證PSO的全局收斂性，在群體最優(yōu)信息陷入停滯時引入位置逃逸機(jī)制保持前期搜索速度快的特性。仿真結(jié)果表明本算法不但具有好的全局收斂性，而且有好的收斂速度。

關(guān)鍵詞：微粒群優(yōu)化; 模擬退火算法; 逃逸位置

中圖分類號：TP301．6文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2008)05-1326-02

微粒群優(yōu)化是由Kennedy 和 Eberhart[1，2]于 1995年提出的，是群智能的代表性方法之一。相比于其他演化算法， PSO算法對解決高維復(fù)雜問題具有很大的優(yōu)越性。然而， 當(dāng)遇到某些具有較多局部極小點(diǎn)的搜索空間時， PSO 也會顯示其不足之處，特別是當(dāng)微粒在空間中運(yùn)行到局部最優(yōu)解附近時，群體的搜索效率可能會突然大大降低。增大微粒數(shù)目對算法性能有一定改善，但不能從根本上解決問題。如果為PSO算法提供一種新機(jī)制，使其在陷入局部最優(yōu)時，以更大概率跳出局部最優(yōu)位置，進(jìn)入解空間的其他區(qū)域進(jìn)行搜索，PSO算法的全局搜索能力就可大大增強(qiáng)。

針對這個問題，許多學(xué)者做了大量工作來改進(jìn)算法的性能。有的從參數(shù)的控制出發(fā)[2]，有的從增加群體多樣性出發(fā)[3~6]，有的從隨機(jī)優(yōu)化算法的全局收斂性條件出發(fā)[7~9]。本文提出了一種基于模擬退火算法的可逃逸微粒群算法。通過微粒群局部收斂性與模擬退火全局收斂性[10]的結(jié)合，有效地克服了微粒群算法的早熟收斂，又通過加入可逃逸機(jī)制加快了收斂速度。

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

PSO算法與其他演化算法相似， 也是基于群體的， 根據(jù)對環(huán)境的適應(yīng)度將群體中的個體移動到好的區(qū)域。然而它不像其他演化算法那樣對個體使用演化算子， 而是將每個個體看做D維搜索空間中的一個沒有體積的微粒點(diǎn)， 在搜索空間中以一定的速度飛行。這個速度根據(jù)它本身的飛行經(jīng)驗(yàn)以及同伴的飛行經(jīng)驗(yàn)進(jìn)行動態(tài)調(diào)整。第i個微粒表示為Xi=xi1，xi2，…，xid，它經(jīng)歷過的最好位置記為pij， 也稱為Pbest。在群體所有微粒經(jīng)歷過的最好位置的索引號用符號g，也稱為Gbest

2模擬退火算法的逃逸微粒群

在理論上已經(jīng)證明，基本微粒群算法并不能保證收斂于最優(yōu)解，甚至是局部最優(yōu)解[9]。所以用所有微粒的當(dāng)前位置與全體最好位置相同時算法停止作為收斂準(zhǔn)則是有缺陷的。模擬退火算法已經(jīng)被證明依概率1 收斂于全局最優(yōu)解集，因此可以使用模擬退火算法作為PSO算法的收斂判據(jù)。當(dāng)基本微粒群算法收斂到某一解pg時，用pg作為模擬退火算法的初始點(diǎn)進(jìn)行搜索，根據(jù)Metropolis準(zhǔn)則接受新解y 。如果存在這樣的一個解y，使得f(y)

在現(xiàn)實(shí)生物界中，當(dāng)物種生存密度過大時，群體有自動分家并找到新生存空間的特性。本文分析了PSO算法種群多樣性與微粒位置的關(guān)系，指出可以通過控制微粒位置來協(xié)調(diào)算法的種群多樣性。結(jié)合PSO算法的特性，對PSO算法模型進(jìn)行了改進(jìn)，給出了一種基于微粒位置的逃逸機(jī)制，用如下公式描述微粒的這種行為：

3．2實(shí)驗(yàn)結(jié)果與討論

本文同時用分段式微粒群優(yōu)化算法和基本微粒群優(yōu)化算法對以上函數(shù)進(jìn)行優(yōu)化測試實(shí)驗(yàn)。共有兩組測試實(shí)驗(yàn)：第一組測試實(shí)驗(yàn)主要考察兩種算法尋優(yōu)時的達(dá)優(yōu)率；第二組實(shí)驗(yàn)主要考察兩種算法尋優(yōu)時的搜索速度。實(shí)驗(yàn)中兩種算法的群體規(guī)模均為20，慣性權(quán)重為ω的值均為從1．2線性遞減至0．001 2，c1=c2=1．9。對于模擬退火算法，溫度衰減函數(shù)取tk+1=α×tk， Markov鏈長取常數(shù)L，鄰域結(jié)構(gòu)取每維為[Yk，i-q，Yk， j+q]的超矩形。計(jì)算實(shí)例如表1所示。

由表1可知，對于Rosenbrock、Levy F5、Ackley、Rastrigin和Alpine函數(shù)，NEPSO優(yōu)化算法在實(shí)驗(yàn)中均能很好地逃脫局部極值點(diǎn)，并都能以1的概率找到全局最好解。

4結(jié)束語

從表1中可以看出，通過NEPSO計(jì)算取得最優(yōu)值的概率要高于PSO獲得最優(yōu)值的概率，同時NEPSO獲得最優(yōu)解的迭代次數(shù)也比標(biāo)準(zhǔn)PSO少。另外，在處理高維優(yōu)化問題時， NEPSO 優(yōu)化性能更加良好。以上結(jié)果說明了NEPSO與標(biāo)準(zhǔn)PSO相比，在優(yōu)化效率和優(yōu)化性能方面有比較大的提升；而NEPSO的算法運(yùn)行時間與標(biāo)準(zhǔn)PSO相差不大。由此可見，NEPSO是一種穩(wěn)健的全局收斂算法。

參考文獻(xiàn)：

[1]KENNEDY J， EBERHART R. Particle swarm optimization[C]//Proc of IEEEInt Conf on Neural Networks. Perth:[s.n.]， 1995:1942－1948.

[2]EBERHART R， KENNEDY J. A new optimizer using particle swarm theory[C]//Proc of the 6th Int Symposium on Micro Machine and Human Science. Nagoya:[s.n.]， 1995:39-43.

[3]SHI Y， EBERHART R C.A modified particle swarm optimizer[C]//Proc of IEEE International Conference on Evolutionary Computation. Piscataway: IEEE Press， 1998:69-73.

[4]SUGANTHAN P N. Particale swarm optimizer with neighbourhood operator[C]//Proc of Congress on Evolutionary Computation. Pisca-taway: IEEE Press， 1999:1958－1961.

[5]KENNEDY J. Small worlds and mega－minds: effects of neighbourhood topology on particle swarm performance[C]//Proc of Congress on Evolutionary Computation. Piscataway: IEEE Press， 1999:1931－1938.

[6]KENNEDY J. Stereotyping: improving particle swarm performance with cluster analysis[C]//Proc of Congress on Evolutionary Computation. Piscataway: IEEE Press， 2000:1507－1512.

[7]BERGH F V D， ENGELBRECHT A P. Cooperative learning in neural networks using particle swarm optimizers[J]. South African Computer Journal， 2000， 26(11): 84-90.

[8]ZENG Jian－chao， CUI Zhi－h(huán)ua. A guaranteed global convergence particle swarm optimizer[J]. Journal of Computer Research and Development， 2004，41(8):1333－1338.

[9]van den BERGH F. An analysis of particle swarm optimization[D]. Pretoria: University of Pretoria， 2001.

[10]KANG Li－shan， XIE Yun， YOU Shi－yong. Nonnumeric parallel algorithm－simulated annealing algorithm[M]. Beijing: Science Press， 1994.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”