【正文】 方法就是將 k和 m對應(yīng)的兩個城市在路徑序列中交換位置 ,稱為 2opt映射。 目標(biāo)函數(shù)：目標(biāo)函數(shù)為訪問所有城市的路徑總長度 。 求解 TSP的模擬退火算法模型可描述如下 : 解空間：解空間 S是遍訪每個城市恰好一次的所有路經(jīng)，解可以表示為{w1,w2 ,……, wn} ， w1, ……, wn 是 1,2,……,n 的一個排列，表明 w1城市出發(fā)，依次經(jīng)過 w2, ……, wn 城 市，再返回 w1城市。 模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達(dá)到平衡態(tài)，最后在常溫時達(dá)到基態(tài)，內(nèi)能減為最小。并且這部分包括一些關(guān)鍵代碼。 基于模擬退火算法求解 TSP 問題詳細(xì)設(shè)計 第三章提供了模擬退火算法的大體框架和組合優(yōu)化要注意的問題，這節(jié)將了解模擬退火算法的具體流程圖和算法模型描述以及 模擬退火算法的參數(shù)控制問題 。描繪出模擬退火算法的流 程圖，了解該算法的運(yùn)行機(jī)制，明確算法在系統(tǒng)整體設(shè)計中的具體功能和應(yīng)用，并且對應(yīng)用模擬退火算法求解 TSP問題做個詳細(xì)的劃分和描述。在利用編寫出的模擬退火算法模型去解決之前所建立的 TSP問題模型。并且在 1個 TSP問題，問題的目標(biāo)是選擇出 路徑路程為所有路徑之中的最小值 的路徑。當(dāng)控制參數(shù)逐漸減小并趨于零時，系統(tǒng)亦越來越趨于平衡狀態(tài)，最后系統(tǒng)狀態(tài)對應(yīng)于優(yōu)化問題的整體最優(yōu)解 。經(jīng)過大量的解變換后，可以求得給定控制參數(shù) t值時優(yōu)化問題的相對最優(yōu)解。算法的基本思想是從一給定解開始的，從鄰域中隨機(jī)產(chǎn)生另一個解，接受準(zhǔn)則允許目標(biāo)函數(shù)在有限范圍內(nèi)變壞。 模擬退火算法與優(yōu)化問題分析 模擬退火算法用于優(yōu)化問題的出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般優(yōu)化問題的相似性 [11]。終止條件通常 取為連續(xù)若干個新解都沒有被接受時終止算法。 模擬退火的基本思想 : (1) 初始化：初始溫度 T(充分大 )，初始解狀態(tài) S(是算法迭代的起點(diǎn) )， 每 個 T 值的迭代次數(shù) L。 模擬退火算法模型 模擬退火算法起源于物理退火。目前人們已經(jīng)構(gòu)造出了許多近似求解法，如遺傳法、蟻群算法、模擬退火算法等 [10]。 一個實例如圖 所示 圖 TSP 問題的示意圖 從圖 。假設(shè)有一個旅行商人要拜訪 n 個城市，他必須選擇所要走的路徑，路經(jīng)的限制是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。 開發(fā)平臺 本課題開發(fā)語言選用 c++語言，可以選用的開發(fā)平臺可以從 c++語言平臺中選擇一種出來，本課題選用 visual C++。面向?qū)ο蟮脑O(shè)計思想是在原來結(jié)構(gòu)化程 序設(shè)計方法基礎(chǔ)上的一個質(zhì)的飛躍， C++完美地體現(xiàn)了面向?qū)ο蟮母鞣N特性。 開發(fā)語言 開發(fā)語言必須是 一種優(yōu)秀的面向?qū)ο蟪绦蛟O(shè)計語言 并且 適合于系統(tǒng)程序設(shè)計 。 應(yīng)用開發(fā)環(huán)境 完成一個完整并且優(yōu)秀的程序，為其配置一個良好的系統(tǒng)開發(fā)環(huán)境是十分必要的，接下來是介紹模擬退火算法解決 TSP 問題所需要配置的環(huán)境要求。 應(yīng)用研究整體規(guī)劃 通過對程序的理解和分析，這個課題項目應(yīng)該分為 2 個階段進(jìn)行。主要對系統(tǒng)進(jìn)行了整體的分析，明確了系統(tǒng)目標(biāo)，確定了開發(fā)環(huán)境，構(gòu)建了基本的框架結(jié)構(gòu)和功能模塊。智能計算將探索智能的新概念，新理論，新方法和新技術(shù)，而這一切將在以后的發(fā) 展中取得重大成就。即人工腦與生物腦將不只是功能模仿，而是具有相同的特性。 目前的智能計算研究水平暫時還很難使 “智能機(jī)器 ”真正具備人類的常識，但智能計算將在 21 世紀(jì)蓬勃發(fā)展。目前已廣泛應(yīng)用于函數(shù)優(yōu)化，神經(jīng)網(wǎng)絡(luò)訓(xùn)練，模糊系統(tǒng)控制以及其他遺傳算法的應(yīng)用領(lǐng)域。而是粒子在解空間追隨最優(yōu)的粒子進(jìn)行搜索。系統(tǒng)初始化為一組隨機(jī)解，通過疊代搜尋最優(yōu)值。源于對鳥群捕食的行為研究 。遺傳算法成功的應(yīng)用包括：作業(yè)調(diào)度與排序、可靠性設(shè)計、車輛路徑選擇與調(diào)度、成組技術(shù)、設(shè)備布置與分配、 交通 問題等等。 近幾年來，遺傳算法主要在復(fù)雜優(yōu)化問題求解和 工業(yè) 工程領(lǐng)域應(yīng)用方面，取得了一些令人信服的結(jié)果，所以引起了很多人的關(guān)注。遺傳算法最初被研究的出發(fā)點(diǎn)不是為專門解決最優(yōu)化問題而設(shè)計的，它與進(jìn)化策略、進(jìn)化規(guī)劃共同構(gòu)成了進(jìn)化算法的主要框架，都是為當(dāng)時人工智能的發(fā)展服務(wù)的。它是在 70 年代初期由美國密執(zhí)根（ Michigan）大學(xué)的霍蘭（ Holland）教授發(fā)展起來的。 3． 遺傳算法 遺傳算法（ Geic Algorithms）是基于生物進(jìn)化理論的原理發(fā)展起來的一種廣為應(yīng)用的、高效的隨機(jī)搜索與優(yōu)化的方法。網(wǎng)絡(luò)收斂就是 指能量函數(shù)達(dá)到極小值 [9]。當(dāng)網(wǎng)絡(luò)達(dá)到穩(wěn)定狀態(tài)的時候，也就是它的能量函數(shù)達(dá)到最小的時候。其狀態(tài)變化可以用差分方程來表征。即：網(wǎng)絡(luò)中的神經(jīng)元 t 時刻的輸出狀態(tài)實際上間接地與自己的 t1 時刻的輸出狀態(tài)有關(guān)。基本的 Hopfield神經(jīng)網(wǎng)絡(luò)是一個由非線性元件構(gòu)成的全連接型單層反饋系統(tǒng)。 2． Hopfield 神經(jīng)網(wǎng)絡(luò) 1986 年美國物 理學(xué) 家 陸續(xù)發(fā)表幾篇論文，提出了 Hopfiel 神經(jīng)網(wǎng)絡(luò)。神經(jīng)元細(xì)胞體將接受到的所有信號進(jìn)行簡單處理 (如：加權(quán)求和，即對所有的輸入信號都加以考慮且對每個信號的重視程度 ——體現(xiàn)在權(quán)值上 ——有所不同 )后由軸突輸出。其末端的許多神經(jīng)末梢使得興奮可以同時傳送給多個神經(jīng)元。每個神經(jīng)元都由一個細(xì)胞體，一個連接其他神經(jīng)元的軸突和一些向外伸出的其它較短分支 ——樹突組成。 神經(jīng)系統(tǒng)的基本構(gòu)造是神經(jīng)元 (神經(jīng)細(xì)胞 )，它是處理人體內(nèi)各部分之間相互信息傳遞的基本單元。早在本世紀(jì) 40 年代初期， 心理 學(xué)家 McCulloch、 數(shù)學(xué) 家 Pitts就提出了人工神經(jīng)網(wǎng)絡(luò)的第一個數(shù)學(xué)模型，從此開創(chuàng)了神經(jīng)科學(xué)理論的研模擬退火算法在 TSP問題中的應(yīng)用研究 第二章 相關(guān)知識介紹 7 究時代。 如人工神經(jīng)網(wǎng)絡(luò)技術(shù)、遺傳算法、模擬退火算法、模擬退火技術(shù)和 群集智能技術(shù)等。 蟻群優(yōu)化算法對于解決貨郎擔(dān)問題并不是目前最好的方法，但首先，它提出了一種解決貨郎擔(dān)問題的 新思路；其次由于這種算法特有的解決方法，它已經(jīng)被成功用于解決其他組合優(yōu)化問題，例如圖的著色 (Graph Coloring)以及最短超串(Shortest Common Supersequence)等問題 [6]。根據(jù) “信息素較濃的路線更近 的原則，即可選擇出最佳路線。 在解決貨郎擔(dān)問題時，蟻群優(yōu)化算法設(shè)計虛擬的 “螞蟻 ”將摸索不同路線，并留下會隨時間逐漸消失的虛擬 “信息素 ”。 蟻群算法及其它算法原 理 蟻群優(yōu)化算法 受螞蟻覓食時的 通信 機(jī)制的啟發(fā)， 90 年代 Dorigo 提出了蟻群優(yōu)化算 法(Ant Colony Optimization， ACO)來解決計算機(jī)算 法學(xué) 中經(jīng)典的 “貨郎擔(dān)問題 ”。正是這些問題的代表性和復(fù)雜性激起了人們對組合優(yōu)化理論與算法的研究興趣。 典型的組合優(yōu)化問題有旅行商問題（ Traveling Salesman Problem－ TSP）、加工調(diào)度問題 （ Scheduling Problem，如 FlowShop， JobShop） 、 01 背包問題（ Knapsack Problem）、裝箱問題（ Bin Packing Problem）、圖著色問題 （ Graph Coloring Problem）、聚類問題（ Clustering Problem）等。 組合優(yōu)化（ Combinatorial Optimization ）問題的目標(biāo)是從組合問題的可行解集中求出最優(yōu)解，通常可描述為：令 Ω＝ {s1， s2， … ， sn} 為所有狀態(tài)構(gòu)成的解空間， C (si) 為狀態(tài) si 對應(yīng)的目標(biāo)函數(shù)值，要求尋找最優(yōu)解 s*，使得對于所有的 si ∈ Ω，有 C(s*)＝ minC(si) 。自從擬陣概念進(jìn)入圖論領(lǐng)域之后，對擬陣中的一些理論問題的研究成為組合規(guī)劃研究的新課題，并得到應(yīng)用。從最廣泛的意義上說，組合規(guī)劃與整數(shù)規(guī)劃這兩者的領(lǐng)域是一致的，都是指在有限個可供選擇的方案的組成集合中，選擇使目標(biāo)函數(shù)達(dá)到極值的最優(yōu)子集。 組合優(yōu)化問題簡述 在給定有限集的所有具備某些條件的子集中，按某種目標(biāo)找出一個最優(yōu)子集的一類數(shù)學(xué)規(guī)劃。 假設(shè)有一個旅行商人要拜訪 N 個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。如何在初始解附近找出一個“好的解”是一項關(guān)鍵技術(shù) ,它直接影響算法的收斂速度。模擬退火算法最早思想由 Met ropolis 在 20 世紀(jì) 1953 年提出 ,1983 年 Kirkpat rick 等成功地將退火思想引入組合優(yōu)化領(lǐng)域。模擬退火算法在 TSP問題中的應(yīng)用研究 第二章 相關(guān)知識介紹 5 因此，任何能使該問題的求解得以簡化的方法，都將受到高度的評價和關(guān)注。 TSP 問題是一個組合優(yōu)化問題。假設(shè)有一個旅行商人要拜訪 n 個城市，他必須選擇所要走的路徑，路經(jīng)的限制是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。 模擬退火算法與初始值無關(guān)，算法求得的解與初始解狀態(tài) S(是算法迭代的起點(diǎn) )無關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率 l 收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。可在此基礎(chǔ)上開始下一輪試驗。 第四步是當(dāng)新解被確定接受時，用新解代替當(dāng)前解，這只需將當(dāng)前解中對應(yīng)于產(chǎn)生新解時的變換部分予以實現(xiàn)，同時修正目標(biāo)函數(shù)值即可。事實表明，對大多數(shù)應(yīng)用而言，這是計算目標(biāo)函數(shù)差的最快方法。 第二步是計算與新解所對應(yīng)的目標(biāo)函數(shù)差。 (7) T 逐漸減少，且 T0，然后轉(zhuǎn)第 2 步。 模擬退火算法在 TSP問題中的應(yīng)用研究 第二章 相關(guān)知識介紹 4 (5) 若 Δ t′0 則接受 S′作為新的當(dāng)前解，否則以概率 exp(Δ t′/T)接受 S′作為新的當(dāng)前解 . (6) 如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。 模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。 模擬退火的原理也和金屬退火的原理近似：將熱力學(xué)的理論套用到 統(tǒng)計 學(xué)上，將搜尋空間內(nèi)每一點(diǎn)想像成空氣內(nèi)的分子；分子的能量，就是它本身的動能；而搜尋空間內(nèi)的每一點(diǎn)，也像空氣分子一樣帶有 “能量 ”，以表示該點(diǎn)對命題的合適程度。 模擬退火的基本思想 模擬退火是一種通用概率算法，用來在一個大的搜尋空間內(nèi)找尋命題的最優(yōu)解。模擬退火作為一種隨機(jī)算法，它的特點(diǎn)非常適于求解 NP 問題，比如著名的旅行商問題 (Traveling Salesman Problem)。模擬退火算法主要應(yīng)用在各種優(yōu)化問題上，函數(shù)優(yōu)化是其中非常重要的一個方面 。它的思想最早在1953 年由 Metropolis 提出，在 1983 年被 Kirkpatrick 等人成功引入組合優(yōu)化領(lǐng)域。 模擬退火算法在 TSP問題中的應(yīng)用研究 第二章 相關(guān)知識介紹 3 第二章 相關(guān)知識介紹 本章主要介紹一些關(guān)于模擬退火算法的原理、 TSP 問題簡述以及相關(guān)重要算法的原理，并且對其進(jìn)行了一些細(xì)致的闡述，以便于對模擬退火算法了解。 很多實際問題，經(jīng)過簡化處理后均可轉(zhuǎn)化為 TSP 問題，對 TSP 問題求解方法的研究具有重要的應(yīng)用價值。目前求解 TSP問題的主要方法有啟發(fā)式搜索法、模 擬退火算法、遺傳算法、 Hopfield 神經(jīng)網(wǎng)絡(luò)算法、二叉樹描述算法 。 TSP 在中國的研究 ， 同樣的問題，在中國還有另一個描述方法：一個郵遞員從郵局出發(fā)，到所轄街道投郵件，最后返回郵局，如果他必須走遍所轄的每條街道至少一次，那么他應(yīng)該如何選擇投遞路線，使所走的路程最短？這個描述之所以稱為中國郵遞員問題（ Chinese Postman Problem CPP）因為是我國學(xué)者管梅古教授于 1962 年提出的這個問題并且給出了一個解法 。 發(fā)展趨勢 TSP 的歷史很久，最早的描述是 1759 年歐拉研究的騎士周游問題，即對于國際象棋棋盤中的 64 個方格，走訪 64 個方格一次且僅一次，并且最終返回到起始點(diǎn)。用固體退火模擬組合優(yōu)化問題，將內(nèi)能 E 模擬為目標(biāo)函數(shù)值 f，溫度 T 演化成控制參數(shù) t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解 i 和控制參數(shù)初值 t 開始，對當(dāng)前解重復(fù) “產(chǎn)生新解 → 計算目標(biāo)函數(shù)差 → 接受或舍棄 ”的迭代，并逐步衰減 t 值，算法終止時的模擬退火算法在 TSP問題中的應(yīng)用研究 第一章 前言 2 當(dāng)前解即為所得近似最 優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過程。 模擬退火算法的背景 模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內(nèi)部粒子隨溫升變 為無