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