李淑香

(重慶郵電大學(xué)移通學(xué)院 數(shù)理教學(xué)部，重慶 401520)

近年來，優(yōu)化問題在很多行業(yè)越來越受到關(guān)注和重視，同時(shí)也發(fā)揮著重要作用.目前，優(yōu)化對象變得越來越復(fù)雜，傳統(tǒng)優(yōu)化方法在解決這些問題時(shí)顯得很困難，甚至無能為力.因此，越來越多的研究人員將思路轉(zhuǎn)變到群智能算法中，從自然界中生物的群體行為得到啟發(fā)，提出將新型智能算法(如遺傳算法、細(xì)菌算法，狼群算法和粒子群算法等[1-2])應(yīng)用在函數(shù)優(yōu)化中，并得到了一定效果.上述算法在解決函數(shù)優(yōu)化問題時(shí)表現(xiàn)出強(qiáng)大的能力和優(yōu)勢，但仍有不足，因此，人們?nèi)栽诶^續(xù)探索研究新的啟發(fā)式智能優(yōu)化算法或混合算法等.

粒子群算法被廣泛應(yīng)用的原因是相較于其他群智能算法，粒子群算法具有結(jié)構(gòu)簡單，參數(shù)易調(diào)整，優(yōu)化結(jié)果明顯等優(yōu)點(diǎn).當(dāng)然，粒子群搜索算法也存在一些不足，如PSO算法易進(jìn)入早熟和局部最優(yōu)等[3].然而由于PSO算法在很多領(lǐng)域內(nèi)總體上都表現(xiàn)出了強(qiáng)大能力，其理論和應(yīng)用方面受到國內(nèi)外許多學(xué)者的重視和進(jìn)一步研究.文獻(xiàn)[4]采用新的粒子編碼方式與位置更新方式，提高了標(biāo)準(zhǔn)粒子群算法的收斂速度；文獻(xiàn)[5]更改了傳統(tǒng)慣性權(quán)重，依據(jù)粒子本身的進(jìn)化經(jīng)驗(yàn)，實(shí)現(xiàn)自適應(yīng)調(diào)整，提高了算法的多樣性和算法的尋優(yōu)能力；文獻(xiàn)[6]有效改變了粒子數(shù)目和算法中的速度位移方程，使得改進(jìn)算法的收斂速度和收斂精度都得到了明顯改善和提高.隨著多種群智能算法的不斷發(fā)展，由兩種或多種算法的相結(jié)合達(dá)到相互取長補(bǔ)短的混合算法得到廣泛應(yīng)用.文獻(xiàn)[7]將量子行為思想引入到PSO系統(tǒng)中，通過改變粒子更新方式，改進(jìn)了PSO算法.改進(jìn)PSO算法雖能在一定程度上改善標(biāo)準(zhǔn)粒子群算法的不足，但效果仍不理想，為了能夠進(jìn)一步提高PSO算法的收斂精度，本文在對粒子群算法和模擬退火算法進(jìn)行了進(jìn)一步研究后，提出了基于模擬退火的粒子群算法，該算法具有較強(qiáng)的全局搜索能力，在接受新解時(shí)既可以接受好解又可以接受差解.將本文算法應(yīng)用到標(biāo)準(zhǔn)粒子群算法中，可以保證種群的多樣性，有利于跳出局部最優(yōu)解，提高算法的收斂速度和尋優(yōu)精度，并避免“早熟”現(xiàn)象的發(fā)生.

1 基本粒子群算法

