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

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

關鍵詞：微粒群優化; 模擬退火算法; 逃逸位置

中圖分類號：TP301．6文獻標志碼：A

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

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

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

1基本粒子群優化算法

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

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

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

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

3．2實驗結果與討論

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

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

4結束語

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

參考文獻：

[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－hua. 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.

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