遺傳算法課件

1、1,第三章 遺傳算法,2,五.遺傳算法的各種變形 5.1其它編碼方法 5.2遺傳運(yùn)算中的問(wèn)題 5.3適值函數(shù)的標(biāo)定(Scaling) 5.4選擇策略 5.5停止準(zhǔn)則 六. 應(yīng)用,遺傳算法,3,5.1 其它編碼方法 順序編碼：用1到N的自然數(shù)的不同順序來(lái) 編碼，此種編碼不允許重復(fù)，即 且 ，又稱自然數(shù)編碼。 該法適用范圍很廣：指派問(wèn)題、旅行商問(wèn)題和單機(jī)調(diào)度問(wèn)題等等。 合法性問(wèn)題：是否符合采用的編碼規(guī)則的問(wèn)題,五.GA的各種變形（1）,4,實(shí)數(shù)編碼： ,R為實(shí)數(shù)集 特征：方便運(yùn)算簡(jiǎn)單，但反映不出基因的特征 整數(shù)編碼類似于順序編碼，但編碼允許重復(fù) 適用于：新產(chǎn)品投入，時(shí)間優(yōu)化，伙伴挑選 例：3212

2、345 對(duì)順序編碼來(lái)說(shuō)是不合法的，而 對(duì)整數(shù)編碼來(lái)說(shuō)是合法的；010200不合法的01 編碼；,五.GA的各種變形（2）,5,5.2 遺傳運(yùn)算中的問(wèn)題 在順序編碼遺傳運(yùn)算的過(guò)程中會(huì)遇見(jiàn)不合法 的編碼，應(yīng)戰(zhàn)的策略有二:拒絕或修復(fù)。 例如：經(jīng)雙切點(diǎn)交叉后，后代編碼不合法 21 345 67 21 125 67 43 125 76 43 345 76 我們采用下面的修復(fù)策略使以上的編碼合法。,五.GA的各種變形（3）,6,順序編碼的合法性修復(fù)： 交叉修復(fù)策略，分為以下幾種： 部分映射交叉 順序交叉 循環(huán)交叉,五.GA的各種變形（4）,7,部分映射交叉(PMX) ( Partially Mapped

3、Crossover)：用特別的修復(fù)程序解決簡(jiǎn)單的雙切點(diǎn)交叉引起的非法性，步驟： 選切點(diǎn)X,Y； 交換中間部分； 確定映射關(guān)系； 將未換部分按映射關(guān)系恢復(fù)合法性。,五.GA的各種變形（5）,8,PMX例題：,五.GA的各種變形（6）,9,順序交叉( OX )Order Crossover：可看做是帶有不同修復(fù)程序的部分映射交叉的變形。 OX步驟： 選切點(diǎn)X,Y； 交換中間部分； 從切點(diǎn)Y后第一個(gè)基因起列出原順序，去掉已有基因； 從切點(diǎn)Y后第一個(gè)位置起，按順序填入。,五.GA的各種變形（7）,10,OX例題：,五.GA的各種變形（8）,11,OX的特點(diǎn)： 較好的保留了相鄰關(guān)系、先后關(guān)系,滿足了TS

4、P 問(wèn)題的需要,但不保留位值特征。,五.GA的各種變形（9）,12,循環(huán)交叉(CX) Cycle Crossover 基本思想：子串位置上的值必須與父母的相同 位置上的位值相等。 CX步驟： 選 的第一個(gè)元素作為 的第一位， 選 的第一個(gè)元素作為 的第一位；,五.GA的各種變形（10）,13, 到 中找 的第一個(gè)元素賦給 的相對(duì)位置，重復(fù)此過(guò)程，直到 上得到 的第一個(gè)元素為止，稱為一個(gè)循環(huán)； 對(duì)最前的基因按 、 基因輪替原則重復(fù)以上過(guò)程； 重復(fù)以上過(guò)程，直到所有位都完成。,五.GA的各種變形（11）,14,CX 例題：,五.GA的各種變形（12）,15,CX的特點(diǎn)： 與OX的特點(diǎn)不同的是， C

