【正文】 率。oldpop[0])。 //變異父代基因 parent=RandomInt(0,m_nGroupSize1) （ 定義 變異范圍 ） nPos1=RandomInt(3,MAXCHROM3)。 變異是單個個體內部發(fā)生變化，導致產生新個體， 從而產生出一條新的巡回路線。 對于二進制編碼符號串所表示的個體，若需要進行變異操作的某一基 因座上的原有基因值為 0，則將其變?yōu)?1；反之，若原有基因值為 1，則將其變?yōu)?0 。交叉運算可以和變異運算相互配合，共同完成對搜索空間的全局搜索和局部搜索。i++) newpop[i].CopyNode(amp。 UpdateWindow()。oldpop[0])。oldpop[maxpos])。jm_nGroupSize。im_nGroupSize1。 // 歸一化 F 值 for(i=0。genm_GANum。其基本思想是：各個個體被選中的概率與其適 應度大小成正比。pop2)。pop2, nPos)。 (amp。 //復制用于交叉的基因對 PopNode pop1。 if(parent1temp) parent1=temp。 int parent1=0。產生 下一代個體在使用 Grefenstette 等提出的 編碼方式 時 ， 染色體 編碼串 前面 的一 些 基因發(fā)生變化 時 ，會對后面的基因值 產生巨大 的影響 ，產生 的新的個體 與 上一代的性狀變化 就會 十分明顯，有利于整個算法 跳出 局部最優(yōu)解。 本 系統使用的是常規(guī)的 單點 交叉算子 。例如 ， 假設現在有這樣一個城市序列： W=(A,B,C,D,E,F,G,H,I,J) 有 如下兩條 巡回 路線 ： T1=(A,D,B,H,F,I,J,G,E,C) T2=(B,C,A,D,E,J,H,I,F,G) 則按本 系統所用的編碼方法 ， 這兩 條 巡回路線可以編碼為： G1 =(1,3,1,5,3,4,4,3,2,1) 12 G2 =(2,2,1,1,1,5,3,3,1,1) 這種 編碼方式的 優(yōu)點 在于任意的染色體都對應一條有實際意義的巡回路線， 因此 可以使用常規(guī)的交叉算子對它 進行 計算，有利于算法的實現。 使用遺傳算法第一件事情就是確定染色編碼方式，它根據不同的問題模型使用不同 的編碼方式，本系統 使用的是 Grefenstette 等提出 的 一種新的巡回路線編碼方法， 是 一種 整數編碼的方式 。在浮點數編 10 碼方法中，必須保證基因值在給定的區(qū)間限制范圍內，遺傳算法中所使用的交叉、變異等 11 遺傳算子也必須保證其運算結果所產生的新個體的基因值也在這個區(qū)間限制范圍內。 ： 對于一些多維、高精度要求的連續(xù)函數優(yōu)化問題，使用二進制編碼來表示個體時將會有一些不利之處。 ： 它由二進制符號 0 和 1 所組成的二值符號集。因為編碼方法將會影響到交叉算 子、變異算子等遺傳算子的運算方法，很大 的程度上決定了遺傳進化的效率。 它可以 大致 描述 為 這樣 ： 有一個旅行商人要拜訪 n 個城市，他必須要 經過所有的城市 ，而且每個城市只能拜訪一次，最后要回到原來出發(fā)的城市?；谶z傳算法的進化模型是研究人工生命現象的重要基礎理論。利用該工具對兩個飛機失事的真實數據庫進行了數據挖掘實驗，結果表明遺傳算法是進行數據挖掘的有效方法之一。 （ 5）數據 挖掘 數據挖掘是近幾年出現的數據庫技術，它能夠從大型數據庫中提取隱含的、先前未知的、有潛在應用價值的知識和規(guī)則。 在單件生產車間調度、流水線生產間調度、生產規(guī)劃、任務分配等方面遺傳算法都得到了有效的應用。 遺傳 算法 已經在求解 TSP 問題、 01 背包 問題、 圖形 劃分問題等方面得到了成功的應用。 尤其是 在數學領域，科學家 構造出了 許許多多復雜 的測試函數： 連續(xù) 函數、離散函數、凸函數、凹函數 、 單峰函數、多峰函數等等。 所以 ， 遺傳算法有很高的容錯能力 ，我 們 可以 利用 遺傳算法 解決復雜的 非 結構化問題。適應度 函數 不僅不受連續(xù)可微的約束，而且其定義域可以任意的設定 ， 故幾乎可處理任何問題 。傳統 優(yōu)化 算 法從單個初始值迭代求最優(yōu)解，容易 早熟 陷入局部最優(yōu)解。 遺傳 算法 與 傳統的 優(yōu)化 方法（ 枚舉 ，啟發(fā) 式 等） 相 比較，以生物進化為原型 ， 具有很多的 優(yōu)點 。 遺傳 算法 算法 流程圖 開始編碼初始化染色體種群計算每個染色體的適應度滿足終止條件根據適應度選擇交叉變異輸出最優(yōu)解是否 7 圖 24 遺傳 算法算法流程圖 遺傳 算法的特點 遺傳算法 屬于進化算法 （ Evolutionary Algorithms） 的 一種 ，它通過模仿自然界的選擇與 遺傳的原理來求出最優(yōu)解，遺傳算法 有 三個 最 基本的算子：選擇、交叉、變異。 步驟六 ： 變異 算子：變異 是根據 生物 遺傳 中基因突變的原理， 以 變異概率 對 群體中的某一些個體 的 某些 “位 ”執(zhí)行 變異。遺傳算法中起核心作用的就是交叉算子。遺傳算法 就是 以這個初始群體為起點開始迭代。 串 結構空間 對 應用 于遺傳學 中的基因 型 的 集合 。遺傳編碼可以看成是從表現型到遺傳子型的 映射。 5）適應度（ fitness） :度量某個物種對于生存環(huán)境的適應程度。 3）種群（ population） :染色體帶有特征的 個體的集合。（另外，值得注意的是遺傳算法不一定要找 “最高的山峰 ”，如果問題的適應度評價越小越好的話，那么全局最優(yōu)解就是函數的最小值，對應的，遺傳算法所要找的就是 “最深的谷底 ”） 。所以也可以把遺傳算法的過程看作是一個在多元函數里面求最優(yōu)解的過程。生存 下來的 染色體被稱為后代 （ offspring） 。 遺傳算法的 思路是通過從給定一個初始群體出發(fā)，利用選擇算子、交叉算子以及變異算子來模擬自然進化的三種原則，逐步改進種群，越來越逼近最優(yōu)解，以達到求解最優(yōu)化問題的目的。 4 1989 年出版了專著《搜索、優(yōu)化和機器學習中的遺傳算法 (Geic Algorithms in Search，Optimization and Machine Learning)》，系統總結了遺傳算法的主要研究成果，全面而完整的論述了遺傳算法的基本原理及其應用。如今 遺傳 算法已經被廣泛的應用于 計算機科學 、人工智能、機械設計、圖像處理等各個領域，不僅如此，利用遺傳算法進行理論研究的優(yōu)化和最優(yōu)解問題的解決能力也顯著提高。 1967 年 ，他的學生 Bagley 提出 “遺傳 算法 ”一詞 ，并發(fā)展了復制、交叉 、 變異、顯性、倒位 等 遺傳算子。 本章 主要 對系統模塊 進行 了介紹，而且 對 應用 系統進行了多組試算，最后得出結論。 這一章 主要 論述遺傳算法的 起源 發(fā) 展 及其實際應用 ，重點介紹了遺傳算法的 算法原理 及 步驟 。 在 求出 之后 將其按照 從大 到小的順序排列，以便于 后面找出 路徑 之 和最小的城市序列 。交叉算法 采用的是常規(guī)的單點交叉， 之所以 可以用這一常規(guī)的交叉法，是因為在編碼方式上使用的是 Grefenstette 等提出 的 一種 新的 巡回路線編碼方法 ，它 可以最大 3 化交叉后后代 與 其 父 代的性狀 差異 ，有利于算法的全局性。 內容 本文 采用遺傳算法求解 45 個 城市的旅行商問題，并對其實現計算機仿真。而在互聯網繼續(xù)擴大普及的時代，電子商務也迎來了期待已久的春天，同時物流產業(yè)也隨之水漲船高。 目前，求解 TSP 問題常用的算法主要有遺傳算法和蟻群 算法，另外 還 有 爬山 法、模擬 退火 算法 、 神經網絡方法、貪婪算 法、禁忌搜索算法等。對于 具有一個城市的旅行商問題，其可能的路徑 數目 為（ n1） ！ /2， 5 個 城市 的問題 模型就對應 120/10=12 條 路線， 10 個 城市的問題模型對應 3628800/20=181440 條 路線。 研究 背景 旅行商問題（ Traveling Salesman Problem, TSP） ,也稱旅行推銷員 問題 ，具體的數學模型可以這樣理解：現在 給定 以下 幾個城市的位置 ，旅行商從 其中 的 某一個城市出發(fā)，不重復地訪問其余的每一個城市，最后又返回到原出發(fā)點城 市，要求找出 這樣 一條路線，使旅行所付出的代價最小。必 需要 非常的了解 ，并 熟悉 每一個 遺傳學 中的 術語 在遺傳學中的具體作用， 然后 應用 到 求解具體 問題當中來。 旅行商 問題 （ Traveling Salesman Problem ,TSP） 是一個 非常經典的組合優(yōu)化問題的 NP難題 ， 長期 以來 都 沒有 一個十分有效的算法來解決它，但 TSP 本身 在許多領域有著重要的應用，如 連鎖店 的貨物配送路線、計算機網絡路由器遍歷、印刷電路板的鉆孔路線等問題都可以 建模為旅行商問題。 1 1 緒論 自 20 世紀 60 年代以來 ,一種模擬生物自然遺傳與進化過程并將生物進化原理、最優(yōu)化技術和 計算機技術結合起來的優(yōu)化方法 —遺傳算法 （ Geic Algorithm,簡稱 GA） 被 提出并得到 廣泛 研究， 該 算法 特別適 用于處理傳統搜索方法難以解決的復雜和非線性 問題 ，可以廣泛 應 用于人工智能、 機械 設計 、自適應控制等領域。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。旅行商 問題是一個具有十分廣泛的 實用 背景 和 重要理論 價值 的組合優(yōu)化問題 。 I 題目： 遺傳算法求解旅行商問題的計算機仿真 II 遺傳 算法求解 TSP 問題 的計算機仿真 摘要 由于 遺傳算法在整體搜索策略和優(yōu)化搜索方法 上 不依賴梯度信息或其他輔助 知識 ， 只需要 影響搜索方向的目標函數和相應的適應度函數， 所以提供了一種 求解復雜系統 問題的通用框架 ，因此 遺傳算法廣泛應用于數學問題、組合優(yōu)化、機械設計、 人工 智能等領域。旅行商 問題（ Traveling Salesman Problem） 就是 要決定一條經過 路線中 所 有城市當 且僅當一次且距離最短的路線，即距離最短的 Hamilton 回路 。 關鍵字：旅行商 問題 ； 遺傳算法 ； 變異 算法；編碼 方式 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 gradien