《軟計(jì)算方法》PPT課件

《《軟計(jì)算方法》PPT課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第四章遺傳算法的基本實(shí)現(xiàn)技術(shù)4.1編碼方法4.2適應(yīng)度函數(shù)4.3選擇算子4.4交叉算子4.5變異算子4.6遺傳算法的運(yùn)行參數(shù)4.7約束條件處理方法4.1編碼方法編碼是應(yīng)用遺傳算法要解決的首要問(wèn)題,也是設(shè)計(jì)遺傳算法的關(guān)鍵.編碼方法除了決定個(gè)體的染色體排列形式以外,它還決定了個(gè)體從搜索空間的基因型轉(zhuǎn)換到解空間的表現(xiàn)型時(shí)的解碼方法.編碼方法也影響到交叉算子、變異算子等遺傳算子的運(yùn)算方法因此，編碼方法在很大程度上決定了如何進(jìn)行群體的遺傳進(jìn)化運(yùn)算以及遺傳進(jìn)化運(yùn)算效率。迄今為止，人們已經(jīng)提出了很多種不同的編碼方法

2、，這些編碼方法可以分為三大類：二進(jìn)制編碼方法浮點(diǎn)數(shù)編碼方法符號(hào)編碼方法二進(jìn)制編碼方法二進(jìn)制編碼方法是遺傳算法中最常用的一種編碼方法，它使用的編碼符號(hào)集為{0，1}，它所構(gòu)成的個(gè)體基因型是一個(gè)二進(jìn)制編碼符號(hào)串。二進(jìn)制編碼符號(hào)串的長(zhǎng)度與問(wèn)題要求的求解精度有關(guān)。假設(shè)一參數(shù)的取值范圍是我們用長(zhǎng)度為的二進(jìn)制表示該參數(shù)二進(jìn)制編碼的精度為二進(jìn)制編碼方法的優(yōu)點(diǎn)：編碼、解碼操作簡(jiǎn)單可行交叉、變異等遺傳操作便于實(shí)現(xiàn)符合最小字符集編碼原則便于利用模式定理對(duì)算法進(jìn)行理論分析浮點(diǎn)數(shù)編碼方法對(duì)于一些多維、高精度要求的連續(xù)函數(shù)優(yōu)化

3、問(wèn)題，使用二進(jìn)制編碼來(lái)表示個(gè)體時(shí)會(huì)有一些不利之處：(1)使用二進(jìn)制編碼存在著連續(xù)函數(shù)離散化時(shí)的映射誤差(2)個(gè)體編碼串較短時(shí)，可能達(dá)不到精度要求；而個(gè)體編碼串的長(zhǎng)度較長(zhǎng)時(shí)，雖然能提高編碼精度，但卻會(huì)使遺傳算法的搜索空間急劇擴(kuò)大例:使用二進(jìn)制方法來(lái)處理一個(gè)含有100個(gè)決策變量的優(yōu)化，每個(gè)決策變量的取值范圍是[-250,250],要求精度是小數(shù)點(diǎn)后面五位，即為0.00001,則　為26這樣每個(gè)個(gè)體必須用2600位長(zhǎng)的二進(jìn)制編碼符號(hào)串來(lái)表示。相應(yīng)的搜索空間大約是２２６００為改變二進(jìn)制編碼方法的缺點(diǎn)，人們提出

4、了浮點(diǎn)數(shù)編碼方法．浮點(diǎn)數(shù)編碼方法指?jìng)€(gè)體的每個(gè)基因值用某一范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)來(lái)表示。個(gè)體的編碼長(zhǎng)度等于其決策變量的個(gè)數(shù)浮點(diǎn)數(shù)編碼方法使用的是決策變量的真實(shí)值，所以該方法也稱為真值編碼方法。例設(shè)一個(gè)優(yōu)化問(wèn)題含有五個(gè)變量　　　　，每個(gè)變量都有其對(duì)應(yīng)的上下限就表示一個(gè)個(gè)體的基因型，對(duì)應(yīng)的表現(xiàn)型為X=[5.80,6.90,3.50,3.80,5.00]在浮點(diǎn)數(shù)編碼的ＧＡ算法中的注意要點(diǎn)(1)必須保證給定的基因值在給定的范圍內(nèi)(2)GA算法中所使用的交叉和變異算子必須使運(yùn)算結(jié)果在所給范圍(3)當(dāng)用多個(gè)字節(jié)來(lái)表示一

