基于模擬退火的粒子群算法尋優(yōu)

李曉婉，韋根原

基于模擬退火的粒子群算法尋優(yōu)

李曉婉，韋根原

（華北電力大學(xué)，河北 保定 071003）

粒子群算法是一種基于群體智能的隨機(jī)尋優(yōu)算法，特別是針對(duì)復(fù)雜的工程問題，通過迭代尋優(yōu)計(jì)算，能迅速找到近似解，因此粒子群算法在工程計(jì)算機(jī)中被廣泛應(yīng)用，但是粒子群優(yōu)化算法容易陷入局部最優(yōu)，收斂精度低且不易收斂。因此，針對(duì)粒子群優(yōu)化算法的不足，通過同步改變學(xué)習(xí)因子以及將模擬退火算法與粒子群算法相結(jié)合的方法對(duì)函數(shù)進(jìn)行極值尋優(yōu)。結(jié)果表明，同步改變學(xué)習(xí)因子以及將模擬退火算法與粒子群算法結(jié)合后的算法提高了全局尋優(yōu)能力，其中模擬退火與粒子群結(jié)合算法具有最好的收斂性和魯棒性，求解結(jié)果更為精確。

測(cè)試函數(shù)；粒子群算法；學(xué)習(xí)因子；模擬退火算法

1 引言

近年來，利用智能算法對(duì)函數(shù)進(jìn)行極值尋優(yōu)是現(xiàn)實(shí)生活中很多科學(xué)計(jì)算和工程問題都采用的方法。將復(fù)雜難解的現(xiàn)實(shí)問題轉(zhuǎn)化成函數(shù)優(yōu)化問題，并利用智能算法求出該函數(shù)模型在可行域內(nèi)的最優(yōu)解在工程計(jì)算機(jī)中廣泛應(yīng)用[1]。本文就是針對(duì)粒子群算法尋優(yōu)存在的容易陷入局部最優(yōu)，收斂精度低且不易收斂的缺點(diǎn)進(jìn)行改進(jìn)，通過同步改變學(xué)習(xí)因子以及將模擬退火算法與粒子群算法相結(jié)合的方法，得到兩個(gè)不同的尋優(yōu)結(jié)果，仿真結(jié)果表明兩種方法均提高了全局尋優(yōu)能力，其中基于模擬退火的粒子群尋優(yōu)算法，大大提高了全局尋優(yōu)能力，具有較好的收斂性和魯棒性，求解結(jié)果更為精確。

2 粒子群算法

粒子群算法是一種基于群體的隨機(jī)優(yōu)化技術(shù)。與基于群體的其他的進(jìn)化算法相比較而言不同的方面是：進(jìn)化計(jì)算遵循的是適者生存原則，而粒子群算法模擬社會(huì)，是對(duì)鳥群覓食行為的模擬[2]。算法首先將每只鳥抽象成沒有體積和質(zhì)量的粒子，即將每個(gè)可能產(chǎn)生的解表述為群中的一個(gè)微粒，每個(gè)微粒都具有自己的位置向量和速度向量，以及一個(gè)由目標(biāo)函數(shù)決定的適應(yīng)度。所有微粒在搜尋空間中以一定速度飛行，然后每個(gè)粒子通過追隨個(gè)體最優(yōu)和全局最優(yōu)來實(shí)時(shí)地決定各自的“速度”和“位置”，從而在整個(gè)解空間中實(shí)現(xiàn)對(duì)全局最優(yōu)解的搜索[3]。具有算法簡(jiǎn)單、容易實(shí)現(xiàn)的特點(diǎn)，但是存在陷入局部極值點(diǎn)和收斂精度低且不易收斂的缺點(diǎn)。

粒子群算法與其他的進(jìn)化類算法相比不同的是，粒子群算法中沒有進(jìn)化算子，而是將每個(gè)個(gè)體看作搜索空間中沒有質(zhì)量和體積的微粒，并在搜索空間中以一定的速度飛行，該飛行速度由個(gè)體飛行經(jīng)驗(yàn)和群體的飛行經(jīng)驗(yàn)進(jìn)行動(dòng)態(tài) 調(diào)整[4]。

因?yàn)榛疚⒘Ｋ惴Ｐ椭?，微粒的飛行速度直接影響算法的全局收斂性，速度過大，能保證微粒很快飛行全局最優(yōu)解的區(qū)域，但當(dāng)逼近最優(yōu)解時(shí)，由于微粒飛行缺乏有效的約束和控制，不易收斂到全局最優(yōu)，因此SHI和EBERHART在算法模型中引入慣性權(quán)重系數(shù)[5]，微粒速度和位置表達(dá)式為：

i，j（+1）={i，j（）+11［i，j－i，j（）］+

22［g，j－i，j（）］} （1）

