一種基于全局劣汰策略的混合粒子群優化算法

摘要：提出一種改進的粒子群優化算法——基于全局劣汰策略的混合粒子群優化算法(GTPSO)。GTPSO在保持PSO算法快速收斂的基礎上，以郭濤算法（GuoA）的尋優機制確保種群的多樣性和算法的堅韌性。數值計算結果表明，對于高維(維數≥10)復雜非凸多峰函數的數值優化問題，GTPSO算法的計算結果均優于GuoA算法和粒子群優化算法。

關鍵詞：粒子群優化算法； 郭濤算法； 全局劣汰策略； 基于全局劣汰策略的混合粒子群優化算法

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

文章編號：1001－3695(2007)08－0075－04

粒子群優化算法(PSO)[1，2]是由Kennedy和Eberhart首先于1995年在IEEE國際神經網絡學術會議上提出的一種新的演化算法。其基本思想源于對自然界中鳥類等生物群體覓食行為的仿真研究，已被廣泛應用于求解連續空間中的各類數值優化問題[3]。目前，國內外提出了許多關于PSO算法的不同改進方法。文獻[4]引入了吸引算子和擴散算子以保證粒子種群的多樣性。文獻[5]提出了一種自由參數PSO算法，用于解決PSO參數選擇困難問題。文獻[6]提出了具有自組織判定能力的PSO算法。文獻[7]提出了耗損PSO算法。總之，人們對于PSO算法的改進進行了許多嘗試，取得了一定的成效，但是仍然存在著許多不容忽視的問題。例如，在求解非凸的、高維復雜多峰函數優化問題時，已有算法的效率和性能均較差，往往不能得到問題的最優解(或近似最優解)。如何進一步改進或探索性能更佳的算法是當前一個研究熱點。

1背景知識

1．1粒子群優化算法一般原理

PSO算法是一種基于群體隨機搜索機制的演化算法。與遺傳算法不同，在PSO算法中，將最優化問題的潛在解看做是搜索空間中一個沒有質量和體積但具有飛行速度和位置的粒子。粒子之間進行信息交換與協作，依靠粒子自身經驗和同伴經驗不斷進行趨優演化。

1．2郭濤算法簡介

郭濤算法(GuoA)[8，9]是基于子空間搜索(多父體重組)和群體爬山法相結合的演化算法。它通過利用少數個體所張成的子空間隨機生成新的個體，體現了隨機搜索的非凸性。此外，由于GuoA算法采用了單個體劣汰策略，算法在每次演化迭代中，只把群體中適應性能最差的個體淘汰出局，淘汰壓力較小，既保證了群體的多樣性，又可使具有較好適應性的個體能夠一直保留。實踐證明[8]，GuoA算法具有較好的堅韌性，對于不同的優化問題無須修改算法的參數，而且效率很高，可能同時找到多個最優解。下面將簡單介紹GuoA算法的一般原理。

算法每一次演化迭代都要執行式(7)，以判斷當前種群的多樣性情況，大大增加了計算開銷，使得ARPSO算法的快速收斂特性減弱，運行速度變慢；②對于高維復雜多峰函數的數值優化問題，根據diversity(S)值判斷當前種群多樣性，會出現吸引與擴散交替執行的現象，使算法失去趨優演化的搜索趨勢，不能求得問題的最優解；③在ARPSO算法中，如果當前最優個體幾乎是最優解時，其他個體必將趨于該個體，此時利用diversity(S)確定的種群多樣性必然較差，從而引起擴散，偏離了最優解所在的方向，使算法不容易得到問題的最優解。這一缺陷最突出表現是算法往往耗費大量的時間，才有可能得到一個近似最優解。

為了克服PSO算法的早熟現象，人們又相繼提出了許多改進算法[10，13]，但所有這些算法的效果并不明顯，必須尋求新的方法來解決這一關鍵問題。

