




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、 遺傳算法的介紹及應(yīng)用目錄1遺傳算法介紹11.1遺傳算法的產(chǎn)生和發(fā)展21.2 遺傳算法的基本求解步驟2編碼2初始化:2估計(jì)適應(yīng)度:3再生(選擇):3交叉:3變異:3重復(fù):32 遺傳算法的應(yīng)用例子42.1 編碼42.2 初始化42.3 計(jì)算適應(yīng)度52.4 再生(選擇)52.5 交叉52.6 變異63 遺傳算法解決TSP的例子73.1 TSP 問(wèn)題描述73.2 遺傳算法用于TSP 問(wèn)題8編碼表示8初始化群體和適應(yīng)度函數(shù)及其終止條件的設(shè)定8選擇算子9交叉算子9變異算子10問(wèn)題的總結(jié)101遺傳算法介紹遺傳算法(genetic algorithms,GA)是一種模擬自然選擇和遺傳機(jī)制的尋優(yōu)方法, 它是建
2、立在達(dá)爾文的生物進(jìn)化論和孟德?tīng)柕倪z傳學(xué)說(shuō)基礎(chǔ)上的算法。基因雜交和基因突變可能產(chǎn)生對(duì)環(huán)境適應(yīng)性強(qiáng)的后代,通過(guò)優(yōu)勝劣汰的自然選擇,適應(yīng)值高的基因結(jié)構(gòu)就保存下來(lái)。遺傳算法就是模仿了生物的遺傳、進(jìn)化原理,并引用了隨機(jī)統(tǒng)計(jì)原理而形成的。1.1遺傳算法的產(chǎn)生和發(fā)展50 年代末60 年代初, 生物學(xué)家Fraser 試圖通過(guò)計(jì)算的方法來(lái)模擬生物界"遺傳與選擇"的進(jìn)化過(guò)程,這便是GA 的雛形。受此啟發(fā),Holland 教授認(rèn)識(shí)到自然遺傳可以轉(zhuǎn)化為人工遺傳算法。1967 年Bagley 在其博士論文中首次提出了"遺傳算法"這一術(shù)語(yǔ)。1975 年,Holland 出版了自然與
3、人工系統(tǒng)中的適應(yīng)性行為。該書系統(tǒng)地闡述了遺傳算法的基本理論和方法,提出了遺傳算法的基本定理-模式定理, 從而奠定了遺傳算法的理論基礎(chǔ)。20 世紀(jì)80 年代初,Holland 教授實(shí)現(xiàn)了第一個(gè)基于遺傳算法的機(jī)器學(xué)習(xí)系統(tǒng)-分類器系統(tǒng)(Classifier System 簡(jiǎn)稱CS),開(kāi)創(chuàng)了基于遺傳算法的機(jī)器學(xué)習(xí)的新概念。l992 年,John RKoza 出版了專著遺傳編程,提出了遺傳編程的概念,并成功地把遺傳編程的方法應(yīng)用于人工智能、機(jī)器學(xué)習(xí)、符號(hào)處理等方面。隨著遺傳算法的不斷發(fā)展, 關(guān)于遺傳算法的國(guó)際學(xué)術(shù)活動(dòng)越來(lái)越多, 遺傳算法已成為一個(gè)多學(xué)科、多領(lǐng)域的重要研究方向。1.2 遺傳算法的基本求解步
4、驟 編碼:確定用何種碼制, 然后將問(wèn)題參數(shù)編碼形成基因碼鏈,每一個(gè)碼鏈代表一個(gè)個(gè)體, 表示優(yōu)化問(wèn)題的一個(gè)解。隨機(jī)產(chǎn)生一個(gè)規(guī)模為P的初始種群, 其中每個(gè)個(gè)體為一定長(zhǎng)度的碼鏈, 該群體代表優(yōu)化問(wèn)題的一些可能解的集合。1.2.3估計(jì)適應(yīng)度:計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度, 適應(yīng)度為群體進(jìn)化時(shí)的選擇提供了依據(jù)。一般來(lái)說(shuō)適應(yīng)度越高, 解的素質(zhì)越好。適應(yīng)度函數(shù)可以根據(jù)目標(biāo)函數(shù)而定。(選擇):根據(jù)每個(gè)個(gè)體的相對(duì)適應(yīng)度, 計(jì)算每個(gè)個(gè)體的再生次數(shù), 并進(jìn)行再生操作, 產(chǎn)生新的個(gè)體加人下一代群體中, 一般再生的概率與其適應(yīng)度成正比。從種群中隨機(jī)選擇兩個(gè)染色體, 按一定的概率進(jìn)行基因交換,交換位置的選取是隨機(jī)的。 變異
5、:從種群中隨機(jī)地選擇一個(gè)染色體, 按一定的變異概率P進(jìn)行基因變異,GA的搜索能力主要是由選擇與交叉賦于的, 變異算子則保證了算法能搜索到問(wèn)題空間的每一點(diǎn), 從而使算法具有全局最優(yōu)性, 它進(jìn)一步增強(qiáng)了GA的能力. 重復(fù):若發(fā)現(xiàn)最優(yōu)解, 則算法停止, 否則轉(zhuǎn)3 ,對(duì)產(chǎn)生的新一代群體進(jìn)行重新評(píng)價(jià)、選擇、交叉、變異操作, 如此循環(huán)往復(fù), 使群體中最優(yōu)個(gè)體的適應(yīng)度和平均適應(yīng)度不斷提高。其流程圖如下:2 遺傳算法的應(yīng)用例子用遺傳算法求解f(x)= (0=<x<=31),x為整數(shù)時(shí)f(x)的最大值2.1 編碼在區(qū)間0,31上的整數(shù)可以用一個(gè)5位的二進(jìn)制位串進(jìn)行編碼,x的值直接對(duì)應(yīng)二進(jìn)制位串的數(shù)值
6、,如:9對(duì)應(yīng)01001,31對(duì)應(yīng)11111。2.2 初始化在0,31范圍內(nèi)按某種分布,隨機(jī)產(chǎn)生一個(gè)規(guī)模為P的初始種群,本例中假定初始種群取為4個(gè)二進(jìn)制串,x1=01100,x2=11001,x3=01000,x4=10010。以上5位字串稱為染色體,每個(gè)分量稱為基因,每個(gè)基因有兩種狀態(tài)0或者1。2.3 計(jì)算適應(yīng)度計(jì)算種群中每個(gè)個(gè)體的適應(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 再生(選擇)初始種群中每個(gè)個(gè)體入選種群的概率為:p(xi)=f
7、itness(xi)/ifitness(xi). 利用上述概率, 對(duì)這四個(gè)整數(shù)進(jìn)行四次有放回的隨機(jī)抽取, 產(chǎn)生四個(gè)新的整數(shù), 顯然概率大的有更多的機(jī)會(huì)被抽中,四個(gè)新的整數(shù)=01100,=11001,=11001,=10010.經(jīng)前四步后,具體情況如表下所示:序號(hào)初始種群X值適應(yīng)度人選種群概率期望復(fù)制數(shù)實(shí)際復(fù)制數(shù)1011001214412%0.4812110012562551%2.0423010008645%0.204100102040032%1.281合計(jì)1233100%44平均308.325%112.5 交叉將(i=1,2,3,4)隨機(jī)結(jié)合成兩組,每組兩個(gè)數(shù);對(duì)每組再進(jìn)行一次隨機(jī)抽樣,以等概
8、率從1,2,3,4中選取一個(gè)數(shù)n.假設(shè)在上述例子中恰=01100,=11001分為一組,隨機(jī)抽取n=3,那么將由二進(jìn)制表示的,從后三位開(kāi)始互換,得到兩個(gè)新的二進(jìn)制整數(shù),記為,。同樣對(duì)另外一組數(shù)作類似處理,假設(shè)另一組抽得n=2,這樣得到四個(gè)新的整數(shù),結(jié)果為=01001,=11100,=11010,=10001.具體情況如表所示:序號(hào)復(fù)制后種群復(fù)制對(duì)象交叉點(diǎn)n交叉后種群X值適應(yīng)度1011002301001981211001131110028784311001422110102248441001031000117289合計(jì)1638平均409.52.6 變異將交叉得到的四個(gè)二進(jìn)制數(shù), 每個(gè)數(shù)每個(gè)二進(jìn)位
9、進(jìn)行一次隨機(jī)抽樣,以一個(gè)小概率P,例如1、1000將該位取反,即由1變?yōu)?,由1變?yōu)?,以概率1-P保持該位數(shù)字不變。這樣得到四個(gè)新的數(shù)記為(I=1,2,3,4),計(jì)算其函數(shù)值f(),回到步驟(4)。對(duì)產(chǎn)生的新一代群體進(jìn)行重新計(jì)算適應(yīng)度、選擇、交叉、變異操作,如此循環(huán)往復(fù),使群體中最優(yōu)個(gè)體的適應(yīng)度和平均適應(yīng)度不斷提高。變異可保持群體的多樣性,可使遺傳算法跳出局部極值點(diǎn)。 以上的簡(jiǎn)單例子, 從開(kāi)始隨機(jī)產(chǎn)生的種群到經(jīng)過(guò)一次再生、交叉、變異操作后的新種群中, 我們不難看出初始種群的平均適應(yīng)度為303.8, 新種群的平均適應(yīng)度為409.5, 最大值從初始種群的625增加到新種群的784。可見(jiàn)經(jīng)過(guò)一次遺
10、傳算法的操作后, 問(wèn)題的解向最優(yōu)解的方向前進(jìn)了一大步。因此經(jīng)過(guò)以上多次類似計(jì)算,問(wèn)題的解最終會(huì)接近最優(yōu)解。當(dāng)然在應(yīng)用遺傳算法時(shí), 可以事先規(guī)定一個(gè)最大允許循環(huán)次數(shù), 以使計(jì)算得到終結(jié), 而以計(jì)算過(guò)程達(dá)到的最大函數(shù)值的作為所要的解, 遺傳算法實(shí)際上是一種搜索方式, 對(duì)那些標(biāo)準(zhǔn)數(shù)學(xué)方法難以奏效的問(wèn)題給出了一種處理辦法。3 遺傳算法解決TSP的例子旅行商問(wèn)題(TSP),也稱為貨郎擔(dān)問(wèn)題,是一個(gè)較古老的問(wèn)題。最早可以追溯到1759 年Euler 提出的騎士旅行問(wèn)題。1948 年,由美國(guó)蘭德公司推動(dòng),TSP 成為近代組合優(yōu)化領(lǐng)域的一個(gè)典型難題。應(yīng)該說(shuō),TSP 是一個(gè)具有廣泛應(yīng)用背景和重要理論價(jià)值的組合優(yōu)
11、化難題,它已經(jīng)被證明屬于NP 難題。對(duì)TSP 問(wèn)題的大量研究使得TSP 問(wèn)題成為了一個(gè)著名的組合優(yōu)化問(wèn)題目前,求解TSP 問(wèn)題的較為常用的方法有二叉樹(shù)描述法、啟發(fā)式搜索法、最近鄰法、神經(jīng)網(wǎng)絡(luò)法、模擬退火法和遺傳算法等。遺傳算法是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過(guò)程而形成的一種自適應(yīng)全局概率搜索算法,具有良好的全局尋優(yōu)能力,成為解決問(wèn)題的有效方法之一。3.1 TSP 問(wèn)題描述TSP(旅行商問(wèn)題)的簡(jiǎn)單描述是:一名商人欲到n 個(gè)城市推銷商品,每?jī)蓚€(gè)城市i 和j 之間的距離為d,存在i,j 如何使商人每個(gè)城市走一遍后回到起點(diǎn),且所走的路徑最短。用數(shù)學(xué)符號(hào)表示為:設(shè)n 維向量表示一條路徑X=(C1,
12、C2, ,Cn),目標(biāo)函數(shù)為minF(x)= 用圖語(yǔ)言來(lái)描述TSP,給出一個(gè)圖G=(V, E),每邊eE 上有非負(fù)權(quán)值w(e),尋找G 的Hamilon 圈C,使得C 的總權(quán)W(C)= 最小。TSP 搜索空間隨著城市數(shù)n 的增加而增大,所有的旅程路線組合數(shù)為(n-1)! /2。5 個(gè)城市的情形對(duì)應(yīng)120/10=12 條路線,10個(gè)城市的情形3628800/20=181440 條路線,100 個(gè)城市的情形則對(duì)應(yīng)有4.6663×條路線。在次龐大的搜索空間中尋求最優(yōu)解,對(duì)于常規(guī)方法和現(xiàn)有的搜索而言,存在諸多的計(jì)算困難。借助遺傳算法的搜索能力解決TSP 問(wèn)題是很自然的想法。3.2 遺傳算法用
13、于TSP 問(wèn)題 編碼表示用遺傳算法求解TSP 時(shí),算法的編碼表示是算法設(shè)計(jì)的重點(diǎn),它對(duì)遺傳基因的操作有一定的限制。TSP 的編碼策略主要包括二進(jìn)制表示、順序表示、路徑表示、矩陣表示和邊表示等。由于二進(jìn)制編碼具有如下的特點(diǎn)數(shù)據(jù)冗長(zhǎng),并且表達(dá)能力有限,計(jì)算機(jī)無(wú)法承受如此巨大的計(jì)算量甚至根據(jù)調(diào)整不同的參數(shù)時(shí),所運(yùn)行的時(shí)間,有時(shí)會(huì)達(dá)到近幾個(gè)小時(shí),從時(shí)間效率來(lái)說(shuō),工作效率實(shí)在是低下,并達(dá)到無(wú)法忍受的程度,所以實(shí)際中很少使用。順序表示是指將所有城市依次排列構(gòu)成一個(gè)順序表,對(duì)于一條旅程,可以依次旅行經(jīng)過(guò)順序處理每個(gè)城市,每個(gè)城市在順序表中的順序就是一個(gè)遺傳因子的表示。每次處理完一個(gè)城市,從順序表中去掉該城市
14、。處理完所有城市后,將每個(gè)城市的遺傳因子連接起來(lái),即成為一條旅程的基因表示(染色體編碼)。路徑表示是表示旅程歲應(yīng)的基因編碼的最自然,最簡(jiǎn)潔的表示方法。 初始化群體和適應(yīng)度函數(shù)及其終止條件的設(shè)定根據(jù)編碼方法,隨機(jī)產(chǎn)生初始群體,直到達(dá)到所需規(guī)模為止。適應(yīng)度函數(shù),由于是求最短路徑,適應(yīng)度函數(shù)一般采用求函數(shù)最大值,例如取路徑總長(zhǎng)度T 的倒數(shù),即fitness=l/T。其中, T=適應(yīng)度越小的個(gè)體,該個(gè)體的路徑越短,該個(gè)體則越好。也有采用fitness=l/T2 計(jì)算適應(yīng)度的算法。也有的算法采用fitness=1/(T+aN),其中N 為未遍歷的城市的個(gè)數(shù),a 為懲罰函數(shù)系數(shù),常取城市間最長(zhǎng)距離的兩倍多
15、,路徑T 越大,適應(yīng)度函數(shù)越小。迭代停止條件一般是:若某代群體中的最差個(gè)體與最好的個(gè)體適應(yīng)度的差不大于某個(gè)數(shù)(根據(jù)問(wèn)題規(guī)模變化),則終止算法。若最佳個(gè)體連續(xù)保持一定代數(shù),則終止算法。若算法迭代次數(shù)達(dá)到一定代數(shù),則終止算法。 選擇算子選擇是從一個(gè)舊種群(old population)中選擇生命力強(qiáng)的個(gè)體位串產(chǎn)生新種群的過(guò)程?;蛘哒f(shuō),選擇是個(gè)體根據(jù)其適值函數(shù)f 拷貝自己的過(guò)程。直觀地講,可以把適值(或目標(biāo))函數(shù)f 看作是我們期望的最大效益或好處的某種量度。根據(jù)個(gè)體的適值拷貝位串意味著:具有高的適值的個(gè)體更大可能在下一代中產(chǎn)生一個(gè)或多個(gè)子孫。顯然這個(gè)操作是模仿自然選擇現(xiàn)象,將達(dá)爾文的適者生存理論運(yùn)用
16、于個(gè)體的選擇。對(duì)于求解TSP 問(wèn)題, 常用的選擇機(jī)制有輪盤賭選擇機(jī)制、隨機(jī)遍歷抽樣法、局部選擇法、截?cái)噙x擇法、錦標(biāo)賽選擇法等。遺傳算法中一個(gè)較難解決的問(wèn)題是如何較快地找到最優(yōu)解并防止“早熟”收斂問(wèn)題。為了保證遺傳算法的全局收斂性,就要維持解群體的個(gè)體多樣性。這種做法會(huì)明顯改善遺傳算法的行為,因?yàn)槠湓黾恿梭w在種群中的分布區(qū)域,但增加了計(jì)算時(shí)間。 交叉算子Goldberg 提出基于路徑表示的部分映射交叉(partiallymapped, PMX),首先隨機(jī)地在父?jìng)€(gè)體中選取兩雜交點(diǎn),并交換相應(yīng)的段再根據(jù)該段內(nèi)的城市確定部分映射。在每代父?jìng)€(gè)體上先填入無(wú)沖突的城市。而對(duì)有沖突的城市分別執(zhí)行這些部分映射直
17、到填人無(wú)沖突,剛可獲得交叉后的兩后代。由Davis 提出順序交叉(order, OX),它與PMX 操作非常類似。也是首先隨機(jī)地在父?jìng)€(gè)體中選擇兩雜交點(diǎn),再交換雜交段,其它位置根據(jù)保持父代個(gè)體中城市的相對(duì)次序來(lái)確定。由Oliver 等提出的循環(huán)交叉(CX),將另一個(gè)父?jìng)€(gè)體作為參照以對(duì)當(dāng)前父?jìng)€(gè)體中的城市進(jìn)行重組。先與另一父?jìng)€(gè)體實(shí)現(xiàn)一個(gè)循環(huán)鏈并將對(duì)應(yīng)的城市填入相應(yīng)的位置,循環(huán)組成后再將另一父體的城市填入相同的位置。上述幾種TSP 操作基本上考慮的是城市的位置和順序,未考慮城市間的連Grefenstette 認(rèn)為遺傳算法應(yīng)用與TSP,其遺傳操作不僅要考慮城市間的位置,而且有必要考慮城市間的關(guān)系,城市間
18、的關(guān)系定義為邊,讓子個(gè)體繼承父?jìng)€(gè)體中邊的信息設(shè)計(jì)邊的遺傳操作很有意義。1989 年,Whitle 等提出了一種邊重組(Edge RecombinationER)交叉操作,使個(gè)體能夠從父?jìng)€(gè)體繼承9599的邊信息。ER 操作是根據(jù)繼承兩個(gè)父?jìng)€(gè)體定義的旅程中城市間的相鄰關(guān)系生成子個(gè)體。1991 年,Stark weather 等提出了一種改進(jìn)的方法,在ER 操作中不再保留父?jìng)€(gè)體中共同部分的序列。實(shí)驗(yàn)結(jié)果表明這種處理方法比隨機(jī)選擇的處理的性能有相當(dāng)?shù)母纳啤?變異算子盡管復(fù)制和交叉操作很重要,在遺傳算法中是第一位的,但不能保證不會(huì)遺漏一些重要的遺傳信息。在人工遺傳系統(tǒng)中,變異是用來(lái)防止這種不可彌補(bǔ)的遺漏,在簡(jiǎn)單遺傳算法中,變異就是某個(gè)字符串某一位的值偶然的(概率很小的)隨機(jī)的改變,即在某些特定位置上簡(jiǎn)單地把1 變成0,或反之。變異是沿著個(gè)體字符空間的隨機(jī)移動(dòng),當(dāng)它有節(jié)制地和交叉一起使用時(shí),它就是一種防止過(guò)度成熟而丟失重要概念的
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 車輛運(yùn)輸保險(xiǎn)理賠服務(wù)合作協(xié)議
- 環(huán)??萍紡S房租賃合同
- 航空班組與個(gè)人安全責(zé)任書
- 國(guó)際旅游團(tuán)組導(dǎo)游服務(wù)合同
- 成都高空廣告安裝工程安全防護(hù)與應(yīng)急預(yù)案合同
- 高新技術(shù)產(chǎn)業(yè)園區(qū)場(chǎng)地合作運(yùn)營(yíng)合同
- 車庫(kù)產(chǎn)權(quán)抵押租賃合同范例
- 文化創(chuàng)意產(chǎn)業(yè)場(chǎng)地調(diào)研合同范本
- 藝術(shù)培訓(xùn)場(chǎng)地租賃意向協(xié)議
- 企業(yè)稅務(wù)籌劃與合規(guī)財(cái)務(wù)顧問(wèn)協(xié)議
- 裝修公司合同保密協(xié)議書
- 2025-2030中國(guó)公路建設(shè)行業(yè)發(fā)展分析及發(fā)展前景與趨勢(shì)預(yù)測(cè)研究報(bào)告
- 2025購(gòu)銷茶葉合同范本
- 戶外場(chǎng)地安全課件
- 研究我國(guó)平臺(tái)企業(yè)在社會(huì)責(zé)任履行及其治理機(jī)制的現(xiàn)狀與問(wèn)題
- 叉車使用安全協(xié)議書
- ai訓(xùn)練師面試題及答案
- 2024-2025學(xué)年人教版數(shù)學(xué)五年級(jí)下學(xué)期期末試卷(含答案)
- 安全管理:承包商安全管理制度(模板)
- 2025年湖北省新華書店(集團(tuán))有限公司招聘筆試參考題庫(kù)附帶答案詳解
- 2025年宣城郎溪開(kāi)創(chuàng)控股集團(tuán)有限公司下屬子公司招聘12人筆試參考題庫(kù)附帶答案詳解
評(píng)論
0/150
提交評(píng)論