李昌興，黃 杉

(1.西安郵電大學(xué) 理學(xué)院,陜西 西安 710121；2.西安郵電大學(xué) 通信與信息工程學(xué)院,陜西 西安 710121)

模擬退火算法(Simulated Annealing Algorithm，SAA)不僅可以解決連續(xù)函數(shù)優(yōu)化問題，也成功應(yīng)用于求解組合優(yōu)化問題[10]。對于組合優(yōu)化問題，必須使用操作算子產(chǎn)生和接受新解。操作算子的策略非常重要，直接影響著模擬退火算法的優(yōu)化性能[11]。在反序、移位和交換算子的基礎(chǔ)上，文獻[12]使用逆轉(zhuǎn)操作算子，文獻[13]使用強制隨機鄰域變換策略，這些操作算子改善了模擬退火算法的局部搜索能力。文獻[14]提出融合最近、最遠和隨機插入操作的統(tǒng)一插入操作和最壞刪除操作，通過自適應(yīng)鄰域提高了搜索性能。文獻[15]提出自適應(yīng)升溫控制策略，平衡了全局搜索與局部搜索的關(guān)系，獲得更好的全局優(yōu)化能力。文獻[16]建立了模擬退火算法的弛豫時間模型，給出退火過程Markov鏈長度的理論估計，提出了Markov鏈的動態(tài)調(diào)整策略，對于模擬退火算法的參數(shù)選擇具有重要的理論指導(dǎo)意義。但是，以上研究并未充分利用不同操作算子的內(nèi)在聯(lián)系與相互作用，導(dǎo)致模擬退火算法精度不足，性能不高。

針對模擬退火算法中操作算子的生成策略問題，研究反序、移位和交換算子的特征與相互關(guān)系，發(fā)現(xiàn)交換操作與反序操作在機理上具有等價關(guān)系。利用這種等價關(guān)系，擬提出一種新的交換/反序聯(lián)合算子(Joint Operator，JO)模擬退火算法，并利用不同規(guī)模的TSP問題對聯(lián)合算子進行仿真實驗。

1 模擬退火算法求解旅行商問題

1.1 模擬退火算法

模擬退火算法從較高的初始溫度出發(fā)，在當(dāng)前解的鄰域不斷通過隨機擾動產(chǎn)生新的候選解，以一定的概率接受候選解。模擬退火算法包括內(nèi)外兩重循環(huán)：外循環(huán)是溫度循環(huán)，控制退火溫度降低的過程；內(nèi)循環(huán)是在每一溫度下迭代產(chǎn)生新解，循環(huán)次數(shù)也稱Markov鏈長度。

模擬退火算法的基本步驟如下。

步驟1隨機產(chǎn)生初始解X0。

步驟2在溫度Tk下進行Lk次循環(huán)迭代。由當(dāng)前解Xold產(chǎn)生新的候選解Xnew，并按Metropolis接受準則，以一定的概率接受候選解Xnew作為當(dāng)前解。候選解與當(dāng)前解目標函數(shù)值的差ΔE及候選解的接受概率P的表達式分別為

ΔE=E(Xnew)-E(Xold)

(1)

(2)

式中：k表示溫度循環(huán)變量；E(Xold)表示當(dāng)前解Xold的目標函數(shù)值；E(Xnew)表示新解Xnew的目標函數(shù)值。

Metropolis準則允許以一定的概率接受惡化解,使算法可以跳出局部最優(yōu)解，是模擬退火算法能收斂于全局最優(yōu)解的關(guān)鍵。

步驟3按照設(shè)定的退火控制策略緩慢降低退火溫度，直到達到溫度終值，完成退火過程，這時的當(dāng)前解就是達到最低能量狀態(tài)的最優(yōu)解。

1.2 求解旅行商問題的操作算子

模擬退火算法要從當(dāng)前解的鄰域中產(chǎn)生新的候選解，解的表達形式和鄰域結(jié)構(gòu)對算法收斂非常重要。組合優(yōu)化問題中，目標函數(shù)不僅依賴于解的取值，而且與解的結(jié)構(gòu)、次序相關(guān)。旅行商問題的路徑長度僅取決于解的排列次序，通常用城市編號序列表示問題的解。

