一種擬隨機初始化模擬退火粒子群算法

王　杰，　李慧慧，　彭金柱

(鄭州大學 電氣工程學院　河南 鄭州 450001)

?

一種擬隨機初始化模擬退火粒子群算法

王杰，李慧慧，彭金柱

(鄭州大學 電氣工程學院河南 鄭州 450001)

針對粒子群優(yōu)化算法在求解高維問題時易出現(xiàn)的早熟收斂、停滯現(xiàn)象，提出一種擬隨機初始化模擬退火粒子群算法.采用Hammersley方法對算法進行初始化，可以提高算法在高維搜索空間的搜索能力，進一步將模擬退火思想引入到粒子群優(yōu)化算法中，結合粒子群優(yōu)化算法的快速尋優(yōu)能力和模擬退火算法的概率突跳特性，使算法具有跳出局部最優(yōu)從而實現(xiàn)全局最優(yōu)的能力.分別在5個經典測試函數上測試算法的性能，仿真實驗結果表明，提出的算法有效克服了傳統(tǒng)粒子群優(yōu)化算法在求解高維空間優(yōu)化問題時易出現(xiàn)的停滯現(xiàn)象，在進化后期仍保持較強的搜索能力，提高了傳統(tǒng)粒子群優(yōu)化算法在高維空間的全局尋優(yōu)能力.

擬隨機序列； 初始化； 模擬退火； 粒子群優(yōu)化

0　引言

粒子群優(yōu)化(particleswarmoptimization,PSO)算法是一種基于群體智能的全局隨機搜索算法[1]，有很好的生物社會背景，對許多優(yōu)化問題都表現(xiàn)出較強的尋優(yōu)性能，在科學研究中得到了廣泛關注[2-4].為增加種群多樣性，提高PSO算法局部探索能力，文獻[5]將高斯變異引入到PSO中，文獻[6]則使用了變異、選擇和繁殖多種操作，同時自適應確定速度更新公式中的鄰域最佳位置以及慣性權值和加速常數.其中，基于算法融合的模擬退火PSO算法充分利用了PSO算法的快速收斂能力和模擬退火(simulatedannealing,SA)算法局部極值突跳特性的優(yōu)點，改善了傳統(tǒng)PSO算法易出現(xiàn)早熟收斂和陷入局部極值的缺點[7-9].文獻[9]將SA算法與PSO算法結合，利用SA算法的全局搜索能力，改善了PSO算法易陷入局部最優(yōu)的不足.但在求解高維空間優(yōu)化問題時，PSO中粒子會向自身歷史最佳位置或群體歷史最佳位置聚集，形成粒子種群快速趨同效應，容易出現(xiàn)局部極值、早熟收斂和停滯現(xiàn)象.為此，文獻[10]提出了協(xié)作PSO算法，利用多個獨立種群在目標搜索空間中的不同維度上分別進行搜索，每一個優(yōu)化解由多個獨立種群協(xié)作完成，每個群體只負責優(yōu)化這個解向量某些維上的分量.文獻[11]提出了一種既可以進行D維空間搜索，又能在不同維上選擇不同學習對象的新的學習策略CLPSO.CLPSO的每個粒子都隨機地向自身或非自身粒子的歷史最優(yōu)學習，并且其每一維可以向不同的粒子學習，該學習策略改善了PSO算法求解多峰值問題的性能，但算法學習過程較為復雜.

均勻分布隨機數進行初始化容易實現(xiàn)，但對高維空間問題進行初始化時，易出現(xiàn)粒子向邊緣聚集現(xiàn)象，采用Hammersley方法進行初始化的PSO算法改善了標準粒子群易早熟收斂的缺點，然而算法在求解高維多峰值問題時優(yōu)化精度較差，易陷入局部最小，算法進化后期會出現(xiàn)停滯現(xiàn)象，精度仍需進一步提高.本文提出一種擬隨機初始化模擬退火粒子群算法，從種群初始化與搜索策略兩個方面對傳統(tǒng)PSO進行改進.將改進算法(H-SA-PSO)與標準PSO算法及Hammersley初始化的PSO算法(H-PSO)進行對比分析，分別在5個通用測試函數上進行了仿真計算，驗證了算法的有效性.

1　粒子群優(yōu)化(PSO)算法

