一種自適應模擬退火粒子群優化算法

閆群民，馬瑞卿，馬永翔，王俊杰

(1．西北工業大學 自動化學院，陜西 西安 710072；2.陜西省工業自動化重點實驗室，陜西 漢中 723001 ；3.陜西理工大學 電氣工程學院，陜西 漢中 723001)

自然界中的生物均具有一定程度的群體行為。在計算機中建模分析這些行為是人工生命研究的一個重要方面，其背后隱藏的規律將對人類的生活產生很大的啟發。粒子群算法(Particle Swarm Optimization，PSO)[1]是KENNEDY博士和EBERHART教授通過對鳥群覓食模型進行改進所提出的。因為粒子群算法需設置的參數少且計算結構簡單，目前已經廣泛地應用在實際工程中，如多目標控制、神經網絡研究、復雜多峰值優化求解問題等。眾多的學者針對粒子群算法早熟和收斂速度慢等問題，做了大量的優化研究，主要可以分為3個方向：(1) 最早出現的是針對粒子群算法自身迭代策略的改進，將原本固定不變的學習因子和慣性權重系數改進，為其設置隨著迭代次數線性或非線性動態變化的調整策略[2-6]。在搜索的初期、中期及末期等階段有著不同的搜索重點，為達到平衡全局和局部搜索能力的要求，在保證搜索精度的情況下提升搜索速度。文獻[6]中針對不同的迭代策略進行對比，經過仿真證明在初始權值和最終權值相同的情況下，正弦函數遞減策略優于線性策略，而線性策略優于正切函數策略。(2) 將粒子群算法的優勢和其他優化算法進行融合，結合其他算法的優勢來改進粒子群算法[7-8]。文獻[8]將牛頓最速下降因子引入粒子群算法中，提高了粒子群體的全局收斂性和收斂速度，克服了這種算法易“早熟”的缺點。(3) 針對粒子種群的拓撲結構進行改進[9-12]。文獻[11]將原本的D維空間轉化到混沌空間，根據混沌具有遍歷性等特點進行迭代，提升了優化效果；文獻[12]結合兩種鄰居拓撲結構，將種群分為3個子群，并采用不同的學習因子組合不同的搜索側重點，經過一定迭代次數后對子種群的性能進行評估，指導粒子在不同子群間遷移，提升了算法的綜合性能。筆者將前兩種類型進行改進，采用線性變化的策略控制社會及自我認知因子，利用雙曲正切函數來控制慣性權重系數，在此基礎上融合模擬退火算法提升了算法跳出局部最優解的能力。選出5種近幾年被提出的改進粒子群算法的優化算法[12-16]，與筆者提出的算法共同通過CEC2017中選出的7種測試函數進行尋優測試(其中包含1種單峰函數和6種典型復雜多峰函數)，結果證明該優化算法在尋優速度、收斂精度及算法穩定性等方面有顯著的提升。

1 相關工作

1.1 粒子群算法

粒子群算法的尋優過程通過粒子在搜索空間的飛行完成。粒子每次迭代中的移動由3個部分組成，分別是對上一次速度的繼承、自身學習以及種群的信息交互，其表達式為

vi(k+1)=ωvi(k)+c1r1(Pbest.i(k)-xi(k))+c2r2(Gbest-xi(k)) ，

(1)

xi(k+1)=xi(k)+vi(k+1) ，

(2)

其中，ω為慣性權重系數；c1、c2分別表示自身認知因子和社會認知因子，是控制粒子群算法的迭代最重要的參數；xi(k)和vi(k)分別代表第i個粒子第k次迭代時的位置和速度；r1和r2為隨機數；Pbest.i為第i個粒子個體最優位置；Gbest為種群最佳位置。飛行粒子的搜索能力不僅受到粒子之前的速度影響，還受到兩個學習因子指導。通過c1控制自我認知部分，指導粒子向該粒子自身的歷史最優解飛行；c2控制社會認知部分，體現種群中各粒子的信息交換，指導粒子向種群最優解的位置飛行。實際問題的尋優的終止條件設置為全局最優解滿足適應度的要求，而實驗中為比較不同算法的效果，設置迭代終止條件為達到最大迭代次數時終止。

