求解旅行商問題的聯(lián)合算子模擬退火算法

李昌興，黃 杉

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

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

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

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

1.1 模擬退火算法

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

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

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

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

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

(1)

(2)

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

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

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

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

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

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

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

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個(gè)城市Ci移動(dòng)到第j個(gè)城市Cj之后的位置，得到新路徑Smove，當(dāng)前路徑和新路徑的表達(dá)式分別為

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個(gè)城市Ci到第j個(gè)城市Cj之間的城市排列順序反向翻轉(zhuǎn)，得到新路徑Sinv，當(dāng)前路徑和新路徑的表達(dá)式分別為

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

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

1.3 多個(gè)新解的競(jìng)爭(zhēng)機(jī)制

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

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

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

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

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

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

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

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

Δ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之間的距離。

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

(6)

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

(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的表達(dá)式分別為

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)方案

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

所提算法實(shí)驗(yàn)環(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 準(zhǔn)則接受新解。

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

表1 Eil51問題實(shí)驗(yàn)結(jié)果對(duì)比

表2 Eil76問題實(shí)驗(yàn)結(jié)果對(duì)比

表3 Eil101問題實(shí)驗(yàn)結(jié)果對(duì)比

表4 Ch150問題實(shí)驗(yàn)結(jié)果對(duì)比

3.2 實(shí)驗(yàn)結(jié)果的分析

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

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

在不同規(guī)模問題的測(cè)試中，聯(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)路徑，但對(duì)Eil101、Ch150問題的優(yōu)化結(jié)果與已知的最優(yōu)路徑還有2%～3%的誤差。這一方面說明大規(guī)模TSP問題的復(fù)雜程度更高，找到最優(yōu)路徑需要更多的搜索；另一方面通過調(diào)整聯(lián)合算子的參數(shù)，還可以獲得更好的優(yōu)化路徑。

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

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

4 結(jié)語

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