【正文】 .................................................................................. 4 遺傳算法的產(chǎn)生及發(fā)展 ......................................................................................................... 4 遺傳算法基本原理 ................................................................................................................. 5 遺傳算法基本步驟 ................................................................................................................. 6 遺傳算法算法流程圖 ............................................................................................................. 6 遺傳算法的特點 ..................................................................................................................... 7 遺傳算法的應用 ..................................................................................................................... 7 3 基于遺傳算法求解 TSP 問題 ........................................................................................ 9 旅行商問題的描述與建模 ...................................................................................................... 9 編碼方式 .................................................................................................................................. 9 遺傳算子的設計（交叉、選擇、變異） ............................................................................ 12 交叉算子 ............................................................................................................................. 12 選擇算子 ............................................................................................................................. 13 變異算子 ............................................................................................................................. 14 適應度函數(shù) ........................................................................................................................... 15 遺傳算法求解 TSP 問題的具體流程圖 ............................................................................... 15 4 45 個 城市旅行商問題的仿真軟件的設計 ............................................................... 17 系統(tǒng)設計模塊 ....................................................................................................................... 17 V 系統(tǒng)詳細設計 ....................................................................................................................... 17 演示模塊設計 ...................................................................................................................... 18 幫助模塊設計 ...................................................................................................................... 21 測試結(jié)果及分析 ................................................................................................................. 22 測試一 ................................................................................................................................. 22 測試二 ................................................................................................................................. 24 測試三 ................................................................................................................................. 26 測試四 ................................................................................................................................. 28 測試五 ................................................................................................................................. 29 5 結(jié)論 ....................................................................................................................................... 31 參考文獻 .................................................................................................................................... 32 謝 辭 ............................................................................................................ 錯誤 !未定義書簽。ll Salesman Problem) is to determine a through route if and only if all cities in time and distance is the shortest route, the shortest distance of Hamilton loop. Traveling salesman problem is a very wide range of practical background and important theoretical value of the binatorial optimization problem. At present the main method of solving TSP problem with simulated annealing algorithm, geic algorithm and Hopfield neural work algorithm, the heuristic search method, the binary tree described algorithm. This article chooses 45 cities geic algorithm to solve the TSP problem, based on Microsoft Visual c + + environment, use the proposed a new tour routes such as Grefenstette coding method, mutation operator adopted conventional basic variation method, through multiple sets of experimental data and the approximate solution of the 45 cities the optimal solution, has realized the puter simulation to solve the TSP problem. KEY WORDS: TRAVELING SALESMAN PROBLEM. GENETIC ALGORITHM。 本文 選 用遺傳算法 求解 45個 城市 的 TSP問題，基于 Microsoft Visual C++環(huán)境 ,采用 Grefenstette 等提出 的 一種 新的 巡回路線編碼方法 ，變異 算 子 采用了常規(guī)的 基本位變異 法 ， 通過 多 組實驗和數(shù)據(jù) 近似的 求解 出了 45 個 城市的最優(yōu)解， 實現(xiàn) 了計算機仿真求解 TSP 問題 。旅行商 問題是一個具有十分廣泛的 實用 背景 和 重要理論 價值 的組合優(yōu)化問題 。特別 適合 于求解傳統(tǒng)的搜索算法不好 處理 的 復雜的 最優(yōu)解問題 。 I 題目： 遺傳算法求解旅行商問題的計算機仿真 II 遺傳 算法求解 TSP 問題 的計算機仿真 摘要 由于 遺傳算法在整體搜索策略和優(yōu)化搜索方法 上 不依賴梯度信息或其他輔助 知識 ， 只需要 影響搜索方向的目標函數(shù)和相應的適應度函數(shù)， 所以提供了一種 求解復雜系統(tǒng) 問題的通用框架 ，因此 遺傳算法廣泛應用于數(shù)學問題、組合優(yōu)化、機械設計、 人工 智能等領域。 遺傳 算法（ Geic Algorithms,簡稱 GA） 是模擬 自然界生物 自然 選擇和進化 的 機制而發(fā)展起來的一種高度并行、 自適應的 隨機 搜索 算法。旅行商 問題（ Traveling Salesman Problem） 就是 要決定一條經(jīng)過 路線中 所 有城市當 且僅當一次且距離最短的路線，即距離最短的 Hamilton 回路 。目前求解TSP 問題的主要方法有模擬退火算法、遺傳算法、 Hopfield 神經(jīng)網(wǎng)絡算法、啟發(fā)式搜索法、二叉樹描述算法。 關鍵字：旅行商 問題 ； 遺傳算法 ； 變異 算法；編碼 方式 III The puter simulation of geic algorithm to solve TSP problem Abstract Due to geic algorithm on the overall search strategy and optimization search method does not depend on the gradient information or other auxiliary knowledge, only need to influence the search dire