5、X較好的保留了位值 特征，適合指派問(wèn)題；而OX較好的保留了相鄰 關(guān)系、先后關(guān)系滿足了TSP問(wèn)題的需要。,五.GA的各種變形（13）,16,變異的修復(fù)策略 換位變異(最常用)是隨機(jī)地在染色體上選取兩個(gè)位置，交換基因的位值。 例： 4 3 1 2 5 6 7 4 5 1 2 3 6 7 移位變異：任選一位移到最前 例： 4 3 1 2 5 6 7 5 4 3 1 2 6 7,五.GA的各種變形（14）,17,實(shí)數(shù)編碼的合法性修復(fù) 交叉 單切點(diǎn)交叉,五.GA的各種變形（15）,18,雙切點(diǎn)交叉(與單切點(diǎn)交叉類似) 該方法最大的問(wèn)題：如何在實(shí)際優(yōu)化中保持可行性。,五.GA的各種變形（16）,19,五.

6、GA的各種變形（17）,凸組合交叉：可以克服上面簡(jiǎn)單交叉操作導(dǎo)致的解的不可行性。 約束是個(gè)凸集，可行性可以保持，但是分散 性太差，又出現(xiàn)了向中間匯集的問(wèn)題。,20,變異 位值變異： 任選一位加（變異步長(zhǎng)）， 例：,五.GA的各種變形（18）,21,向梯度方向變異 缺點(diǎn)：只能用于目標(biāo)函數(shù)可微的問(wèn)題。 例:對(duì)于最大化問(wèn)題可采用如下操作： 優(yōu)點(diǎn)：考慮到了問(wèn)題本身的性質(zhì)，效率較高。但染色體種群也可能因此而趨于聚集，導(dǎo)致種群的多樣性較差。,五.GA的各種變形（19）,22,5.3 適值函數(shù)的標(biāo)定(Scaling),五.GA的各種變形（20）,23,標(biāo)定的目的： 使適值函數(shù)不會(huì)太大，有一定差別 選擇壓力的

7、概念： 選擇壓力是種群好、壞個(gè)體被選中的概率 之差，差大稱為選擇壓力大。 注意：上述概念中的“差大小”是相對(duì)于適值函數(shù)而言的。,五.GA的各種變形（21）,24,局部搜索、廣域搜索與選擇壓力的關(guān)系 局部搜索與廣域搜索是GA中的一對(duì)矛盾，只注重局部搜索很可能陷入局優(yōu)，只注重廣域搜索則會(huì)導(dǎo)致精確開(kāi)發(fā)能力不強(qiáng)。因此，好的算法要將以上二者綜合考慮。一般來(lái)說(shuō)，算法開(kāi)始時(shí)應(yīng)注重廣域搜索，通過(guò)使用較小的選擇壓力來(lái)實(shí)現(xiàn)；隨著迭代的進(jìn)行，逐步偏重于局部搜索，通過(guò)使用較大的選擇壓力來(lái)實(shí)現(xiàn)。,五.GA的各種變形（22）,25,適值的標(biāo)定方法 線性標(biāo)定： 函數(shù)表達(dá)式： , 為目標(biāo)函數(shù)， 為適值函數(shù),五.GA的各種變形

