遺傳算法課件

第三章

遺傳算法1精選可編輯ppt五.遺傳算法的各種變形5.1其它編碼方法5.2遺傳運(yùn)算中的問題5.3適值函數(shù)的標(biāo)定(Scaling)5.4選擇策略5.5停止準(zhǔn)則六.應(yīng)用

遺傳算法2精選可編輯ppt5.1其它編碼方法順序編碼：用1到N的自然數(shù)的不同順序來編碼，此種編碼不允許重復(fù)，即且，又稱自然數(shù)編碼。該法適用范圍很廣：指派問題、旅行商問題和單機(jī)調(diào)度問題等等。合法性問題：是否符合采用的編碼規(guī)則的問題五.GA的各種變形（1）3精選可編輯ppt實(shí)數(shù)編碼：,R為實(shí)數(shù)集特征：方便運(yùn)算簡單，但反映不出基因的特征整數(shù)編碼類似于順序編碼，但編碼允許重復(fù)適用于：新產(chǎn)品投入，時(shí)間優(yōu)化，伙伴挑選例：3212345對順序編碼來說是不合法的，而對整數(shù)編碼來說是合法的；010200不合法的01編碼；五.GA的各種變形（2）4精選可編輯ppt5.2遺傳運(yùn)算中的問題 在順序編碼遺傳運(yùn)算的過程中會(huì)遇見不合法的編碼，應(yīng)戰(zhàn)的策略有二:拒絕或修復(fù)。例如：經(jīng)雙切點(diǎn)交叉后，后代編碼不合法

21|345|6721|125|6743|125|7643|345|76我們采用下面的修復(fù)策略使以上的編碼合法。五.GA的各種變形（3）5精選可編輯ppt順序編碼的合法性修復(fù)：交叉修復(fù)策略，分為以下幾種：部分映射交叉順序交叉循環(huán)交叉

五.GA的各種變形（4）

6精選可編輯ppt部分映射交叉(PMX)(PartiallyMappedCrossover)：用特別的修復(fù)程序解決簡單的雙切點(diǎn)交叉引起的非法性，步驟：⑴選切點(diǎn)X,Y；⑵交換中間部分；⑶確定映射關(guān)系；⑷將未換部分按映射關(guān)系恢復(fù)合法性。五.GA的各種變形（5）7精選可編輯pptPMX例題：五.GA的各種變形（6）映射關(guān)系：3-1，4-2，5-5則：43|125|6721|345|76

21|345|67|125|

43|125|76|345|

XY8精選可編輯ppt順序交叉(OX

)OrderCrossover：可看做是帶有不同修復(fù)程序的部分映射交叉的變形。OX步驟：⑴選切點(diǎn)X,Y；⑵交換中間部分；⑶從切點(diǎn)Y后第一個(gè)基因起列出原順序，去掉已有基因；⑷從切點(diǎn)Y后第一個(gè)位置起，按順序填入。五.GA的各種變形（7）9精選可編輯pptOX例題：五.GA的各種變形（8）列出基因：67213457643125則：34|125|6712|345|76

21|345|67|125|

43|125|76|345|

XY10精選可編輯pptOX的特點(diǎn)：較好的保留了相鄰關(guān)系、先后關(guān)系,滿足了TSP問題的需要,但不保留位值特征。五.GA的各種變形（9）11精選可編輯ppt循環(huán)交叉(CX)CycleCrossover基本思想：子串位置上的值必須與父母的相同位置上的位值相等。CX步驟：⑴選的第一個(gè)元素作為的第一位， 選的第一個(gè)元素作為的第一位；五.GA的各種變形（10）12精選可編輯ppt⑵到中找的第一個(gè)元素賦給的相對位置…，重復(fù)此過程，直到上得到的第一個(gè)元素為止，稱為一個(gè)循環(huán)；⑶對最前的基因按、基因輪替原則重復(fù)以上過程；⑷重復(fù)以上過程，直到所有位都完成。五.GA的各種變形（11）13精選可編輯pptCX例題：五.GA的各種變形（12）

245389617236

398654271362

32，94，58，716

29346

34692

295384671

34865921714精選可編輯pptCX的特點(diǎn)：與OX的特點(diǎn)不同的是，CX較好的保留了位值特征，適合指派問題；而OX較好的保留了相鄰關(guān)系、先后關(guān)系滿足了TSP問題的需要。五.GA的各種變形（13）15精選可編輯ppt變異的修復(fù)策略換位變異(最常用)是隨機(jī)地在染色體上選取兩個(gè)位置，交換基因的位值。

