自適應(yīng)狀態(tài)轉(zhuǎn)移模擬退火算法及其應(yīng)用

徐博 韓曉霞 董穎超 盧佳振 武晉德 張文杰

摘 要：狀態(tài)轉(zhuǎn)移模擬退火算法（STASA）作為解決復(fù)雜優(yōu)化問(wèn)題的有效方法，其搜索效率依賴于搜索算子和參數(shù)值的選擇，在一些高維復(fù)雜問(wèn)題上出現(xiàn)效率低下的問(wèn)題。提出一種自適應(yīng)狀態(tài)轉(zhuǎn)移模擬退火算法（ASTSA），通過(guò)自適應(yīng)算子和參數(shù)選擇策略來(lái)提高算法的適用性和求解效率；借鑒群智能算法的均值更新方法對(duì)平移算子進(jìn)行改進(jìn)，增強(qiáng)算子的搜索特性。通過(guò)23個(gè)基準(zhǔn)測(cè)試函數(shù)和8個(gè)工程設(shè)計(jì)問(wèn)題進(jìn)行實(shí)驗(yàn)驗(yàn)證并與其他算法對(duì)比，證明了ASTSA算法和改進(jìn)策略的有效性。

關(guān)鍵詞：狀態(tài)轉(zhuǎn)移模擬退火算法；自適應(yīng)策略；連續(xù)優(yōu)化問(wèn)題；工程設(shè)計(jì)問(wèn)題

中圖分類號(hào)：TP301.6?? 文獻(xiàn)標(biāo)志碼：A?? 文章編號(hào)：1001-3695（2024）01-022-0150-09

doi：10.19734/j.issn.1001-3695.2023.06.0221

Adaptive state transition simulated annealing algorithm and its application

Abstract：State transition simulated annealing（STASA） algorithm has achieved outstanding results in solving complex optimization problems.However，its search efficiency depends on the selection of search operators and parameter values，resulting in low efficiency in some high-dimensional complex problems.This paper proposed an adaptive state transition simulated annealing（STASA） algorithm by introducing adaptive operators and parameter selection strategies to improve the applicability and efficiency of the algorithm.And it improved the translation operator by referring the mean update method of swarm intelligence algorithms to enhance the search characteristics of operator.This paper demonstrates the effectiveness of ASTSA and the improved strategy through experimental validation with 23 benchmark test functions and 8 engineering design problems and comparision with other algorithms.

Key words：state transition simulated annealing algorithm；adaptation strategy；continuous optimization problem；enginee-ring design problem

智能優(yōu)化算法又稱為元啟發(fā)式算法，起源于20世紀(jì)50年代的數(shù)值優(yōu)化方法，隨著算力的增強(qiáng)和人工智能的不斷發(fā)展，逐漸發(fā)展為一種可以自動(dòng)化地找到最優(yōu)解的優(yōu)化算法。智能優(yōu)化算法具有高效、靈活、全局搜索等特性，可以有效地解決復(fù)雜的優(yōu)化難題。近年來(lái)，隨著數(shù)據(jù)科學(xué)和人工智能技術(shù)的快速發(fā)展，智能優(yōu)化算法得到了極大的推廣和應(yīng)用，在工業(yè)生產(chǎn)、交通運(yùn)輸、資源配置等多個(gè)領(lǐng)域，智能優(yōu)化算法已經(jīng)成為解決優(yōu)化問(wèn)題的重要工具之一。

在智能優(yōu)化算法的研究和發(fā)展中逐漸分為四類算法：a）基于自然進(jìn)化的進(jìn)化類算法，如遺傳算法GA［1］、差分進(jìn)化DE［2］等；b）基于生物種群的群智能算法，如粒子群算法PSO［3］、鯨魚(yú)優(yōu)化算法WOA［4］等；c）基于模擬各種物理現(xiàn)象的優(yōu)化算法，如模擬退火算法SA［5］、引力搜索算法GSA［6］等；d）基于模擬人類智力、行為的優(yōu)化算法，如帝國(guó)競(jìng)爭(zhēng)算法ICA［7］、頭腦風(fēng)暴優(yōu)化BSO［8］等。當(dāng)然，它們的劃分并非絕對(duì)的，如頭腦風(fēng)暴優(yōu)化的靈感來(lái)源于人類的智力行為，但它同樣屬于群智能算法。

狀態(tài)轉(zhuǎn)移模擬退火（state transition si-mulated annealing，STASA）算法是Han等人提出的一種新的混合智能優(yōu)化算法［9］，它結(jié)合了狀態(tài)轉(zhuǎn)移算法STA［10，11］和模擬退火算法SA的優(yōu)點(diǎn)，已在PM 2.5濃度預(yù)測(cè)［12］、化學(xué)過(guò)程模型優(yōu)化［13］、MTSP求解［14］等問(wèn)題中取得了良好的應(yīng)用。然而，STASA在求解大規(guī)模優(yōu)化問(wèn)題時(shí)出現(xiàn)收斂緩慢的問(wèn)題，此外搜索算子的固定變換因子也限制了算法的收斂速度以及搜索效率，在搜索中對(duì)全局搜索和局部挖掘的劃分不夠明確，導(dǎo)致存在無(wú)效搜索。在STA中存在類似問(wèn)題，Zhou等人［15］設(shè)計(jì)了一個(gè)參數(shù)集合來(lái)選擇最優(yōu)參數(shù)；進(jìn)一步，董穎超等人［16，17］使用統(tǒng)計(jì)方法自適應(yīng)調(diào)整算子及參數(shù)值。

