遺傳算法課件1

1、1.遺傳算法原理及應(yīng)用，趙鵬，2，1。遺傳算法起源于1975年由美國(guó)的J.Holland教授在其專著自然與人工系統(tǒng)的適應(yīng)性中首次提出，是一種借鑒生物學(xué)中自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法。1.基本原則；3.生物進(jìn)化循環(huán)圖；4.遺傳算法中生物遺傳概念的對(duì)應(yīng)關(guān)系：5.遺傳算法的主要特征：進(jìn)化發(fā)生在解的編碼中，在生物學(xué)術(shù)語中稱為染色體。因?yàn)榻馐蔷幋a的，所以優(yōu)化問題的所有性質(zhì)都是通過編碼來研究的。編碼和解碼是遺傳算法的一個(gè)課題。自然選擇法則決定了哪條染色體產(chǎn)生的后代多于平均水平。在遺傳算法中，自適應(yīng)函數(shù)是通過優(yōu)化問題的目標(biāo)人工構(gòu)造的，這樣好的染色體可以產(chǎn)生比一般的后代更多的后代。當(dāng)染色體結(jié)合時(shí)，父母

2、基因的結(jié)合使孩子保持父母的特征。當(dāng)染色體結(jié)合在一起時(shí)，隨機(jī)變異會(huì)導(dǎo)致后代和父母之間的差異。遺傳算法的主要處理步驟是首先對(duì)優(yōu)化問題的解進(jìn)行編碼，稱為染色體，組成編碼的元素稱為基因。編碼的目的主要是優(yōu)化問題解的表達(dá)，便于遺傳算法的計(jì)算。二是自適應(yīng)函數(shù)的構(gòu)造和應(yīng)用。適應(yīng)函數(shù)基本上取決于優(yōu)化問題的目標(biāo)函數(shù)。在適應(yīng)度函數(shù)被確定之后，自然選擇規(guī)則確定哪些染色體適合存活，哪些染色體被由適應(yīng)度函數(shù)值大小確定的概率分布消除。幸存的染色體形成一個(gè)群體，形成一個(gè)可以繁殖下一代的群體。第三是染色體的組合。父母的遺傳組合是通過代碼之間的交配產(chǎn)生下一代。新一代的產(chǎn)生是一個(gè)生殖過程，它產(chǎn)生了一個(gè)新的解決方案。最后，變異?；?/p>

3、因變異可能發(fā)生在新解的產(chǎn)生過程中，這改變了一些解的編碼，使解更加遍歷?；具z傳算法，簡(jiǎn)單遺傳算法(簡(jiǎn)稱SGA)，是戈德堡總結(jié)的最基本的遺傳算法之一。它的遺傳進(jìn)化過程簡(jiǎn)單易懂，是其他遺傳算法的雛形和基礎(chǔ)?；具z傳算法的組成，(1)編碼(生成初始種群)，(2)適應(yīng)度函數(shù)，(3)遺傳算子(選擇、交叉、變異)，(4)運(yùn)行參數(shù)，(8)函數(shù)優(yōu)化實(shí)例，并求出下列一元函數(shù)的最大值：x-1，2，求解結(jié)果精確到小數(shù)點(diǎn)后6位。遺傳算法通過某種編碼機(jī)制將對(duì)象抽象成由特定符號(hào)按一定順序排列的字符串。正如生物遺傳的研究始于染色體一樣，染色體是一串基因。SGA使用二進(jìn)制字符串進(jìn)行編碼。代碼9，SGA對(duì)于本例的代碼，由于區(qū)間

4、長(zhǎng)度為3，解的結(jié)果精確到小數(shù)點(diǎn)后6位，由自變量定義的區(qū)間可分為3106個(gè)相等的部分。由于221 3106 222，本例中二進(jìn)制碼的長(zhǎng)度至少需要22位，本例中的編碼過程實(shí)質(zhì)上將區(qū)間-1，2中的相應(yīng)實(shí)值轉(zhuǎn)換為二進(jìn)制字符串(b21b20b0)。10，幾個(gè)術(shù)語，基因型：1000101110101000111，表型：0.637197，編碼，解碼，個(gè)體(染色體)，基因，11，初始群體SGA使用隨機(jī)方法生成一組幾個(gè)個(gè)體，這稱為初始群體。初始種群中的個(gè)體數(shù)量稱為種群規(guī)模。適應(yīng)度函數(shù)遺傳算法通過適應(yīng)度函數(shù)值來評(píng)估個(gè)體(解)的質(zhì)量。適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。適應(yīng)度函數(shù)是遺傳算法進(jìn)化過程的驅(qū)動(dòng)力，也是自然選擇

