遺傳算法課件1

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

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

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

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

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

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

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

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