i，j（+1）=i，j（）+i，j（+1）（=1，…，）（2）

2.1 模擬退火算法

模擬退火是80年代初發(fā)展起來的一種隨機(jī)性質(zhì)的組合優(yōu)化方法。它模擬的是高溫金屬降溫的熱力學(xué)過程，現(xiàn)在廣泛用于解決組合優(yōu)化問題。模擬退火算法是局部搜索算法的擴(kuò)展，從理論上來說，它是一個(gè)全局最優(yōu)算法，在一定條件下可以以概率1收斂于全局最優(yōu)解[6]。

在實(shí)際應(yīng)用中將內(nèi)能模擬為目標(biāo)函數(shù)值，將溫度模擬為控制參數(shù)，然后從一個(gè)給定解開始，從其鄰域中隨機(jī)產(chǎn)生一個(gè)新解，接受準(zhǔn)則允許目標(biāo)函數(shù)在一定范圍內(nèi)接受使目標(biāo)函數(shù)惡化的解，算法持續(xù)進(jìn)行“產(chǎn)生新解—計(jì)算目標(biāo)函數(shù)差—判斷是否接受新解—接受或舍棄”的迭代過程[7]，對(duì)應(yīng)著固體在某一恒定溫度下趨于熱平衡的過程。然后，經(jīng)過多次的解變化后，就可以求出給定的控制參數(shù)值的優(yōu)化問題的相對(duì)最優(yōu)解。再之后，減少控制參數(shù)的值，重復(fù)執(zhí)行上述迭代過程。當(dāng)控制參數(shù)逐漸減小并趨向于零時(shí)，系統(tǒng)也會(huì)慢慢趨于平衡狀態(tài)，最后系統(tǒng)狀態(tài)對(duì)應(yīng)于優(yōu)化問題的整體最優(yōu)解。

2.2 基于模擬退火算法的粒子群算法

基于模擬退火的粒子群算法是把模擬退火機(jī)制引入基本粒子群優(yōu)化算法中，結(jié)合兩種算法的優(yōu)點(diǎn)，保持粒子群算法簡(jiǎn)單、容易實(shí)現(xiàn)的特點(diǎn)，并改善粒子群算法擺脫局部極值點(diǎn)的能力，提高算法的收斂速度和精度[8]。

基于模擬退火算法的粒子群算法采用帶壓縮因子的粒子群算法，速度和位置更新公式如下：

i，j（+1）={i，j（）+11［i，j（）－i，j（）］+

22［i，j（）－i，j（）］} （3）

i，j（+1）=i，j（）+i，j（+1）（=1，…，）（4）

改進(jìn)后的算法尋優(yōu)步驟如下：①初始化微粒的位置和速度；②計(jì)算種群中每個(gè)微粒的目標(biāo)函數(shù)值；③更新微粒的pbest和gbest；④重復(fù)執(zhí)行下列步驟，對(duì)微粒的pbest進(jìn)行SA鄰域搜索，更新各微粒的pbest，執(zhí)行最優(yōu)選擇操作，更新種群gbest，gbest是否滿足終止條件？若是，轉(zhuǎn)④，否則轉(zhuǎn)⑤；⑤輸出種群最優(yōu)解。

2.3 同步變化學(xué)習(xí)因子

為了對(duì)比明顯，同時(shí)對(duì)學(xué)習(xí)因子同步改變粒子群算法進(jìn)行尋優(yōu)仿真，與基于模擬退火的粒子群算法仿真結(jié)果形成對(duì)比，更可以清晰看出改進(jìn)后的算法的優(yōu)越性。

對(duì)于學(xué)習(xí)因子一般固定為常數(shù)，且取值為2，但在實(shí)際應(yīng)用中，也有一些其他的取值方式，常見的有同步變化和異步變化兩種，同步變化的學(xué)習(xí)因子，指的是將學(xué)習(xí)因子1和2的取值范圍設(shè)定為［min，max］，第次迭代式的學(xué)習(xí)因子取值公式[10]為：

3 仿真實(shí)驗(yàn)結(jié)果

利用經(jīng)典測(cè)試函數(shù)Griewank函數(shù)來對(duì)算法進(jìn)行驗(yàn)證，Griewank函數(shù)[11]為：

式（6）中，i∈［﹣600，600］。該函數(shù)存在許多局部極小點(diǎn)，數(shù)目與問題的維數(shù)有關(guān)，全局最小值0在（1，2，3，…，n）=（0，0，0，…，0）處可以獲得，此函數(shù)是典型的非線性多模態(tài)函數(shù)，具有廣泛的搜索空間，通常被認(rèn)為是優(yōu)化算法最難處理的復(fù)雜多模態(tài)問題。

該函數(shù)圖形如圖1所示。

通過粒子群算法對(duì)Griewank函數(shù)進(jìn)行極值尋優(yōu)，得到的適應(yīng)度曲線如圖2所示。

