選擇和適應(yīng)度函數(shù)20160510課件

1、11/30/202112016年年 教學(xué)公開課教學(xué)公開課選擇和適應(yīng)度函數(shù)選擇和適應(yīng)度函數(shù)計(jì)算智能導(dǎo)論電子工程學(xué)院電子工程學(xué)院尚榮華尚榮華2016.05n 問題介紹問題介紹2016年年 教學(xué)公開課教學(xué)公開課從群體中選擇優(yōu)勝個(gè)體，淘汰劣質(zhì)個(gè)體的操作叫從群體中選擇優(yōu)勝個(gè)體，淘汰劣質(zhì)個(gè)體的操作叫選擇選擇。選擇的基礎(chǔ)選擇的基礎(chǔ)是達(dá)爾文的適者生存理論；是達(dá)爾文的適者生存理論；遺傳算法本質(zhì)上是一種隨機(jī)搜索，遺傳算法本質(zhì)上是一種隨機(jī)搜索，選擇算子選擇算子則將遺傳搜索的方向則將遺傳搜索的方向引向引向 最優(yōu)解所在區(qū)域最優(yōu)解所在區(qū)域；選擇的作用選擇的作用使得群體最優(yōu)解所在區(qū)域移動(dòng)。使得群體最優(yōu)解所在區(qū)域移動(dòng)。 se

2、lection主要內(nèi)容：主要內(nèi)容：n選擇壓力選擇壓力n選擇方式選擇方式n適應(yīng)度函數(shù)適應(yīng)度函數(shù)n適應(yīng)度共享適應(yīng)度共享選擇和適應(yīng)度函數(shù)選擇和適應(yīng)度函數(shù)一、選擇壓力一、選擇壓力定義（選擇壓力）：定義（選擇壓力）： 最佳個(gè)體選中的概率與平均選中概率的比值。最佳個(gè)體選中的概率與平均選中概率的比值。n合適的選擇壓力很重要；合適的選擇壓力很重要；n選擇壓力太大容易早熟，選擇壓力太大容易早熟， 選擇壓力太小，進(jìn)化緩慢。選擇壓力太小，進(jìn)化緩慢。n我們希望初始階段選擇壓力小，最終選擇壓力大。具體如下圖所示：我們希望初始階段選擇壓力小，最終選擇壓力大。具體如下圖所示： 二、選擇方式二、選擇方式2.1 2.1 隨機(jī)選

3、擇隨機(jī)選擇n選擇幅度決定了每個(gè)個(gè)體被復(fù)制的次數(shù)；選擇幅度決定了每個(gè)個(gè)體被復(fù)制的次數(shù)； n選擇幅度由以下兩部分組成選擇幅度由以下兩部分組成: : i.i.確定染色體的期望值；確定染色體的期望值；ii.ii. 將期望值轉(zhuǎn)換為實(shí)際值，即該染色體后代個(gè)體的數(shù)目。將期望值轉(zhuǎn)換為實(shí)際值，即該染色體后代個(gè)體的數(shù)目。n經(jīng)過選擇將期望轉(zhuǎn)化為實(shí)際值即后代個(gè)數(shù)的常用的選擇方式：經(jīng)過選擇將期望轉(zhuǎn)化為實(shí)際值即后代個(gè)數(shù)的常用的選擇方式：i.i.輪盤賭的選擇方式；輪盤賭的選擇方式；ii.ii. 一次隨機(jī)采樣。一次隨機(jī)采樣。二、選擇方式二、選擇方式2.1 2.1 隨機(jī)選擇隨機(jī)選擇輪盤賭選擇輪盤賭選擇又稱比例選擇算子，其基本思