例：

43125674512367

移位變異：任選一位移到最前

例：

43125675431267五.GA的各種變形（14）16精選可編輯ppt實(shí)數(shù)編碼的合法性修復(fù)

交叉單切點(diǎn)交叉五.GA的各種變形（15）切點(diǎn)17精選可編輯ppt雙切點(diǎn)交叉(與單切點(diǎn)交叉類似)

該方法最大的問題：如何在實(shí)際優(yōu)化中保持可行性。五.GA的各種變形（16）切點(diǎn)切點(diǎn)18精選可編輯ppt五.GA的各種變形（17）凸組合交叉：可以克服上面簡單交叉操作導(dǎo)致的解的不可行性。約束是個(gè)凸集，可行性可以保持，但是分散性太差，又出現(xiàn)了向中間匯集的問題。19精選可編輯ppt變異位值變異： 任選一位加Δ（變異步長），

例：五.GA的各種變形（18）20精選可編輯ppt向梯度方向變異缺點(diǎn)：只能用于目標(biāo)函數(shù)可微的問題。 例:對于最大化問題可采用如下操作：優(yōu)點(diǎn)：考慮到了問題本身的性質(zhì)，效率較高。但染色體種群也可能因此而趨于聚集，導(dǎo)致種群的多樣性較差。五.GA的各種變形（19）21精選可編輯ppt5.3適值函數(shù)的標(biāo)定(Scaling)五.GA的各種變形（20）

相對差別放大，選擇壓力變大，選優(yōu)功能強(qiáng)化了標(biāo)定

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

函數(shù)表達(dá)式：

,

為目標(biāo)函數(shù)，為適值函數(shù)五.GA的各種變形（23）25精選可編輯ppt對， =1，=

+ξ， 函數(shù)表達(dá)式： +ξ，對， =-1，=

+ξ, 函數(shù)表達(dá)式： +ξ，

上述中的ξ是一個(gè)較小的數(shù)，目的是使種群中最差的個(gè)體仍然有繁殖的機(jī)會(huì)，增加種群的多樣性。五.GA的各種變形（24）26精選可編輯ppt動(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ù)值27精選可編輯ppt加入的意義（同線性標(biāo)定中ξ的意義） 加入使最壞個(gè)體仍有繁殖的可能，隨的增大而減小的取值： ，，， 調(diào)節(jié)和，從而來調(diào)節(jié)五.GA的各種變形（26）28精選可編輯ppt五.GA的各種變形（27）引入的目的： 調(diào)節(jié)選擇壓力，即好壞個(gè)體選擇概率的差，使廣域搜索范圍寬保持種群的多樣性，而局域搜索細(xì)保持收斂性。如下圖表示： 開始：希望選擇壓力小 后來：希望選擇壓力大k29精選可編輯ppt冪律標(biāo)定： 函數(shù)表達(dá)式： 的取值，>1時(shí)選擇壓力加大

<1時(shí)選擇壓力減小對數(shù)標(biāo)定： 函數(shù)表達(dá)式： 對數(shù)標(biāo)定的作用：縮小目標(biāo)函數(shù)值的差別五.GA的各種變形（28）30精選可編輯ppt指數(shù)標(biāo)定： 函數(shù)表達(dá)式： 指數(shù)標(biāo)定的作用：擴(kuò)大差別窗口技術(shù)： 函數(shù)表達(dá)式： 為前W代中的最小目標(biāo)值，它考慮了各代 的波動(dòng)，這樣具有記憶性五.GA的各種變形（29）31精選可編輯ppt正規(guī)化技術(shù)： 函數(shù)表達(dá)式： 正規(guī)化技術(shù)的作用： 將映射到(0,1)區(qū)間，抑制超級染色體 正規(guī)化技術(shù)的實(shí)質(zhì)：特殊的動(dòng)態(tài)標(biāo)定 即 其中：五.GA的各種變形（30）32精選可編輯ppt5.4選擇策略 傳統(tǒng)的GA選擇和遺傳是一起進(jìn)行的，即使后代不如父代，卻無法糾正。下面介紹的選擇策略都是先遺傳后選擇。這樣，樣本空間擴(kuò)大了，可供選擇的個(gè)體增多了。五.GA的各種變形（31）33精選可編輯ppt截?cái)噙x擇： 選擇最好的前T個(gè)個(gè)體，讓每一個(gè)有1/T的選擇概率，平均得到NP/T個(gè)繁殖機(jī)會(huì)。例：NP=100,T=50 即100名學(xué)生，成績前50名的選出。每人的選擇概率為1／50，有平均2個(gè)機(jī)會(huì)。缺點(diǎn)：這種方法將花費(fèi)較多的時(shí)間在適應(yīng)值的排序上。五.GA的各種變形（32）34精選可編輯ppt順序選擇：步驟：⑴從好到壞排序所有個(gè)體⑵定義最好個(gè)體的選擇概率為,則第個(gè)個(gè)體的選擇概率為：五.GA的各種變形（33）35精選可編輯ppt⑶ 由于 有限時(shí)要?dú)w一化，則有下面的公式：，其中順序選擇的優(yōu)點(diǎn)：選擇概率可以離線計(jì)算，節(jié)省算法執(zhí)行時(shí)間，且選擇壓力可控；缺點(diǎn)：把選擇概率固定化了，選擇壓力不可調(diào)節(jié)。五.GA的各種變形（34）36精選可編輯ppt舉例:

