遺傳算法畢業(yè)設(shè)計提綱

1、目錄 TOC o 1-5 h z HYPERLINK l bookmark7 o Current Document 1遺傳算法介紹2 HYPERLINK l bookmark10 o Current Document 1.1遺傳算法的產(chǎn)生和發(fā)展2 HYPERLINK l bookmark13 o Current Document 1.2遺傳算法的基本求解步驟3 HYPERLINK l bookmark16 o Current Document 1.2.1 編碼3 HYPERLINK l bookmark19 o Current Document 1.2.2初始化：3 HYPERLINK l b

2、ookmark22 o Current Document 1.2.3估計適應(yīng)度：4 HYPERLINK l bookmark25 o Current Document 1.2.4再生（選擇）：4 HYPERLINK l bookmark28 o Current Document 交叉：4 HYPERLINK l bookmark31 o Current Document 變異：4 HYPERLINK l bookmark34 o Current Document 重復(fù)：4 HYPERLINK l bookmark37 o Current Document 2遺傳算法的應(yīng)用例子5 HYPERLI

3、NK l bookmark40 o Current Document 2.1編碼5 HYPERLINK l bookmark43 o Current Document 2.2初始化5 HYPERLINK l bookmark46 o Current Document 2.3計算適應(yīng)度62.4再生（選擇）6 HYPERLINK l bookmark52 o Current Document 2.5交叉6 HYPERLINK l bookmark55 o Current Document 2.6變異7 HYPERLINK l bookmark58 o Current Document 3遺傳算法解

4、決TSP的例子8 HYPERLINK l bookmark61 o Current Document 3.1 TSP問題描述8 HYPERLINK l bookmark64 o Current Document 3.2遺傳算法用于TSP問題9 HYPERLINK l bookmark67 o Current Document 3.2.1編碼表示9 HYPERLINK l bookmark70 o Current Document 3.2.2初始化群體和適應(yīng)度函數(shù)及其終止條件的設(shè)定9 HYPERLINK l bookmark73 o Current Document 3.2.3選擇算子10 HY

5、PERLINK l bookmark76 o Current Document 3.2.4交叉算子10 HYPERLINK l bookmark79 o Current Document 3.2.5變異算子11 HYPERLINK l bookmark82 o Current Document 3.2.6 TSP問題的總結(jié)111遺傳算法介紹遺傳算法(genetic algorithms, GA)是一種模擬自然選擇和遺傳機(jī)制的尋 優(yōu)方法，它是建立在達(dá)爾文的生物進(jìn)化論和孟德爾的遺傳學(xué)說基礎(chǔ)上的算法。 基因雜交和基因突變可能產(chǎn)生對環(huán)境適應(yīng)性強(qiáng)的后代，通過優(yōu)勝劣汰的自然選 擇，適應(yīng)值高的基因結(jié)構(gòu)就保存

6、下來。遺傳算法就是模仿了生物的遺傳、進(jìn)化原 理，并引用了隨機(jī)統(tǒng)計原理而形成的。1.1遺傳算法的產(chǎn)生和發(fā)展50年代末60年代初，生物學(xué)家Fraser試圖通過計算的方法來模擬生物 界遺傳與選擇的進(jìn)化過程，這便是GA的雛形。受此啟發(fā)，Holland教授認(rèn)識 到自然遺傳可以轉(zhuǎn)化為人工遺傳算法。1967年Bagley在其博士論文中首次提 出了遺傳算法這一術(shù)語。1975年，Holland出版了自然與人工系統(tǒng)中的適 應(yīng)性行為。該書系統(tǒng)地闡述了遺傳算法的基本理論和方法，提出了遺傳算法的 基本定理-模式定理，從而奠定了遺傳算法的理論基礎(chǔ)。20世紀(jì)80年代初， Holland教授實現(xiàn)了第一個基于遺傳算法的機(jī)器學(xué)習(xí)

