【文章內容簡介】 法研究反饋人工神經網絡的穩(wěn)定性，并利用此方法建立求解優(yōu)化計算問題的系統(tǒng)方程式?；镜腍opfield神經網絡是一個由非線性元件構成的全連接型單層反饋系統(tǒng)。網絡中的每一個神經元都將自己的輸出通過連接權傳送給所有其它神經元，同時又都接收所有其它神經元傳遞過來的信息。即：網絡中的神經元t時刻的輸出狀態(tài)實際上間接地與自己的t1時刻的輸出狀態(tài)有關。所以Hopfield神經網絡是一個反饋型的網絡。其狀態(tài)變化可以用差分方程來表征。反饋型網絡的一個重要特點就是它具有穩(wěn)定狀態(tài)。當網絡達到穩(wěn)定狀態(tài)的時候，也就是它的能量函數(shù)達到最小的時候。這里的能量函數(shù)不是物理意義上的能量函數(shù)，而是在表達形式上與物理意義上的能量概念一致，表征網絡狀態(tài)的變化趨勢，并可以依據Hopfield工作運行規(guī)則不斷進行狀態(tài)變化，最終能夠達到的某個極小值的目標函數(shù)。網絡收斂就是指能量函數(shù)達到極小值[9]。如果把一個最優(yōu)化問題的目標函數(shù)轉換成網絡的能量函數(shù)，把問題的變量對應于網絡的狀態(tài)，那么Hopfield神經網絡就能夠用于解決優(yōu)化組合問題。3．遺傳算法遺傳算法（GeneticAlgorithms）是基于生物進化理論的原理發(fā)展起來的一種廣為應用的、高效的隨機搜索與優(yōu)化的方法。其主要特點是群體搜索策略和群體中個體之間的信息交換，搜索不依賴于梯度信息。它是在70年代初期由美國密執(zhí)根（Michigan）大學的霍蘭（Holland）教授發(fā)展起來的。1975年霍蘭教授發(fā)表了第一本比較系統(tǒng)論述遺傳算法的專著《自然系統(tǒng)與人工系統(tǒng)中的適應性》（《AdaptationinNaturalandArtificialSystems》）。遺傳算法最初被研究的出發(fā)點不是為專門解決最優(yōu)化問題而設計的，它與進化策略、進化規(guī)劃共同構成了進化算法的主要框架，都是為當時人工智能的發(fā)展服務的。迄今為止，遺傳算法是進化算法中最廣為人知的算法。近幾年來，遺傳算法主要在復雜優(yōu)化問題求解和工業(yè)工程領域應用方面，取得了一些令人信服的結果，所以引起了很多人的關注。在發(fā)展過程中，進化策略、進化規(guī)劃和遺傳算法之間差異越來越小。遺傳算法成功的應用包括：作業(yè)調度與排序、可靠性設計、車輛路徑選擇與調度、成組技術、設備布置與分配、交通問題等等。4．粒子群優(yōu)化算法粒子群優(yōu)化算法(PSO)是一種進化計算技術(EvolutionaryComputation)，有Eberhart博士和Kennedy博士發(fā)明。源于對鳥群捕食的行為研究。PSO同遺傳算法類似，是一種基于疊代的優(yōu)化工具。系統(tǒng)初始化為一組隨機解，通過疊代搜尋最優(yōu)值。但是并沒有遺傳算法用的交叉(crossover)以及變異(mutation)。而是粒子在解空間追隨最優(yōu)的粒子進行搜索。同遺傳算法比較，PSO的優(yōu)勢在于簡單容易實現(xiàn)并且沒有許多參數(shù)需要調整。目前已廣泛應用于函數(shù)優(yōu)化，神經網絡訓練，模糊系統(tǒng)控制以及其他遺傳算法的應用領域。粒子群優(yōu)化算法(PSO)也是起源對簡單社會系統(tǒng)的模擬，最初設想是模擬鳥群覓食的過程，但后來發(fā)現(xiàn)PSO是一種很好的優(yōu)化工具。目前的智能計算研究水平暫時還很難使“智能機器”真正具備人類的常識，但智能計算將在21世紀蓬勃發(fā)展。不僅僅只是功能模仿要持有信息機理一致的觀點。即人工腦與生物腦將不只是功能模仿，而是具有相同的特性。這兩者的結合將開辟一個全新的領域，開辟很多新的研究方向。智能計算將探索智能的新概念，新理論，新方法和新技術，而這一切將在以后的發(fā)展中取得重大成就。模擬退火算法在TSP問題中的應用研究 第三章 問題描述與算法分析研究第三章 問題描述與算法分析研究本章介紹了模擬退火算法解決TSP問題的需求分析階段的內容，是本次程序設計中的關鍵環(huán)節(jié)。主要對系統(tǒng)進行了整體的分析，明確了系統(tǒng)目標，確定了開發(fā)環(huán)境，構建了基本的框架結構和功能模塊。并且確定了模擬退火算法在TSP問題中的應用研究的主要設計思想。通過對程序的理解和分析，這個課題項目應該分為2個階段進行。第一階段是模擬退火算法的描述和實現(xiàn)；第二階段是在TSP問題中應用模擬退火算法解決問題，即模擬退火算法在TSP問題中的具體實現(xiàn)。完成一個完整并且優(yōu)秀的程序，為其配置一個良好的系統(tǒng)開發(fā)環(huán)境是十分必要的，接下來是介紹模擬退火算法解決TSP問題所需要配置的環(huán)境要求。接下來為開發(fā)語言和系統(tǒng)運行平臺做下簡介。開發(fā)語言必須是一種優(yōu)秀的面向對象程序設計語言并且適合于系統(tǒng)程序設計。C++語言是一種優(yōu)秀的面向對象程序設計語言，它在C語言的基礎上發(fā)展而來C++以其獨特的語言機制在計算機科學的各個領域中得到了廣泛的應用。面向對象的設計思想是在原來結構化程序設計方法基礎上的一個質的飛躍，C++完美地體現(xiàn)了面向對象的各種特性。因此采用c++語言進行編寫程序。本課題開發(fā)語言選用c++語言，可以選用的開發(fā)平臺可以從c++語言平臺中選擇一種出來，本課題選用visual C++。 TSP問題的描述和分析旅行商問題，即TSP問題（Travelling Salesman Problem）是數(shù)學領域中著名問題之一。假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路經的限制是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。 TSP問題的示意圖。TSP問題的目的就是選擇出路徑路程為所有路徑之中的最小值的路徑。目前人們已經構造出了許多近似求解法，如遺傳法、蟻群算法、模擬退火算法等[10]。下面介紹并且分析模擬退火算法的模型和組合優(yōu)化的問題。模擬退火算法起源于物理退火。物理退火過程： （1） 加溫過程 （2） 等溫過程 （3） 冷卻過程模擬退火算法可以分解為解空間、目標函數(shù)和初始解三部分。模擬退火的基本思想:(1) 初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點)， 每 個T值的迭代次數(shù)L。 (2) 對k=1，……，L做第(3)至第6步： (3) 產生新解S′ (4) 計算增量Δt′=C(S′)C(S)，其中C(S)為評價函數(shù) (5) 若Δt′0則接受S′作為新的當前解，否則以概率exp(Δt′/T)接受S′作為新 的當前解 (6) 如果滿足終止條件則輸出當前解作為最優(yōu)解，結束程序。終止條件通常 取為連續(xù)若干個新解都沒有被接受時終止算法。 (7) T逐漸減少，且T0，然后轉第2步。模擬退火算法用于優(yōu)化問題的出發(fā)點是基于物理中固體物質的退火過程與一般優(yōu)化問題的相似性[11]。模擬退火算法用于優(yōu)化問題的出發(fā)點是基于物理中固體物質的退火過程與一般優(yōu)化問題的相似性。算法的基本思想是從一給定解開始的，從鄰域中隨機產生另一個解，接受準則允許目標函數(shù)在有限范圍內變壞。它由一控制參數(shù)t決定，其作用類似于物理過程中的溫度T，對于控制參數(shù)t的每一取值，算法持續(xù)進行“產生新解——判斷——接受或舍棄”的迭代過程，對應著固體在某一恒定溫度下趨于熱平衡的過程。經過大量的解變換后，可以求得給定控制參數(shù)t值時優(yōu)化問題的相對最優(yōu)解。然后減小控制參數(shù)t的值，重復執(zhí)行上述迭代過程。當控制參數(shù)逐漸減小并趨于零時，系統(tǒng)亦越來越趨于平衡狀態(tài)，最后系統(tǒng)狀態(tài)對應于優(yōu)化問題的整體最優(yōu)解。根據該課題要求，研究模擬退化算法的基本原理以及TSP組合優(yōu)化問題，用一種程序語言實現(xiàn)基于模擬退火算法的TSP問題求解方法。，問題的目標是選擇出路徑路程為所有路徑之中的最小值的路徑。通過C++語言編寫并且實現(xiàn)出模擬退火算法。在利用編寫出的模擬退火算法模型去解決之前所建立的TSP問題模型。模擬退火算法在TSP問題中的應用研究 第四章 算法具體設計與編碼實現(xiàn)第四章 算法具體設計與編碼實現(xiàn)前面的章節(jié)主要介紹了問題描述與算法分析研究的內容，而本章主要是對該系統(tǒng)的具體實現(xiàn)進行了詳細設計。描繪出模擬退火算法的流程圖，了解該算法的運行機制，明確算法在系統(tǒng)整體設計中的具體功能和應用，并且對應用模擬退火算法求解TSP問題做個詳細的劃分和描述。具體分為基于模擬退火算法求解TSP問題詳細設計和求解TSP問題的算法主體模塊詳細設計。第三章提供了模擬退火算法的大體框架和組合優(yōu)化要注意的問題，這節(jié)將了解模擬退火算法的具體流程圖和算法模型描述以及模擬退火算法的參數(shù)控制問題模擬退火算法的應用很廣泛，可以求解NP完全問題，但其參數(shù)難以控制，其主要問題有以下三點溫度T的初始值設置問題，退火速度問題，溫度管理問題。并且這部分包括一些關鍵代碼。模擬退火算法是解決TSP問題的有效方法之一，其最初的思想由Metropolis在1953年提出，Kirkpatrick在1983年成功地將其應用在組合最優(yōu)化問題中。模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變?yōu)闊o序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內能減為最小。用固體退火模擬組合優(yōu)化問題，將內能E模擬為目標函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當前解重復“產生新解→計算目標函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。求解TSP的模擬退火算法模型可描述如下:解空間：解空間S是遍訪每個城市恰好一次的所有路經，解可以表示為{w1,w2 ,……, wn}，w1, ……, wn是1,2,……,n的一個排列，表明w1城市出發(fā)，依次經過w2, ……, wn城市，再返回w1城市。初始解可選為(1,……, n) 。目標函數(shù)：目標函數(shù)為訪問所有城市的路徑總長度。我們要求的最優(yōu)路徑為目標函數(shù)為最小值時對應的路徑。新路徑的產生：隨機產生1和n之間的兩相異數(shù)k和m，不妨假設km，則將原路徑(w1,w2,…,wk,wk+1,…,wm,wm+1,…,wn)變?yōu)樾侣窂剑?w1,w2,…,wm,wk+1,…,wk,wm+1,…,wn)上述變換方法就是將k和m對應的兩個城市在路徑序列中交換位置,稱為2opt映射。 根據上述描述。 YYYYNNNN選擇初始路徑X0確定初