【正文】 數(shù)值算法是基礎(chǔ)科學(xué)，工程技術(shù)和管理科學(xué)等領(lǐng)域中常用的一類計算方法，如許多解組合優(yōu)化問題的算法就是典型的非數(shù)值算法，由于這些問題的尤其是其中的NP完全問題本身所固有的計算復(fù)雜性，求其精確解的計算量往往隨問題規(guī)模呈指數(shù)型增長，以致使用任何高速計算都需要耗費大量的時間，研究非數(shù)值計算的近似算法及其并行實現(xiàn)的途徑具有十分重要的實際意義.模擬退火算法是近幾年提出的一種適合解大規(guī)模組合優(yōu)化問題，特別是解NP完全問題的通用有效近似算法，它與以往的近似算法相比，具有描述簡單，使用靈活，運用廣泛，運行效率高和較少受初始條件限制等優(yōu)點，而且對推動并行計算的研究也有著重要的理論意義.：變量，約束和目標函數(shù)，在求解過程中選定的基本參數(shù)稱為變量，對變量取值的種種限制稱為約束，（TSP）是組合優(yōu)化問題中最為著名的問題，它易于描述難于求解，已引起許多數(shù)學(xué)家的興趣，但至今尚未找到有效的求解算法.貨郎擔問題，是由愛爾蘭數(shù)學(xué)家Sir William Rowan Hamilton和英國數(shù)學(xué)家Thomas Penyngton Kirkman在19世紀提出的數(shù)學(xué)問題，它是指給定n個城市并給出每兩個城市之間的距離，旅行商必須以最短路徑訪問所有的城市一次且僅一次，并回到原出發(fā)地，現(xiàn)已證明它屬于NP(Nondeterministic Polynomial非確定多項式)難題[1].歷史上的第一個正式用來解決TSP問題的算法誕生于1954年,，最早的描述是1759年歐拉研究的騎士周游問題，即對于國際象棋棋盤中的64個方格，走訪64個方格一次且僅一次，(TSP)由美國RAND公司于1948年引入，該公司的聲譽以及線性規(guī)劃這一新方法的出現(xiàn)使得TSP成為一個知名且流行的問題[2]旅行商問題是一個經(jīng)典的圖論問題：設(shè)有n個城市，用=1，2，…，i，j=1，2，…，n，設(shè)所有城市間兩兩連通，旅行商需要跑遍n個城市去推銷他的商品，而這些城市之間的距離都不一樣，這推銷員需要從其中一個城市出發(fā)，而他老板規(guī)定他必須把所有城市跑一遍，則TSP問題就是尋找讓旅行商遍訪每個城市一次且恰好一次的一條回路，：有N個城市由公路相互連通，從任一城市到另外城市都要支付相應(yīng)的費用，一個銷售商從其中一城市出發(fā)，訪問其他N－1個城市且僅一次，如何規(guī)劃一條路徑，使該旅行商的花費最少[3].當城市數(shù)量較小時，通過枚舉法就可以找出最短的路徑，然而隨著問題規(guī)模的增加，是諸多領(lǐng)域內(nèi)出現(xiàn)的多種復(fù)雜問題的集中概括和簡化形式，并且已成為各種啟發(fā)式的搜索、快速、,在物流配送、計算機網(wǎng)絡(luò)、電子地圖、交通誘導(dǎo)、電氣布線、VLSI單元布局等方面都有重要的工程和理論價值，引起了許多學(xué)者的關(guān)注.TSP是典型的組合優(yōu)化問題，早期的研究者使用精確算法求解該問題，、多局部極值的、趨于無窮大的復(fù)雜解的空間，搜索空間是n個點的所有排列的集合，大小為（n1）！.可以形象地把解空間看成是一個無窮大的丘陵地帶，：分枝定界法、線性規(guī)劃法和動態(tài)規(guī)劃法等，但可能的路徑總數(shù)隨城市數(shù)目n是成指數(shù)型增長的，出現(xiàn)了許多獨立于問題的智能優(yōu)化算法，如蟻群算法、遺傳算法、模擬退火、禁忌搜索、神經(jīng)網(wǎng)絡(luò)、粒子群優(yōu)化算法、免疫算法等，通過模擬或解釋某些自然現(xiàn)象或過程而得以發(fā)展，“劣化解”，具有突出的具有脫離局域最優(yōu)陷阱的能力，同時具有較強的局部搜索能力，、通用、靈活的優(yōu)點，將模擬退火算法引入TSP求解，可以避免在求解過程中陷入TSP的局部最優(yōu)解.本文首先介紹傳統(tǒng)的TSP問題，先對其進行數(shù)學(xué)描述，主要介紹其基本思想和關(guān)鍵技術(shù)，在此基礎(chǔ)上將模擬退火的思想引入TSP的求解，設(shè)計出TSP的一種模擬退火算法并用MATABLE語言編程予以實現(xiàn).2 選題背景 題目類型及來源題目類型：研究論文題目來源：專題研究 研究目的和意義 “.分為兩類：一是從待解決問題的原始數(shù)據(jù)結(jié)構(gòu)著手進竹構(gòu)造性求解，很難推廣到不同應(yīng)用領(lǐng)域：：從一個初始解開始，產(chǎn)生一個解序列，： 1)算法往往終止于局部最優(yōu)解.2)，“心”算法往往導(dǎo)致陷入局部最優(yōu)解，而不是全局最優(yōu)解.為了改善迭代型啟發(fā)算法的行為，有時選擇一批初始解，模擬退火(Simulated Annealing，以下簡稱SA)，具有描述簡單、使用靈活、運用廣泛、運行效率高和較少受初始條件約束等優(yōu)點，而且特別適合并行計算，它已成為現(xiàn)代科學(xué)技術(shù)中一個必不可少、重要的數(shù)學(xué)手段和方法，其應(yīng)用和發(fā)展為諸多領(lǐng)域中非線性問題的解決，將其用在貨郎擔問題的求解中. 國內(nèi)外現(xiàn)狀和發(fā)展趨勢與研究的主攻方向模擬退火算法(SA)在理論上已得到證明，它可以達到全局極小值，給出模擬退火算法的某些關(guān)于理想收斂模型的充分條件或充要條件，這些條件在理論上證明了當退火三原則(初始溫度足夠高、降溫速度足夠慢、終止溫度足夠低)滿足時，模擬退火算法以概率l達到全局最優(yōu)解；第二類是針對某些具體問題，正是由于專家和學(xué)者對該算法的鉆研，才讓該算法從經(jīng)典的模擬退火算法走到了今天的多樣型的模擬退火算法，比如快速模擬退火算法，使得該算法的速度和收斂性都得到較大提高，再比如適應(yīng)性的模擬退火算法，使得該算法具有智能性；再比如現(xiàn)在有學(xué)者提到的遺傳一模擬退火算法，(SA)從理論上可以達到全局極小值，所以對該算法的研究更有實際意義，眾多學(xué)者正在努力鉆研將其一般化，使其具有普遍適用性.3 模擬退火算法的一些知識 模擬退火算法的描述模擬退火算法(Simulated Annealing) 等人的文章, 他們在對組合優(yōu)化進行研究后, 根據(jù)迭代改進的思想提出了“模擬退火算法”, 將固體加溫至充分高, 再讓其緩慢降溫(即退火), 使之達到能量, 如果急速降溫(即淬火), 固體內(nèi)部粒子隨溫升變?yōu)闊o序狀, 內(nèi)能增大, 而緩慢降溫時粒子漸趨有序, 在每個溫度上都達到平衡態(tài),最后在常溫時達到基態(tài), 準則,粒子在溫度T 時趨于平衡的概率為exp( E/(kT)), 其中E 為溫度T 時的內(nèi)能, E 為其改變量, k 為Boltzman , 將內(nèi)能E 模擬為目標函數(shù)值f, 溫度T 演化成控制參數(shù)t, 即得到解組合優(yōu)化問題的模擬退火算法:由初始解i 和控制參數(shù)初值t 開始, 對當前解重復(fù)產(chǎn)生“新解→計算目標函數(shù)差→接受或舍棄”的迭代, 并逐步衰減t 值, 算法終止時的當前解即為所得近似最優(yōu)解, (Cooling Schedule)控制, 包括控制參數(shù)的初值t 及其衰減因子a、每個t 值時的迭代次數(shù)L :(1) 初始化:初始溫度T(充分大), 初始解狀態(tài)s(隨機選取一條TSP 路線, 算出走完此路線的長度Cost(s)作為評價函數(shù), 這是算法迭代的起點), 每個T 值的迭代次數(shù)L。(4) 計算增量Cost=Cost(s) C