為了滿足組合優(yōu)化問題的約束條件，需要通過操作算子對當(dāng)前解序列進行變換操作，改變某些點的排列次序產(chǎn)生新解?；镜牟僮魉阕邮墙粨Q算子、移位算子和反序算子[1，11]。

交換算子是將當(dāng)前路徑Snow中的第i個城市Ci與第j個城市Cj的位置交換，得到新路徑Sswap，當(dāng)前路徑和新路徑的表達式分別為

Snow=C1…Ci-1(Ci)Ci+1…Cj-1(Cj)Cj+1…Cn

Sswap=C1…Ci-1(Cj)Ci+1…Cj-1(Ci)Cj+1…Cn

移位算子是將當(dāng)前路徑Snow中的第i個城市Ci移動到第j個城市Cj之后的位置，得到新路徑Smove，當(dāng)前路徑和新路徑的表達式分別為

Snow=C1…Ci-1(Ci)Ci+1…Cj-1(Cj)Cj+1…Cn

Smove=C1…Ci-1Ci+1…Cj-1(Cj)(Ci)Cj+1…Cn

反序算子是將當(dāng)前路徑Snow中從第i個城市Ci到第j個城市Cj之間的城市排列順序反向翻轉(zhuǎn)，得到新路徑Sinv，當(dāng)前路徑和新路徑的表達式分別為

Snow=C1…Ci-1(CiCi+1…Cj-1Cj)Cj+1…Cn

Sinv=C1…Ci-1(CjCj-1…Ci+1Ci)Cj+1…Cn

1.3 多個新解的競爭機制

模擬退火算法本質(zhì)上是基于隨機搜索的優(yōu)化方法，操作算子是模擬退火算法求解旅行商問題的核心機制。操作算子的運行策略不僅決定了新解的可行性，而且與獲得優(yōu)質(zhì)解的概率密切相關(guān)，影響著模擬退火算法的優(yōu)化性能。

交換算子、移位算子和反序算子所產(chǎn)生的新路徑與當(dāng)前路徑相比，分別有8段、6段、4段路徑的改變。隨著當(dāng)前路徑的不斷優(yōu)化，通過這些算子獲得更好路徑的概率越來越小。增大循環(huán)次數(shù)即Mar-kov鏈長度可以提高優(yōu)化性能，但這也帶來了計算量的增大。

在每次循環(huán)產(chǎn)生的多個新解擇優(yōu)使用的競爭機制，可以提高獲得更好路徑的概率。文獻[17]提出了多粒子模擬退火算法，每次擾動產(chǎn)生多個新解，選取最優(yōu)者作為候選解。文獻[18]在每次循環(huán)中通過斷裂、倒置及重組操作產(chǎn)生6個新路徑，選擇最好路徑作為候選解。類似地，文獻[19]提出了多線程的并行算法，可以并行產(chǎn)生多個新解，從中找出最好的候選解。

引入產(chǎn)生多個新解的競爭機制，可以提高模擬退火算法的優(yōu)化性能，但也增大一定的計算量。由于計算量的增長與新解個數(shù)的增加近似成正比，這與直接增大循環(huán)次數(shù)相比算法未必更為有效。只有在循環(huán)中產(chǎn)生多個新解，而又不增大計算量的前提下，才能真正提高模擬退火算法的總體性能。這就需要研究現(xiàn)有操作算子的運行特征與相互關(guān)系，構(gòu)造同時產(chǎn)生多個新解的操作算子。

2 聯(lián)合操作算子

2.1 交換、反序和移位操作的關(guān)系

模擬退火算法由新解與當(dāng)前解的目標函數(shù)差ΔE計算新解的接受概率。在旅行商問題中，使用交換算子、反序算子或移位算子產(chǎn)生新路徑時，并不需要直接計算新路徑的總長度E(Xnew)，可以通過不同變換操作的特征直接計算ΔE，以減少計算量。

交換操作的路徑差ΔEswap、反序操作的路徑差ΔEinv與移位操作的路徑差ΔEmove的表達式分別為

