李曉婉，韋根原

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

李曉婉，韋根原

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

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

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

1 引言

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

2 粒子群算法

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

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

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

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

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

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

基于模擬退火的粒子群算法是把模擬退火機制引入基本粒子群優(yōu)化算法中，結(jié)合兩種算法的優(yōu)點，保持粒子群算法簡單、容易實現(xià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）

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

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

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

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

3 仿真實驗結(jié)果

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

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

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

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

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

圖1 Griewank函數(shù)圖形

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

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

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

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

4 結(jié)論

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

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

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

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

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

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

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

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

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

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

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

［11］YAN H，JIAN-PING L.Griewank函數(shù)優(yōu)化過程中的獨特現(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ōu)化控制。韋根原（1965—），男，碩士研究生導(dǎo)師，研究方向為控制理論與智能儀表。

〔編輯：嚴麗琴〕