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

李曉婉，韋根原

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

李曉婉，韋根原

（華北電力大學，河北 保定 071003）

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

測試函數；粒子群算法；學習因子；模擬退火算法

1 引言

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

2 粒子群算法

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

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

因為基本微粒算法模型中，微粒的飛行速度直接影響算法的全局收斂性，速度過大，能保證微粒很快飛行全局最優解的區域，但當逼近最優解時，由于微粒飛行缺乏有效的約束和控制，不易收斂到全局最優，因此SHI和EBERHART在算法模型中引入慣性權重系數[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年代初發展起來的一種隨機性質的組合優化方法。它模擬的是高溫金屬降溫的熱力學過程，現在廣泛用于解決組合優化問題。模擬退火算法是局部搜索算法的擴展，從理論上來說，它是一個全局最優算法，在一定條件下可以以概率1收斂于全局最優解[6]。

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

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

基于模擬退火的粒子群算法是把模擬退火機制引入基本粒子群優化算法中，結合兩種算法的優點，保持粒子群算法簡單、容易實現的特點，并改善粒子群算法擺脫局部極值點的能力，提高算法的收斂速度和精度[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）

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

2.3 同步變化學習因子

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

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

3 仿真實驗結果

利用經典測試函數Griewank函數來對算法進行驗證，Griewank函數[11]為：

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

該函數圖形如圖1所示。

通過粒子群算法對Griewank函數進行極值尋優，得到的適應度曲線如圖2所示。

通過同步變化學習因子和基于模擬退火的粒子群算法分別對Griewank函數進行極值尋優，得到的適應度曲線，如圖3所示。

圖1 Griewank函數圖形

圖2 粒子群尋優適應度曲線

圖3 改進粒子群尋優適應度曲線

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

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

4 結論

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

［1］王榮亮.基于非線性規劃和遺傳算法的函數尋優［J］.科技與創新，2019（15）：47-48，50.

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

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

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

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

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

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

［8］張立彬，應建陽，陳教料.基于IPSO-SA算法的溫室番茄產量預測方法［J］.浙江工業大學學報，2019，47（5）：527-533.

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

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

［11］YAN H，JIAN-PING L.Griewank函數優化過程中的獨特現象研究（英文）［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—），女，碩士研究生，研究方向為群體智能算法和智能優化控制。韋根原（1965—），男，碩士研究生導師，研究方向為控制理論與智能儀表。

〔編輯：嚴麗琴〕