遺傳算法原理—段玉帥馬聰聰舒豪杰遺傳算法原理—段玉帥馬聰聰舒豪杰1主要內(nèi)容遺傳算法基本原理2遺傳算法概述1遺傳算法的應(yīng)用及一些問(wèn)題4遺傳算法改進(jìn)3主要內(nèi)容遺傳算法基本原理2遺傳算法概述1遺傳算法的應(yīng)用21、優(yōu)化方法遺傳算法概述傳統(tǒng)的優(yōu)化方法（局部?jī)?yōu)化）共軛梯度法、擬牛頓法、單純形方法全局優(yōu)化方法

GA、漫步法（RandomWalk）、模擬退火法遺傳算法（GA）遺傳算法是模擬在自然環(huán)境中的遺傳和進(jìn)化過(guò)程而形成的一種全適應(yīng)概率搜索算法1、優(yōu)化方法遺傳算法概述傳統(tǒng)的優(yōu)化方法（局部?jī)?yōu)化）32、遺傳算法優(yōu)點(diǎn)

遺傳算法（GA）模擬自然選擇和自然遺傳過(guò)程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個(gè)體，利用遺傳算子(選擇、交叉和變異)對(duì)這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過(guò)程，直到滿足某種收斂指標(biāo)為止。其遺傳進(jìn)化操作過(guò)程簡(jiǎn)單，容易理解。

2、遺傳算法優(yōu)點(diǎn)遺傳算法（GA）4GA流程GA流程5遺傳算法基本原理1、基本思想

模擬自然界優(yōu)勝劣汰的進(jìn)化現(xiàn)象，把搜索空間映射為遺傳空間，把可能的解編碼成一個(gè)向量——染色體，向量的每個(gè)元素稱為基因。通過(guò)不斷計(jì)算各染色體的適應(yīng)值，選擇最好的染色體，獲得最優(yōu)解。2、遺傳算法的基本運(yùn)算⑴選擇運(yùn)算⑵交換操作⑶變異遺傳算法基本原理1、基本思想2、遺傳算法的基本運(yùn)算⑴選擇運(yùn)6選擇運(yùn)算

從舊的種群中選擇適應(yīng)度高的染色體，放入匹配集（緩沖區(qū)），為以后染色體交換、變異，產(chǎn)生新的染色體作準(zhǔn)備。選擇方法——適應(yīng)度比例法（轉(zhuǎn)輪法）某染色體被選的概率：Pcxi為種群中第i個(gè)染色體，f(xi)為第i個(gè)染色體的適應(yīng)度值。選擇運(yùn)算選擇方法——適應(yīng)度比例法（轉(zhuǎn)輪法）xi為種群中第7具體步驟1）計(jì)算各染色體適應(yīng)度值2）累計(jì)所有染色體適應(yīng)度值，記錄中間累加值S-mid和最后累加值sum=∑f(xi)3）產(chǎn)生一個(gè)隨機(jī)數(shù)N，0〈N〈sum4）選擇對(duì)應(yīng)中間累加值S-mid的第一個(gè)染色體進(jìn)入交換集5）重復(fù)（3）和（4），直到獲得足夠的染色體。具體步驟1）計(jì)算各染色體適應(yīng)度值2）累計(jì)所有染色體適應(yīng)度值，8舉例：

⒈具有6個(gè)染色體的二進(jìn)制編碼、適應(yīng)度值、Pc累計(jì)值。

染色體的適應(yīng)度和所占的比例用轉(zhuǎn)輪方法進(jìn)行選擇舉例：

⒈具有6個(gè)染色體的二進(jìn)制編碼、適應(yīng)度值、Pc累計(jì)值。9染色體被選的概率染色體編號(hào)12345678910適應(yīng)度8217721211737被選概率0.10.020.220.090.020.160.140.090.030.09適應(yīng)度累計(jì)8

10