4、想是：個(gè)體被選中的概又稱比例選擇算子，其基本思想是：個(gè)體被選中的概率與其適應(yīng)度函數(shù)值成正比。率與其適應(yīng)度函數(shù)值成正比。二、選擇方式二、選擇方式step 1:計(jì)算群體的總適應(yīng)度：計(jì)算群體的總適應(yīng)度：step 2:計(jì)算染色體計(jì)算染色體vk的選擇概率的選擇概率pk ：step 3:計(jì)算染色體計(jì)算染色體vk的累積概率的累積概率 qk ：step 4:隨機(jī)產(chǎn)成一個(gè)隨機(jī)產(chǎn)成一個(gè)0, 1的數(shù)的數(shù)r；step 5:如果如果r q1, 選擇第一條染色體選擇第一條染色體 v1; 否則否則, 如果如果qk-1 r qk, 選擇第選擇第 k條染色體條染色體 vk (2 k popsize).輸入輸入: 群體群體 p(

5、t-1), c(t-1)輸出輸出: 群體群體p(t), c(t)輪盤賭選擇輪盤賭選擇的的具體步驟如下：具體步驟如下：?jiǎn)栴}問題1 1：輪盤賭選擇方輪盤賭選擇方式是式是如何如何做到個(gè)體做到個(gè)體被選中的概率與其被選中的概率與其適應(yīng)度函數(shù)值成正適應(yīng)度函數(shù)值成正比的？比的？二、選擇方式二、選擇方式輪盤賭選擇輪盤賭選擇問題問題2 2：輪盤賭選擇輪盤賭選擇結(jié)果中結(jié)果中個(gè)體個(gè)體的實(shí)際值與期望值一致嗎的實(shí)際值與期望值一致嗎? ?二、選擇方式二、選擇方式2.1 2.1 隨機(jī)選擇隨機(jī)選擇問問題題3 3：這兩種采樣方式有什么區(qū)別？這兩種采樣方式有什么區(qū)別？二、選擇方式二、選擇方式2.2 2.2 確定性選擇確定性選擇所

6、謂確定性選擇就是從父代和子代個(gè)體中選擇最優(yōu)的個(gè)體。所謂確定性選擇就是從父代和子代個(gè)體中選擇最優(yōu)的個(gè)體。具體舉例如下：具體舉例如下：n( + )-selection( 個(gè)父代，個(gè)父代， 個(gè)子代個(gè)子代, 從從 + 選擇最好的選擇最好的 )n( , )-selection( 個(gè)父代，個(gè)父代， 個(gè)子代個(gè)子代, 從從 選擇最好的選擇最好的 ) nelitist selection(貪婪選擇，在比例選擇最優(yōu)個(gè)體沒有被選擇，強(qiáng)制選擇貪婪選擇，在比例選擇最優(yōu)個(gè)體沒有被選擇，強(qiáng)制選擇) nthe generational replacement(代替換代替換) nsteady-state reproductio

7、n(穩(wěn)態(tài)再生，穩(wěn)態(tài)再生，n個(gè)最差的父代個(gè)體被子代替換個(gè)最差的父代個(gè)體被子代替換) 問問題題4 4：請(qǐng)大家分析請(qǐng)大家分析( + )-selection和和( , )-selection兩種兩種選擇選擇方式中，哪種選擇壓力大，哪種選擇壓力??？方式中，哪種選擇壓力大，哪種選擇壓力小？二、選擇方式二、選擇方式2.3 2.3 混合選擇混合選擇混合選擇同時(shí)具有隨機(jī)性和確定性，如混合選擇同時(shí)具有隨機(jī)性和確定性，如tournament selection(競(jìng)賽選擇競(jìng)賽選擇)。 競(jìng)賽選擇競(jìng)賽選擇: 競(jìng)賽規(guī)模競(jìng)賽規(guī)模= t repeat t times從種群中隨機(jī)選擇一個(gè)個(gè)體并記下其適應(yīng)度；從種群中隨機(jī)選擇一個(gè)個(gè)

