基于模擬退火的自適應(yīng)正余弦算法

張 娜，賀興時(shí)

(西安工程大學(xué) 理學(xué)院，陜西 西安 710048)

0 引 言

在科學(xué)技術(shù)飛速發(fā)展推動(dòng)下，生產(chǎn)實(shí)踐中面臨的最優(yōu)化問題的復(fù)雜度成倍增長(zhǎng)。在探尋優(yōu)化問題求解的過程中，大量群體智能算法[1-3]得以發(fā)展并廣泛應(yīng)用于科學(xué)研究和工程應(yīng)用等領(lǐng)域。

正弦余弦算法(SCA)[4]是2016年澳大利亞學(xué)者Seyedali 和Mirjalili提出的一種新型智能算法。該算法將迭代過程歸納為全局搜索和局部開發(fā)2個(gè)過程。針對(duì)2個(gè)具體的過程加入不同的擾動(dòng)，通過重復(fù)迭代找尋最優(yōu)解。該算法參數(shù)少、結(jié)構(gòu)簡(jiǎn)單、易于實(shí)現(xiàn)，因而得以廣泛發(fā)展和應(yīng)用。目前，SCA已經(jīng)被用于資源配置[5]、調(diào)度問題[6]、電力系統(tǒng)優(yōu)化[7]等組合優(yōu)化問題。

正余弦算法(SCA)自身也存在缺點(diǎn)，如局部搜索能力差、迭代后期收斂過慢、易陷入局部最優(yōu)等。對(duì)此，諸多學(xué)者從簡(jiǎn)化算法、調(diào)整參數(shù)、融合其他算法等方面提出了不同的改進(jìn)策略。曲良東等為簡(jiǎn)化算法，將算法調(diào)整為正弦算法(SA)，雖然降低了算法復(fù)雜度但犧牲了部分精度[8]；劉勇等提出轉(zhuǎn)換參數(shù)非線性遞減的正弦余弦算法(PSCA)，在一定程度上提高了計(jì)算精度和收斂速度[9]；徐松金等在算法中引入慣性權(quán)重和反向?qū)W習(xí)策略，提出一種改進(jìn)的正余弦算法(ISCA)，提升了算法性能，特別是提高了高維函數(shù)求解的精度，但算法在迭代后期易陷入局部最優(yōu)[10]；王蕾等將正余弦算法改進(jìn)后嵌入花粉算法，利用正弦和余弦對(duì)花粉個(gè)體進(jìn)行優(yōu)化，提出一種融合正弦余弦算法的花授粉算法，提升了算法尋優(yōu)精度[11]；韓斐斐等將正弦余弦操引入蝙蝠算法，避免算法陷入局部最優(yōu)[12]。可見，改進(jìn)的算法要么存在局部開發(fā)范圍過小而導(dǎo)致算法陷入局部最優(yōu)，要么存在全局搜索范圍過大而導(dǎo)致算法尋優(yōu)精度低的問題。本文針對(duì)正余弦算法的不足，自適應(yīng)調(diào)整參數(shù)r1，在更新公式中引入對(duì)數(shù)遞減的慣性權(quán)重，同時(shí)嵌入模擬退火機(jī)制，在增強(qiáng)局部探索能力，平衡局部與全局2個(gè)過程的同時(shí)，使算法在迭代后期能跳出局部最優(yōu)。

1 標(biāo)準(zhǔn)正余弦算法

正余弦算法(SCA)是利用正弦、余弦函數(shù)的周期波動(dòng)性構(gòu)造迭代方程更新新解，并不斷向最優(yōu)解逼近。首先隨機(jī)產(chǎn)生初始解并獲取當(dāng)前最優(yōu)解位置，然后根據(jù)式(1)進(jìn)行更新:

(1)

SCA算法偽代碼如下：

b) 初始化各參數(shù)N、M, 令t=0,a=2。

d) Whilet≤M

fori=1:N

forj=1:d

計(jì)算r1,隨機(jī)產(chǎn)生r2,r3,r4

ifr4<0.5

根據(jù)式(1)正弦部分更新位置

else

根據(jù)式(1)余弦部分更新位置

end if

end for

end for

t=t+1

end While

2 改進(jìn)正余弦算法

2.1 自適應(yīng)調(diào)整參數(shù)

標(biāo)準(zhǔn)正余弦算法中采用線性遞減的參數(shù)r1，不利于平衡全局搜索和局部開發(fā)2個(gè)線性過程。為提高算法性能，文獻(xiàn)[9]提出了轉(zhuǎn)化參數(shù)拋物線遞減和對(duì)數(shù)遞減2種參數(shù)調(diào)整策略，并通過實(shí)驗(yàn)證明了轉(zhuǎn)換參數(shù)指數(shù)遞減的策略具有更高的尋優(yōu)精度，如式(2)所示：

(2)

