新的混沌粒子群優(yōu)化算法

胥小波，鄭康鋒，李丹，武斌，楊義先

(1. 北京郵電大學(xué) 信息安全中心，北京 100876；

2. 北京郵電大學(xué) 災(zāi)備技術(shù)國家工程實驗室，北京 100876)

1 引言

粒子群優(yōu)化(PSO, particle swarm optimization)算法是由Kennedy和Eberhart在1995年提出的一種群智能優(yōu)化方法[1]。該算法因其建模簡單，收斂速度快且易于實現(xiàn)等優(yōu)點，不僅在求解組合優(yōu)化問題、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模式分類、模糊系統(tǒng)控制等傳統(tǒng)優(yōu)化問題取得了顯著的成效[2,3]，而且在通信、傳感器網(wǎng)絡(luò)、最優(yōu)路徑、資源分配、生物分子研究等領(lǐng)域得到了廣泛的應(yīng)用[4～6]。但是PSO算法在搜索的初期往往收斂較快，而在后期容易陷入局部最優(yōu)。

針對此不足，Bergh等[7]提出了Multi-start PSO算法，即每迭代若干次后，都保留歷史最優(yōu)粒子，粒子全部初始化，以提高粒子的多樣性，擴(kuò)大搜索空間。Jiao等[8]提出了一種動態(tài)慣性權(quán)重的粒子群優(yōu)化算法，慣性權(quán)重隨著迭代次數(shù)的增加而降低，在開始階段具有較強(qiáng)的全局搜索能力，而在后期以較小的慣性權(quán)重能夠收斂到最優(yōu)解。

混沌優(yōu)化算法是一種新型搜索算法，其基本思想是把變量從混沌空間變換到解空間，然后利用混沌變量具有遍歷性、隨機(jī)性和規(guī)律性的特點進(jìn)行搜索，混沌優(yōu)化方法具有全局漸進(jìn)收斂、易跳出局部極小點和收斂速度快的特點。

文獻(xiàn)[9]提出將混沌嵌入粒子群算法的思想，在粒子與種群最優(yōu)解的距離小于門限值時，進(jìn)行混沌搜索，搜索到較優(yōu)解則取代當(dāng)前粒子。混沌粒子群算法提出后，利用混沌策略與粒子群算法的結(jié)合已有不少嘗試，文獻(xiàn)[10]提出了將分段線性混沌映射結(jié)合到粒子群 (PWLCPSO) 算法，取代了經(jīng)典的logistic混沌模型。文獻(xiàn)[11]利用混沌序列產(chǎn)生傳統(tǒng)粒子群算法中的參數(shù)，提出了一種逃離局部最優(yōu)解的新思路。文獻(xiàn)[12]采用Henon混沌映射序列和隱式過濾本地搜索策略來增加收斂速度和搜索精度，可以過濾低幅振蕩，快速接近較優(yōu)解。文獻(xiàn)[13]將人工免疫系統(tǒng)(AIS)、混沌算子、粒子群優(yōu)化算法結(jié)合起來提出了一種混沌免疫粒子群(CIPSO)算法，用來解決多目標(biāo)路徑優(yōu)化問題。

綜上所述，對于混沌粒子群算法的研究目前主要集中于各種混沌映射對于算法的性能影響及利用算法混合思想與一些啟發(fā)式算法相混合。現(xiàn)有的混沌粒子群基本思想是利用混沌序列產(chǎn)生新的粒子代替原來的粒子，效果并不理想。而本文并不是將混沌與粒子群算法簡單地結(jié)合在一起，而是將混沌融入到粒子的運(yùn)動過程中，達(dá)到了較好的效果。

2 PSO算法基本思想

PSO算法模擬鳥集群飛行覓食的行為[14]。設(shè)搜索空間為D維，總粒子數(shù)為n。第i個粒子位置表示為向量Xi=(xi1, xi2,…, xiD)；第i個粒子“飛行”歷史中的過去最優(yōu)位置為Pi=( pi1,pi2, …,piD)，整個種群過去最優(yōu)位置 Pg為所有 Pi(i=1, …,n)中的最優(yōu)；第i個粒子的位置變化率（速度）為向量Vi=(vi1,vi2,…, viD)。每個粒子的位置按如下公式進(jìn)行變化：

