遺傳算法論文

1、數(shù)學(xué)建模論文基本遺傳算法的MATLAB實(shí)現(xiàn)一、問(wèn)題的提出遺傳算法是模仿自然界生物進(jìn)化機(jī)制發(fā)展起來(lái)的隨機(jī)全局搜索和優(yōu)化方 法，它借鑒了達(dá)爾文的進(jìn)化論和孟德?tīng)柕倪M(jìn)化學(xué)說(shuō)。其本質(zhì)是一種高效、并行、 全局搜索的方法，它能在搜索過(guò)程中自動(dòng)獲取和積累有關(guān)搜索空間的知識(shí)，并自 適應(yīng)的控制過(guò)程以求的最優(yōu)解。遺傳算法操作使用適者生存的原則，在潛在的解 決方案中逐次產(chǎn)生一個(gè)近似最優(yōu)方案。在遺傳算法的每一代中，根據(jù)個(gè)體在問(wèn)題 域中的適應(yīng)度值和從自然遺傳中借鑒來(lái)的再造方法進(jìn)行個(gè)體選擇，產(chǎn)生一個(gè)新的 近似解。這個(gè)過(guò)程導(dǎo)致種群中個(gè)體的進(jìn)化，得到新個(gè)體比原來(lái)個(gè)體更適應(yīng)環(huán)境， 就像自然界中的改造一樣。基本遺傳算法，最重要的是

2、產(chǎn)生隨機(jī)數(shù)的過(guò)程，已知目標(biāo)函數(shù) max f(x1,x2)=21.5+x1*sin(4*pi*x1)+x2*sin(20*pi*x2)其中約束條件為：-3.0=x1=12.14.1=x2=5.8編程用matlab實(shí)現(xiàn)基本遺傳算法。二、問(wèn)題的分析與模型的建立：遺傳算法是一種基于生物進(jìn)化原理構(gòu)想出來(lái)的搜索最優(yōu)解的仿真算法，它模 擬基因重組與進(jìn)化的自然過(guò)程，把待解決問(wèn)題的參數(shù)編成二進(jìn)制碼或十進(jìn)制碼即 基因，若干基因組成一個(gè)染色體個(gè)體許多染色體進(jìn)行類(lèi)似于自然選擇配對(duì)交叉和 變異的運(yùn)算，經(jīng)過(guò)多次重復(fù)迭代直到得到最后的優(yōu)化結(jié)果。習(xí)慣上，適應(yīng)度值越 大，表示解的質(zhì)量越好。對(duì)于求解最小值問(wèn)題，可通過(guò)變換轉(zhuǎn)為求解

3、最大值問(wèn)題。 遺傳算法以群體為基礎(chǔ)，不以單點(diǎn)搜索為基礎(chǔ)，能同時(shí)從不同點(diǎn)獲得多具極值， 因此不易陷入局部最優(yōu)；遺傳算法是對(duì)問(wèn)題變量的編碼集進(jìn)行操作，而不是變量 本身，有效地避免了對(duì)變量的微分操作運(yùn)算；遺傳算法只是利用目標(biāo)函數(shù)來(lái)區(qū)別 群體中的個(gè)體好壞而不必對(duì)其進(jìn)行過(guò)多的附加操作。基本遺傳算法定義：基本遺傳算法是一種群體型操作，該操作以群體中的所有個(gè)體為對(duì)象只使 用基本遺傳算子：選擇算子，交叉算子，變異算子其遺傳操作過(guò)程簡(jiǎn)單，容易理 解，是其他一些遺傳算法的基礎(chǔ)。數(shù)學(xué)模型：基本遺傳算法可表示為：SGA=(C,E,P0,M, 0 , r , ,T) 其中：C一個(gè)體的編碼方法E一個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)P0初

4、始種群M 種群大小0一選擇算子r 一交叉算子w 一變異算子T遺傳運(yùn)算終止條件步驟：1.染色體的編碼和解碼?；具z傳算法使用固定長(zhǎng)度的二進(jìn)制符號(hào)來(lái)表示群體中的個(gè)體其等位基 因由二值0,1所組成。初始群體中各個(gè)個(gè)體的基因可用均勻分布的隨機(jī) 數(shù)來(lái)生成。個(gè)體適應(yīng)度的檢測(cè)評(píng)估基本遺傳算法按與個(gè)體適應(yīng)度成正比的概率來(lái)決定當(dāng)前群體中各個(gè)個(gè) 體遺傳到下一代群體中機(jī)會(huì)多少。為了正確估計(jì)這個(gè)概率，要求所有個(gè) 體的適應(yīng)度必須為非負(fù)數(shù)。遺傳算子選擇算子選擇過(guò)程是以旋轉(zhuǎn)賭輪次為基礎(chǔ)的，賭輪上的刻度是每 個(gè)染色體的適應(yīng)度來(lái)劃分的。因此，這些刻度并不是平均分的。染色 體的適應(yīng)度越大，該染色體在賭輪上所占的面積也就越大，該染