7、系統(tǒng)一分類器系統(tǒng) (Classifier System簡稱CS)，開創(chuàng)了基于遺傳算法的機(jī)器學(xué)習(xí)的新概念。l992 年，JohnR. Koza出版了專著遺傳編程，提出了遺傳編程的概念，并成功地 把遺傳編程的方法應(yīng)用于人工智能、機(jī)器學(xué)習(xí)、符號處理等方面。隨著遺傳算法 的不斷發(fā)展，關(guān)于遺傳算法的國際學(xué)術(shù)活動越來越多，遺傳算法已成為一個多 學(xué)科、多領(lǐng)域的重要研究方向。國外遺傳算法的發(fā)展現(xiàn)狀1991年DWhitey在他的論文中提出了基于領(lǐng)域交叉的交叉算子，這個算子 是特別針對用序號表示基因的個體的交叉，并將其應(yīng)用到了 TSP問題中，通過實 驗對其進(jìn)行了驗證。D.H.Ackley等提出了隨即迭代遺傳爬山法

8、采用了一種復(fù)雜的概率選舉 機(jī)制，此機(jī)制中由m個“投票者”來共同決定新個體的值(m表示群體的大小)。 實驗結(jié)果表明，SIGH與單點交叉、均勻交叉的神經(jīng)遺傳算法相比，所測試的六 個函數(shù)中有四個表現(xiàn)出更好的性能，而且總體來講，SIGH比現(xiàn)存的許多算法在 求解速度方面更有競爭力。H.Bersini和G.Seront將遺傳算法與單一方法結(jié)合起來，形成了一種叫 單一操作的多親交叉算子，該算子在根據(jù)兩個母體以及一個額外的個體產(chǎn)生新個 體，事實上他的交叉結(jié)果與對三個個體用選舉交叉產(chǎn)生的結(jié)果一致。同時，文獻(xiàn) 還將三者交叉算子與點交叉、均勻交叉做了比較，結(jié)果表明，三者交叉算子比其 余兩個有更好的性能。國內(nèi)遺傳算法

9、的發(fā)展現(xiàn)狀2002年，戴曉明等應(yīng)用多種群遺傳并行進(jìn)化的思想，對不同種群基于不同 的遺傳策略，如變異概率，不同的變異算子等來搜索變量空間，并利用種群間遷 移算子來進(jìn)行遺傳信息交流，以解決經(jīng)典遺傳算法的收斂到局部最優(yōu)值問題2004年，趙宏立等針對簡單遺傳算法在較大規(guī)模組合優(yōu)化問題上搜索效 率不高的現(xiàn)象，提出了一種用基因塊編碼的并行遺傳算法。該方法以粗粒度并行 遺傳算法為基本框架，在染色體群體中識別出可能的基因塊，然后用基因塊作為 新的基因單位對染色體重新編碼，產(chǎn)生長度較短的染色體，在用重新編碼的染色 體群體作為下一輪以相同方式演化的初始群體。2005年，江雷等針對并行遺傳算法求解TSP問題，探討了

10、使用彈性策略 來維持群體的多樣性，使得算法跨過局部收斂的障礙，向全局最優(yōu)解方向進(jìn)化。1.2遺傳算法的基本求解步驟1.2.1編碼：確定用何種碼制，然后將問題參數(shù)編碼形成基因碼鏈，每一個碼鏈代表一個 個體，表示優(yōu)化問題的一個解。1.2.2初始化：隨機(jī)產(chǎn)生一個規(guī)模為P的初始種群，其中每個個體為一定長度的碼鏈，該群體代表優(yōu)化問題的一些可能解的集合。1.2.3估計適應(yīng)度：計算種群中每個個體的適應(yīng)度，適應(yīng)度為群體進(jìn)化時的選擇提供了依據(jù)。一 般來說適應(yīng)度越高，解的素質(zhì)越好。適應(yīng)度函數(shù)可以根據(jù)目標(biāo)函數(shù)而定。1.2.4再生（選擇）：根據(jù)每個個體的相對適應(yīng)度，計算每個個體的再生次數(shù)，并進(jìn)行再生操作， 產(chǎn)生新的個體

11、加人下一代群體中，一般再生的概率與其適應(yīng)度成正比。1.2.5交叉：從種群中隨機(jī)選擇兩個染色體，按一定的概率進(jìn)行基因交換，交換位置的選 取是隨機(jī)的。1.2.6變異：從種群中隨機(jī)地選擇一個染色體，按一定的變異概率P進(jìn)行基因變異,GA的 搜索能力主要是由選擇與交叉賦于的，變異算子則保證了算法能搜索到問題空 間的每一點，從而使算法具有全局最優(yōu)性，它進(jìn)一步增強(qiáng)7GA的能力.1.2.7重復(fù)：若發(fā)現(xiàn)最優(yōu)解，則算法停止，否則轉(zhuǎn)3 ,對產(chǎn)生的新一代群體進(jìn)行重新評 價、選擇、交叉、變異操作，如此循環(huán)往復(fù)，使群體中最優(yōu)個體的適應(yīng)度和平均 適應(yīng)度不斷提高。其流程圖如下：編碼,生成初始種群計算與評價種群中個體適應(yīng)度物;