在PSO算法中，將多維搜索空間中優(yōu)化問題的解看作一個沒有質量和體積的粒子，每個粒子以一定的速度在解空間運動，每個粒子根據其自身最優(yōu)和群體最優(yōu)粒子位置調整速度.假設在一個D維的目標搜索空間中有n個粒子組成一個群落,其中第i個粒子表示為一個D維向量xi=(xi1, xi2,… ,xiD),i=1,2,…,n, 即第i個粒子在D維搜索空間中的位置為xi,每個粒子的位置代表一個潛在的解.將xi代入一個目標函數就可以計算其適應度值, 根據適應度值的大小衡量xi的優(yōu)劣.第i個粒子的速度也是一個D維向量, 記為vi=(vi1, vi2,… ,viD),i=1,2,…,n，記第i個粒子最終搜索到的最優(yōu)位置為pi= (pi1,pi2,… ,piD),i=1,2,…,n，整個粒子群最終搜索到的最優(yōu)位置為pg=(xg1,xg2，…,xgD).在每一次迭代中，粒子更新當前速度和位置為

vid(t+1)=wvid(t)+c1r1(t)(pid(t)-xid(t))+c2r2(t)(pgd(t)-xid(t)),

(1)

xid(t+1)=xid(t)+vid(t+1),

(2)

式中：c1和c2為加速常數，分別調節(jié)粒子向自身最優(yōu)位置飛行的步長與向全局最優(yōu)位置飛行的步長，通常c1+ c2≤ 4；r1, r2～ U(0,1)為兩個相互獨立的隨機函數；w為慣性常數，可以平衡全局與局部搜索能力.

2　擬隨機初始化模擬退火粒子群算法

為了使粒子能夠在較高維度的搜索空間中跳出局部最優(yōu)收斂到全局最優(yōu)點，本文提出了改進模擬退火粒子群算法，主要從種群初始化與搜索策略兩個方面對基本PSO算法進行改進.Hammersley序列是一種擬隨機低偏差序列[12]，采用此方法對PSO算法進行初始化，擬隨機序列的低偏差性使初始種群能夠均勻覆蓋整個搜索空間，可以有效改善初始種群向邊緣聚集的現(xiàn)象，從而避免算法過早收斂；同時將SA思想引入到PSO算法中，以概率接受PSO算法得到的劣解，有效地解決了標準PSO算法易陷入局部最優(yōu)尤其對高維解空間尋優(yōu)效果差的問題.

2.1初始化方法

Hammersley序列簡單描述如下[12]：

對于任意非負整數i和素數基p，定義

(3)

式中：ak[0,p-1].

(4)

由式(3)、(4)推出Φp(i)(0,1).在D維采樣空間中，設互異素數序列p1, p2,… , pD-1，定義序列Φp1,Φp2,…,ΦpD-1，則第i個Hammersley點定義為

(5)

采用Hammersley法對需要搜索的D維空間進行采樣，將所得到的點集作為粒子群的初始解.進而根據所得到的初始化粒子位置，采用one-rand方法對粒子速度進行初始化：

vid=(xmax,d-xmin,d)U(0,1)-xid.

(6)

2.2退火策略

2.2.1初始溫度值初始溫度值是影響SA算法全局搜索性能的關鍵參數.初始溫度越高，全局搜索能力越強，搜索到全局最優(yōu)解的可能性越大，但搜索時間越長；反之，雖然減少了搜索時間，但可能無法搜索到全局最優(yōu)解.采用基于適應度和接受概率的溫度初始化方法，初始溫度T0為

(7)

2.2.2退火速度每一次外循環(huán)結束后進行降溫，再進行下一次的內循環(huán)過程.這里采取較簡單的溫度線性下降策略:

T(t+1)=λT(t),0<λ<1 ,

(8)

退火速度足夠慢有利于全局搜索，按溫度衰變實施降溫過程，一般λ為大于0接近于1的常數.

2.3參數設置

式(1)所示的粒子速度是一個隨機變量，則由式(2)產生的粒子運動軌跡是不可控的，使得粒子在搜索空間隨機跳動.為此，一般有vid∈[-vmax,vmax].vmax增大，有利于全局搜索；vmax減小，則有利于局部搜索.合理選擇vmax的大小，有利于算法更好地收斂到全局最優(yōu)值.

vmax=αvmax,0<α<1.

(9)

采用衰變因子法動態(tài)調整vmax，有利于算法在整個搜索過程保持較好的優(yōu)化性能.

2.4算法步驟

采用Hammersley方法對種群粒子初始位置進行初始化，根據所得到的粒子位置采用one-rand方法對粒子速度進行初始化，能夠使得初始種群盡可能覆蓋整個搜索空間，從而提高了PSO算法的全局搜索能力.為進一步改善算法的全局搜索能力，使算法可以達到更好的收斂精度,將SA算法的概率突跳特性引入到PSO，有助于PSO算法跳出局部最優(yōu).即對PSO算法中每一代產生的新的粒子，按照SA算法中的概率接受準則更新粒子位置.具體算法步驟如下：

1) 初始化：給定算法種群規(guī)模、變量維數、學習因子、慣性權重、初始溫度、最大迭代次數.進化迭代次數t=1，采用Hammersley方法對需要搜索的維空間進行采樣，將所得到的點集作為粒子群的初始解.進而由式(6)對粒子速度進行初始化.

