融合混沌和捕食搜索的混合粒子群算法

王 濤，劉冬華

(暨南大學(xué)信息科學(xué)技術(shù)學(xué)院，廣州510632)

粒子群優(yōu)化算法(簡稱PSO)是由Kennedy J和Eberhart R·C于1995年提出的一種優(yōu)化算法[1]，粒子群算法源于對鳥群和魚群群體運動行為的研究.粒子群優(yōu)化算法由于其算法的簡單，易于實現(xiàn)，參數(shù)少，收斂速度快，所以發(fā)展十分迅速，且在其他領(lǐng)域得到很好的應(yīng)用.與其他智能算法類似，粒子群算法也存在易陷入早熟收斂和局部尋優(yōu)能力差等缺點.目前解決這些問題的主要方法是增加種群的多樣性以及和其他算法融合等[2－4].文獻[5]引用了捕食搜索策略，巧妙地平衡局域搜索和全局搜索的矛盾，利用較少的粒子數(shù)解決高維規(guī)劃問題，搜索速度較快且能避免陷入局部最優(yōu).

本文提出了一種用復(fù)制函數(shù)優(yōu)化的融合混沌與捕食搜索的混合粒子群算法(簡稱CPSPSO)，該算法首先利用混沌的遍歷性產(chǎn)生初始種群，以克服種群初始化的盲目性和隨機性;其次結(jié)合了捕食搜索策略通過限制的調(diào)節(jié)，控制粒子群搜索空間的增大和減小，從而平衡搜索能力和開發(fā)能力.測試結(jié)果表明，CPSPSO用于復(fù)制多峰函數(shù)優(yōu)化時表現(xiàn)出良好的全局尋優(yōu)能力，可提高優(yōu)化計算效率.

1 標準粒子群算法

設(shè)一個由m個無重量和體積的粒子組成的群體在n維搜索空間中以一定的速度飛行.第i個粒子的位置表示為:

第i個粒子的速度表示為:

vi=(vi1，vi2，…，vin)

第i個粒子經(jīng)歷過的歷史最優(yōu)點表示為:

pi=(pi1，pi2，…，pin)

群體內(nèi)(或鄰域內(nèi))所有粒子經(jīng)歷過的最優(yōu)點表示為:

pbest=(pbest，1，pbest，2，…，pbest，n)

則粒子的位置和速度根據(jù)以下的方程進行變化:

其中:c1和c2為學(xué)習(xí)因子，一般為正常數(shù).ζ，η∈U[0，1]，是在[0，1]區(qū)間內(nèi)的均勻分布的偽隨機數(shù).w為慣性權(quán)重，一般取在0和1之間.

2 捕食策略的基本原理

捕食搜索(PS)算法是由巴西學(xué)者Alexandre Linhares[6－7]在 1988 年提出的一種用于解決組合優(yōu)化問題的模擬動物捕食行為的搜索策略.捕食搜索策略基本思想:在沒有發(fā)現(xiàn)獵物和獵物的跡象時在整個捕食空間沿著一定的方向以很快的速度尋找獵物;一旦發(fā)現(xiàn)獵物或者發(fā)現(xiàn)有獵物的跡象，它們就立即改變自己的運動方式，減速速度，不停地巡回，在發(fā)現(xiàn)獵物或者有獵物跡象的附近區(qū)域進行集中地區(qū)域搜索，持續(xù)不斷地接近獵物.在搜尋一段時間沒有找到獵物后，捕食動物將放棄這種集中地區(qū)域，而繼續(xù)在整個捕食空間尋找獵物[8].

3 混合算法的描述及數(shù)值實驗

3.1 混沌分散的群體初始化

標準粒子群算法的初始值是隨機產(chǎn)生的，容易陷入早熟，我們利用混沌的遍歷性進行搜索跳出局部最優(yōu)，將會有助于求解效率的提高與解得質(zhì)量的改善.比較有名的混沌模型是一維Logistic映射，其迭代公式為

其中:k為迭代次數(shù);μ為控制系統(tǒng)混沌行為的的參數(shù)，當(dāng) μ 值確定后，又任意初始值 x0∈[0，1]，可迭代出一個確定的時間序列 x1，x2，…，xk.已經(jīng)證明，當(dāng)μ=4時，系統(tǒng)沒有穩(wěn)定解，是[0，1]區(qū)間的滿映射，式(3)完全處于混沌狀態(tài).

3.2 基于捕食策略的粒子群算法的基本思想

粒子群算法有著收斂速度快、全局尋優(yōu)能力強、計算簡單和魯棒性好等優(yōu)點，但其缺點是易陷入局部極優(yōu)，搜索精度不高.為避免陷入局部最優(yōu)，并且實現(xiàn)局部搜索與全局搜索的平衡，將捕食搜索策略引入到標準的粒子群算法當(dāng)中.

為了把捕食搜索策略引入標準粒子群算法，本文將限制定義為每個粒子在解空間中的搜索速度，并在解空間中設(shè)置級限制，則在限制L上速度為v=vL/Numlevel.在最小限制L上初始化粒子群，使用標準粒子群算法更新式(1)與(2)搜索，試圖找到較優(yōu)解.若在Cthreshold次內(nèi)不能找到較優(yōu)解，則在限制L+1上混沌初始化，再次用式(1)與(2)進行搜索.若找到更好解，則替代較優(yōu)解，并且重新計算限制，重復(fù).通過限制級別調(diào)節(jié)，從而平衡探索能力與開發(fā)能力.其中:Numlevel為總限制級別，Cthreshold為增大限制等級的閾值，Lthreshold為放棄局部搜索的閾值，L為限制等級.