本文針對(duì)STASA算法的不足對(duì)其進(jìn)行改進(jìn)，提出了一種自適應(yīng)狀態(tài)轉(zhuǎn)移模擬退火算法（ASTSA）。在ASTSA算法中，通過(guò)統(tǒng)計(jì)方法引入自適應(yīng)策略，根據(jù)算法的求解情況選擇當(dāng)前最佳的搜索算子及其對(duì)應(yīng)的參數(shù)值；對(duì)平移算子進(jìn)行改進(jìn)，減少隨機(jī)性，更好地反映優(yōu)化問(wèn)題的收斂方向，以發(fā)揮平移算子的搜索特性。最后將ASTSA在23個(gè)基準(zhǔn)測(cè)試函數(shù)以及8個(gè)工程優(yōu)化設(shè)計(jì)問(wèn)題上進(jìn)行實(shí)驗(yàn)，證明了其有效性。

1 狀態(tài)轉(zhuǎn)移模擬退火算法

STASA采用與STA相同的狀態(tài)轉(zhuǎn)移算子來(lái)生成候選解，并使用SA的Metropolis接受準(zhǔn)則作為解的更新策略，提高跳出局部最優(yōu)的能力。STA是一個(gè)基于現(xiàn)代控制理論中狀態(tài)空間的相關(guān)概念的隨機(jī)優(yōu)化算法，STA使用狀態(tài)空間代表優(yōu)化算法的搜索空間，用“狀態(tài)”表示優(yōu)化問(wèn)題的解，解的更新過(guò)程看作狀態(tài)的轉(zhuǎn)移過(guò)程［10］。因此，STA以及STASA生成候選解的統(tǒng)一形式可以使用控制轉(zhuǎn)移方程表示為

其中：以xk、xk+1表示當(dāng)前解和新一代解，yk為xk的適應(yīng)度值，uk為當(dāng)前狀態(tài)與歷史狀態(tài)的記錄；Ak，Bk∈RApn×n為隨機(jī)矩陣；f（·）表示適應(yīng)度函數(shù)。

1.1 狀態(tài)變換算子

用于求解連續(xù)問(wèn)題的STASA有四個(gè)狀態(tài)轉(zhuǎn)移算子，分別為旋轉(zhuǎn)、平移、伸縮以及軸向變換算子，保證了全局搜索能力、局部開(kāi)發(fā)能力以及啟發(fā)式搜索能力。

a）旋轉(zhuǎn)算子。

其中：εα>0為旋轉(zhuǎn)因子；Rr∈RApn×n是［0，1］內(nèi)服從均勻分布的隨機(jī)矩陣；‖·‖2表示向量的二范數(shù)。旋轉(zhuǎn)算子在以xk為球心、εα為半徑的超球體內(nèi)產(chǎn)生的候選解均。

b）平移算子。

其中：εβ>0為平移因子；Rt∈RAp為［0，1］內(nèi)服從均勻分布的隨機(jī)數(shù)；xk-1表示上一代解；平移變換表示xk沿著xk+1方向進(jìn)行搜索。

c）伸縮算子。

xk+1=xk+εγRexk（4）

其中：εγ>0為伸縮因子；Re∈RApn×n為隨機(jī)對(duì)角矩陣，服從標(biāo)準(zhǔn)高斯分布。伸縮算子具有全局搜索能力。

d）軸向變換算子。

xk+1=xk+εδRaxk（5）

其中：εδ>0為軸向變換因子；Rα∈RApn×n為隨機(jī)稀疏對(duì)角矩陣，只有一個(gè)隨機(jī)位置不為0，服從標(biāo)準(zhǔn)高斯分布。軸向變換算子可以增強(qiáng)單維搜索能力。

1.2 解的更新策略

STASA算法在原有貪婪策略中引入模擬退火算法SA的更新策略，即在新解更優(yōu)時(shí)，按照貪婪策略直接接收更優(yōu)解為當(dāng)前解；而在新解非優(yōu)時(shí)，按照Metropolis準(zhǔn)則依概率接收新解。

在STASA中，使用狀態(tài)變換算子產(chǎn)生的新候選解稱為狀態(tài)集合state，state中最優(yōu)解記為bestk-1，因此該策略的數(shù)學(xué)表示為（以求解最小優(yōu)化為例）

其中：Tk為當(dāng)前模擬退火的溫度；η為［0，1］內(nèi)的隨機(jī)數(shù)。當(dāng)bestk+1優(yōu)于xk時(shí)，e-（f（bestk+1）-f（xk））/Tk為大于1的值，一定接收新解；而非優(yōu)時(shí)，則依概率接收bestk+1，否則保持xk為下一代解。

2 自適應(yīng)狀態(tài)轉(zhuǎn)移模擬退火算法

算子是元啟發(fā)式算法的重要組成和不同算法之間的主要區(qū)分，對(duì)待不同的優(yōu)化問(wèn)題，不同的算子能夠產(chǎn)生不同的效果。為提高STASA算法的收斂速度、增強(qiáng)搜索能力，并提高算法對(duì)不同優(yōu)化問(wèn)題的適用性，將自適應(yīng)策略引入STASA中并對(duì)平移算子進(jìn)行改進(jìn)。將這種自適應(yīng)狀態(tài)轉(zhuǎn)移模擬退火算法記為ASTSA。