5、色體 被選中的概率也就越大。每次旋轉(zhuǎn)都為新的種群選擇一個(gè)新的染色 體。若設(shè)種群數(shù)為M，個(gè)體i的適應(yīng)度為fi，則個(gè)體i被選取的概率為：Pi=fi/丈 fkk=1交叉運(yùn)算使用單點(diǎn)交叉算子，只有一個(gè)交叉點(diǎn)位置，任意挑選經(jīng)過(guò)選 擇操作后的種群中兩個(gè)個(gè)體作為交叉對(duì)象，隨機(jī)產(chǎn)生一個(gè)交叉點(diǎn)位置 互換部分基因碼，形成兩個(gè)子個(gè)體。變異運(yùn)算使用基本位變異算子算法函數(shù)目標(biāo)函數(shù) max f(x1,x2)=21.5+x1*sin(4*pi*x1)+x2*sin(20*pi*x2) 其中約束條件為：-3.0=x1=12.14.1=x2=5.8決策變量為 x1,x2(x1,x2)表現(xiàn)型編碼染色體，當(dāng)(x1,x2)代入算法函

6、數(shù)，算法函數(shù) max f(x1,x2)越大，則個(gè)體適應(yīng)度越強(qiáng)，即選擇概率越大。編碼方法要進(jìn)行編碼工作，即將變量轉(zhuǎn)化為二進(jìn)制串。在此，變量x1的區(qū)間是-3.0,12.1,它要求的精度是小數(shù)點(diǎn)后四位，也就意味著每個(gè)變 量應(yīng)該被分成至少(3.0+12.1)*104個(gè)部分。用下面的式子計(jì)算變量的二進(jìn)制串位數(shù)：217(12.1+3.0)218-1解碼方法設(shè)要求的精度為小數(shù)點(diǎn)后四位，則變量x1,x2可以轉(zhuǎn)化為下面的串：(12.1+3.0)*10000=1510021715100=218所以m1=18(5.8-4.1)*10000=1700021417000=0上述染色體的適應(yīng)度值為：eval(u1)=f(

7、-2.687969,5.361653) 二eval(u2)eval(u3)eval(u4)eval(u5)eval(u6)eval(u7)eval(u8)eval(u9)eval(u10)遺傳操作選擇（輪盤(pán)賭）計(jì)算適應(yīng)度總和：F=如 eval （uk）k=1每個(gè)染色體的選擇概率Pk:、eval （uk）Pk=F計(jì)算每個(gè)染色體的累計(jì)概率Qk：Qk= Epjj=i交叉（單點(diǎn)交叉）隨機(jī)選擇一個(gè)染色體串的節(jié)點(diǎn)，然后交換兩個(gè)父輩節(jié)點(diǎn)右端部分來(lái)產(chǎn)生父輩。在這里假設(shè)交叉概率為25%,即在平均水平上游25%的染色體進(jìn)行了交叉，變異（變異算子）如果被選定的染色體的被選定基因選作變異，即如果該位基因是1，則變異后

8、 就為0。將變異概率設(shè)為Pm=0.01，本題共有33*10=330個(gè)基因，希望每一代中有3.3 個(gè)變異的基因，每個(gè)基因變異的概率是相等的。因此，我們要生成一個(gè)位于0,1 之間的隨機(jī)系列。問(wèn)題的假設(shè)、符號(hào)說(shuō)明:F表示計(jì)算適應(yīng)度總和；Pk表示每個(gè)染色體的選擇概率；Qk表示計(jì)算每個(gè)染色體的累計(jì)概率 x1,x2表示決策變量。五、模型的求解：六、模型的評(píng)價(jià)和推廣：1 .評(píng)價(jià)：.優(yōu)點(diǎn)：對(duì)可行解表示的廣泛性；群體搜索特性；不需要輔助信息；內(nèi)在啟發(fā)式隨機(jī)搜索特性；遺傳算法在搜索過(guò)程中不容易陷入局部最優(yōu)，即使在所定義的適應(yīng)度函數(shù) 是不連續(xù)的，非規(guī)則的或有噪音的情況下，也能以很大的概率找到全局最優(yōu) 解；遺傳算法具有固有的并行性和并行計(jì)算能力；遺傳算法具有可擴(kuò)展性，易于同別的技術(shù)混合。.缺點(diǎn)：編碼不規(guī)則或編碼存在表示的不規(guī)則性；單一的遺傳算法編碼不能全面的將優(yōu)化問(wèn)題的約束表示出來(lái)；遺傳算法通常的效率比比其他傳統(tǒng)的優(yōu)化