3.3 算法流程

步驟1:初始化粒子群中的粒子的位置和速度，對粒子位置用式(3)和式(4)混沌初始化，隨機選擇初始解 gbest，c=0，L=0;

步驟2:根據(jù)式(1)，(2)更新粒子的位置和速度，迭代n次，得到一個歷史最優(yōu)解;

步驟3:如果 p ＜ gbest，gbest=p，轉(zhuǎn)步驟 2;否則，c=c+1，轉(zhuǎn)步驟 4;

步驟4:如果c＜cthreshold，轉(zhuǎn)步驟2;否則，L=L+1，轉(zhuǎn)步驟5;

步驟5:如果L＜Lthreshold，初始化粒子種群，轉(zhuǎn)步驟2;否則L=Numlevel－L，轉(zhuǎn)步驟2.

3.4 數(shù)值仿真實驗

3.4.1 測試函數(shù)

為了測試CPSPSO的性能，使用了3個常用Benchmarks多變量測試函數(shù)(表1)來進行試驗，并且將實驗結(jié)果與標準粒子群算法(PSO)，一般混沌粒子群算法(CPSO)的測試結(jié)果進行比較

表1 常用Benchmarks多變量測試函數(shù)

3.4.2 參數(shù)設(shè)置

在CPSPSO中，由于全局搜索能力和局部搜索能力的平衡主要是靠限制L來實現(xiàn)的，而學(xué)習(xí)因子和慣性權(quán)重作用于內(nèi)循環(huán)當(dāng)中，對全局搜索能力和局部搜索能力并沒有太大的影響，所以，本文采用了固定學(xué)習(xí)因子和慣性權(quán)重，即c1=c2=2，ω=0.9－0.5t/incircul.另外，根據(jù)反復(fù)試驗，本文同時調(diào)整以下3個參數(shù)，可以取得最優(yōu)解:

Numlevel=粒子維數(shù)+1=9

Cthreshold=粒子維數(shù)=8

Lthreshold=2

incircul(內(nèi)循環(huán)次數(shù))=400 outcircul(外循環(huán)次數(shù))=50

在作為對比的標準粒子群算法中，本文采用了時變慣性權(quán)重ω=0.9－0.5t/tmax，和異變學(xué)習(xí)因子c1=2t/tmax+0.5，c2= －2t/tmax+2.

在PSO 與CPSO 中 c1+c2=2.0，ω =0.8最大迭代次數(shù)為2 000.

CPSPSO，CPSO，PSO 種群的規(guī)模 N=100，維數(shù)是每個函數(shù)D表達中n的值.

3.4.3 實驗結(jié)果及分析

函數(shù)測試數(shù)據(jù)是利用Matlab編程實現(xiàn)，每個算法運行30次，取其平均值，實驗結(jié)果如下表2所示.以上述3個Benchmarks函數(shù)為測試函數(shù)，最大迭代次數(shù)為2 000，每個算法運行30次，計算最優(yōu)解平均值，實驗結(jié)果如表3所示.圖1～3是上述3個Benchmarks函數(shù)運行30次后求得的平均最優(yōu)解的收斂曲線圖.從表2、3中可以看出CPSPSO不僅優(yōu)于PSO而且優(yōu)于CPSO.

表2 迭代次數(shù)結(jié)果比較

表3 最優(yōu)結(jié)果比較

4 結(jié)語

本文提出了一種用于復(fù)雜函數(shù)優(yōu)化的融合混沌和捕食搜索的混合粒子群算法.該算法利用混沌的遍歷性初始種群，以克服種群初始化時的隨機性.在搜索過程中運用了捕食策略，通過限制的調(diào)節(jié)，控制粒子群搜索空間的增大和減小，從而平衡搜索能力和開發(fā)能力.克服了標準粒子群易陷入局部最優(yōu)的缺點.算法測試結(jié)果表明，CPSPSO具有較好的優(yōu)化搜索性能，可提高計算的效率，在高維復(fù)雜函數(shù)優(yōu)化方面有一定的實用價值.

[1] KENNEDY J，EBERHART R C.Partial Swarm Optimization[C]//Proc.IEEE International Conference on Neural Networks，Piscataway，NJ:IEEE Service Center，1995，1942 －1948.

[2] 劉瑞芳，王希云.一種混沌權(quán)重的簡化粒子群算法[J].計算機工程與應(yīng)用，2011，47(21):58 －60.

[3] 賈松衛(wèi)，高岳林.融合模擬退火和混沌的混合粒子群算法[J].計算機工程與應(yīng)用，2009，45(7):52 －55.

[4] 曾宇容，王 林，富慶亮.基于DE和PSO的混合智能算法及其在模糊EOQ模型中的應(yīng)用[J].計算機應(yīng)用研究，2012，29(2):438－441.

[5] 符 楊，孟令合，羅萍萍，等.索策略的粒子群算法在輸電網(wǎng)絡(luò)擴展規(guī)劃中的應(yīng)用[J].電力建設(shè)，2009，30(3):1－4.

[6] 喬 燁.基于捕食搜索策略粒子群算法的車輛路徑問題研究[D].西安:長安大學(xué)，2008.

[7] LINHARES A.Preying on optima:A predatory search strategy for combinatorial problems[C]//Proc.IEEE Int.Conf.Systems，Man and Cybernetics，Piscataway NJ:IEEE Service Center，1998:2974 －2978.

[8] 徐耀群，王長舉.一種萬有引力優(yōu)化算法及其收斂性分析[J].哈爾濱商業(yè)大學(xué)學(xué)報:自然科學(xué)版，2013，29(1):63－67.