2.1 自適應(yīng)調(diào)用策略

算子的周期性交替調(diào)用策略并不能完全發(fā)揮每個(gè)算子的搜索能力，導(dǎo)致部分計(jì)算資源不能得到充分的利用；此外，算子參數(shù)的選擇也會(huì)顯著地影響算子的優(yōu)化性能。本文基于統(tǒng)計(jì)方法設(shè)計(jì)了一個(gè)自適應(yīng)算子和參數(shù)選擇策略，引入STASA。自適應(yīng)調(diào)用策略基于統(tǒng)計(jì)方法設(shè)計(jì)了綜合評(píng)價(jià)指標(biāo)ρc，包括成功率ρs和下降率ρd兩部分，定義如下：

其中：SE表示搜索強(qiáng)度；Best0表示算子調(diào)用前的舊最優(yōu)解；fBest0表示Best0的適應(yīng)度值；Ns為適應(yīng)度值優(yōu)于fBest0的解的個(gè)數(shù)；fave表示這Ns個(gè)解的平均適應(yīng)度值。

平移算子只在伸縮、旋轉(zhuǎn)和軸向變換三個(gè)算子發(fā)現(xiàn)更優(yōu)解時(shí)調(diào)用，因此算子的自適應(yīng)選擇部分不包含平移算子，其調(diào)用規(guī)則并不改變。使用ρsE、ρsR、ρsA分別表示伸縮、旋轉(zhuǎn)、軸向變換算子某次搜索的成功率，ρdE、ρdR、ρdA表示對(duì)應(yīng)的下降率，則伸縮、旋轉(zhuǎn)和軸向變換三個(gè)算子的綜合評(píng)價(jià)指標(biāo)ρcE、ρcR、ρcA計(jì)算方式如下：

其中：a1+a2=1，a1和a2為重要性系數(shù)，一般a1=a2=0.5。式（9）～（11）中，成功率ρs代表當(dāng)前搜索中更優(yōu)解所占的比例；下降率ρd反映當(dāng)前搜索中更優(yōu)解的平均收斂程度；綜合評(píng)價(jià)指標(biāo)ρc越大，表示該算子此次搜索的效果越好。

在自適應(yīng)策略中分別計(jì)算三個(gè)算子的綜合評(píng)價(jià)指標(biāo)ρc，以確定最優(yōu)算子，為了充分發(fā)揮最優(yōu)算子的效果，確定算子后會(huì)重復(fù)調(diào)用Tp次。

參數(shù)的取值會(huì)顯著地影響算子的搜索效果。在算法的自適應(yīng)策略中，三個(gè)算子不再是使用固定的參數(shù)，而是設(shè)置一個(gè)參數(shù)集Ω，即在計(jì)算綜合評(píng)價(jià)指標(biāo)過(guò)程中，三個(gè)算子分別基于此參數(shù)集Ω中每個(gè)參數(shù)值進(jìn)行搜索，并根據(jù)式（9）～（11）計(jì)算ρc，選擇最優(yōu)算子。

最優(yōu)參數(shù)的選擇與最優(yōu)算子的選擇在自適應(yīng)策略中相互貫穿。在確定最優(yōu)算子后，找到該算子在此次搜索中產(chǎn)生的最優(yōu)解對(duì)應(yīng)的參數(shù)，即確定為最優(yōu)參數(shù)α*，數(shù)學(xué)表達(dá)為

其中：BestOp（）表示最優(yōu)算子；f（·）表示適應(yīng)度函數(shù)；xk表示當(dāng)前解。

2.2 改進(jìn)平移算子

平移算子在搜索過(guò)程中利用新最優(yōu)解的方向信息，若當(dāng)前解與新最優(yōu)解的方向能夠很好地反映優(yōu)化問(wèn)題的最優(yōu)收斂方向，則平移算子能夠?qū)Ｒ坏匮厥諗糠较蜻M(jìn)行搜索，搜索效率很高；若此方向與最優(yōu)收斂方向存在偏差，搜索效率降低。在此借鑒群智能算法中使用種群均值進(jìn)行輔助更新的思想，對(duì)平移算子的搜索方向進(jìn)行改進(jìn)。群智能算法在搜索過(guò)程中會(huì)使用種群內(nèi)最優(yōu)個(gè)體為產(chǎn)生下一代種群作參考，以求達(dá)到最優(yōu)的搜索效果；也會(huì)使用次優(yōu)個(gè)體［18， 19］、種群平均個(gè)體［20， 21］等信息以保證算法的穩(wěn)定性，進(jìn)而增強(qiáng)搜索效果。

改進(jìn)后的平移算子以當(dāng)前解為分界線，比當(dāng)前解差的候選解記為xworse，優(yōu)于當(dāng)前解的候選解記為xbetter，使用xworse和xbetter的位置信息指示平移算子的搜索方向。改進(jìn)平移算子的數(shù)學(xué)表達(dá)式為

其中：n1和n2分別為劣于、優(yōu)于當(dāng)前解的候選解的數(shù)量。其余與原平移算子相同。

