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

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

最優(yōu)解所在區(qū)域；選擇的作用使得群體最優(yōu)解所在區(qū)域移動(dòng)。Selection主要內(nèi)容：選擇壓力選擇方式適應(yīng)度函數(shù)適應(yīng)度共享選擇和適應(yīng)度函數(shù)一、選擇壓力定義（選擇壓力）：

最佳個(gè)體選中的概率與平均選中概率的比值。合適的選擇壓力很重要；選擇壓力太大容易早熟，選擇壓力太小，進(jìn)化緩慢。我們希望初始階段選擇壓力小，最終選擇壓力大。具體如下圖所示：

二、選擇方式2.1隨機(jī)選擇選擇幅度決定了每個(gè)個(gè)體被復(fù)制的次數(shù)；

選擇幅度由以下兩部分組成:確定染色體的期望值；將期望值轉(zhuǎn)換為實(shí)際值，即該染色體后代個(gè)體的數(shù)目。經(jīng)過選擇將期望轉(zhuǎn)化為實(shí)際值即后代個(gè)數(shù)的常用的選擇方式：輪盤賭的選擇方式；一次隨機(jī)采樣。二、選擇方式2.1隨機(jī)選擇輪盤賭選擇又稱比例選擇算子，其基本思想是：個(gè)體被選中的概率與其適應(yīng)度函數(shù)值成正比。二、選擇方式step1:計(jì)算群體的總適應(yīng)度：step2:計(jì)算染色體vk的選擇概率pk：step3:計(jì)算染色體vk的累積概率qk：step4:隨機(jī)產(chǎn)成一個(gè)[0,1]的數(shù)r；step5:如果r

q1,選擇第一條染色體v1;否則,如果qk-1<r

qk,選擇第k條染色體vk(2

k

popSize).輸入:群體P(t-1),C(t-1)輸出:群體P(t),C(t)輪盤賭選擇的具體步驟如下：問題1：輪盤賭選擇方式是如何做到個(gè)體被選中的概率與其適應(yīng)度函數(shù)值成正比的？二、選擇方式輪盤賭選擇問題2：輪盤賭選擇結(jié)果中個(gè)體的實(shí)際值與期望值一致嗎?二、選擇方式2.1隨機(jī)選擇問題3：這兩種采樣方式有什么區(qū)別？二、選擇方式2.2確定性選擇所謂確定性選擇就是從父代和子代個(gè)體中選擇最優(yōu)的個(gè)體。具體舉例如下：(+)-selection(個(gè)父代，個(gè)子代,從+選擇最好的)(,)-selection(個(gè)父代，個(gè)子代,從選擇最好的)Elitistselection(貪婪選擇，在比例選擇最優(yōu)個(gè)體沒有被選擇，強(qiáng)制選擇)Thegenerationalreplacement(代替換)Steady-statereproduction(穩(wěn)態(tài)再生，n個(gè)最差的父代個(gè)體被子代替換)問題4：請大家分析(+)-selection和(,)-selection兩種選擇方式中，哪種選擇壓力大，哪種選擇壓力??？二、選擇方式2.3混合選擇混合選擇同時(shí)具有隨機(jī)性和確定性，如Tournamentselection(競賽選擇)。

競賽選擇:競賽規(guī)模=t

Repeatttimes從種群中隨機(jī)選擇一個(gè)個(gè)體并記下其適應(yīng)度；返回t個(gè)個(gè)體中最好的個(gè)體?？梢酝ㄟ^選擇t,調(diào)節(jié)選擇壓力。當(dāng)t=2為二進(jìn)制競賽選擇。問題5：請大家分析隨著t的增大選擇壓力如何變化？三、適應(yīng)度函數(shù)3.1定義遺傳算法在進(jìn)化搜索中基本不用外部信息，僅用目標(biāo)函數(shù)即適應(yīng)度函數(shù)為依據(jù)，利用種群每個(gè)個(gè)體的適應(yīng)度來指導(dǎo)搜索。需要強(qiáng)調(diào)的是，適應(yīng)度函數(shù)值是選擇操作的依據(jù)，適應(yīng)度函數(shù)(FitnessFunction)的選取直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解。三、適應(yīng)度函數(shù)

1）對最小化問題，建立如下適應(yīng)函數(shù)和目標(biāo)函數(shù)的映射關(guān)系：其中，cmax可以是一個(gè)輸入值或是理論上的最大值，或者是當(dāng)前所有大或最近K代中g(shù)(x)的最大值，此時(shí)cmax隨著代數(shù)會(huì)有變化。

2）對于最大化問題，一般采用以下映射：

其中，cmin可以是一個(gè)輸入值，或是當(dāng)前所有代或最近K代中g(shù)(x)的最小值。三、適應(yīng)度函數(shù)

3.2適應(yīng)度變換引例：對于最大化問題，假定群體中有以下5個(gè)個(gè)體，其適應(yīng)度分別為：100,0.4,0.3,0.2,0.1--最好個(gè)體的適應(yīng)度為其余個(gè)體適應(yīng)度和的100倍！可以對適應(yīng)度做如下變換：200,100.4,100.3,100.2,100.1--比較合理的情況！定義：這種適應(yīng)度的縮放調(diào)整稱為適應(yīng)度變換。適應(yīng)度變換有兩個(gè)目的：維持個(gè)體之間的合理差距，加速競爭；避免個(gè)體之間的差距過大，限制競爭。假定第k個(gè)染色體的原始的適應(yīng)度為fk,變換后的適應(yīng)度fk'為:fk'=g(fk

)函數(shù)g(·)根據(jù)采用的形式不同會(huì)產(chǎn)生不同的變換方法，具體如下：

線性變換

指數(shù)變換歸一化變換Boltzmann變換三、適應(yīng)度函數(shù)四、適應(yīng)度共享共享函數(shù)法根據(jù)個(gè)體某個(gè)距離內(nèi)與其他個(gè)體的臨近程度來確定該個(gè)體的適應(yīng)度應(yīng)改變多少。在擁擠的峰周圍的個(gè)體的復(fù)制概率受到抑制，利于其他個(gè)體產(chǎn)生后代。適應(yīng)度共享可用于多峰搜索,共享函數(shù)的作用在于根據(jù)個(gè)體臨域內(nèi)個(gè)體的分布情況對個(gè)體的適應(yīng)度進(jìn)行懲罰！四、適應(yīng)度共享根據(jù)兩個(gè)染色體之間采用的舉例測度的不同，分為以下兩類:Genotypicsharing(基因型共享)個(gè)體之間的距離在碼空間進(jìn)行計(jì)算,具體如下:其中,

si表示編碼形式的一個(gè)字符串或者一條染色體。Phenotypicsharing(表現(xiàn)型共享)個(gè)體之間的距離在解空間進(jìn)行計(jì)算,具體如下:

其中,

xi表示解碼后的一個(gè)解。四、適應(yīng)度共享共享函數(shù)Sh(dij)定義如下:

其中，

是一個(gè)常數(shù)，share

是用戶定義的小生境半徑。給定了適應(yīng)度函數(shù)的定義之后，一個(gè)染色體的共享適應(yīng)度fi'

定義如下：mi

為給定染色體i的小生境計(jì)數(shù)（thenichecount），為染色體i與群體中所有染色體之