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