【文章內容簡介】 rithm， GA)n 是模擬是模擬 生物進化生物進化 的自然選擇和遺傳機制的一種的自然選擇和遺傳機制的一種 尋優(yōu)尋優(yōu)算法。算法。n 適用于適用于 復雜的非線性復雜的非線性 問題問題 ,主要應用在組合優(yōu)化和機主要應用在組合優(yōu)化和機器學習兩個方面。器學習兩個方面。n 應用領域：應用領域：n 圖圖 像像 識別識別 、 圖圖 像恢復、自適像恢復、自適 應應 控制、控制、 優(yōu)優(yōu)化化 調調 度等度等 領領 域。域。n 遺傳算法的發(fā)展過程大體上可分為以下三個階段： n （（ 1）） 70年代的興起階段。年代的興起階段。n 1975年美國 Michigan 大學 法的基本理論和方法。 n 在這一時期的大部分研究都處于理論研究和建立實驗模型階段n （（ 2）） 80年代的發(fā)展階段。年代的發(fā)展階段。n 1980年 Smith教授將遺傳算法應用于機器學習領域，研制出了一個著名的分類器 (Classifier)系統(tǒng)。n 這期間許多學者對遺傳算法進行了大量的改進和發(fā)展，提出了許多成功的遺傳算法模型，使遺傳算法應用于更廣泛的領域。 n （（ 3）） 90年代的高潮階段。年代的高潮階段。n 進入 90年代后，遺傳算法作為一種實用、高效的優(yōu)化技術，得到了極為迅速的發(fā)展。 遺傳算法原理 遺傳算法原理 遺傳算法工作過程 遺傳算法的理論基礎 遺傳算法的基本特征 遺傳算法的工作過程n 遺傳算法是一種群體型操作，該操作以群體中的所有個體為對象。n 個體就是模擬生物個體而對問題中的對象（一般就是問題的解）的一種稱呼，一個個體也就是搜索空間中的一個點。n 種群 (population)就是模擬生物種群而由若干個體組成的群體 , 它一般是整個搜索空間的一個很小的子集。n 遺傳算法的三個主要操作算子 ： 選擇 （ selecation）、交叉 （ crossover）和 變異 （ mutation） 構成了遺傳操作（ Geicoperation），使遺傳算法具有了其他傳統(tǒng)方法所沒有的特性。產生新一代群體編碼和初始群體形成輸出種群個體適應值滿意否？ 遺傳算法的工作過程n 首先將問題的每個可能的解按某種形式編碼，編碼后的解稱作染色體（個體）。n 隨機選取 N個染色體構成 初始種群，再根據 預定 的 評價函數 對每個染色體計算適應值，使得性能較好的染色體具有 較高 的適應值。n 選擇 適應值高 的染色體進行復制，通過遺傳算子來產生一群新的更適應環(huán)境的染色體，形成新的種群。n 這樣一代一代不斷繁殖，最后收斂到一個最適應環(huán)境的個體上，求得問題的最優(yōu)解。遺傳算子選擇交叉變異1. 群體中個體的編碼n 如何將問題描述成位串的形式，即問題編碼。一如何將問題描述成位串的形式，即問題編碼。一般將問題的參數用般將問題的參數用 二進制位二進制位 （基因）編碼構成子（基因）編碼構成子串，再將串，再將 子串子串 拼接起來構成拼接起來構成 “染色體染色體 ”位串。位串。 遺傳算法的工作過程例如：例如： 個體個體 染色體染色體 9 1001（（ 2， 5， 6）） 010 101 1102. 適應值函數的確定n 遺傳算法的執(zhí)行過程中，每一代有許多不同的染色體（個體）同時存遺傳算法的執(zhí)行過程中，每一代有許多不同的染色體（個體）同時存在，這些染色體中哪個保留在，這些染色體中哪個保留 (生存生存 )、哪個淘汰、哪個淘汰 (死亡死亡 )是根據它們對環(huán)是根據它們對環(huán)境的適應能力決定的，適應性強的有更多的機會保留下來。境的適應能力決定的，適應性強的有更多的機會保留下來。n 適應性強弱適應性強弱 是計算個體適應值函數是計算個體適應值函數 f(x)的值來判別的，這個值稱為適的值來判別的，這個值稱為適應值應值 (fitness)。n 適應值函數 (即評價函數 )是根據 目標函數 確定的。適應值總是 非 負的，任何情況下總是希望越大越好。如果目標函數不是取最大值時，需要將它映射成適應值函數。 適應值函數適應值函數 f(x)的構成與目標函數有密切的構成與目標函數有密切關系，往往是目標函數的變種。關系，往往是目標函數的變種。n 一般是一個實值函數。該函數就是遺傳算法中指導搜索的評價函數。 遺傳算法的工作過程n （一）選擇（一）選擇 (Selection)算子算子n （二）交叉（二）交叉 (Crossover)算子算子n （三）變異（三）變異 (Mutation)算子算子 遺傳算法的工作過程n 它又稱 復制 (reproduction) 、繁殖算子。n 選擇是從種群中選擇生命力強的染色體產生 新種群的過程 。依據每個染色體的適應值大小，適應值越大，被選中的概率就越大，其子孫在下一代產生的個數就越多。n 選擇操作是建立在群體中個體的 適應值估評基礎 上的。 遺傳算法的工作過程（一）選擇（一）選擇 (Selection)算子算子通常做法是：對于一個規(guī)模為 N的種群 S,按每個染色體 xi∈ S的選擇概率 P(xi)所決定的選中機會 ,分 N次從 S中隨機選定 N個染色體 ,并進行復制。 遺傳算法的工作過程這里的選擇概率 P(xi)的計算公式為（一）選擇（一）選擇 (Selection)算子算子（二）交叉（二）交叉 (crossover)算子算子n 它又稱 重組 (rebination) 、配對 (breeding)算子， 在遺傳算法中起著核心作用。n 染色體重組是分兩步驟進行的 :n 首先在新復制的群體中隨機 選 取 兩個 個體n 然后，沿著 這 兩個個體 (字符串 )隨機地取一個位置，二者互換 從 該 位置起的末尾部分。n 交叉率 (crossover rate)就是 參加 交叉運算的染色體個數占 全體 染色體總數的比例，記為 Pc,取值范圍一般為 ～ 。 遺傳算法的工作過程 遺傳算法的工作過程例 1:有兩個用二進制編碼的個體 A和 B。長度 L=5， A=a1a2a3a4a5 ，B=b1b2b3b4b5隨機選擇一整數 k∈ [1， L1] ，設 k=4，經交叉后變?yōu)椋篈 = a1a2a3|a4a5 ? B = b1b2b3|b4b5 A’= a1a2a3 b4b5? B’ = b1b2b3 a4a5s1′=01000101, s2′=10011011可以看做是原染色體 s1和 s2的子代染色體?！　±?2,設染色體 s1=01001011, s2=10010101,交換其后 4位基因 ,即（二）交叉（二）交叉 (crossover)算子算子n 變異就是以 很小的概率 ，隨機地改變字符串 某個位置 上的值。變異操作是按位（ bit）進行的，即把某一位的內容進行變異。在二進制編碼中，就是將某位 0變成 1， 1變成 0。n 選擇和交叉算子基本上完成了遺傳算法的大部分搜索功能，而變異則增加了遺傳算法找到 接近最優(yōu)解 的能力。n 變異率 (mutation rate)是指發(fā)生 變異 的基因位數所占 全體 染色體的基因總位數的比例，記為 Pm，取值范圍一般為 ～ 。 它保證了遺傳算法的有效性。 遺傳算法的工作過程（三）變異（三）變異 (Mutation)算子算子 遺傳算法的工作過程例如例如 : 設染色體設染色體 s=11001101將其第三位上將其第三位上的的 0變?yōu)樽優(yōu)?1, 即即 s=11001101 →→ 11101101= s′。 s′也可以看做是原染色體也可以看做是原染色體 s的子代染色體。的子代染色體。（三）變異（三）變異 (Mutation)算子算子n 遺傳算法中的參數遺傳算法中的參數n 包括群體中個體的數目、交叉概率、包括群體中個體的數目、交叉概率、 變變 異概率等異概率等n 這這 些參數的些參數的 設設 定隨具體定隨具體 問題問題 的不同將有所差的不同將有所差 別別， 帶帶 有有 經驗經驗 性，它會影響性，它會影響 遺傳遺傳 算法的迭代收算法的迭代收 斂斂過過 程。程。 遺傳算法的工作過程n 1. 遺傳算法的處理對象是問題參數的編碼個體（位串）n 遺傳算法要求將問題的參數編碼成遺傳算法要求將問題的參數編碼成 長度有限長度有限的位串的位串 。n 遺傳算法是在遺傳算法是在 求解問題的編碼串求解問題的編碼串 上進行操作上進行操作，從中找出高適應值的位串，而不是對問題，從中找出高適應值的位串，而不是對問題目標函數和它們的參數直接操作。目標函數和它們的參數直接操作。n 遺傳算法遺傳算法 不受不受 函數限制條件函數限制條件 (如導數存在、連如導數存在、連續(xù)性、單極值等續(xù)性、單極值等 )的約束。的約束。 遺傳算法的基本特征 n 2. 遺傳算法的搜索是從問題解 位串集 開始搜索，而不是從單個解開始n 在最優(yōu)化問題中，傳統(tǒng)的方法是從在最優(yōu)化問題中，傳統(tǒng)的方法是從 一個點一個點 開始搜開始搜索，如爬山法。一般復雜問題會在索，如爬山法。一般復雜問題會在 “地形地形 ”中出現(xiàn)中出現(xiàn)若干若干 “山峰山峰 ”，傳統(tǒng)的方法很容易走入假，傳統(tǒng)的方法很容易走入假 “山峰山峰 ”。n 遺傳算法遺傳算法 同時同時 從種群的每個個體開始搜索，象一從種群的每個個體開始搜索，象一張網罩在張網罩在 “地形地形 ”上，數量極大的個體同時在很多上，數量極大的個體同時在很多區(qū)域中進行搜索，這樣就區(qū)域中進行搜索，這樣就 減少了陷入局部解減少了陷入局部解 的可的可能性。能性。 遺傳算法的基本特征 n 3. 遺傳算法只使用目標函數 (即適應值 )來搜索，而不需要導數等其他輔助信息n 傳統(tǒng)搜索算法需要一些傳統(tǒng)搜索算法需要一些 輔助信息輔助信息 ，如梯度算法需要導數，如梯度算法需要導數，當這些信息不存在時，這些算法就失效了。而遺傳算法當這些信息不存在時，這些算法就失效了。而遺傳算法 只只需目標函數和編碼串，因此，遺傳算法幾乎可以處理任何需目標函數和編碼串，因此，遺傳算法幾乎可以處理任何問題。問題。n 4. 遺傳算法使用的三種遺傳算子是一種隨機操作，而不是確定性規(guī)則n 遺傳算法使用隨機操作，但并不意味著遺傳算法是簡單的遺傳算法使用隨機操作，但并不意味著遺傳算法是簡單的隨機搜索。遺傳算法是使用隨機工具來指導搜索向著一個隨機搜索。遺傳算法是使用隨機工具來指導搜索向著一個最優(yōu)解前進。最優(yōu)解前進。n n ，并具有擴展性；易于同別的技術結合使用 遺傳算法的基本特征 優(yōu)化模型的遺傳算法求解 優(yōu)化模型的計算是遺傳算法最基本的也是最重要的研究和應用領域之一。 一般說來，優(yōu)化計算問題通常帶有大量的局部極值點，往往是不可微的、不連續(xù)的、多維的、有約束條件的、高度非線性的 NP完全問題。 精確地求解優(yōu)化問題的 全局最優(yōu)解 一般是不可能的。 旅行商問題（ TSP）的遺傳算法求解實例 已知 n個城市的地理位置（ x,y），求經過所有城市，并回到出發(fā)城市且每個城市僅經過一次的最短距離。 這是一個 NP完全問題，其計算量為城市個數的指數量級 。現(xiàn)用遺傳算法來解決這個問題。 編碼 31578910426每條路徑每條路徑 對應對應 一個一個 個體，個體形式地表示為個體，個體形式地表示為R={City_No|City_No互不重復互不重復 }n， n為城市數。例如對為城市數。例如對于于 n=10的的 TSP問題，對其中一個個體問題，對其中一個個體它表示一條城市路徑它表示一條城市路徑3 1 5 7 8 9 10 4 2 6其中其中 ni表示個體中第表示個體中第 i位的城市編號，位的城市編號， n11=n1。適應值為非負，且取值越大越好。適應值為非負，且取值越大越好。 表示所有個體的路表示所有個體的路徑長度的總和徑長度的總和適應值函數 每個個體代表一條可能的路徑。個體每個個體代表一條可能的路徑。個體 n的適應值為：的適應值為：其中其中 N為種群數，為種群數， Dn為為 沿個體標示的城市序列的所經過的沿個體標示的城市序列的所經過的距離距離 :交叉 隨機地從種群中選出要交叉的 兩個不同個體 ，隨機地選取一個交叉段。交叉段中兩個個體的對應部分通過匹配換位實現(xiàn)交叉操作。對個體 A和 B： A＝ 9 8 4 |5 6 7| 1 3 2 10 B＝ 8 7 1 |4