2) 評價初始種群，確定局部及最優(yōu)粒子位置.

3) 由式(1)、(2)更新當前粒子速度與位置.

4) 判斷當前迭代次數是否達到設定的最大迭代次數？是，直接跳至步驟9)；否，則繼續(xù)執(zhí)行.

5) 計算所有粒子適應度，更新局部及全局最優(yōu)粒子位置.

6) 由式(1)、(2)更新當前粒子速度與位置.

7) 所有當前粒子位置xi(t)和新的粒子位置xi(t+1)，根據目標函數分別計算所對應的f(xi(t))和f(xi(t+1))，并計算增量f=f(xi(t+1)) - f (xi(t)).

9) T=λT,vmax= α vmax,t = t+1,跳至步驟4)，繼續(xù)執(zhí)行.

10) 輸出當前最優(yōu)粒子位置為最優(yōu)解，算法終止.

3　仿真計算

3.1測試函數

為測試算法的性能，選取5個通用的標準測試函數[9]在不同維度下進行仿真計算：

以上5個標準測試函數的形態(tài)各異，能夠全方位測試算法的性能.f1與f2為連續(xù)單峰函數，通常用于衡量算法的收斂速度.函數f3f5是復雜的非線性多峰函數，存在大量的局部極值，通常用于衡量算法的種群多樣性及全局搜索性能.

3.2實驗結果及分析

分別采用H-PSO算法與H-SA-PSO算法對文獻[9]中給出的5個測試函數進行仿真計算，主要參數設置與文獻[9]一致,其中：粒子群規(guī)模(小于30維)為30，粒子群規(guī)模(大于30維)為50，慣性權重w=0.729，c1=c2=1.494 45，最大迭代次數為1 000，初始溫度為T0，溫度下降系數λ=0.995.此外，文獻[9]中當適值小于10-10時輸出0，本文算法記錄為0的實驗結果均小于10-16.對5個測試函數在不同維度下進行了實驗，50次運算的最優(yōu)適值平均值的計算結果與文獻[9](PSO算法)的計算結果如表1所示.50次實驗結果的平均種群最優(yōu)值進化曲線如圖1～5所示.

所有相關算法都運行在戴爾vostro1088雙核2.0GHz的CPU的MatlabR2010b的環(huán)境下.

表1　三種算法的仿真結果Tab.1　The simulating results of the three algorithms

對比表1結果可以看出，H-SA-PSO算法測試結果明顯好于H-PSO算法.對除f2以外的其余4個測試函數，相比文獻[9]中結果，在更高維的搜索空間，可以在規(guī)定的迭代步數內成功尋得函數最優(yōu)值，有更強的全局尋優(yōu)能力.f2是復雜單峰值函數，雖然沒有在規(guī)定的迭代次數內對其尋優(yōu)成功，但是相比于文獻[9]中結果，可以達到更好的精度，尤其對高維(大于30維)情況下的尋優(yōu)，優(yōu)勢更加明顯.因此，H-SA-PSO算法在解決高維復雜函數時有較好的尋優(yōu)能力.

圖1　函數f1尋優(yōu)過程Fig.1　The optimization process of f1

圖2　函數f2尋優(yōu)過程Fig.2　The optimization process of f2

圖3　函數f3尋優(yōu)過程Fig.3　The optimization process of f3

圖4　函數f4尋優(yōu)過程Fig.4　The optimization process of f4

從圖1～5可以看出，H-PSO算法相比于標準PSO優(yōu)化算法可以得到更好的初始解，從而達到更好的收斂精度，算法性能有所提高，但是容易陷入局部極值.H-SA-PSO算法有更好的初始種群，且不易陷入局部最優(yōu)，對高維度的測試函數在較少的迭代次數內找到全局最優(yōu)值，有效克服了停滯現(xiàn)象，在進化后期依然保持較好的尋優(yōu)性能，具有很強的局部及全局搜索能力，有效解決了傳統(tǒng)粒子群在求解高維復雜問題時尋優(yōu)效果不佳的問題.

圖5　函數f5尋優(yōu)過程Fig.5　The optimization process of f5

4　小結

提出了擬隨機初始化模擬退火粒子群算法，運用Hammersley方法初始化粒子群，使得PSO初始種群能夠均勻覆蓋整個搜索空間，避免了傳統(tǒng)初始化方法在解決高維空間優(yōu)化問題時易于向邊緣聚集的現(xiàn)象，有利于PSO算法在高維空間中的尋優(yōu).同時將SA思想引入到PSO算法中，結合了PSO算法的快速尋優(yōu)能力和SA的概率突跳特性，使算法可以跳出局部最優(yōu)從而實現(xiàn)全局最優(yōu)，達到更好的收斂精度.仿真計算結果表明，本文算法在求解高維復雜函數時優(yōu)勢明顯，算法在進化后期仍有較強的搜索能力，有效改善了傳統(tǒng)PSO算法在求解高維問題時容易出現(xiàn)的停滯現(xiàn)象，不易陷入局部極值且收斂精度較高，是一種有效求解高維函數的全局優(yōu)化算法.