每次粒子飛行前，先判斷vi(k)是否越過設置的速度范圍。若越過，則取速度邊界值替代當前速度。飛行后再判斷xi(k)是否超出最大搜索空間。若超出，同樣取邊界值替代當前值。根據相應的適應度值的變化來更新粒子群中Pbest.i和Gbest，更新方程為

(3)

(4)

1.2 模擬退火法

模擬退火算法(Simulated Annealing，SA )是由米特羅波利斯在20世紀50年代根據對固態物質退火過程的研究而提出的一種算法，后在組合優化領域中得到大規模的應用推廣，如現代的玻爾茲曼機、圖像恢復處理、VLSI最優設計、機器學習等科學領域中的組合優化問題。該算法是一種基于蒙特卡羅思想設計的近似求解最優化問題的方法，結構簡單易實現，初始條件限制少，使用靈活且運行效率高，與其他算法的結合能力較強，有著廣闊的前景。模擬退火算法的核心源自固體降溫熱力學過程，退火指物體的能量隨著溫度的降低達到最低值的過程。米特羅波利斯準則是模擬退火算法中的核心準則，其特別之處在于溫度下降過程中不僅能夠接受優值，也會根據溫度變量產生的概率接受較差的值，增大了算法在尋優過程中跳出局部優解的概率。將粒子群算法和模擬退火算法相結合，可以有效地減少粒子群算法陷入局部最優解的概率。

模擬退火算法在迭代初始階段需要根據種群的初始狀態設置一個初始溫度。每次迭代對模擬固體內部粒子在溫度下降情況下的移動，根據米特羅波利斯準則判斷是否由干擾產生的新解替代全局最優解，其表達式如下：

(5)

其中，Ei(k)表示第i個粒子在第k次迭代時的內能，即當前粒子的適應度值；Eg表示當前種群最優點的內能；Ti表示當前溫度。溫度每次迭代會以一定程度線性衰減，尋優過程是不斷尋找新解和緩慢降溫的交替過程。Ei(k)完全決定了其下一次產生的新狀態Ei(k+1)，與之前的Ei(0)至Ei(k-1)無關，這個過程是一個馬爾可夫過程。使用馬爾可夫過程分析模擬退火步驟，經過有限次的轉換在溫度Ti下的平衡態的分布如下：

(6)

(7)

其中，Smin是最優值的搜索空間集合。當溫度降到0時，pi的分布見式(7)。溫度下降的同時伴隨著大量的狀態轉移，達到熱平衡的狀態，則找到全局最優的概率為1。模擬退火算法最大的優點是跳出局部最優點的能力突出。

2 自適應模擬退火粒子群算法

以往應用經典的粒子群算法設置ω、c1和c2的值時，大多依賴經驗的判斷，或者根據大量的仿真實驗來確定一個固定的值。但通過上述的分析知，如果這3個參數能夠隨著優化的進行不斷變化的話，粒子群算法將會有更加優秀的效果。慣性權重系數ω直接影響著算法搜索能力的強弱，控制粒子繼承以往運動趨勢，即搜索飛行的慣性。若需要算法的全局搜索能力較強，則設置ω的值比較大，但受前一次迭代速度的影響較大，相應的粒子飛行距離較大，不利于局部尋優。若需要進行局部精細解的搜索，提升局部區域的尋優能力，則設置ω的值較小，但陷入局部最優的概率會變大。ω值的選取與算法收斂速度和全局搜索能力成正比，與局部搜索能力成反比。筆者選取[-4，4]之間負的雙曲正切曲線來控制慣性權重系數的變化。雙曲正切曲線是一個非線性的控制策略，在搜索初期其遞減速度較慢，給粒子充分的時間進行大范圍的全局搜索，減小陷入局部最優的情況；中期近似線性遞減，逐漸加強局部搜索的能力；后期變化率再次減小，著重細致的局部搜索，精準確定全局最優解。慣性權重函數如下：