通過大量實驗與詳細分析可見，GuoA算法所具有的優點恰是解決此問題的一個好方法。這是因為在GuoA算法中，通過對新種群中最差個體的淘汰來實現算法的進化，個體之間的競爭壓力較小，體現了群體爬山進化的思想[8，9]；又由于GuoA算法在淘汰最差個體時是利用所張成子空間中一個隨機個體進行的，每次均在種群中增加一個不具有父代種群特性的個體，既保持了種群的多樣性，又使算法在搜索問題的解時具有極好的堅韌性[9]。這一點主要表現在，如果使算法有足夠的運行時間，總能得到最優解。但是，也正是由于GuoA算法每次進化只淘汰一個最差個體，使得算法的收斂速度很慢，對于多維函數往往需要耗費大量時間才能得到問題的最優解，甚至慢得讓人不能忍受。了解了GuoA算法的優缺點，不難發現這樣一個事實：PSO算法的快速收斂優點與GuoA算法利用劣汰策略保持種群多樣性的優點是優勢互補的，而且后者產生子空間中隨機個體的方法簡單、快捷，只需極少的計算量，卻改善了種群的多樣性。由此很自然地聯想到，將GuoA算法與PSO算法的優點相融合，得到一種合理的改進方案，以解決早熟問題。

由表2中數值計算結果的對比可以看出，GTPSO算法對于上述四個典型的高維(維數≥10)復雜非凸多峰benchmark

測試函數的計算結果均遠遠優于PSO算法與GuoA算法的計算結果。這說明將PSO算法與GuoA算法的優點融合在一起所得到的GTPSO算法是成功的。GTPSO算法在保持PSO算法快速收斂的基礎上，吸收了GuoA算法的堅韌性和保持種群多樣性等優點，有效地改進了算法的全局收斂性能，使GTPSO算法在處理復雜多峰非凸的全局優化問題的演化過程中，很好地避免了早熟現象的發生，從而可以得到問題的最優解。

在當前多種優秀演化算法(如遺傳算法、蟻群算法、GuoA算法、粒子群優化算法和思維進化算法)相互割據的形式下，如何將各種算法相互取長補短，以發展性能更優的混合演化算法是演化計算領域中一個研究熱點[12~14]。本文正是基于此，將具有快速收斂性的PSO算法和具有堅韌性的GuoA算法巧妙融合，提出了一種更適于求解高維、復雜、非凸多峰函數的GTPSO算法。今后，除了利用更多的復雜多峰函數對該算法的性能繼續測試之外，還將進一步探討該算法是否能夠吸取蟻群算法和思維進化算法等其他優秀演化算法的優點，使之更加高效通用。

參考文獻：

[1]KENNEDY J， EBERHART R C. Particle swarm optimization[C]//Proc of the IEEE International Conference on Neural Networks.Piscataway， NJ: IEEE Service Center， 1995:19421948.

[2]SHI Y， EBERHART R C. A modified particle swarm optimizer[C]//Proc of the IEEE International Conference on Evolutionary Computation. Piscataway，NJ: IEEE Press，1998:69－73.

[3]BERGH Frans Van den. An analysis of particle swarm optimizers[D].[S.l.]: University of Pretoria， 2001:1－86.

[4]RIGEST J， VESTERSTR J S. A diversityguided particle swarm optimizer:the ARPSO， 2002－02[R].[S.l.]: Universuty of Aarhus， 2002.

[5]CLERC M， KENNEDY J. The particle swarm: explosion， stability， and convergence in a multi dimensional complex space[J]. IEEE Journal of Evolutionary Computation， 2002，6(1):58－73.

[6］SELMAN B，KAUTZ H，COHEN B. Noise strategies for improving local search[C]//Proc of the 12th National Conference on AI ，American Association for Artificial Intelligence.Seattle:[s.n.]，1994:337－343.

[7]XIE Xiaofeng， ZHANG Wenjun， YANG Zhilian.Dissipative particle swarm optimization[C]//Proc of the 2002 Congress on Evolutionary Computation. Honolulu，HI:IEEE， 2002:14561461.

[8]郭濤，康立山，李艷．一種求解不等式約束下函數優化問題的新算法[J]．武漢大學學報：自然科學版，1999，45（5)：771－775.

[9]李艷，康卓，劉溥．郭濤算法及其應用[J]．武漢汽車工業大學學報，2000，22(3)：101104.

[10]KNNEDY J， EBERHART RC.Swarm intelligence[M].[S.l.]: Morgan Kaufmann Publishers，2001:1100.

[11]CLERC M.The swarm and the queen:toward a deterministic and adaptive particle swarm optimization[C]//Proc of CEC.Piscataway:IEEE Press，1999:19511957.

[12]王凌．智能優化算法及其應用[M]．北京：清華大學出版社，2004:1－54.

[13]徐宗本．計算智能—模擬進化計算[M]．北京：高等教育出版社，2005:111132.

[14]黃席樾，張著洪，何傳江，等．現代智能算法理論及應用[M]．北京：科學出版社，2005：283－382.

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