改進(jìn)平移算子的搜索方向不再單一地由新最優(yōu)解確定，而是通過(guò)取均值的方式根據(jù)更劣解、更優(yōu)解確定搜索方向。改進(jìn)平移算子使用更優(yōu)解的均值來(lái)代替單獨(dú)的新最優(yōu)解，減少了搜索方向的誤差，并使用劣解的均值代替原平移算子中的當(dāng)前解，輔助確定搜索方向。因?yàn)榱咏獾木蹬c當(dāng)前解相比更能夠反映優(yōu)化問(wèn)題的收斂方向，所以改進(jìn)平移算子能夠減少原平移算子單一最優(yōu)解提高搜索方向帶來(lái)的隨機(jī)性，更準(zhǔn)確地反映優(yōu)化問(wèn)題的最優(yōu)收斂方向，以發(fā)揮平移算子的搜索特性。

圖1為改進(jìn)前后平移算子在搜索空間產(chǎn)生新候選解的示意圖，背景為等高線圖（圓心為全局最優(yōu)），圖中正方形表示原平移算子產(chǎn)生的候選解，三角形表示改進(jìn)后平移算子產(chǎn)生的候選解，可以看到，沿三角形方向可以更快地接近全局最優(yōu)。

2.3 算法整體框架

自適應(yīng)狀態(tài)轉(zhuǎn)移模擬退火算法的流程如圖2所示。在每次迭代中，首先使用自適應(yīng)策略確定伸縮、旋轉(zhuǎn)、軸變換算子的綜合評(píng)價(jià)指標(biāo)，以確定當(dāng)前迭代的最優(yōu)算子以及最佳參數(shù)值；為了充分發(fā)揮最優(yōu)算子和參數(shù)值的優(yōu)勢(shì)，將其保持運(yùn)行Tp次，并依據(jù)搜索情況調(diào)用改進(jìn)平移算子，以沿收斂方向進(jìn)行搜索。

2.4 時(shí)間復(fù)雜度分析

假設(shè)目標(biāo)函數(shù)評(píng)價(jià)單個(gè)解的時(shí)間復(fù)雜度為O（t0），四個(gè)搜索算子產(chǎn)生單個(gè)解的時(shí)間復(fù)雜度均為O（t1），目標(biāo)函數(shù)評(píng)價(jià)次數(shù)為FE，則STASA的時(shí)間復(fù)雜度為O（FE×（t0+t1））。

在算法運(yùn)行過(guò)程中，SE、NO、Tp以及t0、t1均為常數(shù)，與STASA相比，ASTSA算法的時(shí)間復(fù)雜度的量級(jí)沒(méi)有變化。本次實(shí)驗(yàn)中，SE=100，NO=6，Tp=10，實(shí)際時(shí)間復(fù)雜度僅增加了O（2.86FE）。算法在自適應(yīng)部分增加了一定的計(jì)算量，通過(guò)最優(yōu)算子和參數(shù)增強(qiáng)算法的性能。

改進(jìn)平移算子增加了方向確定部分的計(jì)算量，其他均與原平移算子相同。改進(jìn)平移算子增加計(jì)算量的部分包括確定更優(yōu)解、更劣解，計(jì)算均值，因此時(shí)間復(fù)雜度為O（SE），在實(shí)驗(yàn)中為常數(shù)復(fù)雜度。

3 仿真實(shí)驗(yàn)及分析

3.1 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置

為了驗(yàn)證ASTSA的有效性，使用23個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行實(shí)驗(yàn)測(cè)試，并與STASA、STA、GSA、SCA［22］、WOA、GWO［18］、HGWOP［23］、VAGWO［24］共八個(gè)算法進(jìn)行對(duì)比實(shí)驗(yàn)。然后使用八個(gè)帶約束的工程設(shè)計(jì)問(wèn)題來(lái)驗(yàn)證ASTSA在實(shí)際問(wèn)題中的使用效果。

仿真實(shí)驗(yàn)所有程序均采用MATLAB R2021b進(jìn)行編寫(xiě)、運(yùn)行，運(yùn)行環(huán)境為Windows 10 64位操作系統(tǒng)，硬件平臺(tái)為Intel CoreTM i5-7300HQ CPU @ 2.50 GHz。每個(gè)算法的搜索強(qiáng)度SE、種群大小均設(shè)為100。每個(gè)對(duì)比算法的參數(shù)設(shè)置均與其原文保持一致，或者為經(jīng)典參數(shù)設(shè)置，詳見(jiàn)表1。

3.2 求解基準(zhǔn)測(cè)試函數(shù)

本節(jié)使用基準(zhǔn)測(cè)試函數(shù)對(duì)ASTSA進(jìn)行測(cè)試，基準(zhǔn)測(cè)試函數(shù)包括單峰、多峰的情況，F(xiàn)1～F7為單峰、F8～F23為多峰；且函數(shù)F1～F13的維度可變，在實(shí)驗(yàn)中均設(shè)置為30，F(xiàn)14～F23為固定維。詳細(xì)定義如表2、3所示。

測(cè)試函數(shù)評(píng)價(jià)次數(shù)控制為500 000次，并且每個(gè)算法獨(dú)立運(yùn)行30次，記錄其最優(yōu)值min、30次運(yùn)行的均值mean和標(biāo)準(zhǔn)差std。并將ASTSA與每個(gè)對(duì)比算法的30次獨(dú)立運(yùn)行的最優(yōu)值min進(jìn)行Wilcoxon符號(hào)秩和檢驗(yàn)（顯著性水平p＜0.05）。

3.2.1 求解結(jié)果分析