2734364859666976被選的染色體個(gè)數(shù)隨機(jī)數(shù)2349761312757所選染色體號(hào)碼37103137染色體被選的概率染色體編號(hào)12345610交換操作

方法:隨機(jī)選擇二個(gè)染色體(雙親染色體),隨機(jī)指定一點(diǎn)或多點(diǎn),進(jìn)行交換,可得二個(gè)新的染色體(子輩染色體).新的子輩染色體:A’11010001

B’01011110交換操作方法:隨機(jī)選擇二個(gè)染色體(雙親染色體),11變異模擬生物在自然界環(huán)境變化,引起基因的突變.在染色體二進(jìn)制編碼中,1變成0;或0變成1.突變產(chǎn)生染色體的多樣性,避免進(jìn)化中早期成熟,陷入局部極值點(diǎn),突變的概率很低.變異模擬生物在自然界環(huán)境變化,引起基因的突變12簡(jiǎn)單遺傳算法（GA）的基本參數(shù)①種群規(guī)模P:參與進(jìn)化的染色體總數(shù).②代溝G:二代之間不相同的染色體數(shù)目,無(wú)重疊G=1;有重疊0<G<1③選擇方法:轉(zhuǎn)輪法,精英選擇法,競(jìng)爭(zhēng)法.④交換率:Pc一般為60~100%.⑤變異率:Pm一般為0.1~10%簡(jiǎn)單遺傳算法（GA）的基本參數(shù)①種群規(guī)模P:參與進(jìn)化的染13實(shí)例1、產(chǎn)生初始種群00011000000101111001000000010110011101001010101010（8）（5）（2）（10）（7）1110010110100101101111000000011001110100000101001（12）（5）（19）（10）（14）2、計(jì)算適應(yīng)度實(shí)例1、產(chǎn)生初始種群00011000000101111143、選擇個(gè)體染色體適應(yīng)度選擇概率累積概率10001100000820101111001530000000101241001110100105101010101076111001011012710010110115811000000011991001110100101000010100111488＋5＋2＋10＋7＋12＋5＋19＋10＋140.0869570.05434858＋5＋2＋10＋7＋12＋5＋19＋10＋140.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521743、選擇個(gè)體染色體適應(yīng)度選擇概率累積概率1000110000153、選擇個(gè)體染色體適應(yīng)度選擇概率累積概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.0000003、選擇個(gè)體染色體適應(yīng)度選擇概率累積概率1000110000163、選擇在0～1之間產(chǎn)生一個(gè)隨機(jī)數(shù)：0.5459290.7845670.4469300.5078930.2911980.7163400.2709010.3714350.854641個(gè)體染色體適應(yīng)度選擇概率累積概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0869570.0543480.1413040.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.2717390.3478260.4782610.5326090.7391300.8478261.0000000.163043淘淘汰3、選擇在0～1之間產(chǎn)生一個(gè)0.5459290.784567174、交叉0001100000111001011011000000011001110100101010101011100101101001011011100111010011000000010001010011000110000011100101101100000001100111010000011110100000010110111100001011010110111100001001110100000110011101001100000001101010100010100100114、交叉000110000011100101101185、變異00011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100110001111010000001011011110000101101011011110000100111010000011001110100110000000110101010001010010011000110000011100101101100000001100111010010101010101110010110100101101111000000011001110100000101001100011110100000010110111100001011010110111100001001010100000110011101001100000001101010100010100100115、變異00011000001110010110196、至下一代，適應(yīng)度計(jì)算→選擇→交叉→變異，直至滿足終止條件。6、至下一代，適應(yīng)度計(jì)算→選擇→交叉→變異，直至滿足終止條件20遺傳算法的改進(jìn)輪盤賭選擇方式是傳統(tǒng)遺傳算法中最經(jīng)常使用的選擇手段,因?yàn)檩啽P賭選擇方式非常直觀而且也很簡(jiǎn)單,所以深受歡迎。輪盤賭不足之處：

