遺傳算法介紹及應(yīng)用

1、 遺傳算法的介紹及應(yīng)用目錄1遺傳算法介紹11.1遺傳算法的產(chǎn)生和發(fā)展21.2 遺傳算法的基本求解步驟2編碼2初始化：2估計適應(yīng)度：3再生(選擇):3交叉:3變異：3重復(fù)：32 遺傳算法的應(yīng)用例子42.1 編碼42.2 初始化42.3 計算適應(yīng)度52.4 再生（選擇）52.5 交叉52.6 變異63 遺傳算法解決TSP的例子73.1 TSP 問題描述73.2 遺傳算法用于TSP 問題8編碼表示8初始化群體和適應(yīng)度函數(shù)及其終止條件的設(shè)定8選擇算子9交叉算子9變異算子10問題的總結(jié)101遺傳算法介紹遺傳算法（genetic algorithms，GA）是一種模擬自然選擇和遺傳機制的尋優(yōu)方法， 它是建

2、立在達爾文的生物進化論和孟德爾的遺傳學說基礎(chǔ)上的算法?；螂s交和基因突變可能產(chǎn)生對環(huán)境適應(yīng)性強的后代，通過優(yōu)勝劣汰的自然選擇，適應(yīng)值高的基因結(jié)構(gòu)就保存下來。遺傳算法就是模仿了生物的遺傳、進化原理，并引用了隨機統(tǒng)計原理而形成的。1.1遺傳算法的產(chǎn)生和發(fā)展50 年代末60 年代初， 生物學家Fraser 試圖通過計算的方法來模擬生物界"遺傳與選擇"的進化過程，這便是GA 的雛形。受此啟發(fā)，Holland 教授認識到自然遺傳可以轉(zhuǎn)化為人工遺傳算法。1967 年Bagley 在其博士論文中首次提出了"遺傳算法"這一術(shù)語。1975 年，Holland 出版了自然與

3、人工系統(tǒng)中的適應(yīng)性行為。該書系統(tǒng)地闡述了遺傳算法的基本理論和方法，提出了遺傳算法的基本定理-模式定理， 從而奠定了遺傳算法的理論基礎(chǔ)。20 世紀80 年代初，Holland 教授實現(xiàn)了第一個基于遺傳算法的機器學習系統(tǒng)-分類器系統(tǒng)(Classifier System 簡稱CS)，開創(chuàng)了基于遺傳算法的機器學習的新概念。l992 年，John RKoza 出版了專著遺傳編程，提出了遺傳編程的概念，并成功地把遺傳編程的方法應(yīng)用于人工智能、機器學習、符號處理等方面。隨著遺傳算法的不斷發(fā)展， 關(guān)于遺傳算法的國際學術(shù)活動越來越多， 遺傳算法已成為一個多學科、多領(lǐng)域的重要研究方向。1.2 遺傳算法的基本求解步

4、驟 編碼：確定用何種碼制, 然后將問題參數(shù)編碼形成基因碼鏈，每一個碼鏈代表一個個體, 表示優(yōu)化問題的一個解。隨機產(chǎn)生一個規(guī)模為P的初始種群, 其中每個個體為一定長度的碼鏈, 該群體代表優(yōu)化問題的一些可能解的集合。1.2.3估計適應(yīng)度：計算種群中每個個體的適應(yīng)度, 適應(yīng)度為群體進化時的選擇提供了依據(jù)。一般來說適應(yīng)度越高, 解的素質(zhì)越好。適應(yīng)度函數(shù)可以根據(jù)目標函數(shù)而定。(選擇):根據(jù)每個個體的相對適應(yīng)度, 計算每個個體的再生次數(shù), 并進行再生操作, 產(chǎn)生新的個體加人下一代群體中, 一般再生的概率與其適應(yīng)度成正比。從種群中隨機選擇兩個染色體, 按一定的概率進行基因交換，交換位置的選取是隨機的。 變異

