趙敬和，謝 玲

（1.中國地質(zhì)大學(xué) 地球物理與信息技術(shù)學(xué)院，北京 100083；2.青島理工大學(xué) 自動(dòng)化工程學(xué)院，山東 青島 266033）

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

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

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

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

1 LabVIEW的介紹

2 模擬退火算法（Simulated Annealing）

LabVIEW[2]（Laboratory Virtual Instrument Engineering

2.1 模擬退火算法概述

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

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

2.2 模擬退火算法原理

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

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

算法計(jì)算過程為[3-4]：

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

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

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

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

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

exp（ΔC′/T）接受 S′作為新的當(dāng)前解；

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

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

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

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

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

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

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

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

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

主程序模擬退火算法實(shí)現(xiàn)流程如圖1所示。

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

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

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

文中選取31個(gè)省會(huì)城市作為測試樣本，其相對坐標(biāo)為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仿真實(shí)現(xiàn)模擬退火算法對TSP問題的計(jì)算結(jié)果（也即主界面圖）如圖3所示。

圖3 LabVIEW計(jì)算結(jié)果的路徑圖Fig.3 The path chart of LabVIEW calculation results

以上兩圖是針對31個(gè)城市坐標(biāo)的TSP問題程序進(jìn)行的仿真，在初始溫度10 000，結(jié)束溫度0.001，溫度衰減系數(shù)為α=0.95情況下，計(jì)算得到的31個(gè)城市間最短往返距離是15 377.7 km. 城市的訪問次序?yàn)椋?6、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。

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

5 結(jié)果分析

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

圖4 matlab計(jì)算結(jié)果的路徑圖Fig.4 The path chart of matlab calculation results

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

顯然LabVIEW實(shí)現(xiàn)模擬退火算法對同樣的TSP問題計(jì)算得出的結(jié)果要優(yōu)。

6 結(jié)束語

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

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

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

[3]曲曉麗，潘昊，柳尚斌.旅行商問題的一種模擬退火算法求解[J].現(xiàn)代電子技術(shù)，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]郭茂祖，洪家榮.基于模擬退火算法旅行商問題的并行實(shí)現(xiàn)[J].哈爾濱理工大學(xué)學(xué)報(bào)，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]楊多星，劉蘊(yùn)紅.基于LabVIEW仿真的全局最短路徑的遺傳算法[J].電子設(shè)計(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è)學(xué)院學(xué)報(bào)：自然科學(xué)版，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.