遺傳算法最終章教材

遺傳算法及其MATLAB實(shí)現(xiàn)第4組唐煦堯朱萌萌廉馨6/17/2024目錄概念及背景知識(shí)流程圖算法應(yīng)用程序6/17/2024

遺傳算法的概念最早是由BagleyJ.D于1967年提出的。后來(lái)Michigan大學(xué)的J.H.Holland教授于1975年開(kāi)始對(duì)遺傳算法（GeneticAlgorithm,GA）的機(jī)理進(jìn)行系統(tǒng)化的研究。遺傳算法是對(duì)達(dá)爾文生物進(jìn)化理論的簡(jiǎn)單模擬，其遵循“適者生存”、“優(yōu)勝略汰”的原理。遺傳算法是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法。它被提出以來(lái)，在函數(shù)優(yōu)化、生產(chǎn)調(diào)度、模式識(shí)別、神經(jīng)網(wǎng)絡(luò)、自適應(yīng)控制等領(lǐng)域得到了廣泛的應(yīng)用，大大提高了問(wèn)題求解的效率?，F(xiàn)實(shí)生活中很多問(wèn)題都可以轉(zhuǎn)換為函數(shù)優(yōu)化問(wèn)題，遺傳算法則大大提高了求解全局最優(yōu)解的效率，具有很高的價(jià)值。概念及背景知識(shí)6/17/2024流程圖初始化數(shù)據(jù)統(tǒng)計(jì)計(jì)算選擇交叉突變遺傳迭代結(jié)束？否結(jié)束是6/17/2024例題：求maxf(x(1),x(2))=21.5+x(1)*sin(4πx(1))+x(2)*sin(20πx(2))

-3.0≤x(1)≤12.1

s.t.4.1≤x(2)≤5.8函數(shù)f（x1，x2）的三維圖形如圖所示。6/17/2024（1）編碼首先要進(jìn)行編碼工作，即將變量轉(zhuǎn)化成二進(jìn)制數(shù)串。數(shù)串的長(zhǎng)度取決于所要求的精度。例如，變量x的區(qū)間是（L,U），要求的精度是小數(shù)點(diǎn)后4位，也就意味著每個(gè)變量應(yīng)該被分成至少（L,U）*10^4個(gè)部分。對(duì)一個(gè)變量的二進(jìn)制數(shù)串位數(shù)用以下公式計(jì)算：本例精度要求保留小數(shù)點(diǎn)后4位，則目標(biāo)函數(shù)的兩個(gè)自變量x1及x2所構(gòu)成的染色體數(shù)串可以表示如下：本例中任一染色體數(shù)串都是33位，即000001010100101001101111011111110.以上編碼前18位表示x1，后15位表示x2，如下表所示。6/17/2024則二進(jìn)制轉(zhuǎn)化成十進(jìn)制為假設(shè)初始種群中有10個(gè)個(gè)體，其染色體可隨機(jī)生成如下：6/17/2024相對(duì)應(yīng)的十進(jìn)制的實(shí)際值[x1，x2]為6/17/20246/17/2024(2)評(píng)價(jià)個(gè)體適應(yīng)度對(duì)一個(gè)染色體數(shù)串的適應(yīng)度的評(píng)價(jià)由以下三個(gè)步驟組成：①將染色體串進(jìn)行解碼，轉(zhuǎn)換成真實(shí)值，即：

②評(píng)價(jià)目標(biāo)函數(shù)f=-f（x）③將目標(biāo)函數(shù)值轉(zhuǎn)為適應(yīng)度，上述染色體的適應(yīng)度值如下：6/17/20246/17/2024依照染色體的適應(yīng)度值進(jìn)行新種群的復(fù)制，步驟如下：①計(jì)算染色體的適應(yīng)度值

②計(jì)算種群的適應(yīng)度值總和：③計(jì)算每個(gè)染色體被復(fù)制的概率：④計(jì)算每個(gè)染色體被復(fù)制的累積概率：6/17/2024（3）新種群復(fù)制依照輪盤(pán)選擇法，轉(zhuǎn)動(dòng)輪盤(pán)10次（種群中有10條染色體），每次選擇一個(gè)作為新種群的染色體。假設(shè)10次中產(chǎn)生的0~1隨機(jī)數(shù)序列如下：