8、體并記下其適應(yīng)度；返回返回t個(gè)個(gè)體中最好的個(gè)體。個(gè)個(gè)體中最好的個(gè)體。可以通過可以通過選擇選擇t, 調(diào)節(jié)選擇壓力調(diào)節(jié)選擇壓力。當(dāng)。當(dāng)t =2為二進(jìn)制競(jìng)賽選擇為二進(jìn)制競(jìng)賽選擇。問問題題5 5：請(qǐng)大家分析請(qǐng)大家分析隨著隨著t的增大的增大選擇壓力選擇壓力如何變化如何變化？三、適應(yīng)度函數(shù)三、適應(yīng)度函數(shù)3.1 3.1 定義定義遺傳算法在進(jìn)化搜索中基本不用外部信息，僅用目標(biāo)函數(shù)即適應(yīng)度函數(shù)為依遺傳算法在進(jìn)化搜索中基本不用外部信息，僅用目標(biāo)函數(shù)即適應(yīng)度函數(shù)為依據(jù)，利用種群每個(gè)個(gè)體的適應(yīng)度來指導(dǎo)搜索。據(jù)，利用種群每個(gè)個(gè)體的適應(yīng)度來指導(dǎo)搜索。需要強(qiáng)調(diào)的是，需要強(qiáng)調(diào)的是，適應(yīng)度函數(shù)值是選擇操作的依據(jù)，適應(yīng)度函數(shù)適應(yīng)

9、度函數(shù)值是選擇操作的依據(jù)，適應(yīng)度函數(shù)(fitness (fitness function)function)的選取直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解。的選取直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解。三、適應(yīng)度函數(shù)三、適應(yīng)度函數(shù) 1）對(duì)最小化問題，建立如下適應(yīng)函數(shù)和目標(biāo)函數(shù)的映射關(guān)系：）對(duì)最小化問題，建立如下適應(yīng)函數(shù)和目標(biāo)函數(shù)的映射關(guān)系： 其中，其中，cmax可以是一個(gè)輸入值或是理論上的最大值，或者是當(dāng)前所有大或最可以是一個(gè)輸入值或是理論上的最大值，或者是當(dāng)前所有大或最近近k代中代中g(shù)(x)的最大值，此時(shí)的最大值，此時(shí)cmax隨著代數(shù)會(huì)有變化。隨著代數(shù)會(huì)有變化。 2）對(duì)于最大化