式中：控制參數(shù)a=2。但這種參數(shù)調(diào)整方式未考慮粒子自身狀態(tài)，對(duì)于高維復(fù)雜函數(shù)求解存在局限性?？紤]到進(jìn)化過程各個(gè)粒子間的進(jìn)化能力存在差異，本文提出將參數(shù)r1轉(zhuǎn)為自適應(yīng)參數(shù)，根據(jù)進(jìn)化中每個(gè)粒子自適應(yīng)值的狀態(tài)，動(dòng)態(tài)的調(diào)整參數(shù)r1，如式(3)所示：

(r1max-r1min)]

(3)

(4)

2.2 對(duì)數(shù)遞減慣性權(quán)重

智能算法在進(jìn)化前期需要很強(qiáng)的隨機(jī)震蕩，以獲取全局最優(yōu); 進(jìn)化后期則需提高局部開發(fā)能力。為此,SHI[13]提出一種慣性權(quán)重線性遞減的粒子群算法(PSO)。為平衡算法全局探索和局部開發(fā)能力，參考粒子群算法，在位置更新中引入對(duì)數(shù)遞減的慣性權(quán)重，表示粒子保持原來位置的慣性。為簡(jiǎn)化論述過程，將在簡(jiǎn)化正弦算法的基礎(chǔ)上進(jìn)行改進(jìn)。因此，個(gè)體位置更新公式調(diào)整為式(5)，慣性權(quán)重為式(6)：

(5)

(6)

圖 1 權(quán)重變化曲線圖Fig.1 Weight change curve

2.3 基于模擬退火的正余弦算法

模擬退火算法(SA)是1953年N.Metropolis等基于固體退火原理提出的一種啟發(fā)式算法[14]。該算法的核心是采用重要性采樣方法，也稱為Metropolis準(zhǔn)則，以一定概率接受劣解，使算法能依概率跳出局部最優(yōu)。因此，算法具有良好的全局尋優(yōu)能力，將其與其他優(yōu)化算法結(jié)合[15-16]可以提高改進(jìn)算法性能。本文在正余弦算法中引入模擬退火的機(jī)制，稱之為SASCA算法，以增強(qiáng)算法跳出局部最優(yōu)的能力。

在SASCA算法中，每次迭代時(shí)對(duì)最優(yōu)位置添加高斯擾動(dòng)，以避免算法在迭代后期陷入局部最優(yōu)。

Xt+1=Xt+αε

(7)

式中：Xt=(Xij)N×d;ε為N×d階隨機(jī)矩陣，矩陣中每個(gè)元素εij～N(0,1)。為避免波動(dòng)范圍過大，設(shè)置擾動(dòng)因子α。經(jīng)過測(cè)試,本文將α設(shè)置為0.01。

在SASCA算法中引入Metropolis 準(zhǔn)則，對(duì)當(dāng)前最優(yōu)解添加高斯擾動(dòng)得到全局最優(yōu)的替代值，并根據(jù)Metropolis準(zhǔn)則以一定概率接受擾動(dòng)后的新解。基本迭代過程為：

a) 隨機(jī)產(chǎn)生初始種群，設(shè)置初始參數(shù)種群規(guī)模N，最大迭代次數(shù)M，擾動(dòng)因子α，降溫速率λ,并令t=1,T=T0；

b) 評(píng)價(jià)粒子的適應(yīng)度，找出當(dāng)前最優(yōu)位置存儲(chǔ)于P0；

c) 根據(jù)式(7)進(jìn)行高斯擾動(dòng)，產(chǎn)生當(dāng)前最優(yōu)的替代值Pt′并根據(jù)Metropolis準(zhǔn)則接受Pt′；

d) 根據(jù)式(3)、(6)計(jì)算參數(shù)r1、w，隨機(jī)產(chǎn)生r2、r3、r4；

e) 根據(jù)式(5)更新第i個(gè)粒子的個(gè)體位置；

f) 評(píng)價(jià)粒子的適應(yīng)度，找出當(dāng)前最優(yōu)位置并存儲(chǔ)于Pt；

g) 根據(jù)式(8)、(9)退溫并判斷是否到達(dá)最大迭代次數(shù)，若滿足則輸出最優(yōu)解，否則返回(c)。

T0=f(Pt)/ln 5

(8)

T=λT0

(9)

改進(jìn)的正余弦算法流程圖如圖2。

圖 2 SASCA算法流程圖Fig.2 SASCA algorithm flow chart

3 算法測(cè)試

3.1 標(biāo)準(zhǔn)測(cè)試函數(shù)

為測(cè)試對(duì)比算法的性能，本文選取了10個(gè)不同的測(cè)試函數(shù)[17],分別用5種算法進(jìn)行求解，其中f1～f5為單峰函數(shù)，f6～f10為多峰函數(shù)。

3.2 參數(shù)設(shè)計(jì)

為保證測(cè)試結(jié)果有效，10個(gè)測(cè)試函數(shù)設(shè)置相同的維數(shù)d=50，種群規(guī)模N=40，最大迭代次數(shù)M=1 000,其余參數(shù)設(shè)置如表1所示。

表 1 參數(shù)設(shè)置Tab.1 Parameter settings

3.3 測(cè)試結(jié)果