5、：從種群中隨機地選擇一個染色體, 按一定的變異概率P進行基因變異,GA的搜索能力主要是由選擇與交叉賦于的, 變異算子則保證了算法能搜索到問題空間的每一點, 從而使算法具有全局最優(yōu)性, 它進一步增強了GA的能力. 重復(fù)：若發(fā)現(xiàn)最優(yōu)解, 則算法停止, 否則轉(zhuǎn)3 ,對產(chǎn)生的新一代群體進行重新評價、選擇、交叉、變異操作, 如此循環(huán)往復(fù), 使群體中最優(yōu)個體的適應(yīng)度和平均適應(yīng)度不斷提高。其流程圖如下：2 遺傳算法的應(yīng)用例子用遺傳算法求解f(x)= （0=<x<=31），x為整數(shù)時f(x)的最大值2.1 編碼在區(qū)間0,31上的整數(shù)可以用一個5位的二進制位串進行編碼，x的值直接對應(yīng)二進制位串的數(shù)值

6、，如：9對應(yīng)01001，31對應(yīng)11111。2.2 初始化在0,31范圍內(nèi)按某種分布，隨機產(chǎn)生一個規(guī)模為P的初始種群，本例中假定初始種群取為4個二進制串，x1=01100,x2=11001,x3=01000,x4=10010。以上5位字串稱為染色體，每個分量稱為基因，每個基因有兩種狀態(tài)0或者1。2.3 計算適應(yīng)度計算種群中每個個體的適應(yīng)度，本題中，適應(yīng)度函數(shù)可定為：fitnes(x)=f(x)= ,于是Fitness（x1）=144，F(xiàn)itness（x2）=625,Fitness(x3)=64,Fitness(x4)=4002.4 再生（選擇）初始種群中每個個體入選種群的概率為：p(xi)=f

7、itness(xi)/ifitness(xi). 利用上述概率, 對這四個整數(shù)進行四次有放回的隨機抽取, 產(chǎn)生四個新的整數(shù), 顯然概率大的有更多的機會被抽中，四個新的整數(shù)=01100，=11001，=11001，=10010.經(jīng)前四步后，具體情況如表下所示：序號初始種群X值適應(yīng)度人選種群概率期望復(fù)制數(shù)實際復(fù)制數(shù)1011001214412%0.4812110012562551%2.0423010008645%0.204100102040032%1.281合計1233100%44平均308.325%112.5 交叉將（i=1，2，3，4）隨機結(jié)合成兩組，每組兩個數(shù)；對每組再進行一次隨機抽樣，以等概

8、率從1，2，3，4中選取一個數(shù)n.假設(shè)在上述例子中恰=01100，=11001分為一組，隨機抽取n=3,那么將由二進制表示的，從后三位開始互換，得到兩個新的二進制整數(shù)，記為，。同樣對另外一組數(shù)作類似處理，假設(shè)另一組抽得n=2,這樣得到四個新的整數(shù)，結(jié)果為=01001，=11100，=11010，=10001.具體情況如表所示：序號復(fù)制后種群復(fù)制對象交叉點n交叉后種群X值適應(yīng)度1011002301001981211001131110028784311001422110102248441001031000117289合計1638平均409.52.6 變異將交叉得到的四個二進制數(shù), 每個數(shù)每個二進位

9、進行一次隨機抽樣，以一個小概率P,例如1、1000將該位取反，即由1變?yōu)?，由1變?yōu)?，以概率1-P保持該位數(shù)字不變。這樣得到四個新的數(shù)記為（I=1，2，3，4），計算其函數(shù)值f(),回到步驟（4）。對產(chǎn)生的新一代群體進行重新計算適應(yīng)度、選擇、交叉、變異操作，如此循環(huán)往復(fù)，使群體中最優(yōu)個體的適應(yīng)度和平均適應(yīng)度不斷提高。變異可保持群體的多樣性，可使遺傳算法跳出局部極值點。 以上的簡單例子, 從開始隨機產(chǎn)生的種群到經(jīng)過一次再生、交叉、變異操作后的新種群中, 我們不難看出初始種群的平均適應(yīng)度為303.8, 新種群的平均適應(yīng)度為409.5, 最大值從初始種群的625增加到新種群的784?？梢娊?jīng)過一次遺