首先是在遺傳進(jìn)化的開始階段,這個(gè)時(shí)候可能存在適應(yīng)度較高的生物個(gè)體,根據(jù)輪盤賭選擇方法,那么這個(gè)個(gè)體被選中的機(jī)會(huì)就會(huì)非常大,從而會(huì)選擇復(fù)制出相當(dāng)數(shù)量的子代,這就容易導(dǎo)致種群的多樣性喪失,種群中個(gè)體太單調(diào),很難再進(jìn)行遺傳進(jìn)化,所以也很難搜索到全局最優(yōu)解。選擇算子的改進(jìn)遺傳算法的改進(jìn)輪盤賭選擇方式是傳統(tǒng)遺傳算法中21其次是在遺傳進(jìn)化的末了階段,這個(gè)時(shí)候種群中的所有個(gè)體之間的差異不是很大了,因而適應(yīng)度也很接近,所以此時(shí)的輪盤賭選擇方法已經(jīng)無(wú)效,喪失了繼續(xù)選擇的功能,也就無(wú)法分辨種群中個(gè)體的好壞了。其次是在遺傳進(jìn)化的末了階段,這個(gè)時(shí)候種群中的22改進(jìn)方法：對(duì)種群中的全部個(gè)體來(lái)一次排序,根據(jù)種群中每個(gè)個(gè)體的適應(yīng)度高低對(duì)這些個(gè)體進(jìn)行降序列出。把這些按順序排列出來(lái)的所有個(gè)體從頭到尾依次分成四等份。適應(yīng)度最低的排在最后面的1/4比例的個(gè)體全部扔掉,也就是直接淘汰掉,不進(jìn)入到下一代當(dāng)中;把適應(yīng)度中等的排在中間的2/4比例的個(gè)體全部拷貝一份,也就是選擇到下一代當(dāng)中;剩下來(lái)的適應(yīng)度最高的排在最前面的1/4比例的個(gè)體全部拷貝兩份,也就是把這兩份都選擇到下一代當(dāng)中。改進(jìn)方法：23采用此種改進(jìn)策略進(jìn)行選擇操作可以有以下幾種好處:一、可以把適應(yīng)度非常低的個(gè)體直接淘汰出該種群，使得這些個(gè)體沒(méi)有機(jī)會(huì)進(jìn)入到下一代當(dāng)中，因此能夠提升算法的收斂速度。二、快速增加種群中適應(yīng)度較好的個(gè)體的數(shù)量，使得算法更加高效實(shí)用。采用此種改進(jìn)策略進(jìn)行選擇操作可以有以下幾種好處:24交叉算子的改進(jìn)

一些較早的遺傳算法當(dāng)中，關(guān)于交叉算子的操作是非常簡(jiǎn)陋的，也是有點(diǎn)盲目的。對(duì)于一對(duì)需要進(jìn)行交叉操作的父代個(gè)體，使用一個(gè)恒定不變的交叉概率來(lái)對(duì)這對(duì)父代個(gè)體實(shí)行交叉互換，也不論這對(duì)父代個(gè)體的相似程度如何。相似度：假定有兩個(gè)父代個(gè)體，它們的編碼是二進(jìn)制的，一個(gè)個(gè)體叫做X，另一個(gè)個(gè)體口LI做Y，則關(guān)于個(gè)體X和個(gè)體Y的相似度可以進(jìn)行這樣定義:

s=c/n

S就表示兩個(gè)父代個(gè)體的相似度，C表示個(gè)體X與個(gè)體Y的最長(zhǎng)的共同子串的長(zhǎng)度，n叫做種群中個(gè)體染色體編碼的長(zhǎng)度。交叉算子的改進(jìn)一些較早的遺傳算法當(dāng)中，關(guān)于交25