12、選擇交叉變異2遺傳算法的應(yīng)用例子用遺傳算法求解f(x)= x2 (0=x=31), x為整數(shù)時f(x)的最大值2.1編碼在區(qū)間0,31上的整數(shù)可以用一個5位的二進(jìn)制位串進(jìn)行編碼，x的值直接對 應(yīng)二進(jìn)制位串的數(shù)值，如：9對應(yīng)01001，31對應(yīng)11111。2.2初始化在0,31范圍內(nèi)按某種分布，隨機(jī)產(chǎn)生一個規(guī)模為P的初始種群，本例中假 定初始種群取為4個二進(jìn)制串，x1=01100,x2=11001,x3=01000,x4=10010。以上5 位字串稱為染色體，每個分量稱為基因，每個基因有兩種狀態(tài)0或者1。2.3計算適應(yīng)度計算種群中每個個體的適應(yīng)度，本題中，適應(yīng)度函數(shù)可定為： fitnes(x)=

13、f(x)= %2，于是Fitness(x1)=144，F(xiàn)itness(x2) =625,Fitness(x3)=64,Fitness(x4)二4002.4再生(選擇)初始種群中每個個體入選種群的概率為：p(xi)=fitness(xi)/E ifitness(xi).利用上述概率，對這四個整數(shù)進(jìn)行四次有放回的隨機(jī)抽取，產(chǎn) 生四個新的整數(shù)，顯然概率大的有更多的機(jī)會被抽中，四個新的整數(shù)氣=01100, % =11001，% =11001，% =10010.經(jīng)前四步后，具體情況如表下所示：234序號初始種群X值適應(yīng)度人選種群概率期望復(fù)制數(shù)實際復(fù)制數(shù)1011001214412%0.4812110012

14、562551%2.0423010008645%0.204100102040032%1.281合計1233100%44平均308.325%112.5交叉將土(i=1，2, 3, 4)隨機(jī)結(jié)合成兩組，每組兩個數(shù)；對每組再進(jìn)行一次 隨機(jī)抽樣，以等概率從1，2, 3, 4中選取一個數(shù)n.假設(shè)在上述例子中恰%； =01100， % =11001分為一組，隨機(jī)抽取n=3，那么將由二進(jìn)制表示的%，% 從后三位開始212互換，得到兩個新的二進(jìn)制整數(shù)，記為氣，七。同樣對另外一組數(shù)作類似處理， 假設(shè)另一組抽得n=2,這樣得到四個新的整數(shù)，結(jié)果為=01001， = 11100， = 11010，x=10001.具體

15、情況如表所示:序號復(fù)制后種群復(fù)制對象交叉點n交叉后種群X值適應(yīng)度1011002301001981211001131110028784311001422110102248441001031000117289合計1638平均409.52.6變異將交叉得到的四個二進(jìn)制數(shù)，每個數(shù)每個二進(jìn)位進(jìn)行一次隨機(jī)抽樣，以一個 小概率P,例如1、1000將該位取反，即由1變?yōu)?，由1變?yōu)?，以概率1-P保持該位 數(shù)字不變。這樣得到四個新的數(shù)記為xn+1（1 = 1，2, 3, 4），計算其函數(shù)值f（ xn+1 ）, 回到步驟（4）。對產(chǎn)生的新一代群體進(jìn)行重新計算適應(yīng)度、選擇、交叉、變異操 作，如此循環(huán)往復(fù)，使群體中

