基于模擬退火機制的多微粒群協同進化算法
2009-01-01 00:00:00李雪劉弘常亮
計算機應用研究 2009年1期
(1.山東師范大學 信息科學與工程學院， 濟南 250014; 2.山東大學 齊魯軟件學院， 濟南 250014)
摘 要：模擬退火和多微粒群協同進化是兩種較好的改進微粒群算法性能的方法，將這兩種思想有機地結合起來，提出了一種基于模擬退火機制的多微粒群協同進化算法。通過對三個標準函數優化的實驗表明，該算法高效、穩定地提高了全局尋優能力。
關鍵詞：微粒群算法; 模擬退火; 多微粒群協同進化
中圖分類號：TP391;TP301.6 文獻標志碼：A
文章編號：10013695(2009)01007103
Multiparticle swarm coevolution algorithmbased on simulated annealing method
LI Xue1， LIU Hong1， CHANG Liang2
(1.School of Information Science Engineering， Shandong Normal University， Jinan 250014， China; 2.College of Qilu Software， Shandong University， Jinan 250014， China)
Abstract:Simulated annealing and multiparticle swarm coevolution algorithm are two helpful methods which can improve the performance of particle swarm optimization. This paper combined these two ideas and dervied a new algorithm， that was the multiparticle swarm coevolution algorithm based on simulated annealing method. Through the three criteria function optimization experiments show the efficiency of the algorithm， improving the stability of global optimization capability.
Key words：PSO(particle swarm optimization)； simulated annealing； multiparticle swarm coevolution
微粒群算法(PSO)是在1995年由Eberhart等人[1，2]提出的一種新型進化計算方法，屬于求解全局最優化的群體智能算法。自提出以來，得到了學術界的高度關注且成功地應用于許多領域，如神經網絡訓練[2]、旅行商問題[3]、網絡節點位置優化[4]、網絡路由優化[5]、語言模型優化[6]等。基本PSO算法簡單且易于程序實現，具有良好的收斂性能，但也存在易陷入局部極值點，進化后期收斂慢、精度較差等的缺點。為了克服這些缺點，目前出現了大量的改進粒子群優化算法，如高鷹等人[7]提出的基于模擬退火的粒子群優化算法，Bergh等人[8]給出的協同粒子群優化算法以及李菲菲等人[9]提出的一種多微粒群協同進化算法等。這些算法從不同方面對粒子群優化算法進行了改進，不同程度地提高了算法的收斂速度和精度，但效果并不十分理想。
1 模擬退火簡介
模擬退火算法[10，11]是由Kirkpatrick等人提出的一種模擬金屬退火機理而建立的隨機優化方法。它是源于對固體退火過程的直接簡單模擬而建立的一種通用隨機搜索技術。模擬退火算法是局部搜索算法的擴展，它不同于局部搜索之處是以一定的概率選擇鄰域中費用值大的狀態。基本算法如下：
a)初始化退火溫度Tk(令k=0)，產生隨機初始解X0。
b)在溫度Tk下重復執行如下操作，直至達到溫度Tk的平衡狀態：
(a)在解x的鄰域中產生新的可行解x。
(b)計算新解的評價函數f(x′)和舊解的評價函數f(x)的差值Δf。
(c)依照概率min{1，exp(-Δf/Tk)}＞random[0，1]接收新解。其中random [0，1]是[0，1]內的隨機數。
c)令Tk+1=αTk，k←k+1。其中α∈(0，1)。若滿足收斂判據，則退火過程結束；否則，轉b)。其中退火溫度T控制著求解過程向最小值的優化方向進行，同時它又以概率exp(-Δf/Tk)來接收劣質解，因此算法可以跳出局部極值點。只要初始溫度足夠高，退火過程足夠慢，算法就能收斂到全局最優解。
2 模擬退火與微粒群算法的結合
粒子群優化算法具有深刻的智能背景，算法簡潔、容易實現，無須調整太多參數且不需要梯度信息，早期收斂速度快；但是后期受隨機振蕩現象的影響，使其在全局最優值附近需要較長的搜索時間，收斂速度慢，極易陷于局部極小值，精度降低，易發散。而模擬退火的并行技術能大幅度改進系統性能，加大信息吞吐量和提高運算速度。為此，一些研究建立了模擬退火并行粒子群優化算法模型，將模擬退火思想引入粒子群優化算法，如王麗芳等人[12]提出以模擬退火算法作為微粒群算法的收斂判據并為不收斂的群體置換新的微粒，從而使群體向全局最優解方向飛行。高鷹等人[7]提出把模擬退火思想引入到具有雜交和高斯變異的粒子群優化算法中，對粒子群進化后的適應值按Metropolis準則接受優化解的同時概率受惡化解，進一步優化后代群體。這些改進算法在一定程度上取得了成功。
3 多微粒群協同進化思想簡介
多微粒群協同進化（MPSC）算法[9]是近些年來提出的改進微粒群算法性能的較好的一種方法。其采用一個master種群和若干個slave種群，每個slave種群獨立進化，每次迭代結束后將最好的微粒復制到master種群，然后master種群開始進化，找出最好的微粒，將此微粒信息反饋給各slave種群，各slave種群據此信息修改微粒的速度繼續進化。各slave種群通過master種群進行信息交流，進化過程采用GA和PSO混合算法——GSO算法，即slave種群中一部分采用GA算法，進行交叉和變異操作，另一部分采用PSO算法，按照式(1)和(2)進行速度和位置更新；而master種群采用PSO算法，按照式(5)和(6)進行速度和位置更新。這樣處理可以選取和保留每個子種群的優秀個體，在保持優秀個體進化的穩定性的同時，加快進化速度，避免單種群進化過程中出現的過早收斂現象。
vij(t+1)=χ(ωvij(t)+r1c1(pij-xij(t))+
r2c2(gi-xij(t))+r3c3(G-xij(t))）(1)
xij(t+1)=xij(t)+vij(t+1)(2)
其中：vij(t+1)為第i個slave種群的第j個微粒在第t+1代的速度；xij(t)為第i個slave種群的第j個微粒在第t代的位置；w為慣性權重。隨著進化過程，根據下式調整慣性權重：
ω=ωmax-(ωmax-ωmin)/intermax×inter(3)
χ=2/(2-φ-φ2-4φ)，φ=c1+c2，φ＞4(4)
其中：χ為收縮因子；r1、r2、r3為[0，1]的隨機數；c1、c2、c3 為學習系數。pij為第i個slave種群的第j個微粒的個體歷史最好位置；gi為第i個slave種群的全局最好位置；G為master種群的全局最好位置。
Master種群采用PSO算法，其速度和位置更新公式為
vmi(θ)=χ(ωvmi+c1r1(gmi-xmi)+c2r2(G-xmi))(5)
xmi(θ)=xmi+vmi(θ)(6)
其中：vmi(θ)為master種群中微粒i更新后的速度；xmi(θ)為master種群中微粒i更新后的位置；gmi為當前master種群中最好微粒的位置；G為上次迭代結束后master種群中最好微粒的位置。
Master種群的速度和位置更新結束后，要計算每個微粒的適應值，找出最好的微粒。如果最好的微粒位置差于G，則繼續保留G；否則，將G更新為最好微粒的位置。
4 基于退火機制的多微粒群協同進化算法
本文將模擬退火和多微粒群協同進化這兩種思想有機地結合起來，提出了基于模擬退火機制的多微粒群協同進化算法(SAMPSC)。算法流程如下：
a)初始化控制參數。初始化slave子種群的個數M，每個子種群的個體數m，每個微粒的維數，慣性權重，加速常數c1、c2，交叉概率pic，變異概率pin，溫度冷卻系數Ci，退火初始溫度Ti(i= 1～M)。
b)隨機產生M個初始種群。
c)對每一個子種群i(i=1～M)實施如下操作，以產生一個新子種群，直至產生出M個新子種群。
（a）計算種群中每個個體的適應函數值f(xj)（j=1，2，…，2N + 1)。
（b）把M個子群按概率分為兩部分，其中一部分進行交叉、變異操作，過程如下：
①從第i個種群中隨機選取個體xj，xk，按照概率pic進行交叉操作， 產生兩個新個體x′k、x′k， 計算適應函數值f(x′j)和f(x′k)。若min{1，exp(-(f(x′j)-f(xj))/Ti)}＞random，則接收x′j個體；若min{1，exp(-(f(x′k)-f(xk))/Ti)}＞random，則接收x′k為新個體。其中random為[0，1]上的隨機數。
②對交叉后的個體按照概率pin進行變異操作，按①中的方法決定是否接受新個體。若接受， 則令新個體為新子種群的個體；否則，令舊個體為新子種群的個體。對步驟①②重復N次。
對子種群的另一部分按照式(1)和(2)微粒群的速度和位置公式進行更新，計算每個粒子更新后的適應值置f(xi(t+1))，然后計算兩個位置所引起的適應值的變化量Δf。若Δf＜0，則接受新位置；若min{1，exp(-Δf/T)}＞random[0，1]，也接受新位置，否則拒絕，返回步驟(a)。
d)找出當前M個子種群中各自最優的個體，并把最優的個體復制到master種群。
e)對master種群中的每個微粒根據式(5)(6)更新速度和位置，計算適應值更新G。
f)若當前總最優個體滿足收斂條件， 則進化過程成功結束， 返回全局最優解。
g)若進化次數小于預定最大進化次數，則修改種群的退火溫度，即令Ti←CiTi(i=1～M)，轉步驟c)。
5 仿真實驗
本文比較SAMPSC算法與單純基于模擬退火的PSO算法(SAPSO)、多微粒群協同進化算法(MPSC)對Rosenbrock函數(f1)、Rastrigrin函數(f2)和Griewank函數(f3)三種基準函數的優化精度。
Rosenbrock函數又稱為香蕉函數，其最優解為x*=(1，1，…，1)，極小值為f(x*)=0。
f1(x)=∑n-1i=1[100(xi-1-x2i)2+(xi-1)2] -100≤xi≤100
Rastrigrin函數是一個多峰函數，有很多正弦凸起的局部極小點，它的全局極小點在x*=(0，0，…，0)處，全局極小值f(x*)=0。
f2(x)=∑ni=1[(x2i-10 cos(2πxi))+10] -10≤xi≤10
Griewank 函數也是一個多峰函數，它的全局極小點在x*=(0，0，…，0)處，全局極小值f(x*)=0。
f3(x)=（1/4 000） ∑ni=1x2i-∏ni=1 cos(xi/i)+1 -600≤xi≤600
本文算法用.NET 2003及MATLAB 7.0實現。進行實驗時，退火初始溫度T=5 000，溫度冷卻系數C=0.8。SAPSO實驗時，取m=20，c1=c2=2.0，w=0.7，Vmax=100(對于f1)，Vmax=10（對于f2），Vmax=600（對于f3）；SAMPSC及MPSC算法中，每個微粒設為10維，取微粒群子群體數M=6。每子群中粒子數m=20，相應主群體中粒子數m=6；每次迭代過程中每個子群中的粒子按照概率0.5被分成兩個群體：PSO群體按照式(1)(2)更新速度和位置進行PSO操作，GA群體進行GA操作；主群體進行PSO操作時按照式(5)(6)更新粒子速度和位置，其慣性權重也隨迭代次數從0.7遞減至0.3，學習系數Cmaster的值和子群體的一樣。具體參數設置如表1所示。
表1 SAMPSC優化標準函數的參數設置
函數Vmaxwc1c2c3cmasterpicpinCT迭代次數
f1(x)200.7遞減到0.32.052.052.052.050.50.10.85 00010 000
f2(x)20.7遞減到0.32.052.052.052.050.20.10.85 00010 000
f3(x)2000.7遞減到0.32.052.052.052.050.70.10.85 00010 000
SAMPSC算法運行20次取平均最好適應值與其他算法進行比較，實驗結果如表2所示。該算法相對于前兩種算法顯示了更好的優化性能。當SAMPSC算法的迭代次數在20 000次以上時，每次運行基本都能得到全局最優值。
表2 三種算法運行20次的平均最好適應值對比(平均值±標準差)
函數SAPSOMPSCSAMPSC
f1(x)21.63±40.347.466 8±1.319 534.374±1.173
f2(x)9.732±1.6413.376 22±2.415 22.153 6±1.561
f3(x)0.0064±0.0420.005 3±0.001 50.003 5±0.002
圖1～3分別給出了三種算法對上面三個函數的優化過程，參數取值同上。圖的縱軸是運行20次的平均最優適度值的對數(lg fitness)，橫軸是迭代次數(G)。從這三幅圖也可以看出，SAMPSC尋得解的質量均比其他兩種算法要好，且有著更快的收斂速度。圖2驗證了SAMPSC在持續進化解的能力上的優越性，可以看出它在該能力上更勝MPSC一籌。在優化的過程中， SAMPSC的曲線比MPSC更加平滑，沒有明顯的跳動，而MPSC的則有些跳動。這個現象說明了SAMPSC的利用與全局探索相協調平衡的能力比MPSC更強，探索的尋優經驗能及時得到利用。而且隨著時間的推移， SAMPSC在持續進化能力上優越MPSC的差距有逐漸變大的趨勢。
6 結束語
利用模擬退火思想改進微粒群算法有利于優良個體的保留。隨著進化過程的進行，溫度逐漸下降，接收劣質解的概率逐漸減小，從而提高了收斂性能。利用多種群協同進化思想改進微粒算法是通過不同子種群各自獨立的進化，把每次進化找到的當前最優解分配到各個子種群中去，以促進其他子種群的進化，這樣做可以選取和保留每個子種群的優秀個體，在保持優秀個體進化穩定性的同時，加快進化速度，避免單種群進化過程中出現的過早收斂現象。
參考文獻：
［1］EBERHARTR C， KENNEDY J. A new optimizer using particles swarm theory[C]//Proc of the 6th International Symposium on Micro Machine and Human Science. Nagoya:Municipal Industrial Research Institute， 1995:3943.
[2]KENNEDYJ， EBERHARTR C. Particles swarm optimization[C]//Proc of IEEE International Conference on Neural Network. Piscataway:IEEE Press， 1995:19421948.
[3]肖健梅，李軍軍，王錫淮.改進微粒群優化算法求解旅行商問題[J]. 計算機工程與應用， 2004，40(35):5052.
[4]王雪，王晟，馬俊杰.無線傳感網絡移動節點位置并行微粒群優化策略[J]. 計算機學報， 2007，30(4):563568.
[5]原平，陳紅，王光興.Ad hoc網絡路由優化的微粒群方法[J].小型微型計算機系統，2006，27(7):11931196.
[6]劉建成，蔣新華，吳今培.應用改進型微粒群算法優化語言模型[J].小型微型計算機系統， 2006，27(12):23062309.
[7]高鷹，謝勝利.基于模擬退火的粒子群優化算法[J].計算機工程與應用，2004，40(1):4750.
[8]van den BERGH F， ENGELBRECHT A P. Training product unit networks using cooperative particle swarm optimizers[C]//Proc of International Joint Conference on Neural Networks. 2001:126131.
[9]李菲菲，姚坤，劉希玉.一種多微粒群協同進化算法[J].計算機工程與應用，2007，43(22):4446.
[10]邢文訓，謝金星.現代優化計算方法[M].北京:清華大學出版社，1999.
[11]康立山，謝云，羅祖華.非數值并行算法—模擬退火算法[M].北京:科學出版社，1998.
[12]王麗芳，曾建潮.以模擬退火算法為收斂判據的混合微粒群算法[J].計算機工程與科學，2006，28(5):7779.