所有算法的測(cè)試結(jié)果如表4所示。其中R為Wilcoxon符號(hào)秩和檢驗(yàn)的結(jié)果，1、0、-1分別表示ASTSA優(yōu)于該算法、與該算法效果相同、劣于該算法；RankSum表示與該對(duì)比算法在23個(gè)測(cè)試函數(shù)上秩和檢驗(yàn)的和，反映整體效果。表中粗體表示幾個(gè)對(duì)比算法在當(dāng)前測(cè)試函數(shù)的最優(yōu)值。

由表4可知，除了F2、F3、F5、F6、F7、F12這六個(gè)測(cè)試函數(shù)以外，ASTSA在其他測(cè)試函數(shù)上能夠取得最優(yōu)的結(jié)果，并且在12個(gè)測(cè)試函數(shù)上達(dá)到了理論最優(yōu)值，具有足夠的求解精度。除了HGWOP以外，ASTSA與其他對(duì)比算法的Wilcoxon秩和檢驗(yàn)結(jié)果RankSum均達(dá)到了12以上，且與HGWOP的RankSum也有2，證明ASTSA優(yōu)于對(duì)比算法。

根據(jù)“No-free-lunch”準(zhǔn)則，ASTSA算法在大部分測(cè)試函數(shù)上相較于原STASA取得了更好的結(jié)果，但也在函數(shù)F3上產(chǎn)生了“退步”，求解結(jié)果不如原STASA。改進(jìn)后的ASTSA相對(duì)于原STASA的Wilcoxon秩和檢驗(yàn)結(jié)果為18，證明了改進(jìn)策略的有效性。與HGWOP相比，在23個(gè)測(cè)試函數(shù)中ASTSA占優(yōu)的有F1～F4、F8～F10、F16、F18、F19、F21；HGWOP占優(yōu)的有F5～F7、F12～F15、F20、F22，包含單峰可變維度、多峰可變維度以及多峰固定維的情況，沒(méi)有明顯的傾向。Wilcoxon秩和檢驗(yàn)結(jié)果為2，ASTSA只是略優(yōu)于HGWOP。

3.2.2 收斂性分析

圖3為各個(gè)算法在部分測(cè)試函數(shù)（F1、F3、F4、F6、F9、F10）上的對(duì)數(shù)收斂曲線，分別代表不同的收斂情況。

其中，橫坐標(biāo)為評(píng)價(jià)次數(shù)，縱坐標(biāo)為目標(biāo)函數(shù)值的對(duì)數(shù)；并且每個(gè)算法均選取最優(yōu)的一次進(jìn)行繪制。在函數(shù)F1，ASTSA求解出了最優(yōu)值，始終穩(wěn)步收斂但速度相對(duì)于GWO和WOA較差；在函數(shù)F3，ASTSA沒(méi)有達(dá)到最優(yōu)結(jié)果，相對(duì)于原STASA產(chǎn)生了“退步”；在函數(shù)F4，ASTSA求解出最優(yōu)值且收斂速度最快，但在后期出現(xiàn)了收斂速度減緩的趨勢(shì)；在函數(shù)F6，ASTSA取得最優(yōu)結(jié)果且收斂速度最快，但其前期收斂迅速而后期出現(xiàn)振蕩的情況，即嘗試“逃離”當(dāng)前位置，尋找新的最優(yōu)解，而HGWOP在F6上表現(xiàn)優(yōu)異；在函數(shù)F9，多個(gè)算法均得到最優(yōu)值，其中ASTSA速度最快；在函數(shù)F10，盡管ASTSA結(jié)果和收斂速度均為最優(yōu)，但與其他算法一樣在搜索后期陷入停滯。

綜上，ASTSA能夠在大部分基準(zhǔn)函數(shù)上達(dá)到最優(yōu)效果，但其收斂速度、局部搜索能力在部分問(wèn)題上仍有缺陷（如F1、F3、F6），并且搜索后期開(kāi)發(fā)能力也存在提升空間（如F4、F10）。

3.2.3 算法運(yùn)行耗時(shí)

各算法的平均運(yùn)行時(shí)間如圖4所示。目標(biāo)函數(shù)評(píng)價(jià)次數(shù)相同。23個(gè)測(cè)試函數(shù)中，ASTSA在15個(gè)測(cè)試函數(shù)上優(yōu)于STASA，盡管ASTSA的時(shí)間復(fù)雜度有所增加，但其更強(qiáng)大的求解能力，能夠更快找到最優(yōu)解，因此在一些復(fù)雜問(wèn)題上用時(shí)比STASA更短。

分別計(jì)算ASTSA與對(duì)比算法的耗時(shí)比例（ASTSA耗時(shí)/對(duì)比算法耗時(shí)×100%），然后計(jì)算23個(gè)測(cè)試函數(shù)的平均值，結(jié)果如表5所示，平均耗時(shí)比例均小于100%。按照平均耗時(shí)比例可以分為三檔，第一檔有STASA、STA，它們與ASTSA屬于同一系算法，因其簡(jiǎn)明的搜索結(jié)果耗時(shí)最少；第二檔為40～50%，包括SCA、WOA、GWO、HGWOP，平均耗時(shí)約為ASTSA的兩倍；第三檔為GSA、VAGWO，平均耗時(shí)達(dá)到ASTSA的10倍以上。

3.2.4 穩(wěn)定性分析