10、傳算法的操作后, 問題的解向最優(yōu)解的方向前進了一大步。因此經(jīng)過以上多次類似計算,問題的解最終會接近最優(yōu)解。當然在應(yīng)用遺傳算法時, 可以事先規(guī)定一個最大允許循環(huán)次數(shù), 以使計算得到終結(jié), 而以計算過程達到的最大函數(shù)值的作為所要的解, 遺傳算法實際上是一種搜索方式, 對那些標準數(shù)學方法難以奏效的問題給出了一種處理辦法。3 遺傳算法解決TSP的例子旅行商問題(TSP)，也稱為貨郎擔問題，是一個較古老的問題。最早可以追溯到1759 年Euler 提出的騎士旅行問題。1948 年，由美國蘭德公司推動，TSP 成為近代組合優(yōu)化領(lǐng)域的一個典型難題。應(yīng)該說，TSP 是一個具有廣泛應(yīng)用背景和重要理論價值的組合優(yōu)

11、化難題，它已經(jīng)被證明屬于NP 難題。對TSP 問題的大量研究使得TSP 問題成為了一個著名的組合優(yōu)化問題目前，求解TSP 問題的較為常用的方法有二叉樹描述法、啟發(fā)式搜索法、最近鄰法、神經(jīng)網(wǎng)絡(luò)法、模擬退火法和遺傳算法等。遺傳算法是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應(yīng)全局概率搜索算法，具有良好的全局尋優(yōu)能力，成為解決問題的有效方法之一。3.1 TSP 問題描述TSP（旅行商問題）的簡單描述是：一名商人欲到n 個城市推銷商品，每兩個城市i 和j 之間的距離為d，存在i，j 如何使商人每個城市走一遍后回到起點，且所走的路徑最短。用數(shù)學符號表示為：設(shè)n 維向量表示一條路徑X=(C1,

12、C2, ,Cn)，目標函數(shù)為minF(x)= 用圖語言來描述TSP，給出一個圖G=(V, E)，每邊eE 上有非負權(quán)值w(e)，尋找G 的Hamilon 圈C，使得C 的總權(quán)W(C)= 最小。TSP 搜索空間隨著城市數(shù)n 的增加而增大，所有的旅程路線組合數(shù)為(n-1)! /2。5 個城市的情形對應(yīng)120/10=12 條路線，10個城市的情形3628800/20=181440 條路線，100 個城市的情形則對應(yīng)有4.6663×條路線。在次龐大的搜索空間中尋求最優(yōu)解，對于常規(guī)方法和現(xiàn)有的搜索而言，存在諸多的計算困難。借助遺傳算法的搜索能力解決TSP 問題是很自然的想法。3.2 遺傳算法用

13、于TSP 問題 編碼表示用遺傳算法求解TSP 時，算法的編碼表示是算法設(shè)計的重點，它對遺傳基因的操作有一定的限制。TSP 的編碼策略主要包括二進制表示、順序表示、路徑表示、矩陣表示和邊表示等。由于二進制編碼具有如下的特點數(shù)據(jù)冗長，并且表達能力有限，計算機無法承受如此巨大的計算量甚至根據(jù)調(diào)整不同的參數(shù)時，所運行的時間，有時會達到近幾個小時，從時間效率來說，工作效率實在是低下，并達到無法忍受的程度，所以實際中很少使用。順序表示是指將所有城市依次排列構(gòu)成一個順序表，對于一條旅程，可以依次旅行經(jīng)過順序處理每個城市，每個城市在順序表中的順序就是一個遺傳因子的表示。每次處理完一個城市，從順序表中去掉該城市

14、。處理完所有城市后，將每個城市的遺傳因子連接起來，即成為一條旅程的基因表示（染色體編碼）。路徑表示是表示旅程歲應(yīng)的基因編碼的最自然，最簡潔的表示方法。 初始化群體和適應(yīng)度函數(shù)及其終止條件的設(shè)定根據(jù)編碼方法，隨機產(chǎn)生初始群體，直到達到所需規(guī)模為止。適應(yīng)度函數(shù)，由于是求最短路徑，適應(yīng)度函數(shù)一般采用求函數(shù)最大值，例如取路徑總長度T 的倒數(shù)，即fitness=l/T。其中， T=適應(yīng)度越小的個體，該個體的路徑越短，該個體則越好。也有采用fitness=l/T2 計算適應(yīng)度的算法。也有的算法采用fitness=1/(T+aN)，其中N 為未遍歷的城市的個數(shù)，a 為懲罰函數(shù)系數(shù)，常取城市間最長距離的兩倍多