其中，c1和 c2為正常數(shù)，稱作學(xué)習(xí)因子；rand()是介于[0,1]之間的隨機(jī)數(shù)；w是慣性權(quán)重，可以調(diào)節(jié)算法的全局和局部尋優(yōu)能力。粒子群初始位置和速度隨機(jī)產(chǎn)生，然后按式(1)和式(2)進(jìn)行迭代，直至找到滿意的解。

3 混沌粒子群算法模型

3.1 算法模型

本文受文獻(xiàn)[15]中提出的混沌蟻群（CAS）算法的啟發(fā)，并在此基礎(chǔ)上改進(jìn)，結(jié)合粒子群算法，提出了如下混沌粒子群優(yōu)化系統(tǒng)動力學(xué)模型。

其中，式(3)為粒子速度更新算法，含義與式(1)相同。式(4)為混沌變量，影響粒子的混沌程度。rid是一個小于1的正常數(shù)，定義為第i個粒子第d維的混沌因子。式(5)在粒子群的位置更新中引入混沌。t表示迭代次數(shù)，Ψd表示搜索測度，Mi表示粒子i的搜索空間向負(fù)方向移動的比例，如：Ψd=100，Mi=0.5，則表示搜索空間為[-50,50]。

混沌算法采用了文獻(xiàn)[15]中的混沌算法，即Sole等給出的混沌系統(tǒng)[16]，混沌迭代如式(6)所示。

目前己有的混沌粒子群算法主要是在進(jìn)入穩(wěn)定狀態(tài)后，用混沌序列搜索取代現(xiàn)有粒子。而本算法模擬粒子群混沌與穩(wěn)定的交替運(yùn)動過程，將混沌運(yùn)動與粒子群運(yùn)動結(jié)合到一起，并通過混沌因子來調(diào)節(jié)混沌程度，并提出了數(shù)學(xué)模型。

3.2 混沌變量

混沌變量在粒子群運(yùn)動過程中起到控制粒子混沌程度的作用。當(dāng)混沌變量Cid(t)→1時，粒子的位置更新方法為

此時，式(7)為式(6)經(jīng)過位置變換后的結(jié)果，主要是粒子個體的混沌在發(fā)揮作用。

而當(dāng)混沌變量Cid(t)→0時，粒子的位置更新方法為

可以看出，式(8)與式(2)相同，粒子群算法起主要作用。

3.3 粒子位置更新

原粒子群算法是對所有維的位置作為一個整體更新后，再計算個體歷史最優(yōu)(Pid)和群體全局最優(yōu)(Pgd)，而在本算法中對每一維更新后，計算個體歷史最優(yōu)(Pid)和群體全局最優(yōu)(Pgd)，速度矢量關(guān)系如式(9)所示。

矢量關(guān)系圖如圖1所示。傳統(tǒng)的粒子群算法更新時，將 vi(t)看作一個整體，直接從 Xi(t)更新Xi(t+1)。本算法將vi(t)看作各維度之和(如式(9)所示)對每一維的更新過程進(jìn)行遞增搜索，將搜索過程細(xì)化，增加了搜索空間，提高了搜索精度。而時間復(fù)雜度增量為O(d)，僅與維度有關(guān)，與粒子個數(shù)n無關(guān)，達(dá)到以較小的時間代價來提高搜索精度的效果。相對于傳統(tǒng)的粒子群算法，時間復(fù)雜度提高了O(d)倍，而相對于現(xiàn)有的混沌粒子群算法，時間復(fù)雜度降低了M倍，其中，M代表混沌搜索的步長。

圖1 粒子位置更新過程

3.4 混沌與穩(wěn)定的交替

一直處于混沌或穩(wěn)定狀態(tài)對于尋找最優(yōu)值沒有任何意義，只有在混沌與穩(wěn)定的交替中才能不斷向最優(yōu)結(jié)果靠近。也就是說，要在粒子穩(wěn)定時，引入混沌，跳出局部最優(yōu)；在粒子不穩(wěn)定時，加速向最優(yōu)值靠近，加快收斂過程。

為了定義粒子是否處于穩(wěn)定狀態(tài)，引入了2個變量

