【正文】 描述 為 這樣 ： 有一個(gè)旅行商人要拜訪 n 個(gè)城市，他必須要 經(jīng)過所有的城市 ，而且每個(gè)城市只能拜訪一次，最后要回到原來出發(fā)的城市。人工生命與遺傳算法相輔相成，遺傳算法為人工生命的研究提供一個(gè)有效的工具，人工生命的研究也必將促進(jìn)遺傳算法的進(jìn)一步發(fā)展。基于遺傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要基礎(chǔ)理論。自組織能力和自學(xué)習(xí)能力是人工生命的兩大主要特征。利用該工具對兩個(gè)飛機(jī)失事的真實(shí)數(shù)據(jù)庫進(jìn)行了數(shù)據(jù)挖掘?qū)嶒?yàn)，結(jié)果表明遺傳算法是進(jìn)行數(shù)據(jù)挖掘的有效方法之一。因此，應(yīng)用遺傳算法在數(shù)據(jù)庫中進(jìn)行搜索，對隨機(jī)產(chǎn)生的一組規(guī)則進(jìn)行進(jìn)化 .直 到數(shù)據(jù)庫能被該組規(guī)則覆蓋，從而挖掘出隱含在數(shù)據(jù)庫中的規(guī)則。 （ 5）數(shù)據(jù) 挖掘 數(shù)據(jù)挖掘是近幾年出現(xiàn)的數(shù)據(jù)庫技術(shù)，它能夠從大型數(shù)據(jù)庫中提取隱含的、先前未知的、有潛在應(yīng)用價(jià)值的知識和規(guī)則。所以，機(jī)器人學(xué)理所當(dāng)然地成為遺傳算法的一個(gè)重要應(yīng)用領(lǐng)域。在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。目前在現(xiàn)實(shí)生產(chǎn)中主要是靠一些經(jīng)驗(yàn)來進(jìn)行調(diào)度。 遺傳 算法 已經(jīng)在求解 TSP 問題、 01 背包 問題、 圖形 劃分問題等方面得到了成功的應(yīng)用。 （ 2） 組合優(yōu)化 隨著 變量 n 的 不斷增大，問題的規(guī)模增大，組合優(yōu)化問題的求解空間也急劇增大， 應(yīng) 8 用 傳統(tǒng)的枚舉法等就很難求出最優(yōu)解。 尤其是 在數(shù)學(xué)領(lǐng)域，科學(xué)家 構(gòu)造出了 許許多多復(fù)雜 的測試函數(shù)： 連續(xù) 函數(shù)、離散函數(shù)、凸函數(shù)、凹函數(shù) 、 單峰函數(shù)、多峰函數(shù)等等。 遺傳 算法的應(yīng)用 遺傳 算法為求解復(fù)雜 系統(tǒng)問題 提供了一種通用的算法框架，它不取決于問題的 具體 領(lǐng)域，有很強(qiáng)的魯棒性 ， 因而被廣泛的 使用 于 組合 優(yōu)化 、 機(jī)械設(shè)計(jì)、人工智能、數(shù)學(xué)建模、軟件工程等領(lǐng)域 。 所以 ， 遺傳算法有很高的容錯(cuò)能力 ，我 們 可以 利用 遺傳算法 解決復(fù)雜的 非 結(jié)構(gòu)化問題。遺傳算法 利用 進(jìn)化過程獲得信息自行組織搜索時(shí)，適應(yīng)度高的個(gè)體具有較高的生存率，并獲得更加適應(yīng)環(huán)境的 染色體 。適應(yīng)度 函數(shù) 不僅不受連續(xù)可微的約束，而且其定義域可以任意的設(shè)定 ， 故幾乎可處理任何問題 。 其次 ，算法內(nèi) 含 并行性，遺傳算法采用種群方式組織搜索，因而可同時(shí)搜索解空間的多個(gè)區(qū)域，并 相互 交流信息，能以較小的計(jì)算獲得較大收益。傳統(tǒng) 優(yōu)化 算法從單個(gè)初始值迭代求最優(yōu)解，容易 早熟 陷入局部最優(yōu)解。 首先 ，遺傳算法并行的方式 是 從問題 解 的串 集 開始搜索，而不是從單個(gè)解開始。 遺傳 算法 與 傳統(tǒng)的 優(yōu)化 方法（ 枚舉 ，啟發(fā) 式 等） 相 比較，以生物進(jìn)化為原型 ， 具有很多的 優(yōu)點(diǎn) 。一般的 迭代 方法容易陷入局部極小的陷阱而出現(xiàn)“ 死循環(huán) ” 現(xiàn)象 ， 使迭代無法進(jìn)行。 遺傳 算法 算法 流程圖 開始編碼初始化染色體種群計(jì)算每個(gè)染色體的適應(yīng)度滿足終止條件根據(jù)適應(yīng)度選擇交叉變異輸出最優(yōu)解是否 7 圖 24 遺傳 算法算法流程圖 遺傳 算法的特點(diǎn) 遺傳算法 屬于進(jìn)化算法 （ Evolutionary Algorithms） 的 一種，它通過模仿自然界的選擇與 遺傳的原理來求出最優(yōu)解，遺傳算法 有 三個(gè) 最 基本的算子：選擇、交叉、變異。 步驟七 ： 終止 。 步驟六 ： 變異 算子：變異 是根據(jù) 生物 遺傳 中基因突變的原理， 以 變異概率 對 群體中的某一些個(gè)體 的 某些 “位 ”執(zhí)行 變異。 步驟五 ： 選擇 算子： 選擇 的目的是為了從交換后的群體中 選出 優(yōu)良 的 染色體攜帶者，使 它們 有機(jī)會作為父 代 繁殖 出 下一代群體。遺傳算法中起核心作用的就是交叉算子。 步驟三： 交叉算子：這是遺傳算法最重要的操作。遺傳算法 就是 以這個(gè)初始群體為起點(diǎn)開始迭代。 6 遺傳 算法基本步驟 步驟一 ： 編碼 ： 把 所需要選擇的群體進(jìn)行編號，每一個(gè)個(gè)體就是 一條 染色體 ，一個(gè) 解就是一串基因的組合 。 串 結(jié)構(gòu)空間 對 應(yīng)用 于遺傳學(xué) 中的基因 型 的 集合 。 10）串 結(jié)構(gòu) 空間 （ ss） ： 在串中，基因任意組合所構(gòu)成的串集合。遺傳編碼可以看成是從表現(xiàn)型到遺傳子型的映射。 7）變異（ musation）：復(fù)制時(shí)很小的概率產(chǎn)生的某些復(fù)制差錯(cuò)。 5）適應(yīng)度（ fitness） :度量某個(gè)物種對于生存環(huán)境的適應(yīng)程度。生物在其延續(xù)生命的過程中，逐漸適應(yīng)其生存環(huán)境使得其品質(zhì)不斷得到改良，這種生命現(xiàn)象稱為進(jìn)化。 3）種群（ population） :染色體帶有特征的個(gè)體的集合。生物的基因根據(jù)物種的不同而多少不一。（另外，值得注意的是遺傳算法不一定要找 “最高的山峰 ”，如果問題的適應(yīng)度評價(jià)越小越好的話，那么全局最優(yōu)解就是函數(shù)的最小值，對應(yīng)的，遺傳算法所要找的就是 “最深的谷底 ”） 。而其中也會有一個(gè) “山峰 ”的海拔最高的，那么這個(gè)就是全局最優(yōu)解。所以也可以把遺傳算法的過程看作是一個(gè)在多元函數(shù)里面求最優(yōu)解的過程。新的下一代再重復(fù) 根據(jù) 適應(yīng)度選擇部分后代，淘汰一部分后代，這樣 即 可以 保證 種群染色體的優(yōu)越性，也 保持了 種群大小的穩(wěn)點(diǎn)性。生存 下來的 染色體被稱為后代 （ offspring） 。這些 染色體 在后續(xù)的迭代中不斷 的進(jìn)化，稱為遺傳。 遺傳算法的思路是通過從給定一個(gè)初始群體出發(fā)，利用選擇算子、交叉算子以及變異算子來模擬自然進(jìn)化的三種原則，逐步改進(jìn)種群，越來越逼近最優(yōu)解，以達(dá)到求解最優(yōu)化問題的目的。 1992 年將遺傳算法應(yīng)用于計(jì)算機(jī)程序的優(yōu)化設(shè)計(jì)及自動生成，提出了遺傳編程 (Geic Programming) 的概念，并成功的將其提出的遺傳編程應(yīng)用于人工智能、機(jī)器學(xué)習(xí)符號處理等方面。 4 1989 年出版了專著《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法 (Geic Algorithms in Search，Optimization and Machine Learning)》，系統(tǒng)總結(jié)了遺傳算法的主要研究成果，全面而完整的論述了遺傳算法的基本原理及其應(yīng)用。 2 1967 年在其博士論文中首次提出了：“遺傳算法”一詞，發(fā)展了復(fù)制、交叉、變異、顯性、倒位等遺傳算子，創(chuàng)立了自適應(yīng)遺傳算法的概念。如今 遺傳 算法已經(jīng)被廣泛的應(yīng)用于 計(jì)算機(jī)科學(xué) 、 人工智能、機(jī)械設(shè)計(jì)、圖像處理等各個(gè)領(lǐng)域，不僅如此，利用遺傳算法進(jìn)行理論研究的優(yōu)化和最優(yōu)解問題的解決能力也顯著提高。 在一系列研究工作的基礎(chǔ)上 80 年代 Goldberg進(jìn)行總結(jié)歸納， 形成了 遺傳算法的基本框架 ； Smith將 遺傳算法應(yīng)用于機(jī)械學(xué)習(xí)領(lǐng)域； Bethke 對 函數(shù)優(yōu)化的遺傳算法進(jìn)行了系統(tǒng)的研究。 1967 年 ，他的學(xué)生 Bagley 提出 “遺傳 算法 ”一詞 ，并發(fā)展了復(fù)制、交叉 、 變異、顯性、倒位 等 遺傳算子。對本文的內(nèi)容進(jìn)行總結(jié)。 本章 主要 對系統(tǒng)模塊 進(jìn)行 了介紹，而且 對 應(yīng)用 系統(tǒng)進(jìn)行了多組試算，最后得出結(jié)論。 本章 主要介紹了 本系統(tǒng) 具體使用什么方式實(shí)現(xiàn)求解過程， 包括 編碼方式、選擇、交叉、變異算子的具體選取 。 這一章 主要 論述遺傳算法的 起源 發(fā) 展 及其實(shí)際應(yīng)用 ，重點(diǎn)介紹了遺傳算法的 算法原理 及 步驟 。這一章主要論述旅行商問題的基本概念，以及 本課題 主要的研究方法 及其 研究意義，并對論文的章節(jié)結(jié)構(gòu) 加以 論述。 在 求出 之后 將其按照 從大 到小的順序排列，以便于 后面找出 路徑 之 和最小的城市序列 。在遺傳算法中，以個(gè)體適應(yīng)度的大小來確定該個(gè)體被遺傳到下一代群體中的概率。交叉算法 采用的是常規(guī)的單點(diǎn)交叉， 之所以 可以用這一常規(guī)的交叉法，是因?yàn)樵诰幋a方式上使用的是 Grefenstette 等提出 的 一種 新的 巡回路線編碼方法 ，它 可以最大化交叉后后代 與 其 父 代的性狀 差異 ，有利于算法的全局性。應(yīng)用 遺傳算法 求解 旅行商問題，最難得地方在于問題 建 模 ， 如 城市 編碼方式以及 交叉 、 變異 、 選擇算子的確定等。 內(nèi)容 本文 采用遺傳算法求解 45 個(gè) 城市的旅行商問題，并對其實(shí)現(xiàn)計(jì)算機(jī)仿真。再比如 在裝配線 的 流程中，對每個(gè)工件為完成裝配過程節(jié)約的少許時(shí)間意味著一天的產(chǎn)量的相應(yīng)增加。而在互聯(lián)網(wǎng)繼續(xù)擴(kuò)大普及的時(shí)代，電子商務(wù)也迎來了期待已久的春天，同時(shí)物流產(chǎn)業(yè)也隨之水漲船高。 意義 首先旅行商 問題是 用于 求解 N 個(gè) 城市 存在（ N1） 條 閉合路徑的排列方案， 對于 這一類 問題 很難用全局搜索法精確地求出最優(yōu)解， 這一問題 已經(jīng)困擾眾多 學(xué)者 許多年，因此研究相應(yīng)的算法尋找其最優(yōu)或近似最優(yōu)解是非常必要的。 目前，求解 TSP問題常用的算法主要有遺傳算法和蟻群 算法，另外 還 有 爬山 法、模擬 退火 算法 、 神經(jīng)網(wǎng)絡(luò)方法、貪婪算法、禁忌搜索算法等。 尋求 一種 能 短時(shí)間求 解 出高精度解 的算法，已成為此問題研究的熱門。對于 具有一個(gè)城市的旅行商問題，其可能的路徑 數(shù)目 為（ n1） ！ /2， 5 個(gè) 城市 的問題 模型就對應(yīng) 120/10=12 條 路線， 10 個(gè) 城市的問題模型對應(yīng) 3628800/20=181440 條 路線。 2 TSP 問題可以形式化描述為：設(shè) G=（ V,A,D）是一個(gè)圖，其中 V 是 n 個(gè)頂點(diǎn)的集合，A 是弧線或邊集 ,D=（ ??????）是 與 A 關(guān)聯(lián) 的距離或費(fèi)用矩陣。 研究 背景 旅行商問題（ 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)中來。在 本系統(tǒng)就是要 應(yīng)用遺傳算法 求解 45 個(gè) 城市的 TSP 問題 。 旅行商 問題 （ Traveling Salesman Problem ,TSP） 是一個(gè) 非常經(jīng)典的組合優(yōu)化問題的 NP難題 ， 長期 以來 都沒有 一個(gè)十分有效的算法來解決它，但 TSP 本身 在許多領(lǐng)域有著重要的應(yīng)用，如 連鎖店 的貨物配送路線、計(jì)算機(jī)網(wǎng)絡(luò)路由器遍歷、印刷電路板的鉆孔路線等問題都可以 建模為旅行商問題。 即使在所定義的適應(yīng)度函數(shù) 中 是不連續(xù)的、不規(guī)則 的 情況下，也可以很大概率 找到 全局最優(yōu)解 。 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)域。 IV 目錄 遺傳算法求解 TSP 問題的計(jì)算機(jī)仿真 .............................................................................. II Abstract...................................................................................................................................... III 1 緒論 ......................................................................................................................................... 1 研究背景 ................................................................................................................................. 1 研究意義 ................................................................................................................................. 2 研究內(nèi)容 ................................................................................................................................. 2 本文的結(jié)構(gòu) ............................................................................................................................. 3 2 遺傳算法理論概述 ...........................