遺傳算法的一些實(shí)例課件

遺傳算法(GA)的肇始“活的有機(jī)體是解決問題的專家。它們所表現(xiàn)出來的各種才能足以使最好的計(jì)算機(jī)程序自慚形穢。這種現(xiàn)象尤其令計(jì)算機(jī)科學(xué)家們感到痛楚。計(jì)算機(jī)科學(xué)家們?yōu)榱四撤N算法可能花費(fèi)數(shù)月乃至數(shù)年的腦力勞動(dòng)，而有機(jī)體則能通過進(jìn)化和自然選擇這樣一種顯然并非定向進(jìn)行的機(jī)制獲得這種能力。”---JohnHolland遺傳算法的思想Darwin的進(jìn)化論----“自然選擇、適者生存”特定環(huán)境的考驗(yàn)種群中個(gè)體的選擇種群中的交叉繁殖種群中個(gè)體的變異

上述操作反復(fù)執(zhí)行，個(gè)體逐漸優(yōu)化遺傳算法的手工模擬計(jì)算示例為更好地理解遺傳算法的運(yùn)算過程，下面用手工計(jì)算來簡(jiǎn)單地模擬遺傳算法的各個(gè)主要執(zhí)行步驟。

例：求下述二元函數(shù)的最大值：maxf(x1,x2)=x12+x22s.t.x1

{1,2,3,4,5,6,7}x2

{1,2,3,4,5,6,7}

(1)個(gè)體編碼遺傳算法的運(yùn)算對(duì)象是表示個(gè)體的符號(hào)串，所以必須把變量x1,x2編碼為一種符號(hào)串。本題中，用無符號(hào)二進(jìn)制整數(shù)來表示。因x1,x2為0~7之間的整數(shù)，所以分別用3位無符號(hào)二進(jìn)制整數(shù)來表示，將它們連接在一起所組成的6位無符號(hào)二進(jìn)制數(shù)就形成了個(gè)體的基因型，表示一個(gè)可行解。

例如，基因型X＝101110所對(duì)應(yīng)的表現(xiàn)型是：x＝[5，6]。個(gè)體的表現(xiàn)型x和基因型X之間可通過編碼和解碼程序相互轉(zhuǎn)換。本例中，我們采用與適應(yīng)度成正比的概率來確定各個(gè)個(gè)體復(fù)制到下一代群體中的數(shù)量。其具體操作過程是：

?先計(jì)算出群體中所有個(gè)體的適應(yīng)度的總和fi

(i=1.2,…,M);

?其次計(jì)算出每個(gè)個(gè)體的相對(duì)適應(yīng)度的大小fi/fi

，它即為每個(gè)個(gè)體被遺傳到下一代群體中的概率，

?每個(gè)概率值組成一個(gè)區(qū)域，全部概率值之和為1；

?最后再產(chǎn)生一個(gè)0到1之間的隨機(jī)數(shù)，依據(jù)該隨機(jī)數(shù)出現(xiàn)在上述哪一個(gè)概率區(qū)域內(nèi)來確定各個(gè)個(gè)體被選中的次數(shù)。0124%24%17%35%1#2#3#4#個(gè)體編號(hào)初始群體p(0)適值占總數(shù)的百分比總和1234011101101011011100111001343425500.240.240.170.351431選擇次數(shù)選擇結(jié)果1102011101111001101011111001x1x235533471(5)交叉運(yùn)算交叉運(yùn)算是遺傳算法中產(chǎn)生新個(gè)體的主要操作過程，它以某一概率相互交換某兩個(gè)個(gè)體之間的部分染色體。本例采用單點(diǎn)交叉的方法，其具體操作過程是：

?先對(duì)群體進(jìn)行隨機(jī)配對(duì)；

?其次隨機(jī)設(shè)置交叉點(diǎn)位置；

?最后再相互交換配對(duì)染色體之間的部分基因。選擇結(jié)果011101111001101011111001配對(duì)情況交叉點(diǎn)位置個(gè)體編號(hào)12341-23-41-2：23-4：4交叉結(jié)果011001111101101001111011可以看出，其中新產(chǎn)生的個(gè)體“111101”、“111011”的適應(yīng)度較原來兩個(gè)個(gè)體的適應(yīng)度都要高。(6)變異運(yùn)算變異運(yùn)算是對(duì)個(gè)體的某一個(gè)或某一些基因座上的基因值按某一較小的概率進(jìn)行改變，它也是產(chǎn)生新個(gè)體的一種操作方法。本例中，我們采用基本位變異的方法來進(jìn)行變異運(yùn)算，其具體操作過程是：