其中，move表示粒子當(dāng)前移動距離，stabel表示粒子當(dāng)前位置與粒子歷史上最優(yōu)值之間的距離。

進(jìn)一步，將穩(wěn)定狀態(tài)條件定義為

其中，T表示總迭代次數(shù)。當(dāng)粒子移動距離和距離歷史最優(yōu)值較近時，粒子處于穩(wěn)定狀態(tài)，此時，令混沌變量Cid(t)=0.999，引入混沌。

當(dāng)粒子不穩(wěn)定時，滿足條件：

即當(dāng)粒子移動距離和距離歷史最優(yōu)值較遠(yuǎn)時，粒子處于運(yùn)動狀態(tài)，為了加速收斂過程，令Xid(t)=Pid(t)，保留歷史最優(yōu)值。

4 混沌粒子群算法數(shù)值測試

4.1 混沌粒子群模型的非線性動力學(xué)行為

為了分析混沌粒子群模型的非線性動力學(xué)行為，利用這個優(yōu)化模型來解決Rastrigin函數(shù)優(yōu)化問題。目標(biāo)函數(shù)如下：

其中，-5.12≤xi≤5.12，l=30，最小值在30維x變量均為0時，全局最小值為0。令混沌粒子群算法中：慣性因子w=0.729 8，學(xué)習(xí)因子c1=c2=1.496 2，迭代次數(shù)為 1 000，粒子個數(shù) N=20，混沌因子r(i,d)=0.5+(0.005)rand，混沌變量初值為 Cid(0)=0.999，搜索測度Ψd=10.24，移動因子Mi=0.5。圖2是混沌變量隨迭代過程的變化曲線，開始階段 c(t)由1減為0，是從混沌到粒子群的過程，當(dāng)粒子群穩(wěn)定后，c(t)為1，引入混沌跳出局部最優(yōu)解。

圖2 混沌變量隨時間變化曲線

圖3是粒子1在搜索最優(yōu)解時X1的變化過程，從圖中可以看出，粒子1在對X1的搜索過程中，在穩(wěn)定和混沌之間交替，并向最優(yōu)值靠近。圖4是所有粒子搜索X1最優(yōu)值過程，可以觀察到整個混沌粒子群也是在混沌與穩(wěn)定之間交替搜索，跳出局部最優(yōu)，向全局最優(yōu)接近。

圖3 粒子1搜索X1最優(yōu)值過程

圖4 粒子群搜索X1最優(yōu)值過程

圖5 是粒子1的目標(biāo)函數(shù)值變化過程，圖6是整個粒子群的目標(biāo)函數(shù)值變化過程。可以看到，粒子的值總體趨勢越來越小，但在前0.9T次迭代過程中會有一些起伏的現(xiàn)象，這是因為粒子在混沌的作用下不斷在周圍探索，以跳離局部最優(yōu)。在最后0.1T迭代過程中，沒有引入混沌，所有粒子在粒子群算法下達(dá)到最優(yōu)狀態(tài)。

圖5 粒子1的目標(biāo)函數(shù)值變化過程

圖6 粒子群的目標(biāo)函數(shù)值變化過程

圖7 是粒子群的最優(yōu)值變化過程，隨著迭代次數(shù)增加，最優(yōu)值遞減。最后得到的優(yōu)化極值為4.887 8×10-7，各維度的最優(yōu)位置值均小于1×10-4。

圖7 粒子群最優(yōu)值變化過程

本算法的參數(shù)中，慣性因子w、學(xué)習(xí)因子可根據(jù)粒子群算法最優(yōu)來設(shè)置，搜索測度、移動因子可根據(jù)初始搜索條件進(jìn)行計算得出，混沌變量初值為Cid(0)=0.999，比較重要的參數(shù)是混沌因子的大小，它影響了初始混沌搜索的時間，下面令混沌因子為：r(i,d)=0.1+(0.001)rand進(jìn)行數(shù)值仿真，說明混沌因子參數(shù)對該算法搜索過程的影響。