且：采用旋輪法，隨機(jī)產(chǎn)生當(dāng)，選擇個(gè)體五.GA的各種變形（35）前i-1個(gè)個(gè)體的選擇概率前i個(gè)個(gè)體的選擇概率37精選可編輯ppt正比選擇：個(gè)體i的選擇概率 令： ，用動(dòng)態(tài)標(biāo)定來調(diào)節(jié)選擇壓力，采用旋輪法來共同完成種群的選擇。

五.GA的各種變形（36）38精選可編輯ppt5.5停止準(zhǔn)則指定最大代數(shù)（常用）：該方法簡單但不準(zhǔn)確。檢查種群中適值的一致性：保持歷史上最好的個(gè)體。計(jì)算公式： 或第二種方法因很難實(shí)現(xiàn)，所以很少使用。五.GA的各種變形（37）39精選可編輯ppt背包問題 個(gè)物品，對物品，價(jià)值為，重量為，背包容量是。如何選取物品裝入背包，使背包中的價(jià)值最大。

六.應(yīng)用（1）40精選可編輯ppt模型:

（二進(jìn)制編碼方法）

，裝入物品 ，不裝入物品

六.應(yīng)用（2）41精選可編輯ppt例如，對于一個(gè)7個(gè)項(xiàng)目的背包問題，背包容量W=100，具體數(shù)據(jù)見下表，考察如下編碼X=（1100110）這表示項(xiàng)目1、2、5和6被裝入了背包，經(jīng)過計(jì)算可知產(chǎn)生的解不可行。背包問題示例i1234567wi40503010104030pi4060101032060Pi/wi11.20.3310.30.5242精選可編輯ppt如何處理約束來保持可行性拒絕策略：可行解不易達(dá)到時(shí)，很難達(dá)到一個(gè)初始種群修復(fù)策略：將不可行解修復(fù)為可行的，但將失去多樣性。六.應(yīng)用（3）43精選可編輯ppt懲罰策略：要求設(shè)計(jì)適當(dāng)?shù)膽土P函數(shù)，但設(shè)計(jì)不好會(huì)掩蓋目標(biāo)函數(shù)的優(yōu)化。 下面，我們將分別采用懲罰策略和解碼法來處理上面的背包問題。 六.應(yīng)用（4）44精選可編輯ppt罰函數(shù)法令適值函數(shù) ，其中是目標(biāo)函數(shù)令 ，其中

注： 與 是 的兩個(gè)端點(diǎn)六.應(yīng)用（5）罰函數(shù)45精選可編輯ppt函數(shù)式的意義：⑴ 的作用是使 ，保證⑵可行也懲罰，只有當(dāng) 時(shí)不懲罰。⑶罰函數(shù)法的目的：把解拉向邊界，盡量裝滿。六.應(yīng)用（6）46精選可編輯ppt解碼法——FirstFitHeuristic(優(yōu)先適合啟發(fā)式)解碼法是一段修復(fù)程序(修復(fù)可行性的方法)⑴步驟：將選上物品按降序排列；選前個(gè)物品，使 ；⑵解碼法的關(guān)鍵：如何在GA中解決可行性問題⑶編碼方法：采用順序編碼 六.應(yīng)用（7）47精選可編輯ppt例