單獨(dú)從實(shí)驗(yàn)結(jié)果的標(biāo)準(zhǔn)差（表4中std）來(lái)看，ASTSA為最優(yōu)的有7個(gè)，與GSA、GWO、HGWOP相同，為第一檔。但其中GSA整體的求解效果并不理想，只在固定維度多峰測(cè)試函數(shù)中有良好的表現(xiàn)；而HGWOP求解效果優(yōu)異（ASTSA與其的RankSum僅為2）。ASTSA與STASA相比優(yōu)平劣為10/4/9，但STASA達(dá)到最優(yōu)的僅有4個(gè)，少于ASTSA算法。

盡管ASTSA在F6等測(cè)試函數(shù)存在后期振蕩的現(xiàn)象，但并未對(duì)穩(wěn)定性造成過(guò)多影響，如ASTSA在F6的方差精度達(dá)到10-19，與GSA處于同一精度，僅次于最優(yōu)的HGWOP。ASTSA算法在求解穩(wěn)定性方面可與GSA、GWO、HGWOP同處于第一檔，但GSA整體表現(xiàn)較差，HGWOP稍遜，ASTSA的綜合求解能力最強(qiáng)。

3.3 自適應(yīng)策略有效性檢驗(yàn)

為了檢驗(yàn)自適應(yīng)策略的有效性，進(jìn)行了簡(jiǎn)單的統(tǒng)計(jì)學(xué)檢驗(yàn)。

a）自適應(yīng)算子有效性檢驗(yàn)。在測(cè)試函數(shù)的取值范圍中隨機(jī)生成當(dāng)前解，使用自適應(yīng)策略確定最優(yōu)算子BestOp和最優(yōu)參數(shù)值α*；然后使用最優(yōu)算子BestOp以及另外兩個(gè)算子進(jìn)行搜索（均為最優(yōu)參數(shù)值），記錄產(chǎn)生的所有解中的最優(yōu)解是否屬于自適應(yīng)確定的最優(yōu)算子。在23個(gè)測(cè)試函數(shù)上分別進(jìn)行1 000次，結(jié)果如圖5所示，條形圖為最優(yōu)解屬于最優(yōu)算子的次數(shù)，橫線為均值（1 000次/6個(gè)參數(shù)=166.67）。由圖5可知，除測(cè)試函數(shù)F8以外，其余結(jié)果均達(dá)到均值以上，并在F1、F2等四個(gè)測(cè)試函數(shù)上達(dá)到1 000，且大于800的結(jié)果有9個(gè)，證明了自適應(yīng)算子選擇策略的有效性。

b）自適應(yīng)參數(shù)有效性檢驗(yàn)。與算子有效性檢驗(yàn)類似，通過(guò)自適應(yīng)策略確定最優(yōu)參數(shù)后，使用參數(shù)集合進(jìn)行搜索（最優(yōu)算子），然后記錄最優(yōu)解是否屬于最優(yōu)參數(shù)值。在23個(gè)測(cè)試函數(shù)上分別進(jìn)行1 000次，結(jié)果如圖6所示。由圖6可知，在每個(gè)函數(shù)上測(cè)試結(jié)果均大于均值，最差結(jié)果為235（F19），仍超出均值的40%，證明了自適應(yīng)參數(shù)選擇策略的準(zhǔn)確、有效。

此外，圖7、8分別為實(shí)際運(yùn)行中各算子和參數(shù)值的平均調(diào)用次數(shù)（獨(dú)立運(yùn)行30次）。由圖7可知，對(duì)于同一測(cè)試函數(shù)，不同算子的調(diào)用情況相差很大，并且對(duì)于不同的測(cè)試函數(shù)，不同算子的調(diào)用頻率也不同。由圖8可知，對(duì)于不同的測(cè)試函數(shù)，參數(shù)值的選擇情況差別很大，從側(cè)面佐證了自適應(yīng)選擇策略的有效性。

3.4 改進(jìn)平移算子有效性檢驗(yàn)

為驗(yàn)證修正方向的有效性，對(duì)改進(jìn)平移算子進(jìn)行有效性測(cè)試。在測(cè)試函數(shù)的取值范圍中隨機(jī)生成當(dāng)前解，分別使用旋轉(zhuǎn)算子、伸縮算子、軸向變換算子結(jié)合參數(shù)集合中每個(gè)參數(shù)進(jìn)行搜索（SE=100），再分別使用原平移算子和改進(jìn)平移算子進(jìn)行搜索，對(duì)比改進(jìn)前后平移算子產(chǎn)生新解中各自最優(yōu)解的優(yōu)劣。在23個(gè)測(cè)試函數(shù)中進(jìn)行測(cè)試，分別以3個(gè)算子、每個(gè)參數(shù)（6個(gè)）各進(jìn)行1 000次（共計(jì)1 000×3×6=18 000）并統(tǒng)計(jì)改進(jìn)平移算子更優(yōu)的次數(shù)，結(jié)果如圖9所示。

由圖9可知，在所有測(cè)試函數(shù)上測(cè)試結(jié)果均大于均值（9k），其中在F4上最差為9 172，其次F18為9 421，其余均大于10 000；在14個(gè)測(cè)試函數(shù)上超出均值的1/3（12 000），在8個(gè)上超出均值的1/2（13 500）。整體來(lái)看，改進(jìn)平移算子優(yōu)于原平移算子，且在一些函數(shù)（F1、F3、F5等）上具有優(yōu)秀的效果。但整體效果沒(méi)有達(dá)到最優(yōu)，在部分測(cè)試函數(shù)上效果不明顯（F4、F7等未達(dá)到1/3），沒(méi)有在全部問(wèn)題上達(dá)到跨越性的進(jìn)步。