ω=(ωmax+ωmin)/2+tanh(-4+8×(kmax-k)/kmax)(ωmax-ωmin)/2 ，

(8)

圖1 慣性系數自適應變化圖

其中，ωmax，ωmin是慣性權重系數的最大值和最小值，文中取ωmax=0.95，ωmin=0.40。經大量實驗證明，采用如上取值時算法性能會大幅度提升[2]。k是當前迭代次數，kmax是最大迭代次數，其圖像見圖1。

當c1>c2時，粒子的運動更偏向個體最優的方向；反之，則更偏向群體最優方向。筆者所提的優化算法初始階段注重全局搜索，著重突出粒子的自我認知能力，注重粒子運動的遍歷性，減小陷入局部最優解的概率。隨著迭代的進行，加強粒子間的交流，使種群最優解的位置對每個粒子的運行起到更大的影響作用，著重對Gbest的附近進行局部搜索。對應著這樣的搜索策略，隨著迭代次數的增加，ω不斷減小，c1逐漸減小，c2逐漸增大。筆者采取如下參數變化策略：

c1=c1max-k(c1max-c1min)/kmax，

(9)

c2=c2min-k(c2min-c2max)/kmax，

(10)

其中，c1max，c1min分別是自我學習因子的最大值和最小值；c2max，c2min分別是社會學習因子的最大值和最小值。參照文獻[16]并進行大量實驗后，取c1max=2.50，c2max=1.25，c1min=1.25，c2min=2.50。隨著迭代次數k的增加，c1由2.50線性減小至1.25，而c2則由1.25逐步線性增加到2.50，這樣設置就滿足了初期注重粒子在空間上的遍歷性要求，增強了全局搜索的能力。在迭代次數過半時，c1

將模擬退火算法中的米特羅波利斯準則引入迭代中。根據最初的粒子最優值設置初始溫度，并且每次迭代后以一定的降溫系數μ衰減。具體操作如下：

(11)

其中，T為初始溫度。每次迭代后，計算更新后位置的內能(適應度)與種群最優點內能的差距，根據式(5)計算得出的概率與rand()進行對比，判斷是否接受較差的解。取降溫系數μ=0.95。筆者所提出的自適應模擬退火粒子群算法對粒子群算法的3個重要參數進行了自適應變化且加入了模擬退火操作，增加了尋優的精度和速度。具體步驟如下：

步驟1 設置搜索空間及搜索速度的邊界值，設置種群規模及最大迭代次數kmax。

步驟2 隨機產生種群中所有粒子的初始位置和初始速度。

步驟3 評價全局粒子的適應度值并記錄Gbest，根據式(11)設置模擬退火的初始溫度。

步驟4 根據式(8)～式(10)自適應地改變ω、c1和c2。

步驟5 根據式(1)改變粒子速度，根據式(2)進行一次迭代尋優。

步驟6 計算移動后粒子的適應度。

步驟7 根據式(3)更新粒子的自身的歷史最優位置。

步驟8 根據式(5)計算接受新解的概率pi(k)。

步驟9 以米特羅波利斯準則為依據，對比概率pi(k)與rand()，判斷是否由產生的新解替代全局最優解進行退火操作，更新溫度。

步驟10 判斷是否達到最大迭代次數kmax，若未達到則返回步驟4。

步驟11 輸出當前最優粒子，即尋優結果，算法終止。

3 實驗及結果分析

3.1 測試函數及參數設置

為了驗證筆者提出的模擬退火粒子群優化算法的效果，現從CEC2017測試集中選取出1種單峰函數f1及6種多峰函數f2-f7來對筆者所提出的算法進行測試，根據要求設置其搜索空間。具體的函數表達式見表1。

同時在不同類型的粒子群算法的優化算法中選取5種，分別是MSMPSO[12](Multi-population based Self-adaptive Migration PSO)，RPPSO[13](PSO with Random Parameters)，PSO-DAC[14](PSO baesd on Dynamic Acceleration Coefficients)，NDPSO[15](PSO with inertia weight decay by Normal Distribution)和APSO-DA[16](Adaptive PSO via Disturbing Acceleration coefficents)進行仿真。通過對比筆者所提算法與這5種算法在搜索空間維數分別是D=10和D=30時，粒子群包含的粒子數相同，最大迭代次數相同的情況下的運行效果，來體現筆者所改進的算法的優越性。