ΔEswap=[d(Ci-1,Cj)+d(Ci,Cj+1)]-
[d(Ci-1,Ci)+d(Cj,Cj+1)]+
[d(Cj,Ci+1)+d(Cj-1,Ci)]-
[d(Ci,Ci+1)+d(Cj-1,Cj)]

(3)

ΔEinv=[d(Ci-1,Cj)+d(Ci,Cj+1)]-
[d(Ci-1,Ci)+d(Cj,Cj+1)]

(4)

ΔEmove=[d(Ci-1,Ci+1)+d(Cj,Ci)+d(Ci,Cj+1)]-
[d(Ci-1,Ci)+d(Ci,Ci+1)+d(Cj,Cj+1)]

(5)

式中，d(Ci,Cj)表示城市Ci與Cj之間的距離。

對比這3種操作所產(chǎn)生的路徑差，可以發(fā)現(xiàn)具有很多相同的距離項。特別是式(4)反序操作的路徑差ΔEinv中的全部4段距離，都出現(xiàn)在式(3)交換操作的路徑差ΔEswap中，并且正負號也相同。因此，在計算式(3)交換操作的路徑差ΔEswap時，可以先計算式(4)中ΔEinv的4段距離，再計算剩下的4段距離。就能在計算ΔEswap的同時得到ΔEinv的值，并不增大計算量，同時還獲得了2條新路徑的ΔE。

(6)

于是，交換操作的路徑差等于兩個嵌套的反序操作的路徑差之和，其表達式為

(7)

因此，可以將交換操作分解為兩步：先將當(dāng)前路徑Snow中從城市Ci到城市Cj之間的城市排列順序反向翻轉(zhuǎn)得到新路徑Sinv；再將路徑Sinv中從城市Cj-1到城市Ci+1之間的城市排列順序再次翻轉(zhuǎn)，兩次翻轉(zhuǎn)后得到的路徑就是通過交換算子所得到的新路徑Sswap。第一步反向翻轉(zhuǎn)路徑Sinv和第二步反向翻轉(zhuǎn)路徑Sswap的表達式分別為

Sinv=C1…Ci-1Cj(Cj-1…Ci+1)CiCj+1…Cn
Sswap=C1…Ci-1Cj(Ci+1…Cj-1)CiCj+1…Cn

這說明交換操作等價于兩個嵌套的反序操作的疊加復(fù)合。

2.2 交換-反序聯(lián)合算子

3 實驗結(jié)果及分析

3.1 實驗方案

為檢驗提出的交換-反序聯(lián)合算子的優(yōu)化性能，從 TSPLib 案例庫中選取 4 個不同規(guī)模的旅行商問題Eil51、Eil76、Eil101和Ch150作為測試案例，其城市數(shù)量分別為51、76、101、150，已知的最優(yōu)路徑長度分別為426、538、629和6 528。

所提算法實驗環(huán)境為CPU：Intel(R)Core(TM) i5-4460S@2.90 GHz，內(nèi)存為8 GB/1 600 MHz，操作系統(tǒng)為Window s7(64位/Service Pack 1)，采用 Python 3.8編程。

關(guān)于模擬退火算法的控制函數(shù)選擇，控制溫度按照Tk=αTk-1指數(shù)衰減，衰減系數(shù)取α∈(0.9,1.0)，按照式(2)Metropolis 準則接受新解。

考慮模擬退火算法的性能受到優(yōu)化參數(shù)的影響，對每個測試案例分別采用不同的參數(shù)各進行兩組實驗。第1組參數(shù)為：初溫100，終溫1，衰減系數(shù)0.95，共90個溫度狀態(tài)，Markov鏈長度1 000；第2組參數(shù)為：初溫100，終溫1，衰減系數(shù)0.98，共228個溫度狀態(tài)，Markov鏈線性增大，平均鏈長1 000。由于模擬退火算法的優(yōu)化結(jié)果有一定的隨機性，在每組參數(shù)下各做10次重復(fù)實驗，得到10次重復(fù)實驗的最小值、平均值、最大值，具體對比結(jié)果分別如表1至表4所示。

