【正文】 ................ 17 V 系統(tǒng)詳細設計 ....................................................................................................................... 17 演示模塊設計 ...................................................................................................................... 18 幫助模塊設計 ...................................................................................................................... 21 測試結果及分析 ................................................................................................................. 22 測試一 ................................................................................................................................. 22 測試二 ................................................................................................................................. 24 測試三 ................................................................................................................................. 26 測試四 ................................................................................................................................. 28 測試五 ................................................................................................................................. 29 5 結論 ....................................................................................................................................... 31 參考文獻 .................................................................................................................................... 32 謝 辭 ............................................................................................................ 錯誤 !未定義書簽。 附錄一程序 ................................................................................................................................ 33 附錄二外文翻譯 ......................................................................................... 錯誤 !未定義書簽。 1 1 緒論 自 20 世紀 60 年代以來 ,一種模擬生物自然遺傳與進化過程并將生物進化原理、最優(yōu)化技術和 計算機技術結合起來的優(yōu)化方法 —遺傳算法 （ Geic Algorithm,簡稱 GA） 被 提出并得到 廣泛 研究， 該 算法 特別適 用于處理傳統(tǒng)搜索方法難以解決的復雜和非線性 問題 ，可以廣泛 應 用于人工智能、 機械 設計 、自適應控制等領域。遺傳算法固有的并行性和 并行 計算的能力 ，使 在搜索過程中不容易陷入局部最優(yōu) 。 即使在所定義的適應度函數(shù) 中 是不連續(xù)的、不規(guī)則 的 情況下，也可以很大概率 找到 全局最優(yōu)解 。 采用 自然進化機制來表現(xiàn)復雜的現(xiàn)象，能夠 快速 可靠地解決求解非常困難的問題 ， 非常 適 用于本課題 涉及 的 TSP 問題的求解與 研究。 旅行商 問題 （ Traveling Salesman Problem ,TSP） 是一個 非常經(jīng)典的組合優(yōu)化問題的 NP難題 ， 長期 以來 都沒有 一個十分有效的算法來解決它，但 TSP 本身 在許多領域有著重要的應用，如 連鎖店 的貨物配送路線、計算機網(wǎng)絡路由器遍歷、印刷電路板的鉆孔路線等問題都可以 建模為旅行商問題。 TSP 問題其實是“ 哈密頓回路問題 ”中的“哈密頓最短 回路問題 ”。在 本系統(tǒng)就是要 應用遺傳算法 求解 45 個 城市的 TSP 問題 。 因為 遺傳算法本 身 是模擬生物自然選擇 和遺傳的 過程的， 所以 用遺傳算法求解 TSP 最先要 確定 的 是問題的建模 ， 即如何用 遺傳學的 算子來表示旅行商問題中的變量 。必 需要 非常的了解 ，并 熟悉 每一個 遺傳學 中的 術語 在遺傳學中的具體作用， 然后 應用 到 求解具體問題當中來。 應用 遺傳算法求解旅行商問題最關鍵的 是 編碼方式、交叉、選擇、變異算子的設計， 直接 關系到算法 能否求出 最優(yōu)解 或 近似最優(yōu)解 。 所以 要在 編碼方式的確定上做好足夠的 功夫 ， 以 確定 程序 求解的精確度。 本章 主要 論述 本文所研究的主要內(nèi)容，并對論文 的 章節(jié)結構進行規(guī)劃。 研究 背景 旅行商問題（ Traveling Salesman Problem, TSP） ,也稱旅行推銷員 問題 ，具體的數(shù)學模型可以這樣理解：現(xiàn)在 給定 以下 幾個城市的位置 ，旅行商從 其中 的 某一個城市出發(fā)，不重復地訪問其余的每一個城市，最后又返回到原出發(fā)點城市，要求找出 這樣 一條路線，使旅行所付出的代價最小。雖然它是一個比較古老的問題，最早可以追溯到 Euler 提出的騎士旅行問題，但同時它也是一個新的問題，因為它的計算復雜度 較高， 雖然人們一直在嘗試用新的方法來改進求解該問題的復雜度，但是 這一類問題 距今 都沒有能找到一個有效的算法來解決 。 2 TSP 問題可以形式化描述為：設 G=（ V,A,D）是一個圖，其中 V 是 n 個頂點的集合，A 是弧線或邊集 ,D=（ ??????）是 與 A 關聯(lián) 的距離或費用矩陣。 旅行商 問題就是要解決 一個 最小回路問題，回路中所有頂點有且僅經(jīng)過一次 。對于 具有一個城市的旅行商問題，其可能的路徑 數(shù)目 為（ n1） ！ /2， 5 個 城市 的問題 模型就對應 120/10=12 條 路線， 10 個 城市的問題模型對應 3628800/20=181440 條 路線。所以 當 輸入越大，則 耗費的 時間就是個天文數(shù)字了，因此 旅行商問題至今都沒有 能 找到 一種 有效的求解方法。 尋求 一種 能 短時間求 解 出高精度解 的算法，已成為此問題研究的熱門。 盡管 旅行商問題 至今 仍然沒有找 到 最優(yōu)解， 但 求解它 的算法已經(jīng)在不斷的改進。 目前，求解 TSP問題常用的算法主要有遺傳算法和蟻群 算法，另外 還 有 爬山 法、模擬 退火 算法 、 神經(jīng)網(wǎng)絡方法、貪婪算法、禁忌搜索算法等。 1980Crowder和 Padberg 求解 了 318 個 城市的 TSP 問題； 1987 年 Padberg 和 Rinaldi 成功 將城市數(shù)量增加到了 2392 個 ； 最大的 成功求解的旅行 商問題 已經(jīng) 增加 到 24798 個 城市。 意義 首先旅行商 問題是 用于 求解 N 個 城市 存在（ N1） 條 閉合路徑的排列方案， 對于 這一類 問題 很難用全局搜索法精確地求出最優(yōu)解， 這一問題 已經(jīng)困擾眾多 學者 許多年，因此研究相應的算法尋找其最優(yōu)或近似最優(yōu)解是非常必要的。 其次 ， 隨著旅游業(yè)的快速發(fā)展，大量的旅客在旅途中浪費了不必要的時間和金錢，而這些不必要的浪費完全可以通過對旅行路線的合理規(guī)劃來避免。而在互聯(lián)網(wǎng)繼續(xù)擴大普及的時代，電子商務也迎來了期待已久的春天，同時物流產(chǎn)業(yè)也隨之水漲船高。毫無疑問，高效、低成本、低能耗成了各個物流企業(yè)追求的目標，更加合理的配送路線能明顯地為物流公司增大利潤 。再比如 在裝配線 的 流程中，對每個工件為完成裝配過程節(jié)約的少許時間意味著一天的產(chǎn)量的相應增加。由于 旅行商 問題在計算機網(wǎng)絡、物流、旅游業(yè)、交通運輸?shù)仍S多領域都有著十分廣泛的應用 ，因此尋找一個 求解這類問 題的求解方法 有 很 高的 應用價值 因此 ，對旅行商問題有效算法的研究不僅具有重要的理論意義，而且具有重大的實際應用價值 。 內(nèi)容 本文 采用遺傳算法求解 45 個 城市的旅行商問題，并對其實現(xiàn)計算機仿真。 遺傳算法（ Geic Algorithms,GA） 又叫 基因進化算法或進化算法 ，是 一種通過模擬自然界生物 適者生存 、優(yōu)勝劣 汰的 進化過程而形成的一種自適應、具有全局優(yōu)化能力的隨機搜索算法。應用 遺傳算法 求解 旅行商問題，最難得地方在于問題 建 模 ， 如 城市 編碼方式以及 交叉 、 變異 、 選擇算子的確定等。 本文 采用的 是 Grefenstette 等提出 的 一種 新的 巡回路線編碼方法 ，其 可以在一定程度上克服 常規(guī)巡回路線編碼方法 在 交 異操作時易 產(chǎn)生 不滿足問題約束條件或無實際意義的巡回路線 的 缺點 。交叉算法 采用的是常規(guī)的單點交叉， 之所以 可以用這一常規(guī)的交叉法，是因為在編碼方式上使用的是 Grefenstette 等提出 的 一種 新的 巡回路線編碼方法 ，它 可以最大化交叉后后代 與 其 父 代的性狀 差異 ，有利于算法的全局性。 變異 算法采用的是基本位變異 3 法 ， 即 只是 根據(jù) 變異概率隨機改變?nèi)旧w中的某一 段 染色體， 具體會在后 文 中做詳細說明 。在遺傳算法中，以個體適應度的大小來確定該個體被遺傳到下一代群體中的概率。本課題中以每條路徑長度的倒數(shù)作為適應度函數(shù)值 。 在 求出 之后 將其按照 從大 到小的順序排列，以便于 后面找出 路徑 之 和最小的城市序列 。 本文 的結構 本文 一共分為 5 章 ， 結構 如下： 第一章緒論 。這一章主要論述旅行商問題的基本概念，以及 本課題 主要的研究方法 及其 研究意義，并對論文的章節(jié)結構 加以 論述。 第二章遺傳算法理論 概述 。 這一章 主要 論述遺傳算法的 起源 發(fā) 展 及其實際應用 ，重點介紹了遺傳算法的 算法原理 及 步驟 。 第三 章 基于遺傳 算法求解 TSP 問題。 本章 主要介紹了 本系統(tǒng) 具體使用什么方式實現(xiàn)求解過程， 包括 編碼方式、選擇、交叉、變異算子的具體選取 。 第四 章 45 個城市旅行商問題 的仿真軟件的 設計。 本章 主要 對系統(tǒng)模塊 進行 了介紹，而且 對 應用 系統(tǒng)進行了多組試算，最后得出結論。 第五 章結論 。對本文的內(nèi)容進行總結。 4 2 遺傳算法 理論 概述 遺傳 算法的 產(chǎn)生 及發(fā)展 最早由美國 Michigan(密執(zhí)安大學 )的 Hollang 教授提出，起源于 60 年代對自然和人工自適應系統(tǒng)的研究。 1967 年 ，他的學生 Bagley 提出 “遺傳 算法 ”一詞 ，并發(fā)展了復制、交叉 、 變異、顯性、倒位 等 遺傳算子。 70 年代 De Jong 基于遺傳算法的思想在計算機上進行了大量純數(shù)值函數(shù)優(yōu)化計算實驗 ， 建立了著名的 五 函數(shù)測試平臺。 在一系列研究工作的基礎上 80 年代 Goldberg進行總結歸納， 形成了 遺傳算法的基本框架 ； Smith將 遺傳算法應用于機械學習領域； Bethke 對 函數(shù)優(yōu)化的遺傳算法進行了系統(tǒng)的研究。進入90 年代 ，遺傳算法進入了興盛期，無論是理論研究 還 是實際應用都成了十分熱門的課題。如今 遺傳 算法已經(jīng)被廣泛的應用于 計算機科學 、 人工智能、機械設計、圖像處理等各個領域，不僅如此，利用遺傳算法進行理論研究的優(yōu)化和最優(yōu)解問題的解決能力也顯著提高。 下面 是一些在遺傳算法發(fā)展 進程 中做出 杰出 貢獻的 人物 ： 1 60 年代提出在研究和設計人工自適應系統(tǒng)時 ,可以借鑒生物遺傳的機制； 70 年代初提出了遺傳算法的基本定理－模式定理 (Schema Theorem)，從而奠定了遺傳算法的理論基礎； 80 年代實現(xiàn)了第一個基于遺傳算法的機器學系統(tǒng)－分類器系統(tǒng) (Classifier Sy