《遺傳算法算例》PPT課件.ppt

1、第四章基于遺傳算法的隨機優(yōu)化搜索4.1基本概念4.2基本遺傳算法4.3遺傳算法應用實例4.4遺傳算法的特點和優(yōu)勢4.1基本概念1。個體和群體個體是通過模擬生物個體而產(chǎn)生的問題(通常是問題的解決方案)中對象的名稱，每個個體也是搜索空間中的一個點。種群是由模擬生物種群的干燥個體組成的群體，通常是整個搜索空間的一小部分。2.適合度和適合度功能適合度是一種衡量標準，旨在通過參照生物個體對環(huán)境的適應程度來表示所討論的個體對象的優(yōu)點和缺點。適應度函數(shù)是問題中所有個體與其適應度之間的對應關系。它通常是一個真實的函數(shù)。該函數(shù)是遺傳算法中指導搜索的評價函數(shù)。染色體和基因染色體是以某種字符串形式對個體的編碼表示。

2、字符串中的字符也稱為基因。例如，個體染色體9-1001 (2，5，6)-010-101-110。4.遺傳操作也叫遺傳算子，是關于染色體操作的。遺傳算法中有三種遺傳操作：選擇-繁殖、交叉、交換、交配或雜交、變異，選擇-繁殖的通常做法是：對于一個規(guī)模為N的種群S，根據(jù)每個染色體xiS的選擇概率P(xi)所確定的選擇機會，從S中隨機選擇N次。交叉是在兩條染色體的某個位置進行基因交換。S1=01000101，s2=10011011可視為原始染色體S1和s2的后代。例如，讓s1=01001011，s2=10010101，并交換接下來的四個基因，也就是說，變異是改變?nèi)旧w上某個(某些)位置的基因。例如，讓

3、染色體s=11001101將第三個位置的0改變?yōu)?，即S=11001101101=S。S也可以視為原始染色體S的后代染色體.4.2基本遺傳算法，算法中的一些控制參數(shù)：交叉率是參與交叉操作的染色體數(shù)與染色體總數(shù)的比值，記錄為Pc，其取值范圍一般為0.40.99。突變率是指所有染色體中突變基因的數(shù)量與基因總數(shù)的比率，記錄為Pm，一般范圍為0.00010.1。在基本遺傳算法步驟1中，給定種群規(guī)模n、交叉率Pc和變異率Pm、代數(shù)t，在搜索空間u中定義適應度函數(shù)f(x)；12)在u中隨機生成n個個體S1、S2、sn，形成初始種群s=S1、S2、sn，并設置代數(shù)計數(shù)器t=1；第三步，計算S中每個個體的適應

4、度；在步驟4中，如果滿足終止條件，則將在S中具有最大適應度的個體作為結果，并且算法結束。第五步，根據(jù)選擇概率P(xi)確定的選擇機會，每次從S中隨機選擇一個個體，復制其染色體N次，然后復制得到的N條染色體組成群體S1；步驟6，根據(jù)交叉率Pc確定的參與交叉的C染色體數(shù)目，從S1隨機確定C染色體，配對并進行交叉操作，用新染色體替換原染色體，得到群體S2；步驟7，根據(jù)變異率Pm確定的變異頻率m，從S2隨機確定m條染色體，分別進行變異操作，用生成的新染色體替換原染色體，得到群體S3；第八步，將S3人口作為新一代人口，即將S替換為S3，t=t 1，轉(zhuǎn)到第三步；例4.1用遺傳算法求解區(qū)間0，31中二次函數(shù)

5、y=x2的最大值。對原問題的分析可以轉(zhuǎn)化為尋找能使Y在區(qū)間0，31取最大值的點A的問題。那么，0，31中的點x是一個個體，函數(shù)值f(x)可以看作是x的適應度，區(qū)間0，31是一個(解)空間。因此，只要能給出個體X的適當染色體編碼，這個問題就可以用遺傳算法來解決。(1)設定群體大小，編碼染色體并生成初始群體。將人口規(guī)模設置為4；用5位二進制數(shù)編碼染色體；選擇下列個體形成初始群體13360 S1=13(01101)，S2=24 (11000)，S3=8 (01000)，S4=19 (10011)。(2)定義并采用適應度函數(shù)：f (x)=x2。(3)計算每個種群首先，計算種群中每個個體的適應度f (si)，S1為S1=13 (01101)，S2=24 (11000)，S3=8 (01000)，S4=19 (10011)。很容易找到f(S1)=f(13)=132=169 f(S2)=242=576 f(S3)=f(8)=82=64 f(S4)=f(19)=192=3