5、的唯一標(biāo)準(zhǔn)。它的設(shè)計(jì)應(yīng)該與解決問題本身的要求相結(jié)合。12、選擇算子，遺傳算法利用選擇操作實(shí)現(xiàn)種群中個(gè)體的適者生存：適應(yīng)性強(qiáng)的個(gè)體很有可能被遺傳到下一代種群中；體質(zhì)差的人不太可能遺傳給下一代。選擇操作的任務(wù)就是這樣選擇SGA的選擇算子采用輪盤賭選擇方法。13，輪盤選擇信號(hào)，輪盤選擇方法，14，輪盤選擇方法，輪盤選擇也稱為比例選擇算子，其基本思想是每個(gè)個(gè)體被選擇的概率與其適應(yīng)度函數(shù)值成比例。假設(shè)種群規(guī)模為n，個(gè)體I的適應(yīng)度為fi，選擇個(gè)體I遺傳給下一代種群的概率為：15，輪盤賭選擇方法的實(shí)現(xiàn)步驟，(1)計(jì)算種群中所有個(gè)體的適應(yīng)度函數(shù)值(需要解碼)；(2)利用比例選擇算子公式，計(jì)算每個(gè)個(gè)體被選擇并遺

6、傳給下一代群體的概率；(3)使用模擬賭博操作(即，生成0到1之間的隨機(jī)數(shù)以匹配每個(gè)個(gè)體繼承到下一代群體的概率)來確定每個(gè)個(gè)體是否繼承到下一代群體。16，交叉操作符，即所謂的交叉操作，是指兩對(duì)染色體按照交叉概率Pc以某種方式交換它們的一些基因，從而形成兩個(gè)新的個(gè)體。交叉操作是遺傳算法區(qū)別于其他進(jìn)化算法的一個(gè)重要特征。它在遺傳算法中起著關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法。SGA的交叉算子采用單點(diǎn)交叉算子。17，單點(diǎn)交叉操作，交叉前：00000 | 011100000100011100 | 0000011111000101交叉后：00000 | 000001111000111100000。遺傳算法中的

7、變異操作是產(chǎn)生新個(gè)體的輔助方法，它決定了遺傳算法的局部搜索能力，保持了種群的多樣性。交叉操作和變異操作相互配合，完成搜索空間的全局搜索和局部搜索。SGA的變異算子采用基本變異算子。19、基本變異操作符，基本變異操作符是指對(duì)一個(gè)或幾個(gè)由個(gè)體編碼串隨機(jī)指定的基因進(jìn)行的變異操作。對(duì)于基本遺傳算法中以二進(jìn)制編碼符號(hào)串表示的個(gè)體，如果某個(gè)需要變異操作的基因座上的原始基因值為0，變異操作會(huì)將其改為1；相反，如果原始基因值為1，變異操作會(huì)將其更改為0。20，基本變異算子的執(zhí)行過程，變異前：00000111000000010000，變異后：000001110000010000，變異點(diǎn)，21，運(yùn)行參數(shù)，(1)M

8、:種群規(guī)模，(2)T:遺傳操作的終止進(jìn)化代數(shù)，(3)Pc:24，原始問題的分析可以轉(zhuǎn)化為尋找點(diǎn)A的問題，該點(diǎn)A可以使Y取區(qū)間0，31中的最大值。那么，0，31中的點(diǎn)x是一個(gè)個(gè)體，函數(shù)值f(x)可以看作是x的適應(yīng)度，區(qū)間0，31是一個(gè)(解)空間。因此，只要能給出個(gè)體X的適當(dāng)染色體編碼，這個(gè)問題就可以用遺傳算法來解決。25，解決方案(1)設(shè)置群體大小，編碼染色體，并生成初始群體。將人口規(guī)模設(shè)置為4；用5位二進(jìn)制數(shù)編碼染色體；選擇下列個(gè)體形成初始群體13360 S1=13(01101)，S2=24 (11000)，S3=8 (01000)，S4=19 (10011)。(2)適應(yīng)度函數(shù)的定義和取值如下：f (x)=x2，26，(3，27)，首先計(jì)算人口中每個(gè)個(gè)體的適應(yīng)度f(si):S1=13(01101)，S2=24 (11000)，S3=8 (01000)，S4=19 (10011)。很容易發(fā)現(xiàn)，f(S1)=f(13)=132=