【正文】 的遺傳信息。 1991 年， Stark weather 等提出了一種改進(jìn)的方法，在 ER 操作中不再保留父個(gè)體中共同部分的序列。 1989 年， Whitle 等提出了一種邊重組 (Edge Rebination． ER)交叉操作，使個(gè)體能夠從父個(gè)體繼承 95％～ 99％的邊信息。先與另一父個(gè)體實(shí)現(xiàn)一個(gè)循環(huán)鏈．并將對應(yīng)的城市填入相應(yīng)的位置，循環(huán)組成后．再將另一父體的城市填入相同的位置。也是首先隨機(jī)地在父個(gè)體中選擇兩雜交點(diǎn)，再交換雜交段，其它位置根據(jù)保持父代個(gè)體中城市的相對次序來確定。而對有沖突的城市分別執(zhí)行這些部分映射直到填人無沖突，剛可獲得交叉后的兩后代。 交叉算子 Goldberg 提出基于路徑表示的部分映射交叉 (partially— mapped, PMX)，首先隨機(jī)地在父個(gè)體中選取兩雜交點(diǎn)，并交換相應(yīng)的段再根據(jù)該段內(nèi)的城市確定部分映射。為了保證遺傳算法的全局收斂性，就要維持解群體的個(gè)體多樣性。 對于求解 TSP 問題， 常用的選擇機(jī)制有輪盤賭選擇機(jī)制、隨機(jī)遍歷抽樣法、局部選擇法、截?cái)噙x擇法、錦標(biāo)賽選擇法等。根據(jù)個(gè)體的適值拷貝位串意味著：具有高的適值的個(gè)體更大可能在下一代中產(chǎn)生一個(gè)或多個(gè)子孫?；蛘哒f，選擇是個(gè)體根據(jù)其適值函數(shù) f 拷貝自己的過程。若算法迭代次數(shù)達(dá)到一定代數(shù)，則終止算法。迭代停止條件一般是：若某代群體中的最差個(gè)體與最好的個(gè)體適應(yīng)度的差不大于某個(gè)數(shù)（根據(jù)問題規(guī)模變化），則終止算法。也有采用 fitness=l/T2 計(jì)算適應(yīng)度的算法。適應(yīng)度函數(shù)，由于是求最短路徑，適應(yīng)度函數(shù)一般采用求函數(shù)最大值，例如取路徑總長度 T 的倒數(shù)，即fitness=l/T。路徑表示是表示旅程歲應(yīng)的基因編碼的最自然，最簡潔的表示方法。每次處理完一個(gè)城市，從順序表中去掉該 城市。由于二進(jìn)制編碼具有如下的特點(diǎn)數(shù)據(jù)冗長，并且表達(dá)能力有限，計(jì)算機(jī)無法承受如此巨大的計(jì)算量甚至根據(jù)調(diào)整不同的參數(shù)時(shí)，所運(yùn)行的時(shí)間，有時(shí)會(huì)達(dá)到近幾個(gè)小時(shí)，從時(shí)間效率來說，工作效率實(shí)在是低下，并達(dá)到無法忍受的程度，所以實(shí)際中很少使用。 貴州大學(xué) 第 9 頁 遺傳算法用于 TSP 問題 編碼表示 用遺傳算法求解 TSP 時(shí)，算法的編碼表示是算法設(shè)計(jì)的重點(diǎn)，它 對遺傳基因的操作有一定的限制。在次龐大的搜索空間中尋求最優(yōu)解，對于常規(guī)方法和現(xiàn)有的搜索而言，存在諸多的計(jì)算困難。 TSP 搜索空間隨著城市數(shù)n 的增加而增大，所有 的旅程路線組合數(shù)為 (n1)! /2。 TSP 問題描述 TSP（旅行商問題）的簡單描述是：一名商人欲到 n 個(gè)城市推銷商品，每兩個(gè)城市i 和 j 之間的距離為 d，存在 i， j 如何使商人每個(gè)城市走一遍后回到起點(diǎn)，且所走的路徑最短。對 TSP 問題的大量研究使得 TSP 問題成為了一個(gè)著名的組合優(yōu)化問題目前，求解 TSP 問題的較為常用的方法有二叉樹描述法、啟發(fā)式搜索法、最近鄰法、神經(jīng)網(wǎng)絡(luò)法、模擬退火法和遺傳算法等。 1948 年，由美國蘭德公司推動(dòng)， TSP 成為近代組合優(yōu)化領(lǐng)域的一個(gè)典型難題。其流程圖如下： 遺傳算法流程圖： 貴州大學(xué) 第 8 頁 第三章 遺傳算法的應(yīng)用概述 旅行商問題 (TSP)，也稱為貨郎擔(dān)問題，是一個(gè)較古老的問題。 交叉 : 從種群中隨機(jī)選擇兩個(gè)染色體 , 按一定的概率進(jìn)行基因交換，交換位置 的選取是隨機(jī)的。適應(yīng)度函數(shù)可以根據(jù)目標(biāo)函數(shù)而定。 估計(jì)適應(yīng)度： 計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度 , 適應(yīng)度為群體進(jìn)化時(shí)的選擇提供了依據(jù)。 貴州大學(xué) 第 6 頁 遺傳算法的基本求解步驟 編碼： 確定用何種碼制 , 然后將問題參數(shù)編碼形成基因碼鏈，每一個(gè)碼鏈代表一個(gè)個(gè)體 , 表示優(yōu)化問題的一個(gè)解。 l992 年， John R． Koza 出版了專著《遺傳編程》，提出了遺傳編程的概念，并成功地把遺傳編程的方法應(yīng)用于人工智能、機(jī)器學(xué)習(xí)、符號處理等方面。該書系統(tǒng)地闡述了遺傳算法的基本理論和方法，提出了遺傳算法的基本定理 模式定理， 從而奠定了遺傳算法的理論基礎(chǔ)。 1967 年 Bagley 在其博士論文中首次提出了 遺傳算法 這一術(shù)語。 遺傳算法的產(chǎn)生和發(fā)展 50 年代末 60 年代初， 生物學(xué)家 Fraser 試圖通過計(jì)算的方法來模擬生 物界 遺傳與選擇 的進(jìn)化過程，這便是 GA 的雛形。基因雜交和基因突變可能產(chǎn)生對環(huán)境適應(yīng)性強(qiáng)的后代，通過優(yōu)勝劣汰的自然選擇，適應(yīng)值高的基因結(jié)構(gòu)就保存下來。例如，可靠性優(yōu)化、流水車間調(diào)度、作業(yè)車間調(diào)度、機(jī)器調(diào)度、設(shè)備布局設(shè)計(jì)、圖像處理以及數(shù)據(jù)挖掘等。作為一種全局優(yōu)化搜索算法，遺傳算法以其簡單通用、魯棒性強(qiáng)、適于并行處理以及應(yīng)用范圍廣等特點(diǎn)，使其成為 21世紀(jì)智能計(jì)算核心技術(shù)之一。 遺傳算法的主要特點(diǎn)是群體搜索策略和群體中個(gè)體之間的信息交換，搜索不以梯度信息為基礎(chǔ)。遺傳算法的研究引起了國內(nèi)外學(xué)者的關(guān)注。它是由美國密執(zhí)安大學(xué) J． Holland 教授提出的一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法。geic operator。 Then in view of the problems this paper discusses the geic algorithm (ga) said in coding and geic operators (including selection operator, crossover operator, mutation operator) and so on, the application of simple discuss several encoding methods, finally introduces the TSP problem. 【 keywoeds】 Geic Algorithm。s theory of evolution and Mendel39。 本論文首先介紹了遺傳算法的基本原理、遺傳算法的特點(diǎn)，遺傳算法的發(fā)展方向和主要應(yīng)用領(lǐng)域；接著針對問題論述了遺傳算法在編碼表示和遺傳算子（包括選擇算子，交叉算子、變異算子）等方面的應(yīng)用情況，簡單討論幾種編碼方法 ,最后簡單介紹了 TSP問題。 TSP 問題是古老的經(jīng)典問題，有關(guān)的研究有幾百年的時(shí)間。 其基本思想基于 Darwin 的進(jìn)化論和 Mendel 的遺傳學(xué)。它的研究歷史比較短，早 期是一種試圖解釋自然系統(tǒng)中生物的復(fù)雜適應(yīng)過程入手，模擬生物進(jìn)化的機(jī)制來構(gòu)造人工系統(tǒng)的模型。 特此聲明。 專業(yè)選修課期末考核 （ 論文 ） 遺傳算法及其應(yīng)用淺析 學(xué) 院： 專 業(yè)： 班 級： 學(xué) 號： 學(xué)生姓名： 指導(dǎo)教師： 2021 年 6 月 1 日貴州大學(xué) 貴州大學(xué)論文（設(shè)計(jì)） 誠信責(zé)任書 本人鄭重聲明：本人所呈交的畢業(yè) 論文（設(shè)計(jì)），是在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究所完成。畢業(yè)論文（設(shè)計(jì)）中凡引用他人已經(jīng)發(fā)表或未發(fā)表的成果、數(shù)據(jù)、觀點(diǎn)等，均已明確注明出處。 論文（設(shè)計(jì)）作者簽名： 日 期： 貴州大學(xué) 第 1 頁 目錄 第一章 緒 論 ........................................................... 4 第二章 遺傳算法介紹 ..................................................... 5 遺傳算法介紹 ...................................................... 5 遺傳算法的產(chǎn)生和發(fā)展 .............................................. 5 遺傳算法的基本求解步驟 ............................................ 6 編碼： ...................................................... 6 初始化： ..................................................... 6 估計(jì)適應(yīng)度： ................................................. 6 再生 (選擇 ): .................................................. 6 交叉 : ....................................................... 6 變異： ...................................................... 6 重復(fù)： ...................................................... 7 遺傳算法流程圖： .............................................. 7 第三章 遺傳算法的應(yīng)用概述 ................................................ 8 TSP 問題描述 ..