表1 Eil51問題實驗結(jié)果對比

表2 Eil76問題實驗結(jié)果對比

表3 Eil101問題實驗結(jié)果對比

表4 Ch150問題實驗結(jié)果對比

3.2 實驗結(jié)果的分析

對表1至表4所示的聯(lián)合算子模擬退火算法的優(yōu)化結(jié)果與使用現(xiàn)有的移位、交換、反序算子以及組合移位/交換/反序算子的模擬退火算法的優(yōu)化結(jié)果進行比較分析，可以得到4個不同規(guī)模的旅行商問題在不同測試參數(shù)下的結(jié)果。使用交換-反序聯(lián)合算子時最小值、平均值、最大值都是最好的，表明聯(lián)合算子的性能優(yōu)于移位、交換、反序算子及其組合方案，這得益于聯(lián)合算子與其他算子相比的搜索數(shù)量更大。

使用聯(lián)合算子和現(xiàn)有算子的模擬退火算法在各自的第2組的性能比第1組都有所提高，但計算時間也都更長，且時間增大與Markov鏈長度大致成正比。這也意味著如果通過增大循環(huán)迭代次數(shù)改善性能，將會直接付出計算量成比例增大的代價。各種方案在相同參數(shù)下運行時間隨問題規(guī)模有所增大，但差異并不顯著，這是由于算法中僅計算路徑差，而不需要計算完整的路徑長度。因此，計算量與問題規(guī)模沒有太大關(guān)系。

在不同規(guī)模問題的測試中，聯(lián)合算子模擬退火算法優(yōu)化性能提高的幅度不同。較小規(guī)模的問題，現(xiàn)有算子也已經(jīng)獲得較好的結(jié)果，聯(lián)合算子提高性能的幅度不大；較大規(guī)模的問題，復(fù)雜程度高，現(xiàn)有算子的優(yōu)化結(jié)果較差，而聯(lián)合算子提高性能的幅度較為顯著。

聯(lián)合算子模擬退火算法在Eil51問題找到了已知的最優(yōu)路徑，在Eil76問題很接近已知的最優(yōu)路徑，但對Eil101、Ch150問題的優(yōu)化結(jié)果與已知的最優(yōu)路徑還有2%～3%的誤差。這一方面說明大規(guī)模TSP問題的復(fù)雜程度更高，找到最優(yōu)路徑需要更多的搜索；另一方面通過調(diào)整聯(lián)合算子的參數(shù)，還可以獲得更好的優(yōu)化路徑。

在4個不同問題和兩組不同參數(shù)條件下，使用聯(lián)合算子的計算時間比使用其他算子時略有增大，但并不顯著，這與前文的分析是一致的。而聯(lián)合算子產(chǎn)生的新解數(shù)量是其他算子的3倍，遠高于計算時間的增大。

通過以上分析，聯(lián)合算子模擬退火算法不增加太多的計算量，而通過產(chǎn)生多個新解以增強搜索能力從而提高了算法的優(yōu)化性能。

4 結(jié)語

分析了模擬退火算法操作算子的特征與相互關(guān)系，發(fā)現(xiàn)交換操作等價于兩個嵌套的反序操作的疊加復(fù)合。提出了一種新的交換-反序聯(lián)合算子，獲得由交換操作和反序操作所產(chǎn)生的3條新路徑，從中擇優(yōu)作為新解。聯(lián)合算子既在循環(huán)中產(chǎn)生多個新解，又不增加過多計算量，提高了算法的優(yōu)化性能。通過4個不同規(guī)模的TSP問題的實驗，驗證了聯(lián)合算子的性能優(yōu)于現(xiàn)有的移位、交換、反序算子，也優(yōu)于這些算子的組合方案。交換-反序聯(lián)合算子不僅可以用于模擬退火算法，也可以應(yīng)用于其他進化算法，如遺傳算法、粒子群算法中的變異操作以擴展搜索空間。此外，交換與反序算子存在等價關(guān)系，其他操作算子之間也具有不同程度的相關(guān)性。對于揭示和利用這些相關(guān)性提高算法效率，將是后續(xù)研究工作的方向。