3.5 消融實(shí)驗(yàn)

為了進(jìn)一步驗(yàn)證改進(jìn)策略的有效性，本節(jié)進(jìn)行消融實(shí)驗(yàn)，結(jié)果如表6所示，其中Adaption表示單獨(dú)采用自適應(yīng)策略、NewTrans表示單獨(dú)采用改進(jìn)平移算子，均與原STASA進(jìn)行秩和檢驗(yàn)。

單獨(dú)采用自適應(yīng)策略的算法與STASA相比，Wilcoxon秩和檢驗(yàn)結(jié)果為12，整體效果較好；且采用改進(jìn)平移算子之后達(dá)到18，進(jìn)一步取得改善。單獨(dú)采用改進(jìn)平移算子的秩和檢驗(yàn)結(jié)果為4，與改進(jìn)平移算子有效性檢驗(yàn)的結(jié)果接近，效果有所改善但沒(méi)有跨越性進(jìn)步。而在采用自適應(yīng)策略的基礎(chǔ)上增加改進(jìn)平移算子，Wilcoxon秩和檢驗(yàn)結(jié)果由12變?yōu)?8，即改進(jìn)平移算子與自適應(yīng)策略有促進(jìn)作用。

采用群智能算法種群平均策略來(lái)修正平移算子的搜索方向有一定的效果，但由于策略過(guò)于簡(jiǎn)單，無(wú)法對(duì)所有問(wèn)題產(chǎn)生促進(jìn)作用，因此可以在此基礎(chǔ)上采用更高級(jí)的策略對(duì)搜索方向進(jìn)一步修正，或采用其他群智能的高級(jí)搜索策略，使搜索的解不單單是“一條直線”，進(jìn)而增強(qiáng)搜索效果。

3.6 求解帶約束的工程設(shè)計(jì)優(yōu)化問(wèn)題

本節(jié)使用八個(gè)帶約束的工程設(shè)計(jì)優(yōu)化問(wèn)題來(lái)進(jìn)一步評(píng)估ASTSA的有效性。分別是壓縮/拉伸彈簧、工字梁、焊接梁、懸臂梁、管柱、三桿桁架、減速器、活塞桿共八個(gè)設(shè)計(jì)問(wèn)題［25］，約束條件個(gè)數(shù)分別為2、7、1、6、11、4，如圖10所示。

將ASTSA和STASA以及社交網(wǎng)絡(luò)搜索（social network search，SNS）［25］算法分別運(yùn)行30次，并保證相同的評(píng)價(jià)次數(shù)，結(jié)果如表7所示?？梢钥吹?，在壓縮/拉伸彈簧設(shè)計(jì)問(wèn)題上，ASTSA的求解結(jié)果不如SNS，而在其他七個(gè)問(wèn)題中均得到了最優(yōu)的結(jié)果。在三桿桁架和減速器設(shè)計(jì)問(wèn)題中，ASTSA與SNS都求解到了最優(yōu)值，但ASTSA的均值不如SNS，即ASTSA求解的穩(wěn)定性仍存在不足。

ASTSA與原STASA和SNS的Wilcoxon秩和檢驗(yàn)結(jié)果分別為7和1，即與STASA相比，本文算法所做改進(jìn)使算法效果得到了提升。且整體優(yōu)于對(duì)比算法SNS，具有良好的求解效果。通過(guò)實(shí)驗(yàn)證明了ASTSA算法能夠在帶約束的實(shí)際工程設(shè)計(jì)優(yōu)化問(wèn)題中應(yīng)用求解。

4 結(jié)束語(yǔ)

本文針對(duì)STASA的不足提出了一種自適應(yīng)狀態(tài)轉(zhuǎn)移模擬退火算法（ASTSA）。首先使用統(tǒng)計(jì)方法引入自適應(yīng)策略，根據(jù)生成解的情況自適應(yīng)選擇最優(yōu)的算子和參數(shù)值；然后針對(duì)平移算子的不足，借鑒群智能算法種群“平均解”的思路，修正平移算子的搜索方向，增強(qiáng)算子的穩(wěn)定性。通過(guò)在23個(gè)基準(zhǔn)測(cè)試函數(shù)以及8個(gè)工程設(shè)計(jì)優(yōu)化問(wèn)題以及Wilcoxon秩和檢驗(yàn)驗(yàn)證了ASTSA的有效性，并分析了其不足。在未來(lái)的研究中，將針對(duì)ASTSA在求解復(fù)雜問(wèn)題時(shí)穩(wěn)定性不足的問(wèn)題進(jìn)行改進(jìn)，提高其適用能力。

參考文獻(xiàn)：

［1］Goldberg D E.Genetic algorithm in search，optimization，and machine learning［M］.Boston，MA：Addison-Wesley Longman Publishing Co.，Inc.，1989.

［2］Stron R，Price K.Differential evolution：a simple and efficient adaptive scheme for global optimization over continuous spaces［J］.Journal of Global Optimization，1997，11（12）：341-359.