0.3014310.3220620.7665030.8818930.3508710.5383920.1776180.3432420.0326850.197577根據(jù)以上的計(jì)算方法，可以先計(jì)算出種群中每個(gè)染色體的適應(yīng)度和概率，如下表所列。利用計(jì)算機(jī)模擬輪盤(pán)選擇法，假設(shè)計(jì)算機(jī)產(chǎn)生10個(gè)[0,1]區(qū)間的隨機(jī)數(shù)列如下：6/17/2024第1個(gè)隨機(jī)數(shù)為0.301431，大于Q3小于Q4，所以U4被選中；第2個(gè)隨機(jī)數(shù)為0.322062，大于Q3小于Q4，所以U4再次被選中；……第10個(gè)隨機(jī)數(shù)為0.197577，大于Q1小于Q2，所以被U2選中；依照輪盤(pán)選擇法，新種群的染色體組成如下：這種輪盤(pán)選擇法的機(jī)理是：染色體的適應(yīng)度大意味著[Qk,Qk+1]區(qū)間跨度就大，隨機(jī)數(shù)發(fā)生器產(chǎn)生的均勻隨機(jī)數(shù)就會(huì)有更大的概率落在較大長(zhǎng)度的[Qk，Qk+1]區(qū)間里，這樣具有較大Pk值的染色體自然更有機(jī)會(huì)復(fù)制到下一代。6/17/20246/17/2024（4）新種群交配①交配染色體數(shù)量的確定

交配染色體數(shù)量=染色體總量×交配概率

[10×0.25]=2即交配染色體數(shù)目為2②交配染色體對(duì)象的確立

用計(jì)算機(jī)產(chǎn)生[0,1]區(qū)間的10個(gè)隨機(jī)數(shù)，確定其分別對(duì)應(yīng)10個(gè)個(gè)體，其中低于交配概率的參加交配。③在交配池發(fā)生交配6/17/2024（5）基因突變假設(shè)突變幾率P為0.01，亦即種群內(nèi)所有基因都有0.01的概率進(jìn)行突變。本例中共有33×10＝330個(gè)基因，即希望每一代中有3.3個(gè)突變基因，每個(gè)基因的突變概率是均等的。因此，將產(chǎn)生330個(gè)介于0~1之間的隨機(jī)數(shù)，然后將該隨機(jī)數(shù)小于0.01者選出，并將其對(duì)應(yīng)的基因值加以翻轉(zhuǎn)，如下表：表中第一列顯示的是具體在哪些染色體以及在什么染色體的什么位置進(jìn)行了突變。如，其中第一行表示在第4條染色體的第6個(gè)基因上發(fā)生了突變，因?yàn)榈?條染色體的第6個(gè)基因?qū)?yīng)的基因編號(hào)是33×（4-1)+6＝105。6/17/2024在突變后，最終新種群染色體組成如下：新一代的相對(duì)應(yīng)實(shí)際值[x(1),x(2)]和適應(yīng)度值如下：6/17/2024至此，已完成遺傳算法的第一代流程。至此迭代，在第451代得到對(duì)應(yīng)最大目標(biāo)函數(shù)值的染色體：

U=[111110000000111000111101001010110]相應(yīng)實(shí)際值[x(1),x(2)]=[11.631407,5,724824],適應(yīng)度值eval(U)=f(11.631407,5,724824)=38.818208

從以上實(shí)例可以得出兩點(diǎn)結(jié)論：

①遺傳算法本質(zhì)上是一種啟發(fā)式的隨機(jī)搜索算法，所以由遺傳算法得出的結(jié)果每次都不盡相同。

②自變量在給定的約束條件下進(jìn)行了無(wú)縫編碼（即這種編碼方式能夠表達(dá)解空間中的所有可行解），所以從理論上講，遺傳算法總有很多機(jī)會(huì)得到全局最優(yōu)結(jié)果而不是局部最優(yōu)結(jié)果。6/17/2024應(yīng)用程序例題：求maxf(x(1),x(2))=21.5+x(1)*sin(4πx(1))+x(2)*sin(20πx(2))

-3.0≤x(1)≤12.1

s.t.4.1≤x(2)≤5.8具體求解過(guò)程如下：①編寫(xiě)M文件：

functionf=lbw(x)if(x(1)>12.1||x(1)<-3.0||x(2)>5.8||x(2)<4.1)f=300;elsef=-21.5-x(1)*sin(4*pi*x(1))-x(2)*sin(20*pi*x(2));end6/17/2024

②在命令窗口輸入：>>clearall;>>options=gaoptimset('Generations',600,'StallGenLimit',451,'PlotFcns',@gaplotbestf);>>[x,f]=ga(@lbw,2,options)設(shè)置遺傳算法的參數(shù)和句柄函數(shù)超過(guò)連續(xù)代數(shù)不進(jìn)化則算法停止超過(guò)進(jìn)化代數(shù)時(shí)算法停止繪圖函數(shù)，可供選擇的有@gaplotbes