表1 測試函數信息表

3.2 算法精度對比

使用MATLAB 2016b環境進行仿真驗證。所選取的5種對比算法的慣性權重系數和認知因子等參數都按照文獻[12-16]中的設置，粒子種群規模統一設置為30，最大迭代次數kmax=1 000。每個測試函數的維數在D=10和D=30的情況下分別運行30次，結果記錄如表2及表3所示。從表2～表3中根據30次尋優結果的平均值和標準差可以看出，無論是針對單峰函數還是多峰函數，本文算法針對多種測試函數的搜索精度都優于以往的算法。f2～f5這4個復雜的多峰函數的尋優精度，優于以往優化算法數十倍。f1～f5的尋優結果的標準差最小，有極強的搜索穩定性。

表2 D=10時6種優化算法的運行結果對比

表3 D=30時6種優化算法的運行結果對比

搜索空間維度的增長，表示著每次迭代所需要處理的數據成倍提升，全局最優點位置信息也更加復雜，尋優任務變得十分困難。在實際工況下，面對高維問題首先要做的是降低維數，減少計算量。D=30的這類高維數情況較少，但為證明優化算法面對高維問題時的性能，進行了針對D=30時的尋優實驗。實驗中面對搜索空間維數從10增長到30，大部分算法的收斂精度都大幅度下降，而筆者所提出的算法依然有著精準的尋優精度，針對高維數的復雜多峰測試函數有很強的尋優結果。

3.3 收斂速度對比

為了更加直觀地對比不同算法在精度上的差別以及迭代速度的優劣性，選出部分測試函數的優化曲線圖。圖2～圖5分別顯示在高維數D=30時，筆者所提算法與5種算法的對比。圖2顯示在面對簡單的單峰函數f1時，文中算法的速度優勢并不突出，個別算法也具有較快的速度和精度。由圖3～圖5可知，在面對f3、f5和f7復雜多峰函數時，筆者所提算法在收斂速度上的優勢得到顯著的體現，尋優速度快的同時也保證了收斂的精度。觀察圖5，面對搜索空間極大、峰值極多且分布極不規則的Schwefel測試函數，并且這個函數的各個局部優解的差值極小，尋優難度較大。可以看出在迭代到中期(500次左右)時大部分算法已經陷入局部優解，因為這些算法的尋優過程在這個階段，種群中的大部分粒子已經聚集在局部最優處。隨著越來越多粒子受種群最優的影響被引向局部最優解處，所以跳出局部最優解的能力逐步減弱至喪失；但筆者所提的算法雖然在初始迭代的前400次，其精度優勢并不突出，但其優勢突出體現在其因為融合了模擬退火操作，極大程度地增強了跳出局部最優的能力，在迭代800多次的后期，仍然可以不斷地更新全局最優值，保證跳出局部最優的能力，提升搜索結果的精準性。綜上所述可知，筆者所提的算法在收斂速度上也具有一定程度的優勢。

圖2 f1函數的6種方法優化曲線對比圖

圖3 f3函數的6種方法優化曲線對比圖

圖4 f5函數的6種方法優化曲線對比圖

圖5 f7函數的6種方法優化曲線對比圖

4 結束語

采用雙曲正切函數控制慣性權重系數隨著迭代進行非線性變化，用線性變化策略控制認知因子c1、c2，從而保證了3個控制搜索性能的參數都能隨著迭代進行自適應變化；同時，在粒子群算法尋優過程中加入模擬退火操作，通過米特羅波利斯準則引導種群以一定的概率接受差解，彌補了粒子群算法易陷入局部最優的缺陷，極大地提升了粒子群算法的搜索能力，滿足了算法在不同階段的搜索要求。面對多種高維多峰的測試函數，與以往的粒子群優化算法的尋優效果進行對比，其尋優精度提升數十倍，能精準地收斂在全局最優處，以較快的收斂速度完成尋優目標。