【正文】 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ī) 搜索 算法。特別 適合 于求解傳統(tǒng)的搜索算法 不好 處理 的 復(fù)雜的 最優(yōu)解問(wèn)題 。旅行商 問(wèn)題（ Traveling Salesman Problem） 就是 要決定一條經(jīng)過(guò) 路線中 所 有城市當(dāng) 且僅當(dāng)一次且距離最短的路線，即距離最短的 Hamilton 回路 。旅行商 問(wèn)題是一個(gè)具有十分廣泛的 實(shí)用 背景 和 重要理論 價(jià)值 的組合優(yōu)化問(wèn)題 。目前求解TSP 問(wèn)題的主要方法有模擬退火算法、遺傳算法、 Hopfield 神經(jīng)網(wǎng)絡(luò)算法、啟發(fā)式搜索法、二叉樹描述算法。 本文 選 用遺傳算法 求解 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)題 。 關(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 direction of the objective function and the corresponding fitness function, and so provides a generic framework for solving plicated system problem, so the geic algorithm is widely used in mathematical problem, binatorial optimization, mechanical design, artificial intelligence, etc Geic algorithm (based Algorithms, the GA) is mimic natural biological natural selection and evolution mechanism and developed a kind of highly parallel, adaptive random search algorithm. Particularly suitable for solving the traditional search algorithm is not good to deal with plex optimal solution of problem. Traveling Salesman Problem (39。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。 MUTATION ALGORITHM。 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ì)模塊 .......................................................................................................