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