求解TSP問題的改進模擬退火算法

何錦福 符強 王豪東

摘? 要： 模擬退火算法是一種結構簡單，魯棒性強的群智能方法，在旅行商問題（Traveling Salesman Problem TSP）中得到了較好的應用。但是該算法在獲取高性能解的過程中需要放慢降溫過程，因此收斂速度較慢。為了解決該問題，本文對求解TSP問題的模擬退火算法進行了降溫方式的改進，針對溫度設置能量值，并根據能量值的高低狀態判斷是否進行跳躍式降溫，從而在保證精度的同時，加快了算法的收斂速度。用TSPLIB標準庫數據測試的結果表明，與改進前的模擬退火算法相比，改進的算法具有更加高效的尋優能力。

關鍵詞： TSP問題; 模擬退火算法; 跳躍式降溫; 二重退火

中圖分類號：TP301.6? ? ? ? ? 文獻標志碼：A? ? ?文章編號：1006-8228（2019）07-47-04

Abstract： Simulated annealing is a simple and robust swarm optimization method， which has been well applied in solving Traveling Salesman Problem （TSP）. However， the algorithm needs to slow down the cooling process in the process of obtaining high-performance solutions， so the convergence speed is slow. In order to solve this problem， this paper improves the simulated annealing algorithm for solving TSP， sets the energy value for the temperature， and judges whether the jumping cooling is carried out according to the state of the energy value， thus speeds up the convergence speed of the algorithm while ensuring the accuracy. The performance of the algorithm is verified by the test on standard TSPLIB data， the results show that the improved algorithm has a more efficient optimization.

Key words： TSP; Simulated annealing algorithm; jumping cooling; twice annealing

0 引言

TSP問題又被稱之為旅行商問題，該問題為一名旅行商人要去多個城市旅游，其中每個城市僅去一次，且最終回到原點，求所走路徑最短的方案。隨著TSP問題中的城市數目增加，問題的復雜度呈指數上升，此類問題的大型實例無法用窮舉法這類常規算法求解，需尋找有效的近似方法計算。目前人們已經提出了多種人工智能算法來求解該類問題：蟻群優化算法[4]，遺傳算法[5]，神經網絡算法[6]，改進的遺傳混合蟻群算法[1]等。其中模擬退火算法使用靈活、描述問題簡單直觀，能擴大全局搜索能力，有效解決算法結果陷入局部最優的問題。因此在TSP問題的求解中具有更佳的性能。

模擬退火算法借鑒了固體退火的機制。當固體處于高溫狀態時，內部的粒子無序并且活躍，而在其慢慢冷卻的過程中，隨著溫度逐漸下降，內部粒子將隨之變得漸漸有序。1983年，S. Kirkpatrick等人成功將模擬退火思想引入到組合優化問題上。目前已經廣泛應用于VLSI設計、一維下料問題研究[2]和神經網計算機的研究。在解決TSP問題時，模擬退火算法為得到精確的結果，耗費時間成本較大，本文由此改進了模擬退火算法的退火策略以達到保證結果精度的同時縮減時間的目的。

1 模擬退火算法

1.1 模擬退火算法簡介

給算法一個初始值作為當前解，這個解包含的部分元素通過變換產生大量新解，算法選擇其中的最優解作為當前新解。每一次都以最優解作為當前新解會讓算法結果陷入局部最優，因此模擬退火算法有著概率突跳特性。即會以一定的概率去接受比最優解要差的解作為當前新解，那么下一次選擇當前新解時就會在該差解的鄰域空間中去尋找，這就為尋找全局最優解提供了新的方向，使算法跳出局部最優具有更大的可能性。模擬退火算法突跳性的概率會隨著溫度的降低而降低，在溫度降低的同時算法重復著“產生新解→比較兩個解的優劣→是否接受”的過程。當達到終止條件，算法所得的解即為全局最優解。

1.2 算法流程

Step1 初始化：設定初始溫度T0，每個溫度下的迭代次數L，給定初始解M。

Step2 每個溫度下的L次迭代重復Step3-Step5。

Step3 產生新解MC。

Step4 計算增量ΔT=C（MC）-C（M），其中C（M）為評價函數。

Step5 若ΔT<0則接受MC成為新解，否則以exp（-ΔT/T）的概率接受MC作為新的當前解。

Step6 當算法滿足要求或者達到終止溫度時，程序結束。

2 基于改進模擬退火算法的TSP問題求解方案

