基于Metropolis準則的自適應模擬退火粒子群優化

鄧紹強，郭宗建，李 芳，湯可宗，劉 康

（景德鎮陶瓷大學信息工程學院，江西景德鎮 333403）

0 引言

粒子群優化（Particle Swarm Optimization，PSO）算法是一種受鳥群覓食行為啟發而提出的群體智能優化算法［1-3］。PSO 原理簡單、易于理解且參數較少，面向最優化問題求解過程具有搜索能力強、收斂速度較快等優點，現已廣泛應用于模式識別［4］、路徑規劃［5］、圖像處理［6-7］等理論研究及工程應用領域。

然而，PSO 應用于多模態優化問題求解往往存在易早熟、收斂精度較低等問題。為有效提高PSO 搜索最優解的求解效率，避免PSO 易陷入局部區域而發生早熟收斂現象，本文提出一種新的基于Metropolis 準則的自適應模擬退火粒子群優化（Adaptive Simulated Annealing Particle Swarm Optimization，ASAPSO）算法。首先，ASAPSO 采用一種新的自適應極值慣性權重設置方式，該方式將增強粒子種群全局搜索和局部搜索的有序轉換；其次，以粒子經歷的局部最優解為交流學習對象，構建粒子間學習交流的中心粒子，從而增強粒子個體的社會學習能力；最后，粒子群體搜索過程根據所設計的模擬退火選擇概率變換粒子飛行方向，由中心粒子引領粒子的飛行搜索，避免搜索過程陷入局部最優區域，從而提高最優解的搜索效率和精度。

1 相關研究

針對PSO 易早熟收斂且精度低等問題，諸多學者從如下方面對PSO 進行研究并提出有效的改進策略：

（1）慣性權重控制。例如，Shi 等［8］描述了一種慣性權重的設置方式并采用線性遞減策略改進PSO 算法，提高了粒子群體搜索最優解的效率；閆群民等［9］使用一種雙曲正切策略自適應控制慣性權重變化，并引入模擬退火思想對全局最優粒子進行擾動，提升算法收斂精度和穩定性；徐浩天等［10］以正態分布曲線作為慣性權重的衰減策略曲線，通過引入控制因子對粒子位置進行改進，使得所提出的改進PSO 算法能很好地在優化過程中平衡全局搜索和局部搜索能力。

（2）粒子演化進程中對粒子行為的改善。例如，Zhan等［11］將粒子尋優分成4 個階段，根據階段的不同，通過模糊控制自適應確定組合參數，從而提升PSO 算法的收斂速度和精度；湯可宗等［12］引入廣義中心粒子和狹義中心粒子，提出雙中心粒子群優化，提升了PSO 算法的收斂速度和精度；朱經緯等［13］針對陷入局部最優的粒子，給予一個較大的速度將其彈射出去，增強了算法的全局搜索能力。此外，在PSO 中融入其他啟發示搜索算法特性以進一步增強算法多樣性及搜索能力。

（3）融合其他啟發式搜索算法特性。例如，高鷹等［14］將模擬退火思想引入具有雜交和高斯變異的粒子群優化算法中，改善了算法跳出局部最優的能力；劉玉敏等［15］在算法中引入選擇、變異算子保持種群多樣性，使其具有跳出局部最優的能力；李瀟等［16］采用自然選擇策略，將適應度好的一半粒子速度位置覆蓋至較差的一半粒子，使種群一直以較好的全局最優進行搜索，從而加快改進PSO 的收斂速度；Enireddy 等［17］將布谷鳥搜索和粒子群優化結合，提升了神經網絡對圖像分類的學習效率；周蓉等［18］在PSO中融合灰狼算法思想進一步提高算法收斂精度。

上述研究側重于粒子跳出局部最優解區域的改進策略。然而，當個別陷入局部最優區域的粒子引領整個種群飛行時，其他粒子將快速聚集在局部最優區域從而加快算法早熟。本文提出的ASAPSO 算法中，模擬退火策略不僅作為一種擾動準則對全局最優粒子進行小范圍局部擾動，也作為一種接受準則用于計算新粒子引領整個種群飛行的概率。此外，所構建的自適應極值慣性權重調整策略能有效控制粒子的慣性權重隨迭代過程的自適應變化，并在粒子演化進程中由粒子個體間的學習交流定義新的飛行方向，并由中心粒子引導粒子飛行。

2 相關概念

2.1 Metropolis準則

