基于LabVIEW仿真實現TSP問題的模擬退火算法

趙敬和，謝 玲

（1.中國地質大學 地球物理與信息技術學院，北京 100083；2.青島理工大學 自動化工程學院，山東 青島 266033）

TSP問題[1]是圖論研究中的一個經典算法問題，皆在尋找各個城市結點之間的最短路徑。問題的主要種類有：確定起點的TSP問題；確定終點的TSP問題；全局最優(yōu)的TSP問題。其中TSP問題是求連接各個城市之間最短路徑，它的限制條件最少，但答案的可能性最多。TSP問題在實際應用中具有典型意義，如可用來解決分配問題、路徑問題、車輛調度問題、網絡問題、切割問題等。

模擬退火算法[1]（SimulatedAnnealing，SA）最早由 Kirkpatrick等應用于組合優(yōu)化領域，它是基于Mente-Carlo迭代求解策略的一種隨機尋優(yōu)算法。模擬退火算法是一種通用的優(yōu)化算法，理論上算法具有概率的全局優(yōu)化性能，具有很強的全局搜索能力、通用性強、魯棒性高，目前已在工程中得到了廣泛應用，諸如函數優(yōu)化、生產調度、圖像處理、控制工程、機器學習、神經網絡、信號處理、人工智能與科學計算等領域。Workench）是開發(fā)虛擬儀器的集成環(huán)境，是美國國家儀器（NI）公司的創(chuàng)新軟件產品，也是目前應用最廣、發(fā)展最快、功能最強的圖形化軟件集成開發(fā)環(huán)境，主要用于開發(fā)測試、測量與控制系統(tǒng)。所有的LabVIEW應用程序，即虛擬儀器，包括前面板、流程圖（后面板）以及圖標/連接器3部分。

傳統(tǒng)的文本代碼式編程語言是控制流程圖，程序是按語句的先后順序來執(zhí)行的；而LabVIEW圖形化編程是數據流編程，只是要當某個節(jié)點的輸入數據都變?yōu)橛行r，節(jié)點就開始運行。

LabVIEW程序采用模塊化方法，它由各個模塊組成，每個模塊實現特定的功能，將它們組合起來之后就可以開發(fā)出一個大的用戶程序或項目。子VI作為LabVIEW編程的層次化和模塊化編程的重要組成部分，子VI的使用可以讓整個程序結構變得更加清晰、層次更加分明、程序更加易讀和維護。

1 LabVIEW的介紹

2 模擬退火算法（Simulated Annealing）

LabVIEW[2]（Laboratory Virtual Instrument Engineering

2.1 模擬退火算法概述

模擬退火又稱MonteCarlo退火，是一種常用的全局優(yōu)化方法，它來源于固體退火原理：將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變?yōu)闊o序狀態(tài)，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內能減為最小。

模擬退火算法（SA）是一種新的隨機搜索方法，是近年來提出的一種適合于解決大規(guī)模組合優(yōu)化問題的通用而有效的近似算法。與其它搜索方法相比，具有如下的特點：以一定的概率接受惡化解；引進算法控制參數；使用對象函數值進行搜索；搜索復雜區(qū)域；具有描述簡單、使用靈活、運用廣泛、運行效率高和較少受到初始條件約束等優(yōu)點。

2.2 模擬退火算法原理

模擬退火算法（AS）源于統(tǒng)計物理學，是模擬熔化狀態(tài)下物體由逐漸冷卻至最終達到結晶狀態(tài)的物理過程。模擬退火算法是利用問題的求解過程與熔化物體退火過程的相似性，采用隨機模擬物體退火過程來完成問題的求解，也就是在控制參數（溫度）的作用下對參數的值進行調整，直到所選取的參數值最終使能量函數達到全局極小值。

1982年，Kirkpatrick等將退火思想引入組合優(yōu)化問題，同時綜合了統(tǒng)計物理學和局部搜索方法，提出一種解大規(guī)模組合優(yōu)化問題的方法，特別是NP完全組合優(yōu)化問題的有效近似算法～模擬退火算法。采用Metropolis接受準則，并用一組稱為冷卻進度表的參數控制算法進程，使算法在多項式時間里給出一個近似最優(yōu)。Metropolis準則是Metropolis等1953年提出的重要性采樣法。

算法計算過程為[3-4]：

1）初始化：初始溫度T0，初始解狀態(tài)S（是算法迭代的起點），每個溫度值的迭代次數L，溫度衰減系數α，令當前溫度T=T0，終止條件 q；

2）在當前溫度下，對 k=1，2，……，L 做第 3） 至第 6）步；

3）產生新解 S′；

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

5）若 ΔC′＜0，則接受 S′作為新的當前解，否則以概率

exp（ΔC′/T）接受 S′作為新的當前解；

6）如果滿足終止條件則輸出當前解S′作為最優(yōu)解，結束程序。終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法；

7）T=αT 逐漸減少，且 T＞0，然后轉第 2）步。

按照一定的退火方案逐步降低溫度，重復Metropolis過程，當系統(tǒng)溫度足夠低時，可認為達到了全局最優(yōu)化狀態(tài)。

3 旅行商問題的定義與模型

TSP問題從問題描述上來看是一個非常簡單的問題，它指的是一個旅行者想周游多個城市，條件是必須每個城市都要訪問到，并且只能訪問一次，然后返回出發(fā)城市。在給定城市間的旅行距離的前提下，要求在完成對所有城市的訪問后，所走的距離最短。即：

假設有一個圖G=（V，E），其中V是定點集，E是邊集，設D=dij是頂點i和j之間的距離所組成的距離矩陣，旅行商問題就是求出一條通過所有頂點且每個頂點只通過一次的具有最短距離的回路。若旅行商要訪問的城市數量為n個，那么訪問所有城市路徑的組合數量就有（n-1）!個。這里當n的數值不大時，我們很容易找到整個訪問過程的最短路徑。但是，當n的數值非常大時，整個訪問路徑的組合數量就會急劇的增加，最后達到人工無法計算程度。

