【正文】 運算終止條件 ?；具z傳算法只使用選擇算子、交叉算子和變異算子這三種基本遺傳算子，其遺傳進化操作過程簡單，容易理解，是其他一些遺傳算法的雛形和基礎，它不僅給各種遺傳算法提供了一個基本框架，同時也具有一定的應用價 值。但這些遺傳算法都有共同的特點，即通過對生物遺傳和進化過程中選擇、交叉、變異機理的模仿，來完成對問題最優(yōu)解的自適應搜索過程。 遺傳算法的特點 (1) 遺傳算法對優(yōu)化問題沒有太多的數(shù)學要求 ， 而且只要知道目標函數(shù)的信息即可； (2) 遺傳算法采用的是啟發(fā)性的知識智能搜索算法 ， 在搜索高度空間復雜問題上比以往有更好的效果； (3) 遺傳算法是對問題參數(shù)或者變量編碼群進行優(yōu)化 ， 而不是參數(shù)或變量本身； (4) 遺傳算法使用的選擇、交叉、變異算子都是隨機的； 基本遺傳算法描述 基于對自然界中生物遺傳與進化機理的模仿，針對不同的問題，很多學者設計了許多不同的編碼方法來表示問題的可行解，開發(fā)出了許多種不同的遺傳算子來模仿不同環(huán)境下生物遺傳特性。 選擇 (selection)算子、交叉 (crossover)算子和變異 (mutation)算子是遺傳算法的 3個主要操作算子。 基本原理 遺傳算法是一種借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法 ， 由美國 ， 其主要特 點是群體搜索策略和群體中個體之間的信息交換 ， 搜索不依賴于梯度信息 。 5 1991年 編輯出版了《遺傳算法手冊 (Handbook of Geic Algorithms)》書中包括遺傳算法在科學計算、工程技術和社會經濟中的大量應用實例。 3 Jong 1975年在其博士論文中結合模式定理進行了大量的純數(shù)值函數(shù)優(yōu)化計算實驗，樹立了遺傳算法的工作框架，定義了評價遺傳算法性能的在線指標和離線指標 。 主要以一些關鍵人物所做出的主要貢獻見證了遺傳算法的發(fā)展進程 : 1 60年代提出在研究和設計人工自適應系統(tǒng)時 ,可以借鑒生物遺傳的機制； 70年代初提出了遺傳算法的基本定理－模式定理 (Schema Theorem)，從而奠定了遺傳算法的理論基礎； 80年代實現(xiàn)了第一個基于遺傳算法的機器學系統(tǒng)－分類器系統(tǒng) (Classifier Systems),開創(chuàng)了基于遺傳算法的機器學習的新概念。 70年代 De Jong基于遺傳算法的思想在計算機上進行了大量純數(shù)值函數(shù)優(yōu)化計算實驗。 因此遺傳算法在 TSP問題求解方面的應用研究 ， 對于構 造合適的遺傳算法框架、建立有效的遺傳操作以及有效地解決 TSP問題等有著多方面的重要意義 。所以，有效解決 TSP問題在計算理論上和實際應用上都有很高的價值，而且 TSP問題由于其典型性已經成為各種啟發(fā)式的搜索、優(yōu)化算法的間接比較標準 (如遺傳算法、神經網(wǎng)絡優(yōu)化、列表尋優(yōu) (TABU)法、模擬退火法等 )。 TSP問題是一個典型的、容易描述但是難以處理的 NP完全問題，同 時 TSP問題也是諸多領域內出現(xiàn)的多種復雜問題的集中概括和簡化形式。 貨郎擔問題 (Traveling Salesman Problem ,TSP)， 也稱為巡回旅行商問題 ，是一個較古的問題 。盡管在遺傳算法的研究和應用過程中出現(xiàn)許多難題 ，同時也會產生許多不同的算法設計觀點，然而，目前遺傳算法的各種應用實踐已經展現(xiàn)出了其優(yōu)異的性能和巨大的發(fā)展?jié)摿?，它的發(fā)展前景激勵著各類專業(yè)技術人員把遺傳算法的理論和方法運用于自己的工作實踐中。隱含并行性和全局搜索特性是遺傳算法的兩大顯著特征。遺傳算法給我們呈現(xiàn)出的是一類通用的算法框架，該框架不依賴于問題的種類。 遺傳算法使用群體搜索技術，它通過對當前群體施加選擇、交叉、變異等一系列遺傳操作，從而產生出新一代的群體，并逐步使群體進化到包含或接近最優(yōu)解的狀態(tài)。然而，自然界中的生物卻在這方面表現(xiàn)出了其優(yōu)異的能力，它們能夠以優(yōu)勝劣汰、適者生存的自然進化規(guī)則生存和繁衍，并逐步產生出對其生存環(huán)境適應性很高的優(yōu)良物種。 最后 ， 簡單說明了混合遺傳算法在求解 TSP問題中的應用并對遺傳算法解決 TSP問題的前景提出了展望 。 畢 業(yè) 設 計 (論 文 ) 學院 信息工程學院 專業(yè) 計算機科學技術與應用 班級 姓名 年 月 日 目 錄 摘要 I Abstract II 引 言 1 第一章 基本遺傳算法 2 遺傳算法的產生及發(fā)展 .......................................................... 3 基本原理 ...................................................................... 3 遺傳 算法的特點 ................................................................ 3 基本遺傳算法描述 .............................................................. 5 遺傳算法構造流程 .............................................................. 6 第二章 遺傳算法的實現(xiàn)技術 6 編碼方法 ..................................................................... 7 二進制編碼 .............................................................. 7 格雷碼編碼 .............................................................. 7 符點數(shù)編碼 .............................................................. 8 參數(shù)編碼 ................................................................ 8 適應度函數(shù) .................................................................. 10 選擇算子 .................................................................... 10 交叉算子 .................................................................... 10 單點交叉算 子 ........................................................... 10 雙點交叉算 子 ........................................................... 11 均 勻交叉算 子 ........................................................... 11 部分映射交 叉 ........................................................... 11 順 序交叉 ............................................................... 12 變異算子 .................................................................... 12 運行參數(shù) .................................................................... 12 約束條件的處理方法 .......................................................... 13 遺傳算法流程圖 ............................................................... 14 第三章 遺傳算法在 TSP 上的應用 15 TSP問題的建模與描述 ........................................................ 15 對 TSP的遺傳基因編碼方法 .................................................... 16 針對 TSP的遺傳操作算子 ...................................................... 17 選擇算子 ............................................................... 17 輪盤賭選擇 ...................................................... 17 最優(yōu)保存策略選擇 ................................................ 17 交叉算子 ............................................................... 20 單點交叉 ......................................................... 20 部分映射交叉 ..................................................... 21 變異算子 ............................................................... 23 TSP的混和遺傳算法 ........................................................... 26 第四章 實例分析 27 測試數(shù)據(jù) .................................................................... 27 測試結果 .................................................................... 27 結果分析 .................................................................... 27 摘 要 TSP (Traveling Salesman Problem)旅行商問題是一類典型的 NP完全問題，遺傳算法是解決 NP問題的一種較理想的方法。 文章首先介紹了基本遺傳算法的基本原理、特點及其基本實現(xiàn)技術 ；接著 針對 TSP 問題 ， 論述了遺傳算法在編碼表示和遺傳算子（包括選擇算子、交叉算子變異算子這三種算子）等方面的應用情況 ， 分別指出幾種常用的編碼方法的優(yōu)點和缺點 ，并且結合 TSP的運行實例詳細分析了基 本遺傳算法的 4個運行參數(shù)群體大小、遺傳算法的終止進化代數(shù)、交叉概率、變異概率，對遺傳算法的求解結果和求解效率的影響，經過多次的測試設定出了它們一組比較合理的取值。 關鍵詞 ： TSP 遺傳算法 遺傳算子 編碼 Abstract TSP (Traveling Salesman Problem) is a typical NP plete problem and geic algorithm (GA) is the perfect method for solving NP plete problem. The basic theories, characteristics and the basic techniques of GA are first introduced. Then the encoding model and geic operators (including selection operation, crossover operation and mutation operation) about GA in solving TSP are discussed. The advantages and disadvantages of various encoding method are respectively indicated, and the application of the three basic geic operators is elaborated. According to the given data, the results and efficiencies