模擬退火思想源于固體材質的物理退火原理，固體在高溫情況下冷卻至常溫狀態，其固體內部的粒子會隨著溫度的逐漸降低而釋放自身內能，逐漸使粒子趨于有序狀態，最后在常溫狀態下達到穩定基態。在某個特定溫度T下，由于粒子的運動，固體內部系統的內能會發生改變，如果系統內能朝著減少的方向進行，就接受該變化；反之，則以一定概率決定是否接受這種狀態變化。基于這種粒子狀態變化過程，Metropolis 準則按式（1）定義物體在溫度T下固體由i狀態轉化至j狀態的概率。

其中，e為自然對數，E（i）和E（j）表示物體在i狀態和j狀態下的內能，K是玻爾茲曼常數。

2.2 基本PSO算法

基本PSO 是模擬鳥群覓食過程在給定搜索空間內搜索全局最優解的重復迭代過程。該迭代過程中，每個粒子模擬一只鳥兒，具有速度和位置兩個特征量。粒子在搜索空間中的位置表示問題的一個潛在可行解，而速度表示粒子在搜索空間內一次迭代搜索飛躍的距離。每個粒子通過評價自身的適應度值并跟蹤兩個極值不斷更新自身飛行方向和位置，兩個極值分別是：個體粒子在尋優過程中經歷的歷史最優值Pbest，以及粒子群體在尋優過程中經歷的種群最優值Gbest。每個粒子按式（2）和式（3）更新自身速度和位置。

其中，k是迭代次數，分別表示第i個粒子在第k次迭代時的速度和位置。r1和r2是介于［0，1］區間的隨機數；c1和c2是兩個學習因子，分別控制個體極值Pbest和全局極值Gbest對粒子飛行速度的權重影響，取c1=c2=2；粒子群搜索過程還需判斷自身速度及位置是否越界，常使用兩種越界行為處理方法［10］：一是將粒子越界對應的維度設置為相應維度的邊界值；二是在可行解空間范圍內隨機生成一個新的位置。w為慣性因子，使粒子保持運動慣性，控制著粒子的搜索范圍。當w值較大時，粒子全局搜索能力加強；反之，局部搜索能力加強。PSO 搜索過程中，w常采用線性遞減慣性權重設置方式［12］，即隨著迭代的進行，以線性遞減方式逐代減少慣性權重至一個預先設定的最低值。

3 自適應模擬退火粒子群（ASAPSO）算法

伴隨著迭代過程，粒子種群搜索區域逐漸由全局搜索范圍轉入局部搜索區域，粒子種群在Gbest引領下飛行至局部最優解區域，整個粒子種群將收斂至局部最優解或其鄰近區域。此時，Gbest繼續引導粒子飛行往往不利于粒子種群的全局搜索，若無局部遷移策略，整個粒子種群搜索將陷入局部最優區域。為此，結合粒子真實的自然狀態飛行方式，可在粒子局部最優解之間引入一種新的飛行方式以重新引領粒子種群的集體飛行過程。以Griewank函數為例，如圖1 所示，Pi（i=1，2，3，4）表示粒子i某一次迭代過程所處位置，該次迭代搜索對應的種群最優位置為Gbest_1，五角星標記為所求問題的全局最優解Gbest_e，菱形標記是粒子i經歷的局部最優解，即粒子i的個體極值Pbest_i（i=1，2，3，4），十字形標記是基于個體極值Pbest_2 和Pbest_3交流構建的中心粒子Gbest2，3，該中心粒子除不具有速度外，與其它粒子屬性保持一致，如，粒子位置更新、全局極值競爭、適應度評價等信息操作，分析觀察發現，如果考慮粒子在多個局部最優解之間方向飛行，粒子飛行方向有可能指向全局最優解Gbest_e或其鄰近區域，例如，在中心粒子Gbest2，3的引領下，粒子群體將更快地向全局最優解靠近。因此，從粒子真實的自然飛行狀態反映出：在粒子群體之間進行局部最優解的信息交流，以此構建新的中心粒子，由中心粒子引領整個粒子種群的飛行，將有利于避免粒子群體陷入局部最優區域。粒子種群將更加快速地趨向于所求解問題的全局最優解。

3.1 中心粒子

Fig.1 Individual extreme value information exchange圖1 個體極值信息交流

在粒子群體飛行過程中，為加強個體粒子之間的信息交流，以粒子經歷的局部最優解為交流學習對象，每個粒子均可從粒子種群中任選其他粒子的局部最優解進行交流學習并構建新的中心粒子，中心粒子將增強粒子個體的社會學習能力。在此，定義粒子i向粒子j進行學習交流而構建的中心粒子如式（4）所示。