8、（23）,26,對(duì) ， =1， = + ， 函數(shù)表達(dá)式 ：+， 對(duì) ， =-1， = + , 函數(shù)表達(dá)式： +， 上述中的是一個(gè)較小的數(shù)，目的是使種群中最差的個(gè)體仍然有繁殖的機(jī)會(huì)，增加種群的多樣性。,五.GA的各種變形（24）,27,動(dòng)態(tài)線性標(biāo)定(最常用)：線性標(biāo)定中的參數(shù)隨著迭代次數(shù)的增加而變化時(shí)就得到了動(dòng)態(tài)線性標(biāo)定 優(yōu)點(diǎn)：計(jì)算容易不占用時(shí)間 函數(shù)表達(dá)式： ， 為迭代指標(biāo) 最常用最大化 =1 , 函數(shù)表達(dá)式：,五.GA的各種變形（25）,第k代的最小目標(biāo)函數(shù)值,28,加入的意義（同線性標(biāo)定中 的意義） 加入使最壞個(gè)體仍有繁殖的可能， 隨 的增大而減小 的取值： ， ， ， 調(diào)節(jié) 和 ，從而來(lái)

9、調(diào)節(jié),五.GA的各種變形（26）,29,五.GA的各種變形（27）,引入 的目的： 調(diào)節(jié)選擇壓力，即好壞個(gè)體選擇概率的 差，使廣域搜索范圍寬保持種群的多樣性，而 局域搜索細(xì)保持收斂性。如下圖表示： 開(kāi)始：希望選擇壓力小 后來(lái)：希望選擇壓力大,30,冪律標(biāo)定： 函數(shù)表達(dá)式： 的取值， 1時(shí)選擇壓力加大 1時(shí)選擇壓力減小 對(duì)數(shù)標(biāo)定： 函數(shù)表達(dá)式： 對(duì)數(shù)標(biāo)定的作用：縮小目標(biāo)函數(shù)值的差別,五.GA的各種變形（28）,31,指數(shù)標(biāo)定： 函數(shù)表達(dá)式： 指數(shù)標(biāo)定的作用：擴(kuò)大差別 窗口技術(shù)： 函數(shù)表達(dá)式： 為前W代中的最小目標(biāo)值，它考慮了各代的波動(dòng)，這樣 具有記憶性,五.GA的各種變形（29）,32,正規(guī)化技

10、術(shù)： 函數(shù)表達(dá)式： 正規(guī)化技術(shù)的作用： 將 映射到(0,1)區(qū)間，抑制超級(jí)染色體 正規(guī)化技術(shù)的實(shí)質(zhì)：特殊的動(dòng)態(tài)標(biāo)定 即 其中：,五.GA的各種變形（30）,33,5.4 選擇策略 傳統(tǒng)的GA選擇和遺傳是一起進(jìn)行的，即使 后代不如父代，卻無(wú)法糾正。下面介紹的選擇 策略都是先遺傳后選擇。這樣，樣本空間擴(kuò)大 了，可供選擇的個(gè)體增多了。,五.GA的各種變形（31）,34,截?cái)噙x擇： 選擇最好的前T個(gè)個(gè)體，讓每一個(gè)有1/T的選擇概率，平均得到NP/T個(gè)繁殖機(jī)會(huì)。 例：NP=100,T=50 即100名學(xué)生，成績(jī)前50名的選出。每人的選擇概率為150，有平均2個(gè)機(jī)會(huì)。 缺點(diǎn)：這種方法將花費(fèi)較多的時(shí)間在適應(yīng)

11、值的 排序上。,五.GA的各種變形（32）,35,順序選擇： 步驟： 從好到壞排序所有個(gè)體 定義最好個(gè)體的選擇概率為 ,則第 個(gè)個(gè)體的選擇概率為：,五.GA的各種變形（33）,36,由于 有限時(shí)要?dú)w一化，則有下面的公式： ，其中 順序選擇的優(yōu)點(diǎn)：選擇概率可以離線計(jì)算，節(jié)省算法執(zhí)行時(shí)間，且選擇壓力可控； 缺點(diǎn)：把選擇概率固定化了，選擇壓力不可調(diào)節(jié)。,五.GA的各種變形（34）,37,舉例: 且： 采用旋輪法，隨機(jī)產(chǎn)生 當(dāng) ，選擇個(gè)體,五.GA的各種變形（35）,前i-1個(gè)個(gè)體的選擇概率,前i個(gè)個(gè)體的選擇概率,38,正比選擇：個(gè)體i的選擇概率 令： ， 用動(dòng)態(tài)標(biāo)定來(lái)調(diào)節(jié)選擇壓力，采用旋輪法來(lái)共 同