[1]GARNIERS,GAUTRAISJ,THERAULAZG.Thebiologicalprinciplesofswarmintelligence[J].Swarmintelligence, 2007,1(1):3-31.

[2]劉逸. 粒子群優(yōu)化算法的改進及應用研究[D].西安:西安電子科技大學,2013.

[3]FENGMY,PANH.AmodifiedPSOalgorithmbasedoncachereplacementalgorithm[C]//TenthInternationalConferenceonComputationalIntelligenceandSecurity.Kunming, 2014:558-562.

[4]LANGDONWB,POLIR.Evolvingproblemstolearnaboutparticleswarmandotheroptimisers[C]//IEEECongressonEvolutionaryComputation.Edinburgh,2005:561-578.

[5]HIGASHIN,IBAH.ParticleswarmoptimizationwithGaussianmutation[C]//ProceedingsoftheIEEESwarmIntelligenceSymposium.Indianapolis, 2003: 72-79.

[6]MIRANDAV,FONSECAN.EPSO:evolutionaryparticleswarmoptimization,anewalgorithmwithapplicationsinpowersystems[C]//TransmissionandDistributionConferenceandExhibition.Yokohama, 2002:2491-2505.

[7]劉愛軍,楊育,李斐,等.混沌模擬退火粒子群優(yōu)化算法研究及應用[J].浙江大學學報(工學版),2013,47(10):1722-1730.

[8]YANGHF,YANGZY,YANGY,etal.Animprovedparticleswarmoptimizationalgorithmbasedonsimulatedannealing[C]// 10thInternationalConferenceonNaturalComputation.Xiamen, 2014: 529-533.

[9]呂丹,童創(chuàng)明,鐘衛(wèi)軍. 基于粒子群和模擬退火算法的混合算法研究[J]. 計算機工程與設計，2011, 32(2):663-666.

[10]BERGHF,ENGELBRECHTAP.Acooperativeapproachtoparticleswarmoptimization[J].IEEEtransactiononevolutionarycomputation, 2004,8(3): 225-239.

[11]LIANGJJ,QINAK,SUGANTHANPN,etal.Comprehensivelearningparticleswarmoptimizerforglobaloptimizationofmultimodalfunctions[J].IEEEtransactiononevolutionarycomputation, 2006, 10(3): 281-295.

[12]HARALDNE,SIANGJINGYA.Halton-typesequencesfromglobalfunctionfields[J].ScienceChinamathematics, 2013,56(7):1467-1476.

(責任編輯：孔薇)

AQuasi-randomizedInitializedSimulatedAnnealingParticleSwarmOptimizationAlgorithm

WANGJie,LIHuihui,PENGJinzhu

(School of Electrical Engineering, Zhengzhou University, Zhengzhou 450001, China)

Toovercometheshortcomingsofparticleswarmoptimization(PSO)algorithmsuchasprematureconvergenceandstagnationwhensolvingthehigh-dimensionalproblems,aquasi-randomizedsimulatedannealing(SA)-PSOalgorithmwasproposed.Theperformanceofalgorithminhigh-dimensionaloptimizationspacecouldbeimprovedbyusingtheHammersleyinitialization.AndtheideaofSAalgorithmwasintroducedintothePSOalgorithm,combiningwiththefastsearchingabilityofPSOandtheprobabilisticjumpingpropertyofSA,tojumpoutoflocaloptimalalgorithmtoachievetheglobaloptimum.Theproposedalgorithmcouldeffectivelyovercomethestagnationphenomenon,enhancetheglobalsearchabilityinhigh-dimensionalspace.Theproposedalgorithmwasthentestedon5differentfunctions,andtheresultsdemonstratedbetteroptimizationabilityoverthetraditionalPSOalgorithm.

quasi-randomsequence;initialization;simulatedannealing;particleswarmoptimization

2016-02-01

教育部高等學校博士學科點專項科研基金資助項目(20124101120001)；河南省教育廳科學技術研究重點項目(14A413009)；中國博士后科學基金資助項目(2014T70685)．

王杰(1959—)，男，河南周口人，教授，主要從事模式識別與優(yōu)化算法研究,E-mail:wj@zzu.edu.cn.

TP301

A

1671-6841(2016)03-0075-07

10.13705/j.issn.1671-6841.2016022

引用本文：王杰，李慧慧，彭金柱.一種擬隨機初始化模擬退火粒子群算法[J].鄭州大學學報(理學版)，2016，48(3)：75-81.