16、最優(yōu)個體的適應(yīng)度和平均適應(yīng)度不斷提高。變異可 保持群體的多樣性，可使遺傳算法跳出局部極值點。以上的簡單例子，從開始隨機(jī)產(chǎn)生的種群到經(jīng)過一次再生、交叉、變異操作 后的新種群中，我們不難看出初始種群的平均適應(yīng)度為303.8,新種群的平均適 應(yīng)度為409.5,最大值從初始種群的625增加到新種群的784。可見經(jīng)過一次遺傳 算法的操作后，問題的解向最優(yōu)解的方向前進(jìn)了一大步。因此經(jīng)過以上多次類似 計算，問題的解最終會接近最優(yōu)解。當(dāng)然在應(yīng)用遺傳算法時，可以事先規(guī)定一個 最大允許循環(huán)次數(shù)，以使計算得到終結(jié)，而以計算過程達(dá)到的最大函數(shù)值的xn 作為所要的解，遺傳算法實際上是一種搜索方式，對那些標(biāo)準(zhǔn)數(shù)學(xué)方法難以

17、奏效的問題給出了一種處理辦法。3遺傳算法解決TSP的例子旅行商問題(TSP),也稱為貨郎擔(dān)問題，是一個較古老的問題。最早可以 追溯到1759年Euler提出的騎士旅行問題。1948年，由美國蘭德公司推動，TSP 成為近代組合優(yōu)化領(lǐng)域的一個典型難題。應(yīng)該說，TSP是一個具有廣泛應(yīng)用背景 和重要理論價值的組合優(yōu)化難題，它已經(jīng)被證明屬于NP難題。對TSP問題的大 量研究使得TSP問題成為了一個著名的組合優(yōu)化問題目前，求解TSP問題的較為 常用的方法有二叉樹描述法、啟發(fā)式搜索法、最近鄰法、神經(jīng)網(wǎng)絡(luò)法、模擬退火 法和遺傳算法等。遺傳算法是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的 一種自適應(yīng)全局概率搜

18、索算法，具有良好的全局尋優(yōu)能力，成為解決問題的有效 方法之一。3.1 TSP問題描述TSP (旅行商問題)的簡單描述是：一名商人欲到n個城市推銷商品，每兩 個城市i和j之間的距離為d，存在i，j如何使商人每個城市走一遍后回到起點， 且所走的路徑最短。用數(shù)學(xué)符號表示為：設(shè)n維向量表示一條路徑X=(C1, C2,Cn)，目標(biāo)函數(shù)為minF(x)= Z +1d(C ,C 1) + d(C1 + C )用圖語言來描述TSP，給出一個圖G=(V, E)，每邊eEE上有非負(fù)權(quán)值w(e)， 尋找G的Hamilon圈C，使得C的總權(quán)W(C)= Zw(e)最小。TSP搜索空間隨eu E (C)著城市數(shù)n的增加而

19、增大，所有的旅程路線組合數(shù)為(n-1)! /2。5個城市的情 形對應(yīng)120/10=12條路線，10個城市的情形3628800/20=181440條路線，100個 城市的情形則對應(yīng)有4.6663 X 10155條路線。在次龐大的搜索空間中尋求最優(yōu)解， 對于常規(guī)方法和現(xiàn)有的搜索而言，存在諸多的計算困難。借助遺傳算法的搜索能 力解決TSP問題是很自然的想法。3.2遺傳算法用于TSP問題3.2.1編碼表示用遺傳算法求解TSP時，算法的編碼表示是算法設(shè)計的重點，它對遺傳基因 的操作有一定的限制。TSP的編碼策略主要包括二進(jìn)制表示、順序表示、路徑表 示、矩陣表示和邊表示等。由于二進(jìn)制編碼具有如下的特點數(shù)據(jù)

20、冗長，并且表達(dá) 能力有限，計算機(jī)無法承受如此巨大的計算量甚至根據(jù)調(diào)整不同的參數(shù)時，所運 行的時間，有時會達(dá)到近幾個小時，從時間效率來說，工作效率實在是低下，并 達(dá)到無法忍受的程度，所以實際中很少使用。順序表示是指將所有城市依次排列 構(gòu)成一個順序表，對于一條旅程，可以依次旅行經(jīng)過順序處理每個城市，每個城 市在順序表中的順序就是一個遺傳因子的表示。每次處理完一個城市，從順序表 中去掉該城市。處理完所有城市后，將每個城市的遺傳因子連接起來，即成為一 條旅程的基因表示(染色體編碼)。路徑表示是表示旅程歲應(yīng)的基因編碼的最自 然，最簡潔的表示方法。3.2.2初始化群體和適應(yīng)度函數(shù)及其終止條件的設(shè)定根據(jù)編碼