12、完成種群的選擇。,五.GA的各種變形（36）,39,5.5 停止準(zhǔn)則 指定最大代數(shù)（常用）：該方法簡(jiǎn)單但不準(zhǔn)確。 檢查種群中適值的一致性：保持歷史上最好的個(gè)體。計(jì)算公式： 或 第二種方法因很難實(shí)現(xiàn)，所以很少使用。,五.GA的各種變形（37）,40,背包問(wèn)題 個(gè)物品，對(duì)物品 ，價(jià)值為 ，重量為 ， 背包容量是 。如何選取物品裝入背包，使背 包中的價(jià)值最大。,六.應(yīng)用（1）,41,模型: （二進(jìn)制編碼方法） ，裝入物品 ，不裝入物品,六.應(yīng)用（2）,42,例如，對(duì)于一個(gè)7個(gè)項(xiàng)目的背包問(wèn)題，背包容量W=100，具體數(shù)據(jù)見(jiàn)下表，考察如下編碼X=（1 1 0 0 1 1 0） 這表示項(xiàng)目1、2、5和6被

13、裝入了背包，經(jīng)過(guò)計(jì)算可知產(chǎn)生的解不可行。 背包問(wèn)題示例,43,如何處理約束來(lái)保持可行性 拒絕策略： 可行解不易達(dá)到時(shí)，很難達(dá)到一個(gè)初始種群 修復(fù)策略： 將不可行解修復(fù)為可行的，但將失去多樣性。,六.應(yīng)用（3）,44,懲罰策略： 要求設(shè)計(jì)適當(dāng)?shù)膽土P函數(shù)，但設(shè)計(jì)不好會(huì)掩蓋目標(biāo)函數(shù)的優(yōu)化。 下面，我們將分別采用懲罰策略和解碼法來(lái)處理上面的背包問(wèn)題。,六.應(yīng)用（4）,45,罰函數(shù)法 令適值函數(shù) ，其中 是目標(biāo)函數(shù) 令 ，其中 注： 與 是 的兩個(gè)端點(diǎn),六.應(yīng)用（5）,46,函數(shù)式的意義： 的作用是使，保證 可行也懲罰，只有當(dāng) 時(shí)不懲罰。 罰函數(shù)法的目的：把解拉向邊界，盡量裝滿。,六.應(yīng)用（6）,47,

14、解碼法First Fit Heuristic(優(yōu)先適合啟 發(fā)式)解碼法是一段修復(fù)程序(修復(fù)可行性的方法) 步驟： 將選上物品按 降序排列； 選前 個(gè)物品，使； 解碼法的關(guān)鍵：如何在GA中解決可行性問(wèn)題 編碼方法：采用順序編碼,六.應(yīng)用（7）,48,例： =7 用順序( 3 2 5 1 4 6 7 )表示選擇物品的順序 用優(yōu)先適合啟發(fā)式保留前K位，使解可行 即： =3， ( 3 2 5 ) 問(wèn)題：編碼長(zhǎng)度是可變的，如何做交叉和變異,六.應(yīng)用（8）,30,50,10,40,100,49,變長(zhǎng)順序編碼的遺傳算法插入式交叉算法 在 上選一個(gè)隨機(jī)的斷點(diǎn)； 在 上隨機(jī)選一個(gè)基因片斷插入 的斷點(diǎn)處； 去掉 上的重復(fù)基因； 按優(yōu)先適合啟發(fā)式得到可行解 見(jiàn)下頁(yè)例題,六.應(yīng)用（9）,5