?首先確定出各個(gè)個(gè)體的基因變異位置，下表所示為隨機(jī)產(chǎn)生的變異點(diǎn)位置，其中的數(shù)字表示變異點(diǎn)設(shè)置在該基因座處；?然后依照某一概率將變異點(diǎn)的原有基因值取反。對(duì)群體P(t)進(jìn)行一輪選擇、交叉、變異運(yùn)算之后可得到新一代的群體p(t+1)。個(gè)體編號(hào)1234交叉結(jié)果011001111101101001111011變異結(jié)果變異點(diǎn)4526011101111111111001111010子代群體p(1)011101111111111001111010個(gè)體編號(hào)初始群體p(0)適值fi(x1,x2)占總數(shù)的百分比fi/f1234011101101011011100111001343425500.240.240.170.35x1x235533471fi=143fmax=50f=35.75選擇結(jié)果011101111001101011111001配對(duì)情況交叉點(diǎn)位置1-23-41-2：23-4：4交叉結(jié)果011001111101101001111011選擇次數(shù)1102變異結(jié)果變異點(diǎn)4526011101111111111001111010子代群體p(1)適值fi(x1,x2)占總數(shù)的百分比fi/f011101111111111001111010349850530.140.420.210.23x1x235777172fi=253fmax=98f=58.75遺傳算法的一個(gè)實(shí)例求解方程：將方程求解問題轉(zhuǎn)化為生存問題：解一定在[0,10]之間，將區(qū)間[0,10]劃分成若干個(gè)小區(qū)間，設(shè)想每個(gè)小區(qū)間為一個(gè)生物個(gè)體，使下列表達(dá)式最小的個(gè)體有最好的生存能力，該個(gè)體即為解。遺傳算法的一個(gè)實(shí)例如何找到這個(gè)最優(yōu)個(gè)體？可通過Darwin的進(jìn)化論由初始個(gè)體經(jīng)過代代演化，逐漸進(jìn)化出來。如何將生物進(jìn)化的操作轉(zhuǎn)化為計(jì)算機(jī)可以執(zhí)行的操作？通過編碼表征生物個(gè)體，則生物之間的演化轉(zhuǎn)化為編碼的變化。定義適應(yīng)度函數(shù)：選擇（適應(yīng)度較大的個(gè)體）

步驟二：選擇為何取倒數(shù)？0.10.30.20.40.10.10.30.40.20.60.41.0ABCD隨機(jī)產(chǎn)生[0,1]之間的數(shù)RN，選擇個(gè)體RN個(gè)體ABCD選中的優(yōu)勢(shì)個(gè)體進(jìn)行交叉-----由父?jìng)€(gè)體生成子個(gè)體步驟三：交叉相同的兩個(gè)父?jìng)€(gè)體生成相同的兩個(gè)子個(gè)體變異操作在個(gè)體中隨機(jī)選擇一位，改變?cè)撐坏闹挡襟E四：變異交叉和變異操作均以一定概率進(jìn)行遺傳算法各步驟的評(píng)價(jià)選擇---優(yōu)勝劣汰

選擇操作為種群提供了演進(jìn)的方向交叉---優(yōu)優(yōu)組合

交叉操作的作用在于匯集散布于不同個(gè)體間的局部?jī)?yōu)勢(shì)模式變異---尋找新模式

變異操作是種群向外擴(kuò)展的觸角(隨機(jī))好的變異將保留，壞的淘汰遺傳算法的總體評(píng)價(jià)優(yōu)點(diǎn)解決問題的方法具有普適性全局收斂性（依概率收斂）能解決的問題范圍很廣不足求得的解為近似的數(shù)值解對(duì)于經(jīng)典數(shù)學(xué)可以解決的問題，效率較低遺傳算法的適應(yīng)度函數(shù)求函數(shù)的全局極小值取的初始區(qū)間，例如：[-10,10]將此區(qū)間分為1024個(gè)小區(qū)間，然后編碼若求全局極大值(且為正)，可直接取函數(shù)值為其適應(yīng)度值，據(jù)此作概率選擇；若求全局極小值(且為正)，可取函數(shù)值的倒數(shù)為其適應(yīng)度值，據(jù)此作概率選擇。若不全為負(fù)，可統(tǒng)一加上一個(gè)正數(shù)，使為正。個(gè)體編碼取長(zhǎng)度為N的數(shù)字串，串中數(shù)字互不重復(fù)，取值范圍為[1,N]之間的整數(shù)。則每一個(gè)數(shù)字串代表一個(gè)個(gè)體，個(gè)體中數(shù)字出現(xiàn)的位置表征路徑中城市出現(xiàn)的順序。初始種群令種群中有M個(gè)個(gè)體，可隨機(jī)產(chǎn)生M個(gè)數(shù)字串構(gòu)成初始種群。例如：將數(shù)字串1234…N上的數(shù)字進(jìn)行隨機(jī)的交換步驟一：初始化適應(yīng)度的計(jì)算步驟二：適應(yīng)度選擇12345對(duì)于個(gè)體，適應(yīng)度為：被選中作為父?jìng)€(gè)體的概率：選擇M次重新生成種群TSP中交叉算子的特點(diǎn)