21、方法，隨機(jī)產(chǎn)生初始群體，直到達(dá)到所需規(guī)模為止。適應(yīng)度函數(shù)， 由于是求最短路徑，適應(yīng)度函數(shù)一般采用求函數(shù)最大值，例如取路徑總長度T的 倒數(shù)，即fitness=l/T。其中，T= Z +1 d(C , C 1) + d(C1 + C )適應(yīng)度越小的個體，該個體的路徑越短，該個體則越好。也有采用fitness=l/T2 計算適應(yīng)度的算法。也有的算法采用fitness=1/(T+aN)，其中N為未遍歷的城市 的個數(shù)，a為懲罰函數(shù)系數(shù)，常取城市間最長距離的兩倍多，路徇 越大，適應(yīng) 度函數(shù)越小。迭代停止條件一般是：若某代群體中的最差個體與最好的個體適應(yīng) 度的差不大于某個數(shù)(根據(jù)問題規(guī)模變化)，則終止算法。

22、若最佳個體連續(xù)保持 一定代數(shù)，則終止算法。若算法迭代次數(shù)達(dá)到一定代數(shù)，則終止算法。3.2.3選擇算子選擇是從一個舊種群(old population)中選擇生命力強(qiáng)的個體位串產(chǎn)生新 種群的過程?；蛘哒f，選擇是個體根據(jù)其適值函數(shù)f拷貝自己的過程。直觀地講， 可以把適值(或目標(biāo))函數(shù)f看作是我們期望的最大效益或好處的某種量度。根 據(jù)個體的適值拷貝位串意味著：具有高的適值的個體更大可能在下一代中產(chǎn)生一 個或多個子孫。顯然這個操作是模仿自然選擇現(xiàn)象，將達(dá)爾文的適者生存理論運 用于個體的選擇。對于求解TSP問題，常用的選擇機(jī)制有輪盤賭選擇機(jī)制、隨機(jī)遍歷抽樣法、 局部選擇法、截斷選擇法、錦標(biāo)賽選擇法等。遺

23、傳算法中一個較難解決的問題是 如何較快地找到最優(yōu)解并防止“早熟”收斂問題。為了保證遺傳算法的全局收斂 性，就要維持解群體的個體多樣性。這種做法會明顯改善遺傳算法的行為，因為 其增加了體在種群中的分布區(qū)域，但增加了計算時間。3.2.4交叉算子Goldberg提出基于路徑表示的部分映射交叉(partiallymapped, PMX)， 首先隨機(jī)地在父個體中選取兩雜交點，并交換相應(yīng)的段再根據(jù)該段內(nèi)的城市確定 部分映射。在每代父個體上先填入無沖突的城市。而對有沖突的城市分別執(zhí)行這 些部分映射直到填人無沖突，剛可獲得交叉后的兩后代。由Davis提出順序交叉 (order, OX)，它與PMX操作非常類似

24、。也是首先隨機(jī)地在父個體中選擇兩雜交 點，再交換雜交段，其它位置根據(jù)保持父代個體中城市的相對次序來確定。由 Oliver等提出的循環(huán)交叉(CX)，將另一個父個體作為參照以對當(dāng)前父個體中的 城市進(jìn)行重組。先與另一父個體實現(xiàn)一個循環(huán)鏈.并將對應(yīng)的城市填入相應(yīng)的位 置，循環(huán)組成后.再將另一父體的城市填入相同的位置。上述幾種TSP操作基本上考慮的是城市的位置和順序，未考慮城市間的連 Grefenstette認(rèn)為遺傳算法應(yīng)用與TSP，其遺傳操作不僅要考慮城市間的位置， 而且有必要考慮城市間的關(guān)系，城市間的關(guān)系定義為邊，讓子個體繼承父個體中 邊的信息設(shè)計邊的遺傳操作很有意義。1989年，Whitle等提出了一種邊重組 (Edge Recombination. ER)交叉操作，使個體能夠從父個體繼承95%99%的邊 信息。ER操作是根據(jù)繼承兩個父個體定義的旅程中城市間的相鄰關(guān)系生成子個 體。1991年，Stark weather等提出了一種改進(jìn)的方法，在ER操作中不再保留 父個體中共同部分的序列。實驗結(jié)果表明這種處理方法比隨機(jī)選擇的處理的性能 有相當(dāng)?shù)母纳啤?.2.5變異