15、，路徑T 越大，適應(yīng)度函數(shù)越小。迭代停止條件一般是：若某代群體中的最差個體與最好的個體適應(yīng)度的差不大于某個數(shù)（根據(jù)問題規(guī)模變化），則終止算法。若最佳個體連續(xù)保持一定代數(shù)，則終止算法。若算法迭代次數(shù)達到一定代數(shù)，則終止算法。 選擇算子選擇是從一個舊種群(old population)中選擇生命力強的個體位串產(chǎn)生新種群的過程。或者說，選擇是個體根據(jù)其適值函數(shù)f 拷貝自己的過程。直觀地講，可以把適值（或目標）函數(shù)f 看作是我們期望的最大效益或好處的某種量度。根據(jù)個體的適值拷貝位串意味著：具有高的適值的個體更大可能在下一代中產(chǎn)生一個或多個子孫。顯然這個操作是模仿自然選擇現(xiàn)象，將達爾文的適者生存理論運用

16、于個體的選擇。對于求解TSP 問題， 常用的選擇機制有輪盤賭選擇機制、隨機遍歷抽樣法、局部選擇法、截斷選擇法、錦標賽選擇法等。遺傳算法中一個較難解決的問題是如何較快地找到最優(yōu)解并防止“早熟”收斂問題。為了保證遺傳算法的全局收斂性，就要維持解群體的個體多樣性。這種做法會明顯改善遺傳算法的行為，因為其增加了體在種群中的分布區(qū)域，但增加了計算時間。 交叉算子Goldberg 提出基于路徑表示的部分映射交叉(partiallymapped, PMX)，首先隨機地在父個體中選取兩雜交點，并交換相應(yīng)的段再根據(jù)該段內(nèi)的城市確定部分映射。在每代父個體上先填入無沖突的城市。而對有沖突的城市分別執(zhí)行這些部分映射直

17、到填人無沖突，剛可獲得交叉后的兩后代。由Davis 提出順序交叉(order, OX)，它與PMX 操作非常類似。也是首先隨機地在父個體中選擇兩雜交點，再交換雜交段，其它位置根據(jù)保持父代個體中城市的相對次序來確定。由Oliver 等提出的循環(huán)交叉(CX)，將另一個父個體作為參照以對當前父個體中的城市進行重組。先與另一父個體實現(xiàn)一個循環(huán)鏈并將對應(yīng)的城市填入相應(yīng)的位置，循環(huán)組成后再將另一父體的城市填入相同的位置。上述幾種TSP 操作基本上考慮的是城市的位置和順序，未考慮城市間的連Grefenstette 認為遺傳算法應(yīng)用與TSP，其遺傳操作不僅要考慮城市間的位置，而且有必要考慮城市間的關(guān)系，城市間

18、的關(guān)系定義為邊，讓子個體繼承父個體中邊的信息設(shè)計邊的遺傳操作很有意義。1989 年，Whitle 等提出了一種邊重組(Edge RecombinationER)交叉操作，使個體能夠從父個體繼承9599的邊信息。ER 操作是根據(jù)繼承兩個父個體定義的旅程中城市間的相鄰關(guān)系生成子個體。1991 年，Stark weather 等提出了一種改進的方法，在ER 操作中不再保留父個體中共同部分的序列。實驗結(jié)果表明這種處理方法比隨機選擇的處理的性能有相當?shù)母纳啤?變異算子盡管復(fù)制和交叉操作很重要,在遺傳算法中是第一位的,但不能保證不會遺漏一些重要的遺傳信息。在人工遺傳系統(tǒng)中,變異是用來防止這種不可彌補的遺漏，在簡單遺傳算法中，變異就是某個字符串某一位的值偶然的（概率很小的）隨機的改變,即在某些特定位置上簡單地把1 變成0，或反之。變異是沿著個體字符空間的隨機移動，當它有節(jié)制地和交叉一起使用時，它就是一種防止過度成熟而丟失重要概念的