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