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