10、問題，一般采用以下映射：）對(duì)于最大化問題，一般采用以下映射： 其中，其中，cmin可以是一個(gè)輸入值，或是當(dāng)前所有代或最近可以是一個(gè)輸入值，或是當(dāng)前所有代或最近k代中代中g(shù)(x)的最小值。的最小值。否則若, 0)(),()(maxmaxcxgxgcxf否則若, 00)(,)()(minmincxgcxgxf三、適應(yīng)度函數(shù)三、適應(yīng)度函數(shù) 3.2 3.2 適應(yīng)度變換適應(yīng)度變換n引例：引例：對(duì)于最大化問題對(duì)于最大化問題，假定群體中有以下，假定群體中有以下5個(gè)個(gè)體，其適應(yīng)度分別為：個(gè)個(gè)體，其適應(yīng)度分別為： 100, 0.4, 0.3, 0.2, 0.1 -最好個(gè)體的適應(yīng)度為其余個(gè)體適應(yīng)度和的最好個(gè)體的適

11、應(yīng)度為其余個(gè)體適應(yīng)度和的100倍！倍！可以對(duì)適應(yīng)度做如下變換：可以對(duì)適應(yīng)度做如下變換：200, 100.4, 100.3, 100.2, 100.1 -比較合理的情況！比較合理的情況！n定義：定義：這種適應(yīng)度的縮放調(diào)整稱為適應(yīng)度變換。這種適應(yīng)度的縮放調(diào)整稱為適應(yīng)度變換。n適應(yīng)度變換有兩個(gè)目的：適應(yīng)度變換有兩個(gè)目的： 維持個(gè)體之間的合理差距，加速競(jìng)爭(zhēng)；維持個(gè)體之間的合理差距，加速競(jìng)爭(zhēng)； 避免個(gè)體之間的差距過大，限制競(jìng)爭(zhēng)。避免個(gè)體之間的差距過大，限制競(jìng)爭(zhēng)。假定第假定第k個(gè)染色體的原始的適應(yīng)度為個(gè)染色體的原始的適應(yīng)度為fk , 變換后的適應(yīng)度變換后的適應(yīng)度 fk為為: fk = g( fk ) 函數(shù)

12、函數(shù)g() 根據(jù)采用的形式不同會(huì)產(chǎn)生不同的變換方法，具體如下：根據(jù)采用的形式不同會(huì)產(chǎn)生不同的變換方法，具體如下： n線性變換線性變換bfafkkn 指數(shù)變換指數(shù)變換kkffminmaxmin, 01 ()kkfffff對(duì)于最大化問題n歸一化變換歸一化變換tfkkef/n boltzmann變換變換三、適應(yīng)度函數(shù)三、適應(yīng)度函數(shù)四、適應(yīng)度共享四、適應(yīng)度共享n共享函數(shù)法根據(jù)個(gè)體某個(gè)距離內(nèi)與其他個(gè)體的臨近程度來確定該個(gè)體共享函數(shù)法根據(jù)個(gè)體某個(gè)距離內(nèi)與其他個(gè)體的臨近程度來確定該個(gè)體的適應(yīng)度應(yīng)改變多少。的適應(yīng)度應(yīng)改變多少。n在擁擠的峰周圍的個(gè)體的復(fù)制概率受到抑制，利于其他個(gè)體產(chǎn)生后代。在擁擠的峰周圍的個(gè)體

13、的復(fù)制概率受到抑制，利于其他個(gè)體產(chǎn)生后代。n適應(yīng)度共享可用于多峰搜索適應(yīng)度共享可用于多峰搜索, , 共享函數(shù)的作用在于根據(jù)個(gè)體臨域內(nèi)個(gè)共享函數(shù)的作用在于根據(jù)個(gè)體臨域內(nèi)個(gè)體的分布情況對(duì)個(gè)體的適應(yīng)度進(jìn)行懲罰！體的分布情況對(duì)個(gè)體的適應(yīng)度進(jìn)行懲罰！四、適應(yīng)度共享四、適應(yīng)度共享根據(jù)兩個(gè)染色體之間采用的舉例測(cè)度的不同，分為以下兩類根據(jù)兩個(gè)染色體之間采用的舉例測(cè)度的不同，分為以下兩類: genotypic sharing(基因型共享基因型共享) 個(gè)體之間的距離在碼空間進(jìn)行計(jì)算個(gè)體之間的距離在碼空間進(jìn)行計(jì)算,具體如下具體如下:其中其中, si表示編碼形式的一個(gè)字符串或者一條染色體。表示編碼形式的一個(gè)字符串或者

14、一條染色體。 phenotypic sharing(表現(xiàn)型共享表現(xiàn)型共享)個(gè)體之間的距離在解空間進(jìn)行計(jì)算個(gè)體之間的距離在解空間進(jìn)行計(jì)算,具體如下具體如下: 其中其中, xi表示解碼后的一個(gè)解。表示解碼后的一個(gè)解。),(jiijddss),(jiijddxx四、適應(yīng)度共享四、適應(yīng)度共享共享函數(shù)共享函數(shù)sh(dij) 定義如下定義如下: 其中，其中， 是一個(gè)常數(shù)，是一個(gè)常數(shù)， share 是用戶定義的小生境半徑。是用戶定義的小生境半徑。給定了適應(yīng)度函數(shù)的定義之后，一個(gè)染色體的共享適應(yīng)度給定了適應(yīng)度函數(shù)的定義之后，一個(gè)染色體的共享適應(yīng)度fi 定義如下：定義如下：mi 為給定染色體為給定染色體i的小生境計(jì)數(shù)（的小生境計(jì)數(shù)（the niche count），為染色體），為染色體i與群體中所有染與群體中所有染色體之間共享函數(shù)之和，具體定義如下：色體之間共享函數(shù)之和，具體定義如下： otherwise, 0if,1shshareshareijijijdddiiimff popsizejijid