【正文】 the structure from the parent chromosomes and still ends up with a legal tour in the child chromosomes, which leads to a better solution than ever before. And the prospect for the future of geic algorithm in solving TSP is made. Keywords: TSP geic algorithm geic operators encoding 引 言 現(xiàn)代科學(xué)理論研究與實(shí)踐中存在著大量與優(yōu)化、自適應(yīng)相關(guān)的問(wèn)題，但除了一些簡(jiǎn)單 的情況之外，人們對(duì)于大型復(fù)雜系統(tǒng)的優(yōu)化和自適應(yīng)問(wèn)題仍然無(wú)能為力。 畢 業(yè) 設(shè) 計(jì) (論 文 ) 學(xué)院 信息工程學(xué)院 專(zhuān)業(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問(wèn)題的建模與描述 ........................................................ 15 對(duì) TSP的遺傳基因編碼方法 .................................................... 16 針對(duì) TSP的遺傳操作算子 ...................................................... 17 選擇算子 ............................................................... 17 輪盤(pán)賭選擇 ...................................................... 17 最優(yōu)保存策略選擇 ................................................ 17 交叉算子 ............................................................... 20 單點(diǎn)交叉 ......................................................... 20 部分映射交叉 ..................................................... 21 變異算子 ............................................................... 23 TSP的混和遺傳算法 ........................................................... 26 第四章 實(shí)例分析 27 測(cè)試數(shù)據(jù) .................................................................... 27 測(cè)試結(jié)果 .................................................................... 27 結(jié)果分析 .................................................................... 27 摘 要 TSP (Traveling Salesman Problem)旅行商問(wèn)題是一類(lèi)典型的 NP完全問(wèn)題，遺傳算法是解決 NP問(wèn)題的一種較理想的方法。然而，自然界中的生物卻在這方面表現(xiàn)出了其優(yōu)異的能力，它們能夠以?xún)?yōu)勝劣汰、適者生存的自然進(jìn)化規(guī)則生存和繁衍，并逐步產(chǎn)生出對(duì)其生存環(huán)境適應(yīng)性很高的優(yōu)良物種。遺傳算法給我們呈現(xiàn)出的是一類(lèi)通用的算法框架，該框架不依賴(lài)于問(wèn)題的種類(lèi)。盡管在遺傳算法的研究和應(yīng)用過(guò)程中出現(xiàn)許多難題 ，同時(shí)也會(huì)產(chǎn)生許多不同的算法設(shè)計(jì)觀(guān)點(diǎn)，然而，目前遺傳算法的各種應(yīng)用實(shí)踐已經(jīng)展現(xiàn)出了其優(yōu)異的性能和巨大的發(fā)展?jié)摿Γ陌l(fā)展前景激勵(lì)著各類(lèi)專(zhuān)業(yè)技術(shù)人員把遺傳算法的理論和方法運(yùn)用于自己的工作實(shí)踐中。 TSP問(wèn)題是一個(gè)典型的、容易描述但是難以處理的 NP完全問(wèn)題，同 時(shí) TSP問(wèn)題也是諸多領(lǐng)域內(nèi)出現(xiàn)的多種復(fù)雜問(wèn)題的集中概括和簡(jiǎn)化形式。 因此遺傳算法在 TSP問(wèn)題求解方面的應(yīng)用研究 ， 對(duì)于構(gòu) 造合適的遺傳算法框架、建立有效的遺傳操作以及有效地解決 TSP問(wèn)題等有著多方面的重要意義 。 主要以一些關(guān)鍵人物所做出的主要貢獻(xiàn)見(jià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)－分類(lèi)器系統(tǒng) (Classifier Systems),開(kāi)創(chuàng)了基于遺傳算法的機(jī)器學(xué)習(xí)的新概念。 5 1991年 編輯出版了《遺傳算法手冊(cè) (Handbook of Geic Algorithms)》書(shū)中包括遺傳算法在科學(xué)計(jì)算、工程技術(shù)和社會(huì)經(jīng)濟(jì)中的大量應(yīng)用實(shí)例。 選擇 (selection)算子、交叉 (crossover)算子和變異 (mutation)算子是遺傳算法的 3個(gè)主要操作算子。但這些遺傳算法都有共同的特點(diǎn)，即通過(guò)對(duì)生物遺傳和進(jìn)化過(guò)程中選擇、交叉、變異機(jī)理的模仿，來(lái)完成對(duì)問(wèn)題最優(yōu)解的自適應(yīng)搜索過(guò)程。 基本遺傳算法可以形式化定義為一個(gè)八元組： SGA=(C,E,Po,M,φ ,τ ,ψ ,T) C —— 個(gè)體的編碼方法 ； E —— 個(gè)體適應(yīng)度評(píng)價(jià)函數(shù) ； Po—— 初始群體 ； M —— 群體大小 ； φ —— 選擇算子 ； τ —— 交叉算子 ； ψ —— 變異算子 ； T —— 遺傳運(yùn)算終止條件 。 第四步：確定解碼方法，即確定出個(gè)體基因型 X到個(gè)體表現(xiàn)型 X的對(duì)應(yīng)關(guān)系轉(zhuǎn)換方法。 遺傳算法構(gòu)造流程 遺傳算法的構(gòu)造過(guò)程可以用下圖進(jìn)行描述： 圖 1－ 1 遺傳算法的主要構(gòu)造過(guò)程示意圖 第二章 遺傳算法的實(shí)現(xiàn)技術(shù) 編碼方法 在遺傳算法中如何描述問(wèn)題的可行解，即把一個(gè)問(wèn)題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法稱(chēng)為編碼。目前還沒(méi)有一套既嚴(yán)密有完整的指導(dǎo)理論及評(píng)價(jià)準(zhǔn)則能夠指導(dǎo)我們?cè)O(shè)計(jì)編碼方案。 二進(jìn)制編碼 二進(jìn)制編碼方法是遺傳算法中最常用的一種編碼方法，它使用的編碼符號(hào)集是由二進(jìn)制符號(hào) 0和 0組成的二值符號(hào)集｛ 0， 1｝，它所構(gòu)成的個(gè)體基因型是一個(gè)二進(jìn)制編碼符號(hào)串。 (4)便于利用模式定理對(duì)算法進(jìn)行理論分析。格雷碼有這樣一個(gè)特點(diǎn)：任意兩個(gè)整數(shù)的差是這兩個(gè)整數(shù)所對(duì)應(yīng)的海明距離（ Hamming distance）。 (3)符合最小字符集編碼原則。 由于二進(jìn)制編碼存在著連續(xù)函數(shù)離散化時(shí)的映射誤差，而且不便于反映所求問(wèn)題的特定知識(shí)，因而人們提出了用符點(diǎn)數(shù)來(lái)對(duì)個(gè) 體進(jìn)行編碼。 (4)改善了遺傳算法的復(fù)雜性，提高了運(yùn)算效率。 符號(hào)編碼方法是指?jìng)€(gè)體染色體編碼串中的基因值取自一個(gè)無(wú)數(shù)值含義，而只有代碼含義的符號(hào)集．它的主要優(yōu)點(diǎn)如下： (1)符合有意義積木塊編碼原則。 最后，簡(jiǎn)要介紹一下參數(shù)編碼方法。對(duì)生存環(huán)境適應(yīng)程度較高的物種將有更多的繁殖機(jī)會(huì)；而對(duì)生存環(huán)境適應(yīng)度較低的物種，其繁殖的機(jī)會(huì)就相對(duì)較少，甚至?xí)饾u滅絕。個(gè)體適應(yīng)度大小決定該個(gè)體被遺傳到下一代群體中的概率。評(píng)價(jià)個(gè)體適應(yīng)度的一般過(guò)程： (1)對(duì)個(gè)體編碼串進(jìn)行解碼處理后，可得到個(gè)體的表現(xiàn)型。 適應(yīng)度尺度變換 (Fitness Scaling):對(duì)個(gè)體的適應(yīng)度進(jìn)行適當(dāng)?shù)臄U(kuò)大或縮小變換。 選擇算子 遺 傳算法中使用選擇算子（也叫復(fù)制算子 Reproduction Operator）來(lái)對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰操作：適應(yīng)度較高的個(gè)體被遺傳到下一代的概率較大；適應(yīng)度較低的個(gè)體被遺傳到下一代的概率較小。有以下幾種常用的選擇算子的操作方法：比例選擇 、最優(yōu)保存策略、確定式采樣選擇、無(wú)放回隨機(jī)選擇、無(wú)放回余數(shù)隨機(jī)選擇、排序選擇和隨機(jī)聯(lián)賽選擇等。我們希望適應(yīng)度最好的個(gè)體要盡可能的保存到下一代群體中，為達(dá)到這個(gè)目的我們使用最優(yōu)保存策略進(jìn)化模型。 (5) 確定式采樣選擇（ Determinstic Sampling selection） 基本思想是按照一種確定的方式進(jìn)行選擇操作。模仿這個(gè)環(huán)節(jié)，在遺傳算法中也使用交叉算子來(lái)產(chǎn)生新個(gè)體。它是在個(gè)體編碼串中只隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，然后在該點(diǎn)相互交換兩個(gè)配對(duì)個(gè)體的部分染色體 。 (2) 交換兩個(gè)個(gè)體