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

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

關(guān)鍵詞：粒子群優(yōu)化算法； 郭濤算法； 全局劣汰策略； 基于全局劣汰策略的混合粒子群優(yōu)化算法

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

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

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

1背景知識(shí)

1．1粒子群優(yōu)化算法一般原理

PSO算法是一種基于群體隨機(jī)搜索機(jī)制的演化算法。與遺傳算法不同，在PSO算法中，將最優(yōu)化問(wèn)題的潛在解看做是搜索空間中一個(gè)沒(méi)有質(zhì)量和體積但具有飛行速度和位置的粒子。粒子之間進(jìn)行信息交換與協(xié)作，依靠粒子自身經(jīng)驗(yàn)和同伴經(jīng)驗(yàn)不斷進(jìn)行趨優(yōu)演化。

1．2郭濤算法簡(jiǎn)介

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

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

為了克服PSO算法的早熟現(xiàn)象，人們又相繼提出了許多改進(jìn)算法[10，13]，但所有這些算法的效果并不明顯，必須尋求新的方法來(lái)解決這一關(guān)鍵問(wèn)題。

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

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

測(cè)試函數(shù)的計(jì)算結(jié)果均遠(yuǎn)遠(yuǎn)優(yōu)于PSO算法與GuoA算法的計(jì)算結(jié)果。這說(shuō)明將PSO算法與GuoA算法的優(yōu)點(diǎn)融合在一起所得到的GTPSO算法是成功的。GTPSO算法在保持PSO算法快速收斂的基礎(chǔ)上，吸收了GuoA算法的堅(jiān)韌性和保持種群多樣性等優(yōu)點(diǎn)，有效地改進(jìn)了算法的全局收斂性能，使GTPSO算法在處理復(fù)雜多峰非凸的全局優(yōu)化問(wèn)題的演化過(guò)程中，很好地避免了早熟現(xiàn)象的發(fā)生，從而可以得到問(wèn)題的最優(yōu)解。

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

參考文獻(xiàn)：

[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]郭濤，康立山，李艷．一種求解不等式約束下函數(shù)優(yōu)化問(wèn)題的新算法[J]．武漢大學(xué)學(xué)報(bào)：自然科學(xué)版，1999，45（5)：771－775.

[9]李艷，康卓，劉溥．郭濤算法及其應(yīng)用[J]．武漢汽車(chē)工業(yè)大學(xué)學(xué)報(bào)，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]王凌．智能優(yōu)化算法及其應(yīng)用[M]．北京：清華大學(xué)出版社，2004:1－54.

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

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

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