【正文】 2022/2/11 遺傳算法的一般算法 (續(xù) ) ? 3. 繁殖 (包括子代突變 ) 帶有較高適應(yīng)度值的那些染色體更可能產(chǎn)生后代 (后代產(chǎn)生后也將發(fā)生突變 )。 后代是父母的產(chǎn)物 ， 他們由來自父母的基因結(jié)合而成 ， 這個(gè)過程被稱為 “ 雜交 ” 。 4. 下一代 如果新的一代包含一個(gè)解 ， 能產(chǎn)生一個(gè)充分接近或等于期望答案的輸出， 那么問題就已經(jīng)解決了 。 如果情況并非如此 ， 新的一代將重復(fù)他們父母所進(jìn)行的繁衍過程 ， 一代一代演化下去 ， 直到達(dá)到期望的解為止 。 22 2022/2/11 遺傳算法的一般算法 (續(xù) ) ? 5. 并行計(jì)算 * 非常容易將遺傳算法用到并行計(jì)算和群集環(huán)境中。 * 一種方法是直接把每個(gè)節(jié)點(diǎn)當(dāng)成一個(gè)并行的種群看待。然后有機(jī)體根據(jù)不同的繁殖方法從一個(gè)節(jié)點(diǎn)遷移到另一個(gè)節(jié)點(diǎn)。 * 另一種方法是“農(nóng)場(chǎng)主 /勞工”體系結(jié)構(gòu)，指定一個(gè)節(jié)點(diǎn)為“農(nóng)場(chǎng)主”節(jié)點(diǎn)，負(fù)責(zé)選擇有機(jī)體和分派適應(yīng)度的值，另外的節(jié)點(diǎn)作為“勞工”節(jié)點(diǎn)，負(fù)責(zé)重新組合、變異和適應(yīng)度函數(shù)的評(píng)估。 23 2022/2/11 遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生 的 繁殖、交叉和基因突變 現(xiàn)象，在每次迭代中 都保留一組候選解，并按某種指標(biāo)從解群中選 取較優(yōu)的個(gè)體，利用 遺傳算子 (選擇、交叉和變 異 )對(duì)這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解 群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。 遺傳算法的搜索機(jī)制 24 2022/2/11 局部 全局 遺傳算法 (GA) 25 2022/2/11 We have a dream!! I am at the top Height is ... I am not at the top. My high is better! I will continue 遺傳算法 (GA) GA第 0代 26 2022/2/11 Dead one New one 遺傳算法 (GA) GA第 1代 27 2022/2/11 Not at the top, Come Up!!! 遺傳算法 (GA) GA第 ?代 28 2022/2/11 I am the BEST !!! 遺傳算法 (GA) GA第 N代 29 2022/2/11 生物進(jìn)化與遺傳算法對(duì)應(yīng)關(guān)系 生物進(jìn)化 遺傳算法 適者生存 適應(yīng)函數(shù)值最大的解被保留的概率最大 個(gè)體 問題的一個(gè)解 染色體 解的編碼 基因 編碼的元素 群體 被選定的一組解 種群 根據(jù)適應(yīng)函數(shù)選擇的一組解 交叉 以一定的方式由雙親產(chǎn)生后代的過程 變異 編碼的某些分量發(fā)生變化的過程 環(huán)境 適應(yīng)函數(shù) 30 2022/2/11 遺傳算法的基本操作 ? 選擇 (selection): 根據(jù)各個(gè)個(gè)體的適應(yīng)值，按照一定的規(guī)則或方法，從第 t代群體 P(t)中選擇出一些優(yōu)良的個(gè)體遺傳到下一代群體 P(t+1)中。 ? 交叉 (crossover): 將群體 P(t)內(nèi)的各個(gè)個(gè)體隨機(jī)搭配成對(duì)，對(duì)每一個(gè)個(gè)體，以某個(gè)概率 Pc (稱為交叉概率， crossvoer rate)交換它們之間的部分染色體。 ? 變異 (mutation): 對(duì)群體 P(t)中的每一個(gè)個(gè)體，以某一概率 Pm(稱為變異概率， mutation rate)改變某一個(gè)或一些基因座上基因值為其它的等位基因。 31 2022/2/11 如何設(shè)計(jì)遺傳算法 ? 如何進(jìn)行編碼？ ? 如何產(chǎn)生初始種群？ ? 如何定義適應(yīng)函數(shù)？ ? 如何進(jìn)行遺傳操作 (復(fù)制、交叉、變異 )？ ? 如何產(chǎn)生下一代種群？ ? 如何定義停止準(zhǔn)則 ？ 32 2022/2/11 編碼 (Coding) 表現(xiàn)型空間 編碼 (Coding) 解碼 (Decoding) 基因型空間 = {0,1}L 011101001 010001001 10010010 10010001 33 2022/2/11 編碼 設(shè)某一參數(shù)的取值范圍為（ L， U），使用長(zhǎng)度為 k 的二進(jìn)制編碼表示該數(shù)，則共有 種不同的編碼。 k2k??????0000000000 00000000001 10000000010 20000000011 31111111111 2 134 2022/2/11 解碼 解碼的目的是為了將不直觀的二進(jìn)制數(shù)據(jù)串還原成十進(jìn)制。 ()kii kiULx L b ???????112 21設(shè)某一個(gè)體的二進(jìn)制編碼為 ,k k kb b b b b b??1 2 3 2 1則對(duì)應(yīng)的解碼公式為： 35 2022/2/11 適應(yīng)函數(shù) (Fitness Function) ? GA在搜索中不依靠外部信息，僅以 適應(yīng)函數(shù) 為依據(jù)，利用群體中每個(gè)染色體 (個(gè)體 )的適應(yīng)值來進(jìn)行搜索。 以染色體適應(yīng)值的大小來確定該染色體被遺傳到下一代群體中的概率 。染色體適應(yīng)值越大，該染色體被遺傳到下一代的概率也越大；反之，染色體的適應(yīng)值越小，該染色體被遺傳到下一代的概率也越小。因此適應(yīng)函數(shù)的選取至關(guān)重要，直接影響到 GA的收斂速度以及能否找到最優(yōu)解。 ? 群體中的每個(gè)染色體都需要計(jì)算適應(yīng)值 ? 適應(yīng)函數(shù)一般由 目標(biāo)函數(shù) 變換而成 36 2022/2/11 適應(yīng)函數(shù) (Fitness Function) ? 適應(yīng)函數(shù)常見形式： ? 直接將目標(biāo)函數(shù)轉(zhuǎn)化為適應(yīng)函數(shù) ? 若目標(biāo)函數(shù)為最大化問題： Fitness(f(x)) = f(x) ? 若目標(biāo)函數(shù)為最小化問題： Fitness(f(x)) = f(x) 37 2022/2/11 適應(yīng)函數(shù) (Fitness Function) ? 界限構(gòu)造法 m i n m i n( ) , ( )F it n e s s ( ( ) )0f x C f x Cfxo th e r s????? ??? ， ? 目標(biāo)函數(shù)為最大化問題 其中 Cmin為 f(x)的最小估計(jì)值 m a x m a x( ) , ( )F it n e s s ( ( ) )0C f x f x Cfxo th e r s???????? ， ? 目標(biāo)函數(shù)為最小化問題 其中 Cmaxn為 f(x)的最大估計(jì)值 38 2022/2/11 選擇 (Selection) ? 選擇 (復(fù)制 )操作把當(dāng)前種群的染色體按與適應(yīng)值成正比例的概率復(fù)制到新的種群中 ? 主要思想 : 適應(yīng)值較高的染色體體有較大的選擇 (復(fù)制 )機(jī)會(huì) 設(shè)種群的規(guī)模為 N xi是種群中第 i個(gè)染色體 1()()()???isi Njjfxpxfx染色體 xi被選概率 39 2022/2/11 選擇 (Selection) ? 實(shí)現(xiàn) 1： ” 輪盤賭 ” 選擇 (Roulette wheel selection) ?產(chǎn)生一個(gè)在 0與總和之間的的隨機(jī)數(shù) m ?從種群中編號(hào)為 1的染色體開始，將其適應(yīng)值與后續(xù)染色體的適應(yīng)值相加，直到累加和等于或大于 m 40 2022/2/11 選擇 (Selection) 染色體的適應(yīng)值和所占的比例 輪盤賭選擇 41 2022/2/11 選擇 (Selection) 隨機(jī)數(shù) 23 49 13 38 6 27 所選號(hào)碼 2 6 2 5 1 4 所選染色體 11000 00011 11000 01100 01110 10010 染色體編號(hào) 1 2 3 4 5 6 染色體 01110 11000 00100 10010 01100 00011 適應(yīng)度 8 15 2 5 12 8 被選概率 0. 24 適應(yīng)度累計(jì) 8 23 25 30 42 50 染色體被選的概率 被選的染色體 42 2022/2/11 選擇 (Selection) ? 輪盤上的片分配給群體的染色體 ， 使得每一個(gè)片的大小與對(duì)于染色體的適應(yīng)值成比例 ? 從群體中選擇一個(gè)染色體可視為旋轉(zhuǎn)一個(gè)輪盤 ， 當(dāng)輪盤停止時(shí) ，指針?biāo)傅钠瑢?duì)于的染色體就時(shí)要選的染色體 。 ? 模擬 “ 輪盤賭 ” 算法 ： (1)r=rand(0, 1)， s=0， i=0； (2)如果 s≥r， 則轉(zhuǎn) (4)； (3)s=s+p(xi)， i=i+1, 轉(zhuǎn) (2) (4)xi即為被選中的染色體 ， 輸出 I (5)結(jié)束 43 2022/2/11 選擇 (Selection) ? 其他選擇法 ： ? 隨機(jī)遍歷抽樣 (Stochastic universal sampling) ? 局部選擇 (Local selection) ? 截?cái)噙x擇 (Truncation selection) ? 競(jìng)標(biāo)賽選擇 (Tournament selection) ? 特點(diǎn) ： 選擇操作得到的新的群體稱為交配池，交配池是當(dāng)前代和下一代之間的中間群體，其規(guī)模為初始群體規(guī)模。選擇操作的作用效果是提高了群體的平均適應(yīng)值 (低適應(yīng)值個(gè)體趨于淘汰，高適應(yīng)值個(gè)體趨于選擇 )，但這也損失了群體的 多樣性 。選擇操作沒有產(chǎn)生新的個(gè)體，群體中最好個(gè)體的適應(yīng)值不會(huì)改變。 44 2022/2/11 交叉 (crossover, Rebination) ? 遺傳交叉 (雜交、交配、有性重組 )操作發(fā)生在兩個(gè)染色體之間，由兩個(gè)被稱之為雙親的父代染色體，經(jīng)雜交以后，產(chǎn)生兩個(gè)具有雙親的部分基因的新的染色體，從而檢測(cè)搜索空間中新的點(diǎn)。 ? 選擇 (復(fù)制 )操作每次作用在一個(gè)染色體上，而交叉操作每次作用在從交配池中隨機(jī)選取的兩個(gè)個(gè)體上(交叉概率 Pc)。 ? 交叉產(chǎn)生兩個(gè)子染色體，他們與其父代不同，且彼此不同 , 每個(gè)子染色體都帶有雙親染色體的遺傳基因。 45 2022/2/11 單點(diǎn)交叉 (1point crossover) ? 在雙親的父代染色體中隨機(jī)