其中，rand為介于0 和1 之間的隨機數，Pbesti和Pbestj分別是粒子i和j的個體極值。粒子迭代飛行過程中，以中心粒子引領粒子群體飛行，粒子速度更新公式如式（5）所示。

3.2 模擬退火選擇概率

粒子群體搜索過程中，中心粒子的作用是增強PSO 的搜索能力，擴大粒子的搜索范圍，在粒子陷入局部最優時跳出局部區域。在此，基于Metropolis 準則和中心粒子，給出以下模擬退火選擇概率以確定粒子搜索過程的飛行速度更新方式。在模擬退火算法中，初溫設置極其重要，初溫越大，算法搜索范圍越廣，獲得解的質量越高。結合文獻［9］的初溫設置，模擬退火選擇概率其計算步驟如下：

Step1：初始化溫度T，PSO 迭代搜索過程的對應溫度Tk按式（6）設置。

其中，Kmax為算法最大迭代次數，u為溫度衰減系數，取u=0.95，k是迭代次數。

Step2：按式（7）計算粒子i使用中心粒子Cbesti，j引領飛行搜索的模擬退火選擇概率。

其中，fit（Pbesti）為i粒子局部最優解的適應度值，j為種群中除i粒子外任一隨機粒子，k為迭代次數。

Step3：均勻生成一個0 到1 之間的隨機數ri，j，若式（7）中模擬退火選擇概率小于ri，j，粒子按照式（5）更新速度，否則按照式（2）更新。

3.3 自適應極值慣性權重

通常情況下，PSO 慣性權重w采用線性變換方式，其隨搜索迭代過程逐漸減小。在粒子群體搜索前期，w取值較大則有利于粒子種群在廣域空間內開展大范圍搜索，在后期迭代搜索過程中，w隨迭代次數增加而逐漸變小，整個搜索過程伴隨著全局搜索和局部搜索之間的多次環境轉換，粒子種群搜索區域也會發生多次變換。因此，單純地使用線性變換方式改變w值將不利于全局搜索和局部搜索之間的環境變換。在此，使用式（8）定義的自適應極值慣性權重設置方式控制w隨迭代過程自適應線性變化：

其中，wk為第k次迭代的慣性權重；wmax、wmin為慣性權重w的最大和最小值；Kmax為最大迭代次數；fit（Gbest）和fitmean分別為全局最優粒子適應度和粒子種群的平均適應度值。不同于以往w線性變換方式，上述公式表明：伴隨著持續的粒子種群搜索過程，粒子群體隨迭代過程逐漸趨近于全局最優極值Gbest的鄰近區域。此時，粒子種群平均適應度值fitmean逐漸趨近于fit（Gbest），fit（Gbest）與fitmean間的比值逐漸變大，粒子種群逐漸轉入局部搜索區域。為此，隨著局部搜索過程的推移，逐漸增大的wk會增強粒子種群跳出局部搜索區域的能力，轉入全局搜索狀態，且隨著搜索過程的持續進行，wk值會逐漸減少，這種搜索狀態又逐漸進入局部搜索狀態。

3.4 算法流程

ASAPSO 算法流程如圖2所示。

Fig.2 Flow of ASAPSO algorithm圖2 ASAPSO算法流程

ASAPSO 算法執行步驟如下：

Step1：種群初始化，分別設置c1、c2、wmax、wmin、T、u。

Step2：初始化全局極值Gbest和每個粒子的個體極值Pbest。

Step3：根據式（8）設置粒子飛行過程的自適應極值慣性權重w。

Step4：對于每個粒子i，在粒子種群中確定一個學習交流粒子j，并根據式（4）構建粒子i的學習交流中心粒子Cbesti，j。

Step5：根據上文描述的模擬退火選擇概率計算粒子的飛行速度，并根據式（3）計算粒子的飛行位置。

Step6：更新粒子群體的Gbest和每個粒子的個體極值Pbest。

Step7：判斷是否達到最大迭代次數或滿足精度，若滿足條件則輸出算法求解結果，若未達到則轉至Step3。

4 仿真實驗及結果分析

4.1 參數設置及測試函數

為驗證本文所提出ASAPSO 算法的有效性，選取DCP?SO［12］、IIWPSO［19］、DACPSO［20］、和TSAPSO［21］這4 種算法，面向6 個典型測試函數（見表1）測試各比較算法的性能。為增強算法的可比較性，各比較算法設置相同的初始參數，其種群規模N=40，c1=c2=2，慣性權重wmax=0.9、wmin=0.4，最大迭代次數Kmax=1 000，測試函數維度d=30。實驗所采用的軟硬件環境為：Windows 10 Professional 21H1；In?tel（R）Xeon（R）CPU E3-1231 v3 處理器，內存16GB，在Matlab2019a語言環境下測試。