要保證生成的解為有效解從一個(gè)父?jìng)€(gè)體中隨機(jī)選取一段子串A，在另一個(gè)父?jìng)€(gè)體中將A中出現(xiàn)的數(shù)字去掉形成串B，AB為一個(gè)子串步驟三：交叉操作此外還有多種交叉算子反復(fù)執(zhí)行步驟二、三、四結(jié)束判定循環(huán)執(zhí)行G次(例如G=500)后當(dāng)最優(yōu)個(gè)體的總路徑長(zhǎng)度小于預(yù)期時(shí)步驟五：中國(guó)各省會(huì)城市的運(yùn)行結(jié)果4.1遺傳算法簡(jiǎn)介

智能優(yōu)化計(jì)算簡(jiǎn)單實(shí)例產(chǎn)生初始種群計(jì)算適應(yīng)度4.1.4遺傳算法的基本操作

0001100000010111100100000001011001110100101010101011100101101001011011110000000110011101000001010011（8）（5）（2）（10）（7）（12）（5）（19）（10）（14）4.1遺傳算法簡(jiǎn)介

智能優(yōu)化計(jì)算簡(jiǎn)單實(shí)例選擇4.1.4遺傳算法的基本操作

個(gè)體染色體適應(yīng)度選擇概率累積概率10001100000820101111001530000000101241001110100105101010101076111001011012710010110115811000000011991001110100101000010100111488＋5＋2＋10＋7＋12＋5＋19＋10＋140.08695758＋5＋2＋10＋7＋12＋5＋19＋10＋140.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521744.1遺傳算法簡(jiǎn)介

智能優(yōu)化計(jì)算簡(jiǎn)單實(shí)例選擇4.1.4遺傳算法的基本操作

個(gè)體染色體適應(yīng)度選擇概率累積概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.0000004.1遺傳算法簡(jiǎn)介

智能優(yōu)化計(jì)算簡(jiǎn)單實(shí)例選擇在0～1之間產(chǎn)生一個(gè)隨機(jī)數(shù)：4.1.4遺傳算法的基本操作

個(gè)體染色體適應(yīng)度選擇概率累積概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.0000000.0702210.5459290.7845670.4469300.5078930.2911980.7163400.2709010.3714350.854641淘汰！淘汰！00011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100114.1遺傳算法簡(jiǎn)介

智能優(yōu)化計(jì)算簡(jiǎn)單實(shí)例交叉4.1.4遺傳算法的基本操作

00011000001110010110110000000110011101001010101010111001011010010110111001110100110000000100010100110001111010000001011011110011000010011101000001100111010011000000010100114.1遺傳算法簡(jiǎn)介

智能優(yōu)化計(jì)算簡(jiǎn)單實(shí)例變異4.1.4遺傳算法的基本操作

000110000011100101101100000001100111010010101010101110010110100101101111000000011001110100000101001100011110100000010110111100110000100101010000011001110100110000000101001100011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100110001111010000001011011110011000010011101000001100111010011000000010100114.2基本遺傳算法

智能優(yōu)化計(jì)算問題的提出

一元函數(shù)求最大值：4.2.1簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例

4.2基本遺傳算法

智能優(yōu)化計(jì)算問題的提出

用微分法求取f(x)的最大值：解有無窮多個(gè)：4.2.1簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例

4.2基本遺傳算法

智能優(yōu)化計(jì)算問題的提出

當(dāng)i為奇數(shù)時(shí)xi對(duì)應(yīng)局部極大值點(diǎn)，i為偶數(shù)時(shí)xi對(duì)應(yīng)局部極小值。x19即為區(qū)間[-1,2]內(nèi)的最大值點(diǎn)：此時(shí)，函數(shù)最大值f(x19)比f(1.85)=3.85稍大。4.2.1簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例

4.2基本遺傳算法

智能優(yōu)化計(jì)算編碼

表現(xiàn)型：x基因型：二進(jìn)制編碼（串長(zhǎng)取決于求解精度）

串長(zhǎng)與精度之間的關(guān)系：若要求求解精度到6位小數(shù)，區(qū)間長(zhǎng)度為2-(-1)＝3，即需將區(qū)間分為3/0.000001=3×106等份。所以編碼的二進(jìn)制串長(zhǎng)應(yīng)為22位。4.2.1簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例

4.2基本遺傳算法

智能優(yōu)化計(jì)算產(chǎn)生初始種群

產(chǎn)生的方式：隨機(jī)產(chǎn)生的結(jié)果：長(zhǎng)度為22的二進(jìn)制串產(chǎn)生的數(shù)量：種群的大?。ㄒ?guī)模），如30，50，…11111011000110101011101001000010011100111001

10000000000……4.2.1簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例

4.2基本遺傳算法

智能優(yōu)化計(jì)算計(jì)算適應(yīng)度

不同的問題有不同的適應(yīng)度計(jì)算方法本例：直接用目標(biāo)函數(shù)作為適應(yīng)度函數(shù)①將某個(gè)體轉(zhuǎn)化