用模擬退火算法求解TSP

朱靜麗

（英德廣播電視大學(xué)，廣東 英德 513000）

用模擬退火算法求解TSP

朱靜麗

（英德廣播電視大學(xué)，廣東 英德 513000）

貨郎擔(dān)問題，即TSP（Travelling Salesman Problem），是一個(gè)組合優(yōu)化問題。具有NPC計(jì)算復(fù)雜性。本文分析了模擬退火算法模型，研究了用模擬退火算法求解TSP算法的可行性，并給出了用模擬退火算法求解TSP問題的具體實(shí)現(xiàn)方法。

模擬退火原理；算法；TSP

一、貨郎擔(dān)問題

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

圖1 TSP的示意圖

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

二、模擬退火算法

（一）模擬退火算法原理

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

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

模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。

模擬退火的基本思想:

1.初始化：初始溫度T（充分大），初始解狀態(tài)S（是算法迭代的起點(diǎn)），每個(gè)T值的迭代次數(shù)L

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

3.產(chǎn)生新解S′

4.計(jì)算增量Δt′=C（S′）-C（S），其中 C（S）為評價(jià)函數(shù)

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

6.如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。

終止條件通常取為連續(xù)若干個(gè)新解都沒有被接受時(shí)終止算法。

7.T逐漸減少，且T-〉0，然后轉(zhuǎn)第2步。

三、模擬退火算法求解TSP

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

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

目標(biāo)函數(shù)：目標(biāo)函數(shù)為訪問所有城市的路徑總長度；要求的最優(yōu)路徑為目標(biāo)函數(shù)為最小值時(shí)對應(yīng)的路徑。新路徑的產(chǎn)生：隨機(jī)產(chǎn)生1和n之間的兩相異數(shù)k和m，不妨假設(shè)k〈m，則將原路徑

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

變?yōu)樾侣窂剑?/p>

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

四、代碼實(shí)現(xiàn)

UINT SACompution(LPVOID pParam)

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

[1] 劉曉禹，張洪強(qiáng). 基于模擬退火算法的城市公交線路鋪設(shè)分析[J]. 交通科技與經(jīng)濟(jì)，2010，5.

[2] 朱振方，劉培玉，張洪軍，王美方. 基于退火遺傳算法的網(wǎng)絡(luò)信息過濾系統(tǒng)研究[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2009，2.

[3] 徐俊杰. 利用微正則退火算法求解車輛路徑問題[J]. 安慶師范學(xué)院學(xué)報(bào)（自然科學(xué)版），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