【正文】 .................................................................................. 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ū)簽。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個(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)題 。旅行商 問(wèn)題是一個(gè)具有十分廣泛的 實(shí)用 背景 和 重要理論 價(jià)值 的組合優(yōu)化問(wèn)題 。特別 適合 于求解傳統(tǒng)的搜索算法不好 處理 的 復(fù)雜的 最優(yōu)解問(wèn)題 。 I 題目： 遺傳算法求解旅行商問(wèn)題的計(jì)算機(jī)仿真 II 遺傳 算法求解 TSP 問(wèn)題 的計(jì)算機(jī)仿真 摘要 由于 遺傳算法在整體搜索策略和優(yōu)化搜索方法 上 不依賴梯度信息或其他輔助 知識(shí) ， 只需要 影響搜索方向的目標(biāo)函數(shù)和相應(yīng)的適應(yīng)度函數(shù)， 所以提供了一種 求解復(fù)雜系統(tǒng) 問(wèn)題的通用框架 ，因此 遺傳算法廣泛應(yīng)用于數(shù)學(xué)問(wèn)題、組合優(yōu)化、機(jī)械設(shè)計(jì)、 人工 智能等領(lǐng)域。 遺傳 算法（ Geic Algorithms,簡(jiǎn)稱 GA） 是模擬 自然界生物 自然 選擇和進(jìn)化 的 機(jī)制而發(fā)展起來(lái)的一種高度并行、 自適應(yīng)的 隨機(jī) 搜索 算法。旅行商 問(wèn)題（ Traveling Salesman Problem） 就是 要決定一條經(jīng)過(guò) 路線中 所 有城市當(dāng) 且僅當(dāng)一次且距離最短的路線，即距離最短的 Hamilton 回路 。目前求解TSP 問(wèn)題的主要方法有模擬退火算法、遺傳算法、 Hopfield 神經(jīng)網(wǎng)絡(luò)算法、啟發(fā)式搜索法、二叉樹(shù)描述算法。 關(guān)鍵字：旅行商 問(wèn)題 ； 遺傳算法 ； 變異 算法；編碼 方式 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