［3］Kennedy J，Eberhart R.Particle swarm optimization［C］//Proc of International Conference on Neural Networks.Piscataway，NJ：IEEE Press，1995：1942-1948.

［4］Mirjalili S，Lewis A.The whale optimization algorithm［J］.Advances in Engineering Software，2016，95（5）：51-67.

［5］Kirkpatrick S，Jr Gelatt C D，Vecchi M P.Optimization by simulated annealing［J］.Science，1983，220（4598）：671-680.

［6］Rashedi E，Nezamabadi-Pour H，Saryazdi S.GSA：a gravitational search algorithm［J］.Information Sciences，2009，179（13）：2232-2248.

［7］Atashpaz-Gargari E，Lucas C.Imperialist competitive algorithm：an algorithm for optimization inspired by imperialistic competition［C］//Proc of IEEE Congress on Evolutionary Computation.Piscataway，NJ：IEEE Press，2007：4661-4667.

［8］Shi Yuhui.Brain storm optimization algorithm［C］//Proc of the 2nd International Conference on Swarm Intelligence.Berlin：Springer，2011：303-309.

［9］Han Xiaoxia，Dong Yingchao，Yue Lin，et al.State transition simulated annealing algorithm for discrete-continuous optimization problems［J］.IEEE Access，2019，7：44391-44403.

［10］Zhou Xiaojun，Yang Chunhua，Gui Weihua.State transition algorithm［J］.Journal of Industrial & Management Optimization，2012，8（4）：1039-1056.

［11］周曉君，陽(yáng)春華，桂衛(wèi)華.狀態(tài)轉(zhuǎn)移算法原理與應(yīng)用［J］.自動(dòng)化學(xué)報(bào)，2020，46（11）：2260-2274.（Zhou Xiaojun，Yang Chunhua，Gui Weihua.The principle of state transition algorithm and its applications［J］.Acta Automatica Sinica，2020，46（11）：2260-2274.）

［12］Chu Junwen，Dong Yingchao，Han Xiaoxia，et al.Short-term prediction of urban PM2.5 based on a hybrid modified variational mode decomposition and support vector regression model［J］.Environmental Science and Pollution Research，2021，28（1）：56-72.

［13］Shen Yadi，Dong Yingchao，Han Xiaoxia，et al.Prediction model for methanation reaction conditions based on a state transition simulated annealing algorithm optimized extreme learning machine［J］.International Journal of Hydrogen Energy，2023，48（64）：24560-24573.

［14］Zhang Yan，Han Xiaoxia，Dong Yingchao， et al.A novel state transition simulated annealing algorithm for the multiple traveling salesmen problem［J］.Journal of Supercomputing，2021，77（10）：11827-11852.

［15］Zhou Xiaojun，Yang Chunhua，Gui Weihua.A statistical study on parameter selection of operators in continuous state transition algorithm［J］.IEEE Trans on Cybernetics，2019，49（10）：3722-3730.

［16］董穎超，張宏立，王聰.帶有策略自適應(yīng)的狀態(tài)轉(zhuǎn)移算法［J］.控制與決策，2022，37（3）：574-82.（Dong Yingchao，Zhang Hongli，Wang Cong.State transition algorithm with strategy adaptation［J］.Control and Decision，2022，37（3）：574-582.）

［17］Dong Yingchao，Zhang Hongli，Wang Cong，et al.An adaptive state transition algorithm with local enhancement for global optimization［J］.Applied Soft Computing，2022，121（5）：108733.

［18］Mirjalili S，Mirjalili S M，Lewis A.Grey wolf optimizer［J］.Advances in Engineering Software，2014，69（3）：46-61.

［19］郭振洲，劉然，拱長(zhǎng)青，等.基于灰狼算法的改進(jìn)研究［J］.計(jì)算機(jī)應(yīng)用研究，2017，34（12）：3603-3606，3610.（Guo Zhenzhou，Liu Ran，Gong Changqing，et al.Study on improvement of gray wolf algorithm［J］.Application Ｒesearch of Computers，2017，34（12）：3603-3606，3610.）

［20］Heidari A A，Mirjalili S，F(xiàn)aris H，et al.Harris hawks optimization：algorithm and applications［J］.Future Generation Computer Systems，2019，97（8）：849-872.

［21］李雅梅，孟嗣博，陳雪蓮.多策略改進(jìn)的天鷹優(yōu)化算法及其應(yīng)用［J］.計(jì)算機(jī)應(yīng)用研究，2023，40（5）：1352-1359.（Li Yamei，Meng Sibo，Chen Xuelian.Multi-strategy improved aquila optimizer and its application［J］.Application Research of Computers，2023，40（5）：1352-1359.）

［22］Mirjalili S.SCA：a sine cosine algorithm for solving optimization problems［J］.Knowledge-Based Systems，2016，96（3）：120-133.

［23］Zhang Xinming，Lin Qiuying，Mao Wentao，et al.Hybrid particle swarm and grey wolf optimizer and its application to clustering optimization［J］.Applied Soft Computing，2021，101（3）：107061 .

［24］Rezaei F，Safavi H R，Elaziz M A，et al.An enhanced grey wolf optimizer with a velocity-aided global search mechanism［J］.Mathema-tics，2022，10（3）：351.

［25］Bayzidi H，Talatahari S，Saraee M，et al.Social network search for solving engineering optimization problems［J］.Computational Intelligence and Neuroscience，2021，2021：8548639.