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