4 模擬退火算法TSP問題的LabVIEW仿真

模擬退火算法解決 TSP問題：問題重述，已知這個城市之間的相互間距離，現有一個旅行者必須訪遍這n個城市，并且每個城市只能訪問一次，最后又必須返回出發(fā)城市。

在此由8個LabVIEW的子VI模塊實現模擬退火算法解決該TSP問題的求解。首先，建立產生1到n（n表示城市數，在此城市分別給以標號）數組、產生隨機路徑、任意兩城市間距離、任意路徑的距離、兩組路徑選優(yōu)程子VI，然后是主程序選模擬退火算法的優(yōu)化過程、畫圖子VI，最后是主界面的子VI[5]。

主程序模擬退火算法實現流程如圖1所示。

圖1 主程序算法的程序流程圖Fig.1 The flow chart of main program algorithm procedures

主界面實現模擬退火算法的初始條件：初始溫度、結束溫度的設置、城市距離文件的讀取，以及結果的查看（分圖形化和數字化，圖形化是可以直接查看走的路徑和線路，數字化就是以城市的標號，直觀地表示出路徑），其主界面的流程圖如圖2所示。

圖2 主界面的程序流程圖Fig.2 Program flow chart of main interface

文中選取31個省會城市作為測試樣本，其相對坐標為cities=[1 304，2 312；3 639，1 315；4 177，2 244；3 712，1 399；3 488，1 535；3 326，1 556；3 238，1 229；4 196，1 004；4 312，790；4 386，570；3 007，1 970；2 562，1 756；2 788，1 491；2 381，1 676；1 332，695；3 715，1 678；3 918，2 179；4 061，2 370；3 780，2 212；3 676，2 578；4 029，2 838；4 263，2 931；3 429，1 908；3 507，2 367；3 394，2 643；3 439，3 201；2 935，3 240；3 140，3 550；2 545，2 357；2 778，2 826；2 370，2 975；]， 由LabVIEW仿真實現模擬退火算法對TSP問題的計算結果（也即主界面圖）如圖3所示。

圖3 LabVIEW計算結果的路徑圖Fig.3 The path chart of LabVIEW calculation results

以上兩圖是針對31個城市坐標的TSP問題程序進行的仿真，在初始溫度10 000，結束溫度0.001，溫度衰減系數為α=0.95情況下，計算得到的31個城市間最短往返距離是15 377.7 km. 城市的訪問次序為：16、4、8、9、10、2、5、6、7、13、12、14、15、1、29、31、30、27、28、26、25、20、21、22、18、3、17、19、24、11、23。

運用LabVIEW軟件實現的解決TSP問題的模擬退火算法，計算多次雖然城市的訪問起點不同，但城市的訪問次序是一定的，說明該LabVIEW實現的模擬退火算法的仿真將結果具有穩(wěn)定性，以及算法的可靠性。

5 結果分析

對于同樣的TSP問題用matlab編程來實現其模擬退火算法解，在此應用相同的城市數據，經多次計算，最優(yōu)結果15 461 km，路徑如圖4所示。

圖4 matlab計算結果的路徑圖Fig.4 The path chart of matlab calculation results

還有與文獻[6]中的最優(yōu)結果15 383 km對比（在文獻[6]中有詳細的路徑圖），LabVIEW實現的結果明顯占有優(yōu)勢，比其它的軟件實現的結果要好。

顯然LabVIEW實現模擬退火算法對同樣的TSP問題計算得出的結果要優(yōu)。

6 結束語

本文主要針對LabVIEW做了簡單的介紹，對模擬退火算法原理進行了分析，完全由LabVIEW來實現該算法的計算過程，并將該算法應用于TSP問題的求解，得到了預期效果。前人有很多用遺傳算法求解該TSP問題，但結果也不是非常的理想，但是如果用LabVIEW把這兩種算法結合起來一起實現，可能結果會更好，因此還有許多工作有待研究，需進一步去實現。

[1]康立山，謝云.非數值并行算法-模擬退火算法[M].北京：科學出版社，1994.

[2]雷振山，趙晨光，魏麗，等.LabVIEW8.2基礎教程[M].北京：中國鐵道出版社，2008.

[3]曲曉麗，潘昊，柳尚斌.旅行商問題的一種模擬退火算法求解[J].現代電子技術，2007（18）：78-82.

QU Xiao-li，PAN Hao，LIU Shang-bin.Solution of travelling salesman problem by a kind of simulated annealing algorithm[J].Modern Electronics Technique，2007（18）：78-82.

[4]郭茂祖，洪家榮.基于模擬退火算法旅行商問題的并行實現[J].哈爾濱理工大學學報，1997（5）：80-83.

GUO Mao-zu，HONG Jia-rong.A parallel algorithm for the simulated annealing based traveling salesman problem[J].Journal of Harbin University of Science and Technology，1997（5）：80-83.

[5]楊多星，劉蘊紅.基于LabVIEW仿真的全局最短路徑的遺傳算法[J].電子設計工程，2010（10）：29-33.

YANG Duo-xing，LIU Yun-hong.Genetic algorithm design of the global shortest path lines based on LabVIEW simulation[J].Electronic Design Engineering，2010（10）：29-33.

[6]高尚.求旅行商問題的模擬退火算法[J].華東船舶工業(yè)學院學報：自然科學版，2003，17（3）：13-16.

GAO Shang.Sloving TSP with simulated annealing algorithm[J].Journal of East China Shipbuilding Institute：Natural Science，2003，17（3）：13-16.