用模擬退火算法求解TSP

朱靜麗

（英德廣播電視大學，廣東 英德 513000）

用模擬退火算法求解TSP

朱靜麗

（英德廣播電視大學，廣東 英德 513000）

貨郎擔問題，即TSP（Travelling Salesman Problem），是一個組合優化問題。具有NPC計算復雜性。本文分析了模擬退火算法模型，研究了用模擬退火算法求解TSP算法的可行性，并給出了用模擬退火算法求解TSP問題的具體實現方法。

模擬退火原理；算法；TSP

一、貨郎擔問題

貨郎擔問題，即TSP（Travelling Salesman Problem），也叫旅行商問題，是數學領域中著名問題之一。其一般提法為：假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路經的限制是每個城市只能拜訪一次，而且最后要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。如圖1所示，顯然左邊的路程要小于右邊的路程。

圖1 TSP的示意圖

貨郎擔問題（TSP問題）是一個組合優化問題。具有NPC計算復雜性。因此，任何能使該問題的求解得以簡化的方法，都將受到高度的評價和關注。一個最容易想到的方法是利用排列組合的方法把所有的路徑都計算出來，并逐一比較，選出最小的路徑。雖然該方法在理論上是可行的，但路徑的個數與城市的個數成指數增長，當城市個數較大時，該方法的求解時間是難以忍受的，甚至是不可能完成的。以每秒1億次的計算速度來估算，如果TSP問題包含20個城市時，求解時間長達350年；如果要處理30個城市，則求解時間更長達1+10e16年。如此長的時間，在實際中完成是不現實的?；谀M退火算法在處理全局優化、離散變量優化等困難問題中，具有傳統優化算法無可比擬的優勢。嘗試用模擬退火算法求解。

二、模擬退火算法

（一）模擬退火算法原理

模擬退火算法原理來源于固體退火：將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最后在常溫時達到基態，內能減為最小。根據Metropolis準則，粒子在溫度T時趨于平衡的概率為e-ΔE/（kT），其中E為溫度T時的內能，ΔE為其改變量，k為Boltzmann常數。用固體退火模擬組合優化問題，將內能E模擬為目標函數值f，溫度T演化成控制參數t，即得到解組合優化問題的模擬退火算法：由初始解i和控制參數初值t開始，對當前解重復“產生新解→計算目標函數差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當前解即為所得近似最優解，這是基于蒙特卡羅迭代求解法的一種啟發式隨機搜索過程。退火過程由冷卻進度表（Cooling Schedule）控制，包括控制參數的初值t及其衰減因子Δt、每個t值時的迭代次數L和停止條件S。

（二）模擬退火算法的模型

模擬退火算法可以分解為解空間、目標函數和初始解三部分。

模擬退火的基本思想:

1.初始化：初始溫度T（充分大），初始解狀態S（是算法迭代的起點），每個T值的迭代次數L

2.對k=1，……，L做第（3）至第6步：

3.產生新解S′

4.計算增量Δt′=C（S′）-C（S），其中 C（S）為評價函數

5.若Δt′〈0則接受S′作為新的當前解，否則以概率exp（-Δt′/T）接受S′作為新的當前解.

6.如果滿足終止條件則輸出當前解作為最優解，結束程序。

終止條件通常取為連續若干個新解都沒有被接受時終止算法。

7.T逐漸減少，且T-〉0，然后轉第2步。

三、模擬退火算法求解TSP

求解TSP的模擬退火算法模型描述如下:

解空間：解空間 S是遍訪每個城市恰好一次的所有路經，解可以表示為{w1,w2 ,…, wn}，w1, …, wn是1,2,…,n的一個排列，表明w1城市出發，依次經過w2, …, wn城市，再返回w1城市。初始解可選為（1,…, n） ;

目標函數：目標函數為訪問所有城市的路徑總長度；要求的最優路徑為目標函數為最小值時對應的路徑。新路徑的產生：隨機產生1和n之間的兩相異數k和m，不妨假設k〈m，則將原路徑

（w1,w2,…,wk,wk+1,…,wm,wm+1,…,wn）

變為新路徑：

（w1,w2,…,wm,wk+1,…,wk,wm+1,…,wn）上述變換方法就是將k和m對應的兩個城市在路徑序列中交換位置,稱為2-opt映射。

四、代碼實現

UINT SACompution(LPVOID pParam)

以上程序在Windows XP Professional、Visual C++ 6.0、STLport 4.6.2環境下調試完成。模擬退火算法一種新的隨機搜索方法，經實驗研究，能有效解決組合優化問題，與以往的近似算法相比，模擬退火算法具有使用靈活、運用廣泛、運行效率高和較少受到初始條件約束等優點。

[1] 劉曉禹，張洪強. 基于模擬退火算法的城市公交線路鋪設分析[J]. 交通科技與經濟，2010，5.

[2] 朱振方，劉培玉，張洪軍，王美方. 基于退火遺傳算法的網絡信息過濾系統研究[J]. 計算機工程與設計，2009，2.

[3] 徐俊杰. 利用微正則退火算法求解車輛路徑問題[J]. 安慶師范學院學報（自然科學版），2009，2 .

Simulated annealing algorithm for TSP

ZHU Jing-li

Traveling salesman problem, that TSP (Travelling Salesman Problem), is a combinatorial optimization problem. Computational complexity with the NPC. This paper analyzes the simulated annealing algorithm model to study the simulated annealing algorithm for TSP of the algorithm, and gives the simulated annealing algorithm for TSP on the specific implementation.

Simulated annealing principles; algorithms; TSP

TP3

A

1008-7427（2011）09-0159-02

2011-07-20