采用本文算法(SASCA)，標(biāo)準(zhǔn)正余弦算法(SCA)，改進(jìn)的正余弦算法(ISCA)，正弦算法(SA)以及基于模擬退火的蝙蝠算法(SABA)，分別在10個(gè)不同的高維標(biāo)準(zhǔn)函數(shù)上進(jìn)行測(cè)試。對(duì)每個(gè)算法獨(dú)立運(yùn)行50次并記錄其均值、最優(yōu)值、方差，以避免偶然性造成的誤差。其中均值和最優(yōu)值用于評(píng)價(jià)算法尋優(yōu)精度，標(biāo)準(zhǔn)差用于衡量算法的魯棒性。5種算法運(yùn)行結(jié)果如表2所示。

表 2 5種算法的運(yùn)行結(jié)果Tab.2 The running results of five algorithms

從表2可以看出:對(duì)于單峰函數(shù)f1～f5，ISCA算法和SASCA算法在求解5個(gè)函數(shù)時(shí)，基本都找到真實(shí)最優(yōu)值，且標(biāo)準(zhǔn)差皆為0，魯棒性強(qiáng);對(duì)于多峰函數(shù)f6，雖未求得真實(shí)最優(yōu)值，SASCA算法和ISCA算法也有更高的尋優(yōu)精度，比其余算法提高了10多個(gè)數(shù)量級(jí)。對(duì)于多峰函數(shù)f7～f10，ISCA算法在求解函數(shù)f7和f8時(shí)可以直接找到真實(shí)最優(yōu)解，但在函數(shù)f9和f10求解中尋優(yōu)精度和算法魯棒性略為遜色，而SASCA算法在求解時(shí)都找到真實(shí)最優(yōu)值。表明改進(jìn)的算法對(duì)單峰、多峰函數(shù)都具有更高的尋優(yōu)精度和魯棒性。

為比較不同算法的收斂速度，圖3給出了5種算法求解不同測(cè)試函數(shù)的迭代曲線圖，其中f2、f6、f7、f8的迭代曲線較為集中，因此目標(biāo)函數(shù)優(yōu)化值用以10 為底的對(duì)數(shù)形式表示，以便更顯著的區(qū)分5種算法的迭代曲線。從圖3(a)～(j)可以看出：SASCA算法能快速收斂到最優(yōu)值，ISCA算法次之，其余3種算法在迭代500次之后仍未收斂。特別是對(duì)于函數(shù)f2～f4和f6～f9，其余3種算法都陷入了局部最優(yōu)且無(wú)法收斂到最優(yōu)解。因此，本文的改進(jìn)算法收斂速度比其余算法更優(yōu)，能更高效實(shí)現(xiàn)高維函數(shù)的求解。

(a) f1函數(shù)

(b) f2函數(shù)

(c) f3函數(shù)

(d) f4函數(shù)

(e) f5函數(shù)

(f) f6函數(shù)

(g) f7函數(shù)

(h) f8函數(shù)

(i) f9函數(shù)

(j) f10函數(shù)圖 3 5種算法迭代曲線Fig.3 Iterative curve of five algorithms

3.4 統(tǒng)計(jì)分析

為進(jìn)一步比較5種算法的優(yōu)劣性，采用t檢驗(yàn)法比較分析 SASCA 與 SCA、SA、ISA 、SABA算法的性能。5種算法在每個(gè)測(cè)試函數(shù)上都獨(dú)立運(yùn)行50次，因而都有50個(gè)樣本。t檢驗(yàn)使用自由度為98，顯著性水平為0.05的雙尾檢驗(yàn)，檢驗(yàn)結(jié)果如表3所示。表3中，“+”表示對(duì)于同一測(cè)試函數(shù)，SASCA算法顯著性優(yōu)于本列算法；“～”表示對(duì)于同一測(cè)試函數(shù)，SASCA算法與本列算法顯著性相同。

表 3 SASCA算法與其他算法的t檢驗(yàn)Tab.3 t-test of SASCA algorithm and other algorithms

從表3可以看出,SASCA算法的顯著性優(yōu)于SCA、SA、SABA算法。除f3和f9外的其余8個(gè)函數(shù),ISA算法與SASCA算法顯著性相同；對(duì)于函數(shù)f3和f9，SASCA算法顯著性更優(yōu)。從統(tǒng)計(jì)的角度出發(fā)，在大部分測(cè)試函數(shù)上，SASCA算法的顯著性優(yōu)于其他4種算法。

4 結(jié) 語(yǔ)

通過將高斯擾動(dòng)和模擬退火機(jī)制引入正余弦算法，在算法迭代的后期增加種群多樣性以增強(qiáng)算法全局搜索能力。同時(shí)，設(shè)置自適應(yīng)調(diào)整的參數(shù)r1以及對(duì)數(shù)遞減的慣性權(quán)重，實(shí)現(xiàn)全局搜索與局部開發(fā)平衡，以提高算法尋優(yōu)精度和收斂速度。5種算法仿真結(jié)果表明，基于模擬退火的正余弦算法尋優(yōu)精度更高，收斂速度更快。統(tǒng)計(jì)檢驗(yàn)的結(jié)果進(jìn)一步驗(yàn)證了改進(jìn)算法的有效性。