通過同步變化學(xué)習(xí)因子和基于模擬退火的粒子群算法分別對(duì)Griewank函數(shù)進(jìn)行極值尋優(yōu)，得到的適應(yīng)度曲線，如圖3所示。

圖1 Griewank函數(shù)圖形

圖2 粒子群尋優(yōu)適應(yīng)度曲線

圖3 改進(jìn)粒子群尋優(yōu)適應(yīng)度曲線

通過對(duì)尋優(yōu)結(jié)果進(jìn)行對(duì)比可以看出，基于模擬退火的粒子群算法隨著進(jìn)化過程的進(jìn)行，溫度會(huì)慢慢下降，接收差解的概率會(huì)逐漸減小，提高了收斂性能。該算法不但基本保持住了基本粒子群優(yōu)化算法簡(jiǎn)便、易實(shí)現(xiàn)的優(yōu)點(diǎn)，而且還增強(qiáng)了粒子群優(yōu)化算法的全局尋優(yōu)能力，加快了算法的進(jìn)化速度，提高了收斂精度。

對(duì)于學(xué)習(xí)因子同步改變粒子群算法而言，可以實(shí)現(xiàn)比較好的收斂，但是收斂速度相對(duì)于改進(jìn)算法來說會(huì)差一些[11]。

4 結(jié)論

通過仿真結(jié)果，可以得到基于模擬退火的粒子群算法是有一定有效性和優(yōu)越性的，既保持了粒子群算法簡(jiǎn)單、容易實(shí)現(xiàn)的特點(diǎn)，又在一定程度上改善了粒子群算法易陷入局部極值點(diǎn)的特點(diǎn)。因此。在解決實(shí)際問題的過程中，適當(dāng)利用相應(yīng)的智能算法以及不斷改進(jìn)的新算法，通過對(duì)函數(shù)尋優(yōu)的方式，是可以高效快速解決實(shí)際工程中遇到的問題的。

［1］王榮亮.基于非線性規(guī)劃和遺傳算法的函數(shù)尋優(yōu)［J］.科技與創(chuàng)新，2019（15）：47-48，50.

［2］黃磊.粒子群優(yōu)化算法綜述［J］.機(jī)械工程與自動(dòng)化，2010（5）：197-199.

［3］楊娜，荊園園.基于改進(jìn) PSO算法的函數(shù)極值尋優(yōu)研究［J］.計(jì)算機(jī)仿真，2015，32（9）：263-266.

［4］焦嵩鳴，譚雨林，桑士杰.基于改進(jìn)粒子群算法的主汽溫控制系統(tǒng)PID參數(shù)優(yōu)化［J］.電力科學(xué)與工程，2012，28（12）：9-13.

［5］李艷，陳倩.基于慣性權(quán)重非線性遞減的粒子群優(yōu)化算法研究［J］.陜西科技大學(xué)學(xué)報(bào)，2020，38（3）：166-171.

［6］王娟，唐秋華，毛永年.基于遺傳模擬退火算法的自動(dòng)化制造單元周期調(diào)度［J］.武漢科技大學(xué)學(xué)報(bào)，2020，43（4）：283-289.

［7］高尚，楊靜宇，吳小俊，等.基于模擬退火算法思想的粒子群優(yōu)化算法［J］.計(jì)算機(jī)應(yīng)用與軟件，2005（1）：103-104，80.

［8］張立彬，應(yīng)建陽，陳教料.基于IPSO-SA算法的溫室番茄產(chǎn)量預(yù)測(cè)方法［J］.浙江工業(yè)大學(xué)學(xué)報(bào)，2019，47（5）：527-533.

［9］郭明杰，韋根原.基于SA-PSO算法的主汽溫控制系統(tǒng)參數(shù)優(yōu)化研究［J］.山東電力技術(shù)，2019，46（7）：44-47.

［10］胡丁丁，梁翀.基于改進(jìn)粒子群優(yōu)化算法的無人機(jī)路徑規(guī)劃研究［J］.數(shù)字技術(shù)與應(yīng)用，2020，38（4）：104，107.

［11］YAN H，JIAN-PING L.Griewank函數(shù)優(yōu)化過程中的獨(dú)特現(xiàn)象研究（英文）［J］.Frontiers of Information Technology & Electronic Engineering，2019，20（10）：1344-1361.

TPL8

A

10.15913/j.cnki.kjycx.2020.22.007

2095－6835（2020）22－0019－02

李曉婉（1995—），女，碩士研究生，研究方向?yàn)槿后w智能算法和智能優(yōu)化控制。韋根原（1965—），男，碩士研究生導(dǎo)師，研究方向?yàn)榭刂评碚撆c智能儀表。

〔編輯：嚴(yán)麗琴〕