粒子群(PSO)算法是應(yīng)用較廣的一種算法，最早是在1995年由Kennedy和Eberhart提出來的，該算法是一種對自然界鳥群、魚群等在群體生活中的捕食與移動過程的一種近似模擬[2].粒子群算法通過不斷迭代來搜尋目標(biāo)函數(shù)的最優(yōu)值，初始化一組隨機(jī)解，而每個(gè)粒子都可看成是問題的潛在解.鳥群能否成功捕獲到食物不僅與過去積累的經(jīng)驗(yàn)和認(rèn)知有關(guān)，同時(shí)還和群體中的其它個(gè)體之間存在聯(lián)系[8].在粒子群算法中粒子在解空間追隨最優(yōu)粒子進(jìn)行搜索，在搜索過程中速度和位置信息是在不斷調(diào)整改變的，其主要依據(jù)是粒子過去積累的經(jīng)驗(yàn)和群體中的其它個(gè)體信息等.在PSO算法初始化過程中隨機(jī)產(chǎn)生粒子群的種群，其中每個(gè)粒子都是目標(biāo)函數(shù)的解，為了尋找函數(shù)的最優(yōu)解，每個(gè)粒子會根據(jù)個(gè)體歷史最優(yōu)位置和種群的最優(yōu)位置來多次調(diào)整自身的速度和位置更新策略，并經(jīng)多次迭代尋優(yōu)最終找到問題的最優(yōu)解.

在PSO算法中，每個(gè)粒子都可以看作多維搜索空間中優(yōu)化問題的解.假設(shè)在一個(gè)D維搜索空間中某群體中共有n個(gè)粒子，第i個(gè)粒子在D維搜索空間中的位置向量Xi=(xi1，xi2，…，xiD)，每個(gè)粒子的位置代表一個(gè)潛在解，代入目標(biāo)函數(shù)就可以計(jì)算其適應(yīng)度值.第i個(gè)粒子的速度向量為Vi=(vi1，vi2，…，viD)，利用目標(biāo)函數(shù)求解其適應(yīng)度值，確定個(gè)體最優(yōu)位置向量Pi=(pi1，pi2，…，piD)與當(dāng)前情況下群體所經(jīng)歷的歷史最優(yōu)位置向量Pg=(pg1，pg2，…，pgD).粒子群算法對粒子操作時(shí)涉及的更新公式[9]為

vij(t+1)=ωvij(t)+c1r1(pij(t)-xij(t))+

c2r2(pgj(t)-xij(t))

(1)

xij(t+1)=xij(t)+vij(t+1)

(2)

式中：c1和c2為加速常數(shù)，分別調(diào)節(jié)粒子向自身最優(yōu)位置與向全局最優(yōu)位置飛行的步長，通常c1+c2≤4；r1和r2為兩個(gè)相互獨(dú)立的隨機(jī)函數(shù)；ω為慣性常數(shù)，可以平衡全局與局部搜索能力；xij(t)為第i個(gè)粒子在t時(shí)刻的第j維位置分量；vij(t)為第i個(gè)粒子在t時(shí)刻的第j維速度分量；pij(t)為第i個(gè)粒子的第j維分量更新前的歷史最優(yōu)位置；pgj(t)為t時(shí)刻種群所經(jīng)歷的最優(yōu)位置.

式(1)由三項(xiàng)組成：第一項(xiàng)為粒子的當(dāng)前速度，即現(xiàn)在狀態(tài)部分；第二項(xiàng)為粒子從自身出發(fā)的自我認(rèn)知部分；第三項(xiàng)為粒子在整個(gè)群體中與其它粒子間進(jìn)行協(xié)調(diào)的社會部分.通過公式(1)、(2)不斷更新，粒子不斷向全局最優(yōu)解靠攏，尋找搜索空間中的最佳值.基本粒子群算法需要用戶確定的參數(shù)并不多，而且操作簡單，故使用比較方便.但是它的缺點(diǎn)是易陷入局部極值點(diǎn)，搜索精度不高，因此，人們提出了許多改進(jìn)算法，從而在一定程度上改進(jìn)了基本粒子群算法的性能[10].

2 模擬退火算法

模擬退火(SA)算法不僅是一種統(tǒng)計(jì)優(yōu)化方法，還是一種全局優(yōu)化算法.該算法從物理退火原理得到啟發(fā)，最早由Metropolis提出.當(dāng)固體物質(zhì)不斷升溫時(shí)，隨著溫度的增加，物質(zhì)內(nèi)部的粒子變得活躍起來并處于不穩(wěn)定狀態(tài)；與之相反，當(dāng)溫度不斷降低時(shí)，物質(zhì)內(nèi)部粒子的活躍度又在不斷下降，從不穩(wěn)定狀態(tài)變成穩(wěn)定狀態(tài).依照固體物質(zhì)退火過程和組合優(yōu)化問題的共性特點(diǎn)，將模擬退火算法應(yīng)用于各種組合優(yōu)化問題中.