5、個(gè)基因時(shí)，交叉運(yùn)算必須在兩個(gè)基因的分界字節(jié)處進(jìn)行，而不能在某個(gè)基因的中間字節(jié)分隔處進(jìn)行。浮點(diǎn)數(shù)編碼方法的優(yōu)點(diǎn)：(1)適合于在ＧＡ中表示范圍較大的數(shù)(2)適合于精度要求較高的ＧＡ(3)便于較大空間的遺傳搜索(4)改善了ＧＡ的計(jì)算的復(fù)雜性，提高了運(yùn)算效率(5)便于ＧＡ與經(jīng)典的優(yōu)化算法的使用符號(hào)編碼方法指?jìng)€(gè)體染色體編碼串中基因值取自一個(gè)無(wú)數(shù)值含義，而只有代碼含義的符號(hào)集?？梢允且粋€(gè)字母表{A,B,C,…}也可以是一個(gè)數(shù)字序號(hào)集{1,2,3,…}還可以是一個(gè)代碼表{A1,A2,A3,…}如ＴＳＰ問(wèn)題，假設(shè)有n

6、個(gè)城市C1C2…Cn，將各個(gè)城市的代碼按其被訪問(wèn)的順序連接起來(lái)，可以構(gòu)成一條旅行路線的個(gè)體Ｘ＝［Ｃ１，Ｃ２，…，Ｃn]4.2適應(yīng)度函數(shù)生物學(xué)家使用適應(yīng)度這個(gè)術(shù)語(yǔ)來(lái)度量某個(gè)物種對(duì)于其生存環(huán)境的適應(yīng)程度，適應(yīng)度高的物種有更多的繁殖機(jī)會(huì)，而對(duì)環(huán)境適應(yīng)程度較低的物種，其繁殖機(jī)會(huì)就較低，甚至回逐步滅絕。ＧＡ使用這個(gè)概念來(lái)度量群體中各個(gè)個(gè)體在優(yōu)化計(jì)算中有可能達(dá)到或接近于或有助于找到最優(yōu)解的優(yōu)良程度。度量個(gè)體適應(yīng)度的函數(shù)稱為適應(yīng)度函數(shù)目標(biāo)函數(shù)與適應(yīng)度函數(shù)轉(zhuǎn)換關(guān)系解空間目標(biāo)函數(shù)學(xué)值f(x)搜索空間適應(yīng)度F(x)適應(yīng)度

7、尺度變換實(shí)踐表明，使用上面的轉(zhuǎn)化關(guān)系來(lái)計(jì)算個(gè)體的適應(yīng)度時(shí)，有些GA會(huì)收斂得很快，也有些收斂得很慢。所以，如何確定適應(yīng)度對(duì)ＧＡ的性能有較大影響。在ＧＡ運(yùn)行初期群體中可能會(huì)有少數(shù)幾個(gè)各個(gè)的適應(yīng)度相對(duì)于其他個(gè)體來(lái)說(shuō)非常高。如果按照常用的比例選擇算子來(lái)確定個(gè)體的遺傳數(shù)量，則這幾個(gè)相對(duì)較好的個(gè)體將在下一代群體中占有較高比例，在極端情況下或群體規(guī)模較小時(shí)，新的群體甚至完全由這少數(shù)幾個(gè)個(gè)體組成。這時(shí)產(chǎn)生新個(gè)體作用較大的交叉算子不起作用。這樣就會(huì)使群體的多樣性降低。容易導(dǎo)致GA過(guò)早收斂。使GA所得到的解停留在某一局部

8、最優(yōu)點(diǎn)上。結(jié)論：我們希望在遺傳算法運(yùn)行的初期階段，算法能對(duì)一些適應(yīng)度較高的個(gè)體進(jìn)行控制，降低其適應(yīng)度與其他個(gè)體適應(yīng)度之間的差異程度，從而限制其復(fù)制的數(shù)量，以維護(hù)群體的多樣性。在ＧＡ運(yùn)行后期群體中所有個(gè)體的平均適應(yīng)度可能會(huì)接近群體中最佳個(gè)體的適應(yīng)度。即大部分個(gè)體的適應(yīng)度和最佳個(gè)體的適應(yīng)度差異不大。它們之間無(wú)競(jìng)爭(zhēng)力，都會(huì)以相接近的概率被遺傳到下一代。從而使進(jìn)化過(guò)程無(wú)競(jìng)爭(zhēng)可言。只是一種隨機(jī)的選擇過(guò)程。這就導(dǎo)致無(wú)法對(duì)某些重點(diǎn)區(qū)域進(jìn)行重點(diǎn)搜索。從而影響GA的效率。