圖 8是混沌變量隨時間變化曲線，圖 9和圖10分別是單個粒子、粒子群對變量X1的搜索過程，圖11和圖12分別給出了單個粒子、粒子群的能量函數(shù)時間演化，圖13給出了整個粒子群最優(yōu)值的變化過程。通過對比圖8～圖13與圖2～圖7，可以看出混沌因子對算法搜索過程的影響，初始混沌搜索過程由原來的20次迭代變?yōu)?00次迭代。混沌因子 r(i,d)越小，混沌變量減小的過程越慢，混沌搜索時間越長，有利于搜索到較優(yōu)值，但初始混沌收斂過程越長。最后得到的優(yōu)化極值為1.388 50×10-7，各維度的最優(yōu)位置值均小于1×10-4。

圖8 混沌變量隨時間變化曲線

圖9 粒子1搜索X1最優(yōu)值過程

圖10 粒子群搜索X1最優(yōu)值過程

圖11 粒子1的目標(biāo)函數(shù)值變化過程

圖12 粒子群的目標(biāo)函數(shù)值變化過程

圖13 粒子群最優(yōu)值變化過程

4.2 算法性能數(shù)值測試

為了檢測混沌粒子群算法的性能，選取5個測試函數(shù)進(jìn)行測試，它們是在進(jìn)化規(guī)劃、模擬退火、遺傳算法和粒子群優(yōu)化中廣泛使用的數(shù)值測試函數(shù)，分別如下。

Sphere 函數(shù)：

其中，-50≤xi≤50，其全局最優(yōu)點在 X=(0,0,0,…,0)，全局極值為0。

DeJong函數(shù)：

其中，-20≤xi≤20，其全局最優(yōu)點在 X=(0,0,0,…,0)，全局極值為0。

Griewank 函數(shù)：

其中，-600≤xi≤600，其全局最優(yōu)點在X= (0,0,0,…,0)，

表1 數(shù)值測試結(jié)果

全局極值為0。

Rosenbrock 函數(shù)：

其中，-100≤xi≤100，其全局最優(yōu)點在 X=(1,1,1,…,1)，全局極值為0。

Rastrigin函數(shù)：

其中，-5.12≤xi≤5.12，其全局最優(yōu)點在X=(0,0,0,…,0)，全局極值為0。

混沌粒子群參數(shù)設(shè)置為：w=0.729 8，c1=c2=1.496 2，T=1 000，r(i,d)=0.5+(0.005)rand，N=20，Cid(t)=0.999，Ψd為各自搜索空間長度，Mi=0.5，粒子初始值為 Ψd×Mi×(2rand()-1)。現(xiàn)有的粒子群算法實驗采用logistic混沌模型，最大迭代步長為15。在維度l=30的情況下，進(jìn)行50次測試取平均值的結(jié)果如表1所示，其他算法結(jié)果來自文獻(xiàn)[15]。

對比表1中的結(jié)果可以看出，本文所提出的混沌粒子群算法測試結(jié)果明顯好于粒子群、卡爾曼群、混沌螞蟻群、現(xiàn)有混沌粒子群的測試結(jié)果，搜索精度至少提升了100倍。

圖14～圖18為現(xiàn)有混沌粒子群算法與本文提出的混沌粒子群算法對5個標(biāo)準(zhǔn)測試函數(shù)進(jìn)行優(yōu)化的過程中，種群最優(yōu)值進(jìn)化曲線的對比。可以看出，相對于現(xiàn)有的混沌粒子群算法，本文提出的混沌粒子群在經(jīng)過若干代運(yùn)算之后仍保持較高的活性，可以從局部最優(yōu)中跳離出來，保持較快的收斂速度，極大地提高了對最優(yōu)值的全局搜索能力。

圖14 Sphere函數(shù)尋優(yōu)過程

圖15 DeJong函數(shù)尋優(yōu)過程

圖16 Griewank函數(shù)尋優(yōu)過程

圖17 Rosenbrock函數(shù)尋優(yōu)過程

圖18 Rastrigin函數(shù)尋優(yōu)過程

5 結(jié)束語