假設(shè)個(gè)體x的染色體編碼為10101011，個(gè)體Y的染色體編碼為10101110，則個(gè)體X和個(gè)體Y的最長(zhǎng)的共同子串就為101011。這個(gè)最長(zhǎng)的共同子串的長(zhǎng)度即為6，也就是C等于6，種群中個(gè)體染色體編碼的長(zhǎng)度是8，也即n等于8,因此就得到了個(gè)體X和個(gè)體Y的相似度的大小，即等于6/8。顯然，種群中任意兩個(gè)個(gè)體的相似度S的值是一個(gè)[0,1]之間的數(shù)。修正過(guò)的交叉臨界值的公式為:

r就表示交叉臨界值，g表示該種群此時(shí)的進(jìn)化代數(shù)，G表示該種群規(guī)定的總的進(jìn)化代數(shù)。假設(shè)個(gè)體x的染色體編碼為10101011，個(gè)26r是一個(gè)(1/3,2/3]之間的數(shù)，并不是固定不變的，是隨著當(dāng)前的進(jìn)化代數(shù)的增長(zhǎng)而不斷增大的。如果需要進(jìn)行交叉的兩個(gè)父代個(gè)體的相似度S大于或等于當(dāng)前的交叉臨界值r時(shí)，則不準(zhǔn)這兩個(gè)父代個(gè)體進(jìn)行交叉互換操作，以避免破壞它們的優(yōu)良基因模式。需要進(jìn)行交叉的兩個(gè)父代個(gè)體的相似度S小于當(dāng)前的交叉臨界值r時(shí)，則允許這兩個(gè)父代個(gè)體進(jìn)行交叉互換操作。r是一個(gè)(1/3,2/3]之間的數(shù)，并不是固定不變的，27在種群進(jìn)化的初期，由于種群中各個(gè)個(gè)體之間的差異比較大，因此它們的染色體編碼也具有很大的差別，這個(gè)時(shí)候種群中各個(gè)個(gè)體之間的相似程度也會(huì)很小，所以必須給出一個(gè)相對(duì)較小的交叉臨界值。隨著種群的不斷進(jìn)化，種群中各個(gè)個(gè)體之間的差異會(huì)漸漸變小，因而各個(gè)個(gè)體之間的相似程度也會(huì)漸漸提高，所以此時(shí)必須給出一個(gè)相對(duì)較大的交叉臨界值。種群中個(gè)體之間的交叉臨界值隨著當(dāng)前進(jìn)化代數(shù)動(dòng)態(tài)的改變是有道理的，有助于提高遺傳算法的收斂性能以及收斂速度。在種群進(jìn)化的初期，由于種群中各個(gè)個(gè)體之間的差異比較大，28變異算子的改進(jìn)基本遺傳算法(SGA)中,變異概率是固定不變的，通常是一個(gè)很小的常數(shù)。在遺傳進(jìn)化后期,如果變異概率不發(fā)生改變，很容易造成局部收斂的情況,從而對(duì)算法的運(yùn)行效率產(chǎn)生極大地影響。提出一種修正過(guò)的變異概率p。隨適應(yīng)度作自適應(yīng)變化的公式：

Pm為將要變異個(gè)體的變異概率，Pm_max為最大變異概率,這里取0.2，Pm_min為最小變異概率,這里取0.001，f即為將要變異個(gè)體的適應(yīng)度，f_max為種群中最大的適應(yīng)度，favg為每一代種群適應(yīng)度的平均值。變異算子的改進(jìn)基本遺傳算法(SGA)中,變異29

變異的個(gè)體的適應(yīng)度大于等于此時(shí)種群的平均適應(yīng)度時(shí)，如果將要變異個(gè)體的適應(yīng)度越大，則該個(gè)體的變異概率就越小，正好符合“優(yōu)勝劣汰,適者生存”的進(jìn)化規(guī)律。

