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