本文利用混沌的遍歷性和粒子群收斂快的特點，提出了一種新的混沌粒子群算法。該算法將混沌融入到粒子運(yùn)動過程中，不同于己有的混沌粒子群算法的簡單粒子序列替換，使粒子群在混沌與穩(wěn)定之間交替向最優(yōu)點靠近，并提出了一種新的混沌粒子群數(shù)學(xué)模型。本文還給出了混沌粒子群算法的非線性動力學(xué)行為分析，并和目前國際上流行的算法，如粒子群算法、卡爾曼群算法、混沌蟻群算法和現(xiàn)有混沌粒子群算法作了對比分析。文中給出的數(shù)值結(jié)果表明該方法用于解決函數(shù)最優(yōu)化問題的有效性，并且能有效避免粒子群優(yōu)化算法的早熟收斂問題，能跳出局部最優(yōu)，極大提高了計算精度和全局尋優(yōu)能力。

[1] KENNEDY J, EBERHART R C. Particle swarm optimization[A]. Proc of the First IEEE International Conference on Neural Networks[C].Perth, Australia：IEEE Press, 1995. 1942-1948.

[2] MODARES H, ALFI A, NAGHIBI-SISTANI M B. Parameter estimation of bilinear systems based on an adaptive particle swarm optimization[J]. Engineering Applications of Artificial Intelligence, 2010, 23(7):1105-1111.

[3] KARAKUZU C. Parameter tuning of fuzzy sliding mode controller using particle swarm optimization[J]. International Journal of Innovative Computing, Information and Control, 2010, 6(10):4755-4770.

[4] KULKARNI R V, VENAYAGAMOORTHY G K. Bio-inspired algorithms for autonomous deployment and localization of sensor nodes[J].IEEE Transactions on Systems, Man, and Cybernetics, 2010, 40(6):663-675.

[5] ZHANG W, LIU J, NIU Y Q. Quantitative prediction of MHC-II binding affinity using particle swarm optimization[J]. Artificial Intelligence in Medicine,2010,50(2):127-132.

[6] GHEITANCHI S, ALI F, STIPIDIS E. Particle swarm optimization for adaptive resource allocation in communication networks[J]. EURASIP Journal on Wireless Communications and Networking, 2010. 1-13.

[7] BERGH F. An Analysis of Particle Swarm Optimizers[D]. Department of Computer Science, University of Pretoria, South Africa, 2006.118-123.

[8] JIAO B, LIAN Z G, GU X S. A dynamic inertia weight particle swarm optimization algorithm[J]. Chaos, Solitons & Fractals, 2008, 37(3):698-705.

[9] MENG H J, ZHENG P, WU R Y, et al. A hybrid particle swarm algorithm with embedded chaotic search[A]. Proceedings of the 2004 IEEE Conference on Cybernetics and Intelligent Systems[C]. Singapore, 2004. 367-371.

[10] XIANG T, LIAO X F, WONG K. An improved particle swarm optimization algorithm combined with piecewise linear chaotic map[J].Applied Mathematics and Computation, 2007,190(2): 1637-1645

[11] ALATAS B, AKIN E, OZER A B. Chaos embedded particle swarm optimization algorithms[J]. Chaos Solitons & fractals, 2009, 40(4):1715-1734.

[12] COELHO L D, MARIANI V C. A novel chaotic particle swarm optimization approach using Henon map and implicit filtering local search for economic load dispatch[J]. Chaos Solitons & Fractals, 2009,39(2):510-518.

[13] ZHANG Y D, JUN Y, WEI G, et al. Find multi-objective paths in stochastic networks via chaotic immune PSO[J]. Expert Systems With Applications, 2010, 37(3): 1911-1919.

[14] 高飛, 童恒慶. 基于改進(jìn)粒子群優(yōu)化算法的混沌系統(tǒng)參數(shù)估計方法[J]. 物理學(xué)報, 2006, 55(2): 577-582.GAO F, TONG H Q. Parameter estimation for system based on particle swarm optimization[J]. Acta Phys, 2006, 55(2):577-582.

[15] LI L X, PENG H P, WANG X D, et al. An optimization method inspired by chaotic ant behavior[J]. International Journal of Bifurcation and Chaos, 2006, (16): 2351-2364.

[16] SOLE R V, MIRAMONTES O, GOODWIN B C. Oscillations and chaos in ant societies[J]. Journal of Theoretical Biology, 1993,161(3): 343-357.