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