SA算法在對目標(biāo)問題進(jìn)行迭代優(yōu)化尋找最優(yōu)解時(shí)，首先需要確定一個(gè)初始溫度，并在問題解空間上生成一個(gè)初始狀態(tài)作為初始解，然后對當(dāng)前初始狀態(tài)進(jìn)行干擾，模擬固體內(nèi)部粒子在一定溫度下的狀態(tài)轉(zhuǎn)移過程.之后評估由干擾得出的新解，將新解和當(dāng)前解進(jìn)行比較并根據(jù)Metropolis準(zhǔn)則進(jìn)行替換.SA算法以概率1來接受最優(yōu)解，以某種概率來接受較差解.正因?yàn)榫哂羞@種能力，所以該算法不易陷入局部最優(yōu)陷阱，從而可以跳出局部最優(yōu)解.Metropolis準(zhǔn)則定義了物體在某一溫度T下從狀態(tài)i轉(zhuǎn)移到狀態(tài)j的內(nèi)能概率，其表達(dá)式為

(3)

式中：E(i)和E(j)分別為固體在狀態(tài)i和j下的內(nèi)能；ΔE為內(nèi)能增量；K為波爾茲曼常數(shù).

由式(3)可知，當(dāng)E(j)

3 模擬退火粒子群算法

粒子群算法在函數(shù)優(yōu)化過程中主要依賴粒子之間的信息不斷更新粒子的位置和速度，使其不斷向最優(yōu)解方向靠攏.PSO算法存在易早熟，易陷入局部最優(yōu)，后期收斂速度較慢，搜索精度較差等缺點(diǎn).模擬退火算法具有很強(qiáng)的全局搜索能力，存在接受較差解的可能，在運(yùn)算時(shí)遇到較差解能夠以一定的概率接受，從而可以跳出局部最優(yōu)解陷阱，收斂于全局最優(yōu)解區(qū)域，擁有較高的搜索精度.但在算法運(yùn)算時(shí)，因其需要非常高的退火溫度，故收斂速度十分緩慢.

PSO算法和SA算法各具優(yōu)缺點(diǎn)，結(jié)合SA算法中的Metropolis準(zhǔn)則并與PSO算法相互融合形成一種模擬退火粒子群混合優(yōu)化(SAPSO)算法.該混合算法以基本粒子群算法運(yùn)算流程作為主體流程，把模擬退火機(jī)制引入其中并實(shí)現(xiàn)取長補(bǔ)短，明顯克服PSO算法早熟收斂的弊端，改善SA算法收斂速度慢的缺點(diǎn)，從而提升了算法的整體性能.模擬退火粒子群算法流程如圖1所示.

圖1 模擬退火粒子群算法流程Fig.1 Flow chart of SAPSO algorithm

利用模擬退火粒子群算法進(jìn)行函數(shù)優(yōu)化時(shí)的具體步驟為：

1)對粒子群里的相關(guān)參數(shù)進(jìn)行初始化，如種群、迭代次數(shù)、粒子維度、粒子速度和位置等，并計(jì)算初始粒子群的適應(yīng)度及相關(guān)參數(shù).

2)模擬退火初始化過程，設(shè)置初始溫度，生成初始解S，求出評價(jià)函數(shù)C(S)，并令C(S)為全局最優(yōu)解.

3)生成新解S′.

4)按照式(1)、(2)更新粒子的速度和位置，并計(jì)算適應(yīng)度值.

5)求得C(S′)=min{f(xi)}，ΔC=C(S′)-C(S)，其中，f(xi)為最小適應(yīng)度值.若ΔC<0或exp(-ΔC/T)>rand(0，1)，C(S)=C(S′)，S=S′，并接受由S′所更新的速度和位置；否則將拒絕S′的值，采用當(dāng)前時(shí)刻值來更新速度和位置，并計(jì)算適應(yīng)度值.

6)根據(jù)適應(yīng)度值來更新全局最優(yōu)解和局部最優(yōu)解.