變異的個(gè)體的適應(yīng)度小于此時(shí)種群的平均適應(yīng)度時(shí)，說(shuō)明此個(gè)體為劣質(zhì)個(gè)體或是非優(yōu)良個(gè)體，不適應(yīng)生存，為了擴(kuò)大解空間，增強(qiáng)種群的多樣性,需要給該個(gè)體一個(gè)較大的變異概率。

這樣做還可以使算法的局部搜索能力增強(qiáng)，有助于算法更快地達(dá)到全局收斂，因而能夠很好的改善遺傳算法的性能。變異的個(gè)體的適應(yīng)度大于等于此時(shí)種群的平均適應(yīng)30遺傳算法的應(yīng)用及一些問(wèn)題1、遺傳算法的應(yīng)用領(lǐng)域（1）組合優(yōu)化（2）函數(shù)優(yōu)化（3）自動(dòng)控制（4）生產(chǎn)調(diào)度（5）圖像處理（6）機(jī)器學(xué)習(xí)（7）人工生命（8）數(shù)據(jù)挖掘2、遺傳算法在應(yīng)用中的一些問(wèn)題1）知識(shí)的編碼

二進(jìn)制和十進(jìn)制的比較：二進(jìn)制有更多圖式和更大的搜索范圍；十進(jìn)制更接近于實(shí)際操作。遺傳算法的應(yīng)用及一些問(wèn)題1、遺傳算法的應(yīng)用領(lǐng)域（1）組合優(yōu)化31基本遺傳算法應(yīng)用實(shí)例：求函數(shù)的最大值

基本遺傳算法應(yīng)用實(shí)例：

32遺傳算法算法實(shí)現(xiàn)背包問(wèn)題

假定背包的最大容量為W，N件物品，每件物品都有自己的價(jià)值和重量，將物品放入背包中使得背包內(nèi)物品的總價(jià)值最大。

背包問(wèn)題是一種組合優(yōu)化的NP完全問(wèn)題。

背包問(wèn)題可以想象這樣一個(gè)場(chǎng)景—小偷在屋子里偷東西，他帶著一只背包。屋子里物品數(shù)量有限—每件物品都具有一定的重量和價(jià)值—珠寶重量輕但價(jià)值高，桌子重但價(jià)值低。最重要的是小偷背包容量有限。很明顯，他不能把桌子分成兩份或者帶走珠寶的3/4。對(duì)于一件物品他只能選擇帶走或者不帶走。遺傳算法算法實(shí)現(xiàn)背包問(wèn)題假定背包的最大容量為W遺傳算法是從代表問(wèn)題可能潛在的解集的一個(gè)種群（population）開始的，而一個(gè)種群則由經(jīng)過(guò)基因（gene）編碼的一定數(shù)目的個(gè)體(individual)組成。每個(gè)個(gè)體實(shí)際上是染色體(chromosome)帶有特征的實(shí)體。

所謂狀態(tài),

是指在一定的時(shí)空范圍內(nèi)，問(wèn)題所涉及的人、物、時(shí)間等的布局關(guān)系。通常把問(wèn)題的初始布局關(guān)系稱為初始狀態(tài)，問(wèn)題解決時(shí)到達(dá)的狀態(tài)叫目標(biāo)狀態(tài)。知識(shí)表示狀態(tài)空間遺傳算法是從代表問(wèn)題可能潛在的解集的一個(gè)種群（popu在背包問(wèn)題中，初始狀態(tài)就是有一個(gè)空包，包的重量固定為W，有N個(gè)商品，每個(gè)商品的重量為Wi,價(jià)值Ci。目標(biāo)狀態(tài)就是將n(n<=N)個(gè)商品裝入包里，包重不超過(guò)W，使得包中商品的總重量最大。狀態(tài)空間就是將商品裝入包的所有組合，本實(shí)驗(yàn)的解就是價(jià)值和最大的裝包組合。3、遺傳算法中的抽象概念在背包問(wèn)題的具體化（1）基因：0或1