在求解tsp問題時，模擬退火算法在初始溫度、降溫系數、終止溫度、每個溫度的迭代次數L共同作用下，算法進行大規模的數據迭代以及更新，搜尋比當前解更好的解，當達到終止溫度后，算法運行結束得到的最新解就是最優解。模擬退火算法因為其大量的迭代次數以及概率突跳特性，擁有強大的全局搜索能力。但同時也需要大量的時間來完成算法的搜索過程。為了提升算法的效率，目前對模擬退火算法的改進方案大多是通過增加算子或與其他人工智能算法相結合等途徑，來達到提高算法最優解精度的目的，而對于時間效率的考慮較少。本文對模擬退火算法的過程進行了探索，針對提高收斂速度的要求，提出了以下改進措施。

2.1 跳躍式降溫

針對退火策略提出跳躍式降溫，每一個溫度都有能量值P。在某溫度下的L次迭代中，迭代成功的次數越多，則該溫度的能量值P越大。給定一個能量標準值N，把此溫度的P值與N值相比較，如果P值超過設定的N值，那么該溫度被稱為跳躍溫度J。跳躍溫度是指該溫度在臨近的溫度當中，進行迭代的成功次數很多。可以進行一次跳躍式降溫，把該溫度臨近的溫度所需要進行的降溫環節省略，進行一次幅度比較大的降溫。在算法使用跳躍式降溫后，相比沒有使用跳躍式降溫的算法，數據迭代處理的次數大大減少。

2.2 二重退火

跳躍溫度分為基準跳躍溫度JR和超級跳躍溫度JS。JR代表P值略大于或等于N值。JS代表P值遠遠大于N值。在JS 中能搜尋到的最優解質量是遠高于JR中得到的解。在判定某個溫度為JR后進行了跳躍，如果該溫度的臨近溫度中出現了JS，那么JS就會被跳過。這種情況下就遺漏了這附近所有溫度中所能得到的最優解。為了盡量消除這種情況帶來的影響，算法還使用了二重退火。利用第一次退火產生一個較優的解，然后把溫度初始化。開始進行第二次退火，產生一個最終解。進行第二次退火等價于讓第一次退火中產生的較優解重新回到高溫狀態下去迭代。第二次退火中，初始解的精確度已經較高了，因此退火過程中整體的迭代成功率下降。原來的JR退化成了普通溫度，而JS相較之下則更可能被保存下來仍然被判定為跳躍溫度，進行跳躍式降溫。這樣就更容易搜尋到最優解，解決了JR與JS出現位置相近帶來的問題。算法使用跳躍式降溫與二重退火的改進后，相比其他文獻，在保證了結果的精確性的基礎上又減少了數據迭代處理次數。

2.3 路徑的變異方式

路徑變異方式的多樣性影響到全局解是否會陷入到局部最優。在產生新路徑的時候，如果只用一種路徑的變異方式，那么新的路徑產生就只朝著該變異方式的方向進行下去，即使模擬退火算法以一定概率接受較差解來跳出局部最優解，所能達到的也只是該種路徑變異方式下的全局最優解。多增加幾種路徑的變異方式，新路徑的產生就能從多個方向去進行，此時就會有更大的可能去逼近標準的解。本文采用了交換、移位、倒置的路徑變異方式。

路徑交換是指隨機選擇若干個城市進行交換位置。如果是兩個城市之間的交換看成是點與點的交換。若干個城市點之間的交換，可以看成是城市點連成的城市段之間形成的交換。以此來形成新的路徑。路徑移位是指隨機在路徑中選出兩個城市，把這兩個城市以及它們中間的若干個城市，統一向左或者向右移動若干個位置，得到了新的路徑。路徑倒置是指隨機在路徑中選出兩個城市，將這兩個城市之間的城市順序完全倒置得出新的路徑。

2.4 改進后的算法流程

Step1 初始化：設定初始溫度T0，溫度下降系數A，終止溫度Tf，每個溫度下的迭代次數L，給定一條初始路徑以及初始解。

Step2 每個溫度下的L次迭代重復Step3-Step5。

Step3 用交換、移位、倒置的方式產生新的路徑。

Step4 把新路徑長度與原來的路徑相比較，若新路徑更短則直接替代原來的路徑。如果新路徑長則以“exp（-（Ln+1-Ln）/T）”的概率來接受新路徑。（Ln+1為最新路徑長度，Ln為原來長度，T為當前溫度）

Step5 根據P值與N值得關系判斷溫度是否為跳躍溫度。

Step6 降溫。

Step7 達到終止溫度Tf。算法運行結束得到結果。

3 仿真實驗分析

