基于LabVIEW仿真實現(xiàn)TSP問題的模擬退火算法

趙敬和，謝 玲

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

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

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

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

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

1 LabVIEW的介紹

2 模擬退火算法（Simulated Annealing）

LabVIEW[2]（Laboratory Virtual Instrument Engineering

2.1 模擬退火算法概述

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

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

2.2 模擬退火算法原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

主界面實現(xiàn)模擬退火算法的初始條件：初始溫度、結(jié)束溫度的設(shè)置、城市距離文件的讀取，以及結(jié)果的查看（分圖形化和數(shù)字化，圖形化是可以直接查看走的路徑和線路，數(shù)字化就是以城市的標號，直觀地表示出路徑），其主界面的流程圖如圖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仿真實現(xiàn)模擬退火算法對TSP問題的計算結(jié)果（也即主界面圖）如圖3所示。

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

以上兩圖是針對31個城市坐標的TSP問題程序進行的仿真，在初始溫度10 000，結(jié)束溫度0.001，溫度衰減系數(shù)為α=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軟件實現(xiàn)的解決TSP問題的模擬退火算法，計算多次雖然城市的訪問起點不同，但城市的訪問次序是一定的，說明該LabVIEW實現(xiàn)的模擬退火算法的仿真將結(jié)果具有穩(wěn)定性，以及算法的可靠性。

5 結(jié)果分析

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

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

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

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

6 結(jié)束語

本文主要針對LabVIEW做了簡單的介紹，對模擬退火算法原理進行了分析，完全由LabVIEW來實現(xiàn)該算法的計算過程，并將該算法應(yīng)用于TSP問題的求解，得到了預(yù)期效果。前人有很多用遺傳算法求解該TSP問題，但結(jié)果也不是非常的理想，但是如果用LabVIEW把這兩種算法結(jié)合起來一起實現(xiàn)，可能結(jié)果會更好，因此還有許多工作有待研究，需進一步去實現(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]郭茂祖，洪家榮.基于模擬退火算法旅行商問題的并行實現(xiàn)[J].哈爾濱理工大學(xué)學(xué)報，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].電子設(shè)計工程，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é)報：自然科學(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.