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