為了驗證改進后的算法相比較于模擬退火算法在解決TSP問題時，在提高了收斂速度的同時還保證了解的精準度。該算法在TSPLIB標準庫中隨機選擇不同規模的城市進行測試。為了保證實驗不出現偶然性，針對每一個城市規模的TSP問題都進行十次仿真實驗并采集數據。記錄下最優解、計算出平均解，并以其他文獻中的優秀解或官方解做參考。實驗分別記錄了每一個TSP問題的前五次算法平均運行時間和后五次的算法平均運行時間。每個問題的10次實驗中前五次是沒有改進降溫機制的，后五次是使用了改進的降溫機制。為節省篇幅，實驗數據采用整數。

算法測試在Window 10系統core i7的環境下進行，測試的程序為MATLAB R2017b。每個TSP問題的實驗初始溫度為97?目標溫度為3?迭代次數L為5000。eil51問題，st70問題，eil76問題，pr107問題，lin105的降溫系數A為0.999，dantzig42問題、berlin52問題、kroA100問題、kroa150問題為0.99。從表中的平均值可看出本文算法的結果比較穩定，這是因為二重退火機制可以增強算法魯棒性。實驗數據中得到的最優解與參考解精度相近，從個別TSP問題中的到的最優解已經超越了參考解。從前五組與后五組的平均時間對比中可以得出在使用改進的降溫方式以后，退火所需時間基本減少，加快了收斂速度。在針對城市數越多分布越復雜，降溫越慢的情況上，效果更加明顯。

為了更好地展現改進后的模擬退火算法比改進前收斂速度的加快情況，本文記錄并繪制了在不同城市規模下，各tsp測試結果的收斂曲線圖。因篇幅的長度限制，這里僅顯示st70在算法改進前降溫系數為0.999（圖1），以及改進后降溫系數為0.999（圖2）數據處理次數的測試結果。

在圖1和圖2兩幅圖中，曲線呈快速下降的趨勢說明是高溫狀態。而趨于平緩則是已經到了低溫期。從圖中曲線的下降趨勢可以看出，算法在改進前處理st70問題時，當數據處理1×107次時路徑長度為1000～1500還處于快速縮短的過程。而算法改進后當數據處理1×107次時路徑長度為500～1000已經處于平緩狀態。圖1的數據處理次數為52132245次，圖2的數據處理次數為26949830次，減少了近一半的處理次數，因此花費時間也相應的縮短了一半，所得到路徑長度是相近的。綜上所述，本文改進后的模擬退火算法能夠提高時間效率，節省時間。

4 結論

本文提出了一種改進的模擬退火算法，通過結合多種路徑變異方式保證了解的精準度。創造了跳躍式降溫的降溫方式減少了運算時間。在保證算法尋找全局最優解能力的前提下，加快了從高溫到低溫的降溫過程。使模擬退火算法的概率跳變特性更具有自適應性，利于算法尋優，并將改進的思想在程序中實現，通過對TSP不同實例的優化實驗結果及對比分析表明，本文設計的算法具有可行性，可以為想要在模擬退火算法解的質量上做改進的同行，提供縮短算法運行時間的方法。該方法提高了針對TSP問題的優化效率，但是目前只對能量值做出一個定性的判定，下一步將對能量值做出一個定量的分析，使跳躍溫度的判定更加準確。

參考文獻（References）：

[1] 徐德明.改進的遺傳混合蟻群算法在TSP問題中的應用[J].計算機時代，2012（11）：31-32+36.

[2] 張夢，陳仕軍，李嘉賓，劉朝陽.基于模擬退火算法的一維下料研究[J].計算機時代，2017.12：1-4

[3] 杜鵬楨，唐振民，孫研.一種面向對象的多角色蟻群算法及其TSP問題求解[J].控制與決策，2014.29（10）：1729-1736

[4] 易正俊，李勇霞，易校石.自適應蟻群算法求解最短路徑和TSP問題[J].計算機技術與發展，2016.26（12）：1-5

[5] 姚明海，王娜，趙連朋.改進的模擬退火和遺傳算法求解TSP問題[J].計算機工程與應用，2013.49（14）：60-65

[6] 郭中華，金靈，鄭彩英.人工神經網絡求解TSP問題的改進算法研究[J].計算機仿真，2014.31（4）：355-358

[7] 張家善，王志宏.基于信息素的改進蟻群算法及其在TSP中的應用[J].數學的實踐與認識，2013.43（22）：157-161

[8] 于宏濤，高立群，田衛華.求解TSP的離散人工蜂群算法[J].東北大學學報：自然科學版，2015.36（8）：1074-1079

[9] 程博，楊育，劉愛軍等.基于遺傳模擬退火算法的大件公路運輸路徑選擇優化[J].計算機集成制造系統，2013.19（4）：879-887