7)判斷是否滿足結(jié)束條件，若滿足，輸出最優(yōu)值；若不滿足，轉(zhuǎn)到步驟3).

4 仿真實(shí)驗(yàn)

4.1 測試函數(shù)

為了檢驗(yàn)SAPSO混合算法的優(yōu)化效果，選取了PSO和GA算法進(jìn)行對比實(shí)驗(yàn)，并引入5個(gè)非線性函數(shù)進(jìn)行測試.5個(gè)測試函數(shù)分別為Sphere、Rosenbrock、Ackley、Griewank和Rastrigrin函數(shù).除了Rosenbrock函數(shù)在全局最優(yōu)解[1，1，…，1]處具有極小值外，其余測試函數(shù)均在全局最優(yōu)解[0，0，…，0]處具有極小值，且極小值均為0，函數(shù)最優(yōu)值也均為0.測試函數(shù)具體表達(dá)式如表1所示.

表1 測試函數(shù)Tab.1 Test functions

4.2 結(jié)果與分析

利用SAPSO、PSO和GA算法對上述5個(gè)測試函數(shù)進(jìn)行數(shù)值模擬來驗(yàn)證本文算法可行性.主要參數(shù)設(shè)置為：種群規(guī)模40；最大迭代次數(shù)1 000；函數(shù)維度30.PSO算法中慣性權(quán)重初始最大值為0.9，慣性權(quán)重初始最小值為0.4；c1=1.49，c2=1.49.退火算法中K=0.7，初始溫度為10 000 ℃；遺傳算法中交叉概率為0.7，變異概率為0.3.

為了驗(yàn)證模擬退火粒子群混合算法的優(yōu)越性和可行性，通過對表1中的5個(gè)非線性測試函數(shù)進(jìn)行對比分析，得出Sphere、Griewank、Rosenbrock、Ackley和Rastrigrin函數(shù)的優(yōu)化曲線，結(jié)果如圖2～6所示.

圖2 Sphere函數(shù)優(yōu)化曲線Fig.2 Optimization curves of Sphere function

由圖2～6可見，與粒子群算法和遺傳算法相比，基于模擬退火的粒子群混合算法在高維函數(shù)優(yōu)化中具有明顯優(yōu)勢，混合算法易跳出局部最優(yōu)解，避免“早熟”現(xiàn)象且具有收斂速度快等優(yōu)點(diǎn)，克服了傳統(tǒng)PSO算法和GA算法中出現(xiàn)的不足和缺點(diǎn).

圖3 Griewank函數(shù)優(yōu)化曲線Fig.3 Optimization curves of Griewank function

圖4 Rosenbrock函數(shù)優(yōu)化曲線Fig.4 Optimization curves of Rosenbrock function

圖5 Ackley函數(shù)優(yōu)化曲線Fig.5 Optimization curves of Ackley function

圖6 Rastrigrin函數(shù)優(yōu)化曲線Fig.6 Optimization curves of Rastrigrin function

5 結(jié) 論

針對傳統(tǒng)PSO算法易出現(xiàn)局部最優(yōu)等缺點(diǎn)，在標(biāo)準(zhǔn)粒子群算法的基礎(chǔ)上引進(jìn)模擬退火算法思想，提出了模擬退火粒子群混合算法.該混合算法利用模擬退火算法的概率突變能力，不僅能接受最優(yōu)解，還能以某種概率來接受較差解.因此，混合算法不易陷入局部最優(yōu)的陷阱，從而具有跳出局部最優(yōu)解的能力.該混合算法不僅基本保持了粒子群優(yōu)化算法簡單易實(shí)現(xiàn)的特點(diǎn)，而且能夠增強(qiáng)粒子群算法的全局尋優(yōu)能力，加快了算法的進(jìn)化速度，提高了算法的收斂精度.利用5個(gè)測試函數(shù)對模擬退火粒子群混合算法進(jìn)行測試后發(fā)現(xiàn)，與PSO和GA算法相比，本文算法具有較快的收斂性和較好的穩(wěn)定性，從而驗(yàn)證了本文算法的有效性.