【正文】 題 ”。遺傳算法固有的并行性和 并行 計算的能力 ，使 在搜索過程中不容易陷入局部最優(yōu) 。 MUTATION ALGORITHM。目前求解TSP 問題的主要方法有模擬退火算法、遺傳算法、 Hopfield 神經(jīng)網(wǎng)絡(luò)算法、啟發(fā)式搜索法、二叉樹描述算法。 遺傳 算法（ Geic Algorithms,簡稱 GA） 是模擬 自然界生物 自然 選擇和進化 的 機制而發(fā)展起來的一種高度并行、 自適應(yīng)的 隨機 搜索 算法。特別 適合 于求解傳統(tǒng)的搜索算法不好 處理 的 復(fù)雜的 最優(yōu)解問題 。 本文 選 用遺傳算法 求解 45個 城市 的 TSP問題，基于 Microsoft Visual C++環(huán)境 ,采用 Grefenstette 等提出 的 一種 新的 巡回路線編碼方法 ，變異 算 子 采用了常規(guī)的 基本位變異 法 ， 通過 多 組實驗和數(shù)據(jù) 近似的 求解 出了 45 個 城市的最優(yōu)解， 實現(xiàn) 了計算機仿真求解 TSP 問題 。 IV 目錄 遺傳算法求解 TSP 問題的計算機仿真 .............................................................................. II Abstract...................................................................................................................................... III 1 緒論 ......................................................................................................................................... 1 研究背景 ................................................................................................................................. 1 研究意義 ................................................................................................................................. 2 研究內(nèi)容 ................................................................................................................................. 2 本文的結(jié)構(gòu) ............................................................................................................................. 3 2 遺傳算法理論概述 ............................................................................................................. 4 遺傳算法的產(chǎn)生及發(fā)展 ......................................................................................................... 4 遺傳算法基本原理 ................................................................................................................. 5 遺傳算法基本步驟 ................................................................................................................. 6 遺傳算法算法流程圖 ............................................................................................................. 6 遺傳算法的特點 ..................................................................................................................... 7 遺傳算法的應(yīng)用 ..................................................................................................................... 7 3 基于遺傳算法求解 TSP 問題 ........................................................................................ 9 旅行商問題的描述與建模 ...................................................................................................... 9 編碼方式 .................................................................................................................................. 9 遺傳算子的設(shè)計（交叉、選擇、變異） ............................................................................ 12 交叉算子 ............................................................................................................................. 12 選擇算子 ............................................................................................................................. 13 變異算子 ............................................................................................................................. 14 適應(yīng)度函數(shù) ........................................................................................................................... 15 遺傳算法求解 TSP 問題的具體流程圖 ............................................................................... 15 4 45 個 城市旅行商問題的仿真軟件的設(shè)計 ............................................................... 17 系統(tǒng)設(shè)計模塊 ....................................................................................................................... 17 V 系統(tǒng)詳細設(shè)計 ....................................................................................................................... 17 演示模塊設(shè)計 ...................................................................................................................... 18 幫助模塊設(shè)計 ...................................................................................................................... 21 測試結(jié)果及分析 ................................................................................................................. 22 測試一 ................................................................................................................................. 22 測試二 ................................................................................................................................. 24 測試三 ................................................................................................................................. 26 測試四 ................................................................................................................................. 28 測試五 ................................................................................................................................. 29 5 結(jié)論 ....................................................................................................................................... 31 參考文獻 .................................................................................................................................... 32 謝 辭 ............................................................................................................ 錯誤 !未定義書簽。 即使在所定義的適應(yīng)度函數(shù) 中 是不連續(xù)的、不規(guī)則 的 情況下，也可以很大概率 找到 全局最優(yōu)解 。在 本系統(tǒng)就是要 應(yīng)用遺傳算法 求解 45 個 城市的 TSP 問題 。 所以 要在 編碼方式的確定上做好足夠的 功夫 ， 以 確定 程序 求解的精確度。 2 TSP 問題可以形式化描述為：設(shè) G=（ V,A,D）是一個圖，其中 V 是 n 個頂點的集合，A 是弧線或邊集 ,D=（ ??????）是 與 A 關(guān)聯(lián) 的距離或費用矩陣。 尋求 一種 能 短時間求 解 出高精度解 的算法，已成為此問題研究的熱門。 意義 首先旅行商 問題是 用于 求解 N 個 城市 存在（ N1） 條 閉合路徑的排列方案， 對于 這一類 問題 很難用全局搜索法精確地求出最優(yōu)解， 這一問題 已經(jīng)困擾眾多 學者 許多年，因此研究相應(yīng)的算法尋找其最優(yōu)或近似最優(yōu)解是非常必要的。再比如 在裝配線 的 流程中，對每個工件為完成裝配過程節(jié)約的少許時間意味著一天的產(chǎn)量的相應(yīng)增加。應(yīng)用 遺傳算法 求解 旅行商問題，最難得地方在于問題 建 模 ， 如 城市 編碼方式以及 交叉 、 變異 、 選擇算子的確定等。在遺傳算法中，以個體適應(yīng)度的大小來確定該個體被遺傳到下一代群體中的概率。這一章主要論述旅行商問題的基本概念，以及 本課題 主要的研究方法 及其 研究意義，并對論文的章節(jié)結(jié)構(gòu) 加以 論述。 本章 主要介紹了 本系統(tǒng) 具體使用什么方式實現(xiàn)求解過程， 包括 編碼方式、選擇、交