【文章內容簡介】 產生一個交叉點位置 ? 在交叉點位置分離雙親染色體 ? 互換交叉點位置右邊的基因碼產生兩個子代染色體 ? 交叉概率 Pc 一般范圍為 (60%, 90%)，平均約 80% 1 1 1 1 1 1 1 1 父代 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 子代 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 交叉點位置 46 2022/2/11 交叉 (crossover, Rebination) ? 單點交叉操作可以產生與父代染色體完全不同的子代染色體；它不會改變父代染色體中相同的基因。但當雙親染色體相同時，交叉操作是不起作用的。 假如交叉概率 Pc ＝ 50%,則交配池中 50%的染色體 (一半染色體 ) 將進行交叉操作，余下的 50%的染色體進行選擇 (復制 )操作。 ? GA利用 選擇和交叉操作 可以產生具有 更高平均適應值和更好染色體的群體 47 2022/2/11 變異 (Mutation) ? 以變異概率 Pm改變 染色體的某一個基因 ,當以二進制編碼時，變異的基因由 0變成 1，或者由 1變成 0。 ? 變異概率 Pm 一般介于 1/種群規(guī)模與 1/染色體長度之間，平均約 12% 1 1 0 1 0 1 0 0 父代 0 1 0 1 0 1 0 1 子代 變異基因 變異基因 48 2022/2/11 變異 (Mutation) ? 比起選擇和交叉操作， 變異操作 是 GA中的次要操作，但它在恢復群體中失去的 多樣性 方面具有潛在的作用。 在 GA執(zhí)行的開始階段，染色體中一個特定位上的值 1可能與好的性 能緊密聯(lián)系，即搜索空間中某些初始染色體在那個位上的值 1可能一 致產生高的適應值。因為越高的適應值與染色體中那個位上的值 1相聯(lián) 系，選擇操作就越會使群體的遺傳多樣性損失。 等到達一定程度時，值 0會從整個群體中那個位上消失，然而全局最 優(yōu)解可能在染色體中那個位上為 0。如果搜索范圍縮小到實際包含全局 最優(yōu)解的那部分搜索空間，在那個位上的值 0就可能正好是到達全局最 優(yōu)解所需要的。 49 2022/2/11 停止準則 (Termination Criteria) ? 種群中個體的 最大適應值 超過預設定值 ? 種群中個體的 平均適應值 超過預設定值 ? 種群中個體的 進化代數(shù) 超過預設定值 50 2022/2/11 基本步驟 (Step by Step) (1) 隨機產生 初始種群 。 (2) 計算種群體中每個個體的 適應度值 ,判斷是否滿足停止條件，若不滿足，則轉第 (3)步 ,否則轉第(6)步 。 (3) 按由個體適應值所決定的某個規(guī)則 選擇 將進入下一代的個體 。 (4) 按交叉概率 Pc進行 交叉操作 ,生產新的個體 。 (5) 按變異概率 Pm進行 變異操作 ,生產新的個體 。 (6) 輸出種群中適應度值最優(yōu)的染色體作為問題的 滿意解或最優(yōu)解 。 51 2022/2/11 流程圖 (Flow Chart) 52 2022/2/11 基本遺傳算法 基本遺傳算法 （ Simple Geic Algorithms, 簡稱 SGA）是一種統(tǒng)一的最基本的遺傳算法，它只 使用 選擇、交叉、變異 這三種基本遺傳算子，其遺傳 進化操作過程簡單，容易理解，是其他一些遺傳算法 的雛形和基礎，它不僅給各種遺傳算法提供了一個基 本框架，同時也具有一定的應用價值。 53 2022/2/11 SGA偽碼描述 Procedure Geic Algorithm begin t = 0 。 %遺傳代數(shù) 初始化 P(t) 。 %初始化種群或染色體 計算 P(t) 的適應值 。 while (不滿足停止準則 ) do begin t = t+1 。 從 P(t1)中選擇 P(t) 。 % selection 重組 P(t) 。 % crossover and mutation 計算 P(t) 的適應值 。 end end 54 2022/2/11 遺傳算法的應用 ? 函數(shù)優(yōu)化 函數(shù)優(yōu)化是遺傳算法的經典應用領域，也是對遺傳算法進行性能測試評價的常用算例。對于一些非線性、多模型、多目標的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解，而遺傳算法卻可以方便地得到較好的結果。 遺傳算法提供了一種求解復雜系統(tǒng)優(yōu)化問題的通用框 架，它不依賴于問題的具體領域，對問題的種類有很 強的魯棒性，所以廣泛應用于很多學科。下面列舉一 些遺傳算法的主要應用領域。 55 2022/2/11 遺傳算法的應用 ? 組合優(yōu)化 遺傳算法是尋求組合優(yōu)化問題滿意解的最佳工具之一，實踐證明，遺傳算法對于組合優(yōu)化問題中的 NP完全問題非常有效。例如，遺傳算法已經在求解旅行商問題 (Traveling Salesman Problem , TSP)、背包問題 (Knapsack Problem)、裝箱問題 (Bin Packing Problem) 等方面得到成功的應用。 ? 生產調度問題 生產調度問題在很多情況下所建立起來的數(shù)學模型難以精確求解，即使經過一些簡化之后可以進行求解也會因簡化得太多而使求解結果與實際相差太遠?，F(xiàn)在遺傳算法已經成為解決復雜調度問題的有效工具。 56 2022/2/11 遺傳算法的應用 ? 自動控制 遺傳算法已經在自動控制領域中得到了很好的應用，例如基于遺傳算法的模糊控制器的優(yōu)化設計、基于遺傳算法的參數(shù)辨識、基于遺傳算法的模糊控制規(guī)則的學習、利用遺傳算法進行人工神經網(wǎng)絡的結構優(yōu)化設計和權值學習等。 ? 機器人智能控制 機器人是一類復雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于對人工自適應系統(tǒng)的研究，所以機器人智能控制自然成為遺傳算法的一個重要應用領域。 57 2022/2/11 遺傳算法的應用 ? 圖象處理和模式識別 圖像處理和模式識別是計算機視覺中的一個重要研究領域。在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免地存在一些誤差，這些誤差會影響圖像處理的效果。如何使這些誤差最小是使計算機視覺達到實用化的重要要求，遺傳算法在這些圖像處理中的優(yōu)化計算方面得到了很好的應用。 ? 人工生命 人工生命是用計算機、機械等人工媒體模擬或構造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。自組織能力和自學習能力是人工生命的兩大重要特征。人工生命與遺傳算法有著密切的關系，基于遺傳算法的進化模型是研究人工生命現(xiàn)象的重要理論基礎。 58 2022/2/11 遺傳算法的應用 ? 遺傳程序設計 Koza發(fā)展了遺傳程序設計的概念，他使用了以 LISP語言所表示的編碼方法，基于對一種樹形結構所進行的遺傳操作來自動生成計算機程序。 ? 機器學習 基于遺傳算法的機器學習，在很多領域中都得到了應用。例如基于遺傳算法的機器學習可用來調整人工神經網(wǎng)絡的連接權，也可以用于人工神經網(wǎng)絡的網(wǎng)絡結構優(yōu)化設計。分類器系統(tǒng)在多機器人路徑規(guī)劃系統(tǒng)中得到了成功的應用。 59 2022/2/11 SGA實例 1：函數(shù)最值 SGA參數(shù) : ? 編碼方式 : 二進制碼 . 00000?0。 01101 ? 13。 11111?31 ? 種群規(guī)模 : 4 ? 隨機初始群體 ? “ 轉盤賭 ” 選擇 ? 一點雜交 , 二進制變異 求函數(shù) f(x)=x2的最大值， x為自然數(shù)且 0≤x≤31. ? 手工方式完成演示 SGA過程 60 2022/2/11 SGA實例 1 max x2 : 選擇操作 61 2022/2/11 SGA實例 1 max x2 : 交叉操作 62 2022/2/11 SGA實例 1 max x2 : 變異操作 63 2022/2/11 SGA實例 2 : 連續(xù)函數(shù)最值 求下列函數(shù)的最大值 ： ( ) sin( 1 0 ) 2 .0 [ 1 , 2 ]f x x x x?? ? ? ?64 2022/2/11 SGA實例 2 : 編碼 ? 高精度 100( , .. ., ) ( 2 ) [ , ]21LiLi Liyxb a x b x y???? ? ? ? ? ?? ??編碼 ? [x,y] ? {0,1}L 必須可逆 (一個表現(xiàn)型對應一個基因型 ) ? 解碼算子 ： ?: {0,1}L ? [x,y] ? 染色體長度 L決定可行解的最大精度 長染色體 (慢進化 ) ? 實數(shù)問題 ： 變量 z為實數(shù)，如何把 {a1,…,a L} ? {0,1}L z∈ [x,y] 65 2022/2/11 SGA實例 2 : 編碼 設定求解精確到 6位小數(shù)，因區(qū)間長度位 2(1)=3,則需將區(qū) 間分為 3X106等份。因 2097152＝ 221 3X106≤222＝ 4194304。故編碼的二進制串長 L=22。 212 1 0 2 1 002 ( 1 )( , . . . , ) 1 ( 2 ) [ 1 , 2 ]21iiLib b b???? ? ? ? ? ? ?? ?將一個二進制串 (b21b20…b0) 轉化為 10進制數(shù)： . 0000000000000000000000 ? 1。 1111111111111111111111 ? 2 1110000000111111000101 ? 888 = 1+3x(1110000000111111000101) 2 /(2221) = 1+3x3674053/(2221) 66 2022/2/11 SGA實例 2 : 初始化種群、適應函數(shù) ? 隨機初始化種群 ? 適應函數(shù) 本實例目標函數(shù)在定義域內均大于 0， 且是求函數(shù)最大值，故直接引用目標函數(shù)作為適應函數(shù)：