【正文】 齊算法，整個(gè)過程僅由一個(gè)馬爾可夫鏈構(gòu)成，要求相連的狀態(tài)轉(zhuǎn)移中，溫度t 是下降的。2．溫度的下降函數(shù)溫度管理問題也是模擬退火算法難以處理的問題之一。因此，溫度參數(shù)的設(shè)定影響到模擬退火算法能否收斂到全局最優(yōu)解。溫度參數(shù)是模擬退火算法中一個(gè)關(guān)鍵的參數(shù)，初始溫度不夠高或退火時(shí)間不夠長將會(huì)使得搜索過快，從而使得算法容易陷于局部最優(yōu)解。然后從Xi的鄰域中隨即選擇Xj，計(jì)算Xi與Xi的路徑差，比較差值。 YYYYNNNN選擇初始路徑X0確定初始溫度T0當(dāng)前路徑Xi=X0當(dāng)前溫度Ti=T0當(dāng)前路徑Xi=Xj△f=0Exp(△f/Ti)random(0,1)跳出內(nèi)循環(huán)跳出外循環(huán)結(jié) 束當(dāng)前溫度Ti下降從Xi的鄰域中隨機(jī)選擇Xi，計(jì)算Xi與Xj的路程差△f=f(Xj)f(Xi)。新路徑的產(chǎn)生：隨機(jī)產(chǎn)生1和n之間的兩相異數(shù)k和m，不妨假設(shè)km，則將原路徑(w1,w2,…,wk,wk+1,…,wm,wm+1,…,wn)變?yōu)樾侣窂剑?w1,w2,…,wm,wk+1,…,wk,wm+1,…,wn)上述變換方法就是將k和m對應(yīng)的兩個(gè)城市在路徑序列中交換位置,稱為2opt映射。目標(biāo)函數(shù)：目標(biāo)函數(shù)為訪問所有城市的路徑總長度。求解TSP的模擬退火算法模型可描述如下:解空間：解空間S是遍訪每個(gè)城市恰好一次的所有路經(jīng)，解可以表示為{w1,w2 ,……, wn}，w1, ……, wn是1,2,……,n的一個(gè)排列，表明w1城市出發(fā)，依次經(jīng)過w2, ……, wn城市，再返回w1城市。模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。并且這部分包括一些關(guān)鍵代碼。第三章提供了模擬退火算法的大體框架和組合優(yōu)化要注意的問題，這節(jié)將了解模擬退火算法的具體流程圖和算法模型描述以及模擬退火算法的參數(shù)控制問題描繪出模擬退火算法的流程圖，了解該算法的運(yùn)行機(jī)制，明確算法在系統(tǒng)整體設(shè)計(jì)中的具體功能和應(yīng)用，并且對應(yīng)用模擬退火算法求解TSP問題做個(gè)詳細(xì)的劃分和描述。在利用編寫出的模擬退火算法模型去解決之前所建立的TSP問題模型。問題的目標(biāo)是選擇出路徑路程為所有路徑之中的最小值的路徑。當(dāng)控制參數(shù)逐漸減小并趨于零時(shí)，系統(tǒng)亦越來越趨于平衡狀態(tài)，最后系統(tǒng)狀態(tài)對應(yīng)于優(yōu)化問題的整體最優(yōu)解。經(jīng)過大量的解變換后，可以求得給定控制參數(shù)t值時(shí)優(yōu)化問題的相對最優(yōu)解。算法的基本思想是從一給定解開始的，從鄰域中隨機(jī)產(chǎn)生另一個(gè)解，接受準(zhǔn)則允許目標(biāo)函數(shù)在有限范圍內(nèi)變壞。模擬退火算法用于優(yōu)化問題的出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般優(yōu)化問題的相似性[11]。終止條件通常 取為連續(xù)若干個(gè)新解都沒有被接受時(shí)終止算法。模擬退火的基本思想:(1) 初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點(diǎn))， 每 個(gè)T值的迭代次數(shù)L。模擬退火算法起源于物理退火。目前人們已經(jīng)構(gòu)造出了許多近似求解法，如遺傳法、蟻群算法、模擬退火算法等[10]。 TSP問題的示意圖。假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路經(jīng)的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。本課題開發(fā)語言選用c++語言，可以選用的開發(fā)平臺可以從c++語言平臺中選擇一種出來，本課題選用visual C++。面向?qū)ο蟮脑O(shè)計(jì)思想是在原來結(jié)構(gòu)化程序設(shè)計(jì)方法基礎(chǔ)上的一個(gè)質(zhì)的飛躍，C++完美地體現(xiàn)了面向?qū)ο蟮母鞣N特性。開發(fā)語言必須是一種優(yōu)秀的面向?qū)ο蟪绦蛟O(shè)計(jì)語言并且適合于系統(tǒng)程序設(shè)計(jì)。完成一個(gè)完整并且優(yōu)秀的程序，為其配置一個(gè)良好的系統(tǒng)開發(fā)環(huán)境是十分必要的，接下來是介紹模擬退火算法解決TSP問題所需要配置的環(huán)境要求。通過對程序的理解和分析，這個(gè)課題項(xiàng)目應(yīng)該分為2個(gè)階段進(jìn)行。主要對系統(tǒng)進(jìn)行了整體的分析，明確了系統(tǒng)目標(biāo)，確定了開發(fā)環(huán)境，構(gòu)建了基本的框架結(jié)構(gòu)和功能模塊。智能計(jì)算將探索智能的新概念，新理論，新方法和新技術(shù)，而這一切將在以后的發(fā)展中取得重大成就。即人工腦與生物腦將不只是功能模仿，而是具有相同的特性。目前的智能計(jì)算研究水平暫時(shí)還很難使“智能機(jī)器”真正具備人類的常識，但智能計(jì)算將在21世紀(jì)蓬勃發(fā)展。粒子群優(yōu)化算法(PSO)同遺傳算法比較，PSO的優(yōu)勢在于簡單容易實(shí)現(xiàn)并且沒有許多參數(shù)需要調(diào)整。但是并沒有遺傳算法用的交叉(crossover)以及變異(mutation)。PSO同遺傳算法類似，是一種基于疊代的優(yōu)化工具。Computation)，有Eberhart博士和Kennedy博士發(fā)明。4．粒子群優(yōu)化算法在發(fā)展過程中，進(jìn)化策略、進(jìn)化規(guī)劃和遺傳算法之間差異越來越小。迄今為止，遺傳算法是進(jìn)化算法中最廣為人知的算法。Systems》）。andin它是在70年代初期由美國密執(zhí)根（Michigan）大學(xué)的霍蘭（Holland）教授發(fā)展起來的。Algorithms）是基于生物進(jìn)化理論的原理發(fā)展起來的一種廣為應(yīng)用的、高效的隨機(jī)搜索與優(yōu)化的方法。3．遺傳算法網(wǎng)絡(luò)收斂就是指能量函數(shù)達(dá)到極小值[9]。當(dāng)網(wǎng)絡(luò)達(dá)到穩(wěn)定狀態(tài)的時(shí)候，也就是它的能量函數(shù)達(dá)到最小的時(shí)候。其狀態(tài)變化可以用差分方程來表征。即：網(wǎng)絡(luò)中的神經(jīng)元t時(shí)刻的輸出狀態(tài)實(shí)際上間接地與自己的t1時(shí)刻的輸出狀態(tài)有關(guān)?；镜腍opfield神經(jīng)網(wǎng)絡(luò)是一個(gè)由非線性元件構(gòu)成的全連接型單層反饋系統(tǒng)。2．Hopfield神經(jīng)網(wǎng)絡(luò)，提出了Hopfiel神經(jīng)網(wǎng)絡(luò)。神經(jīng)元細(xì)胞體將接受到的所有信號進(jìn)行簡單處理(如：加權(quán)求和，即對所有的輸入信號都加以考慮且對每個(gè)信號的重視程度——體現(xiàn)在權(quán)值上——有所不同)后由軸突輸出。其末端的許多神經(jīng)末梢使得興奮可以同時(shí)傳送給多個(gè)神經(jīng)元。每個(gè)神經(jīng)元都由一個(gè)細(xì)胞體，一個(gè)連接其他神經(jīng)元的軸突和一些向外伸出的其它較短分支——樹突組成。神經(jīng)系統(tǒng)的基本構(gòu)造是神經(jīng)元(神經(jīng)細(xì)胞)，它是處理人體內(nèi)各部分之間相互信息傳遞的基本單元。J其后，F(xiàn)NETWORK，簡稱ANN)是在對人腦組織結(jié)構(gòu)和運(yùn)行機(jī)制的認(rèn)識理解基礎(chǔ)之上模擬其結(jié)構(gòu)和智能行為的一種工程系統(tǒng)。 “人工神經(jīng)網(wǎng)絡(luò)”(ARTIFICIAL如人工神經(jīng)網(wǎng)絡(luò)技術(shù)、遺傳算法、模擬退火算法、模擬退火技術(shù)和群集智能技術(shù)等。Supersequence)等問題[6]。Coloring)以及最短超串(Shortest由于這個(gè)算法利用了正反饋機(jī)制，使得較短的路徑能夠有較大的機(jī)會(huì)得到選擇，并且由于采用了概率算法，所以它能夠不局限于局部最優(yōu)解。虛擬的“信息素”也會(huì)揮發(fā)，每只螞蟻每次隨機(jī)選擇要走的路徑，它們傾向于選擇路徑比較短的、信息素比較濃的路徑。如果有n個(gè)城市，需要對所有n個(gè)城市進(jìn)行訪問且只訪問一次的最短距離[5]。Colony 蟻群算法及其它算法原理正是這些問題的代表性和復(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)域是一致的，都是指在有限個(gè)可供選擇的方案的組成集合中，選擇使目標(biāo)函數(shù)達(dá)到極值的最優(yōu)子集。在給定有限集的所有具備某些條件的子集中，按某種目標(biāo)找出一個(gè)最優(yōu)子集的一類數(shù)學(xué)規(guī)劃。假設(shè)有一個(gè)旅行商人要拜訪N個(gè)城市，他必須選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。如何在初始解附近找出一個(gè)“好的解”是一項(xiàng)關(guān)鍵技術(shù),它直接影響算法的收斂速度。模擬退火算法最早思想由Met ropolis 在20世紀(jì)1953 年提出,1983 年Kirkpat rick 等成功地將退火思想引入組合優(yōu)化領(lǐng)域。因此，任何能使該問題的求解得以簡化的方法，都將受到高度的評價(jià)和關(guān)注。 TSP問題是一個(gè)組合優(yōu)化問題。假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路經(jīng)的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。 模擬退火算法與初始值無關(guān)，算法求得的解與初始解狀態(tài)S(是算法迭代的起點(diǎn))無關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率l 收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性?？稍诖嘶A(chǔ)上開始下一輪試驗(yàn)。 第四步是當(dāng)新解被確定接受時(shí)，用新解代替當(dāng)前解，這只需將當(dāng)前解中對應(yīng)于產(chǎn)生新解時(shí)的變換部分予以實(shí)現(xiàn)，同時(shí)修正目標(biāo)函數(shù)值即可。事實(shí)表明，對大多數(shù)應(yīng)用而言，這是計(jì)算目標(biāo)函數(shù)差的最快方法。第二步是計(jì)算與新解所對應(yīng)的目標(biāo)函數(shù)差。 (7) T逐漸減少，且T0，然后轉(zhuǎn)第2步。(5) 若Δ t′0則接受S′作為新的當(dāng)前解，否則以概率exp(Δ t′/T)接受S′作為新的當(dāng)前解. 　　(6) 如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。　模擬退火的原理也和金屬退火的原理近似：將熱力學(xué)的理論套用到統(tǒng)計(jì)學(xué)上，將搜尋空間內(nèi)每一點(diǎn)想像成空氣內(nèi)的分子；分子的能量，就是它本身的動(dòng)能；而搜尋空間內(nèi)的每一點(diǎn)，也像空氣分子一樣帶有“能量”，以表示該點(diǎn)對命題的合適程度。 模擬退火的基本思想模擬退火是一種通用概率算法，用來在一個(gè)大的搜尋空間內(nèi)找尋命題的最優(yōu)解。模擬退火作為一種隨機(jī)算法，它的特點(diǎn)非常適于求解NP問題，比如著名的旅行商問題(Traveling Salesman Problem)。模擬退火算法主要應(yīng)用在各種優(yōu)化問題上，函數(shù)優(yōu)化是其中非常重要的一個(gè)方面。它的思想最早在1953年由Metropolis提出