4.2 實驗數據分析

為評價算法性能，采用以下評價指標評價算法性能：最優解適應值（Min）、種群均值（Mean）、種群適應值標準差（SD）、收斂率（CR）。CR 表示100 次迭代內滿足所需精度的收斂次數，反映算法可收斂性；平均收斂迭代次數（ACIT）用于測試算法成功收斂所需的平均迭代次數，該性能反映算法收斂速度。每種比較算法求解測試函數，各獨立運行100次，其測試統計結果如表2所示。

表2 中數據顯示，在多模態函數f1和f2的測試中，無論從Min 和Mean 還是SD 而言，ASAPSO 算法相對其他比較算法均有明顯優勢，其計算數值的精度也遠高于其他比較算法。并且各比較算法獨立運行100 次，ASAPSO 的CR 能夠達到94%，其收斂率遠高于其他比較算法。在非對稱多模態函數f3測試中，ASAPSO 與DCPSO 在Min 測試性能較為接近，但前者收斂穩定性要低于DCPSO。ASAPSO 在算法迭代前期時，由于模擬退火選擇概率的作用，種群能夠快速地尋找到可能存在的最優解鄰近區域，在Min、Mean和SD 等測試性能的精度要優于IIWPSO 與DACPSO。在f4的測試過程中，TSAPSO 與DCPSO 均無法尋找到滿足條件的解。IIWPSO 與DACPSO 雖能夠得到較好的Min，但就Mean、SD、CR 和ACIT 性能而言，其測試性能要劣于ASAP?SO。在f5的函數求解中，ASAPSO 與DCPSO 性能測試上較為接近，兩種算法都能100%收斂至最優值，優于其他比較算法。在單模態圓形函數f6中，ASAPSO 各項測試性能數據均與DCPSO 相接近，兩種算法的收斂率均為100%。然而，從表2 數據可見，ASAPSO 收斂精度明顯優于DCPSO 與TSAPSO，相比IIWSO 和DACPSO 兩種比較算法，雖然在測試函數也能夠收斂到最優值0，但就CR 和SD 而言，其可收

斂性和收斂穩定性均劣于ASAPSO。

Table 1 Typical test function表1 典型測試函數

Table 2 Test results of five comparison algorithms表2 5種比較算法測試結果

為了更直觀地說明ASAPSO 在以上6 個模態函數中的測試性能，各比較算法在粒子群體尋優過程中種群最小適應度值隨迭代次數變化曲線如圖3所示。

Fig.3 Variation curve of optimal solution of five comparison algorithms in the solution of test function圖3 5種比較算法求解測試函數的最優解變化曲線

由圖3 可以看出，ASAPSO 的軌跡與DACPSO 軌跡較為接近，在曲線趨于平緩時其軌跡有跳躍式下降的情形。因此，ASAPSO 精度相較于DACPSO 顯示出較好的全局最優值，但其收斂速度要略慢于DACPSO。而TSAPSO 要明顯劣于其他比較算法，DCPSO 的尋優軌跡呈緩慢下降趨勢，其收斂到所需精度的全局最優值需較長時間，往往在600 次迭代之后才能搜尋到最優值。相較于DCPSO，ASAPSO 能夠在較短時間內找到全局最優解。

4 結語

針對PSO 搜索過程中易陷入局部最優區域的問題，本文提出了一種新的自適應模擬退火粒子群算法。所提出的ASAPSO 算法構建了粒子間學習交流的中心粒子，中心粒子將增強粒子個體的社會學習能力。種群中每個粒子根據模擬退火選擇概率確定是否向中心粒子學習，并由中心粒子引領粒子向著全局最優解區域飛行。ASAPSO 能夠增強粒子跳出局部最優區域的能力，提高粒子種群搜尋全局最優解的效率。仿真測試表明，ASAPSO 在收斂速度和收斂精度上均優于其他比較算法，能夠在較短時間內搜尋到全局最優解。后續工作中，將基于ASAPSO 進一步分析粒子的飛行真實狀態，將粒子按飛行方向劃分為不同類別的粒子群體，針對每種類別的粒子給出不同的慣性權重設置方式，使得粒子種群不再以式（8）表現的單一方式向著全局最優解區域靠近，并在實際工程應用案例中進一步驗證所提出ASAPSO 改進算法的測試性能。