人工智能遺傳算法

1、第4章 遺傳算法,4.1 基本概念 4.2 選擇算子 4.3 交叉算子 4.4 變異算子4.5 基本遺傳算法 4.6 基本實現(xiàn)技術(shù)4.7 遺傳算法應(yīng)用,第4章 遺傳算法,生物進化自然法則優(yōu)勝劣汰適者生存有性繁殖基因通過有性繁殖不斷進行混合和重組遺傳算法從生物界按照自然選擇和有性繁殖、遺傳變異的自然進化現(xiàn)象中得到啟發(fā)，而設(shè)計的一種優(yōu)化搜索算法,第4章 遺傳算法,應(yīng)用函數(shù)優(yōu)化組合優(yōu)化：旅行商、圖形化分…生產(chǎn)

2、調(diào)度：車間調(diào)度、生產(chǎn)規(guī)劃…自動控制：控制器、參數(shù)辨識…機器人智能控制：機器人路徑規(guī)劃、運動軌跡規(guī)劃…圖像處理與模式識別：特征提取、圖像分割…人工生命：進化模型、學習模型、行為模型…遺傳程序設(shè)計機器學習,4.1 基本概念,個體個體就是模擬生物個體而對問題中的對象（一般就是問題的解）的一種稱呼一個個體也就是搜索空間中的一個點種群 種群(population)就是模擬生物種群而由若 干個體組成的群體它一般

3、是整個搜索空間的一個很小的子集通過對種群實施遺傳操作，使其不斷更新?lián)Q代而實現(xiàn)對整個論域空間的搜索,4.1 基本概念,適應(yīng)度(fitness)借鑒生物個體對環(huán)境的適應(yīng)程度，而對問題中的個體對象所設(shè)計的表征其優(yōu)劣的一種測度適應(yīng)度函數(shù)(fitness function)問題中的全體個體與其適應(yīng)度之間的一個對應(yīng)關(guān)系一般是一個實值函數(shù)該函數(shù)就是遺傳算法中指導搜索的評價函數(shù),4.1 基本概念,染色體(chromosome)染色體是由若

4、干基因組成的位串（生物學）個體對象由若干字符串組成來表示（遺傳算法）遺傳算法(genetic algorithm)染色體就是問題中個體的某種字符串形式的編碼表示染色體以字符串來表示基因是字符串中的一個個字符,個體 染色體 9 ---- 1001 （2，5，6）---- 010 101 110,4.1 基本概念,遺傳算子(genetic oper

5、ator)選擇(selection)交叉(crossover)變異(mutation),4.2 選擇算子,選擇算子模擬生物界優(yōu)勝劣汰的自然選擇法則的一種染色體運算從種群中選擇適應(yīng)度較高的染色體進行復(fù)制，以生成下一代種群算法：個體適應(yīng)度計算在被選集中每個個體具有一個選擇概率選擇概率取決于種群中個體的適應(yīng)度及其分布個體適應(yīng)度計算，即個體選擇概率計算個體選擇方法按照適應(yīng)度進行父代個體的選擇,4.2 選擇算子,個體適應(yīng)度

6、計算按比例的適應(yīng)度計算(proportional fitness assignment)基于排序的適應(yīng)度計算(rank-based fitness assignment)個體選擇方法輪盤賭選擇(roulette wheel selection)隨機遍歷抽樣(stochastic universal sampling)局部選擇(local selection)截斷選擇(truncation selection)錦標賽選擇

7、(tournament selection),4.2.1 按比例的適應(yīng)度計算,算法： 對一個規(guī)模為N的種群S，按每個染色體xi?S的選擇概率P(xi)所決定的選中機會，分N次從S中隨機選擇N個染色體，并進行復(fù)制 其中：f為適應(yīng)度函數(shù)f(xi)為xi的適應(yīng)度,優(yōu)勝劣汰概率越高，隨機選中概率越大概率越高，選中次數(shù)越多適應(yīng)度高的染色體后代越多,4.2.3 輪盤賭選擇,原理：做一個單位圓，然后按各個染色體的選擇概率

8、將圓面劃分為相應(yīng)的扇形區(qū)域轉(zhuǎn)動輪盤，輪盤靜止時指針指向某一扇區(qū)，即為選中扇區(qū)，相應(yīng)的個體/染色體即被選中,,,4.2.3 輪盤賭選擇,算法：在[0, 1]區(qū)間，產(chǎn)生一個均勻分布的偽隨機數(shù)r若r?q1，則染色體1被選中若qk-1< r?qk(2 ?k?N)，則染色體k被選中其中qi為染色體xi(i=1, 2, …, n)的累積概率一個染色體xi被選中的次數(shù)，可由期望值e(xi)來確定 為種群S中全體

9、染色體的平均適應(yīng)度,4.3 交叉算子,交叉算子交換、交配、雜交互換兩個染色體某些位上的基因隨機化算子，生成新個體,4.3 交叉算子,一點雜交產(chǎn)生一個在1到L－1之間的隨機數(shù)I配對的兩個串相互對應(yīng)的交換從i＋1到L的位段,4.3 交叉算子,例3.1設(shè)染色體s1 = 1011 0111 00 染色體s2 = 0001 1100 11 交換其后2位基因,4.4 變異算子,變異算子突變改變?nèi)旧w某個/些位上的基因

10、隨機化算子，生成新個體次要算子，但在恢復(fù)群體中失去的多樣性方面具有潛在的作用,4.4 變異算子,例4.1設(shè)染色體s = 1011 0111 00,4.5 基本遺傳算法,遺傳算法對種群中的染色體反復(fù)做三種遺傳操作使其朝著適應(yīng)度增高的方向不斷更新?lián)Q代，直至出現(xiàn)了適應(yīng)度滿足目標條件的染色體為止算法拓展遺傳算法在自然與社會現(xiàn)象模擬、工程計算等方面得到了廣泛的應(yīng)用基本遺傳算法是Holland提出的一種統(tǒng)一的最基本的遺傳算法，簡稱S

11、GA（Simple Genetic Algorithm )、CGA（Canonical Genetic Algorithm）其它的“GA類”算法稱為GAs(Genetic Algorithms）,可以把GA看作是GAs的一種特例,4.5 基本遺傳算法,參數(shù)種群規(guī)模種群的大小，用染色體個數(shù)表示最大換代數(shù)種群更新?lián)Q代的上限，也是算法終止一個條件交叉率Pc參加交叉運算的染色體個數(shù)占全體染色體總數(shù)的比例取值范圍：0.4-0.99

12、變異率Pm發(fā)生變異的基因位數(shù)占全體染色體的基因總位數(shù)的比例取值范圍：0.0001-0.1染色體編碼長度L,4.5 基本遺傳算法,算法,步1 ：在論域空間U上定義一個適應(yīng)度函數(shù)f(x)，給定種群規(guī)模N，交叉率Pc， 變異率Pm，代數(shù)Gen步2： 隨機產(chǎn)生U中的N個染色體s1,s2…sN, 組成初始種群S={s1,s2…sN}，置代 數(shù)t=1步3：若終止條件滿足，則取S中適應(yīng)度最大的

13、染色體作為所求結(jié)果，算法結(jié)束步4：計算S中每個染色體的適應(yīng)度f()步5： 按選擇概率p(si)所決定的選中機會，每次從S中隨機選中1個染色體并將 其復(fù)制，共做N次，然后將復(fù)制得到的N染色體組成群體S1步6 ：按Pc所決定的參加交叉的染色體數(shù)c，從S1中隨機確定c個染色體，配對 進行交叉操作，并用產(chǎn)生的染色體代替原染色體，組成群體S2步7 ：按Pm所決定的變異次數(shù)m，從S2中隨機確定m個染

14、色體，分別進行變異 操作，并用產(chǎn)生的新染色體代替原染色體，組成群體S3步8 ：將群體S3作為新種群，即用S3代替S， Gen = Gen +1，轉(zhuǎn)步3,4.5 流程圖,4.6 基本實現(xiàn)技術(shù),編碼方法二進制編碼格雷編碼編碼規(guī)則應(yīng)使用能易于產(chǎn)生與所求問題相關(guān)的且具有低階、短定義長度模式的編碼方案應(yīng)使用能使問題得到自然表示或描述的具有最小編碼字符集的編碼方案,4.6 基本實現(xiàn)技術(shù),適應(yīng)值函數(shù)適應(yīng)值函數(shù)必須是

15、正數(shù)出現(xiàn)負數(shù)時應(yīng)進行變換，常用變換方式有三種：線性比例法：g(x) = a*f(x)+b (b>0)指數(shù)比例法：g(x) = exp(a f(x)) (a?0)冪指數(shù)比例法：g(x) = (f(x))a (a為偶數(shù)),4.7 算法舉例,例7.1 利用遺傳算法求解區(qū)間[0,31]上的二次函數(shù)y=x2的最大值分析原問題轉(zhuǎn)化為[0,31]中尋找能使y取最大值的點x區(qū)間[0,31]為論域空間/解空間x為個

16、體對象函數(shù)f(x)= x2 可作為適應(yīng)度函數(shù),4.7 算法舉例,解：定義適應(yīng)度函數(shù)，編碼染色體適應(yīng)度函數(shù)取f(x)= x2 用5位二進制數(shù)作為個體x的基因型編碼/染色體設(shè)定種群規(guī)模，產(chǎn)生初始種群種群規(guī)模N=4初始種群S={s1=01101(13),s2=11000(24)， s3=01000(8)， s4=10011(19)},4.7 算法舉例,計算各代種群中各染色體的適應(yīng)度，并進行遺傳操作 選擇設(shè)從區(qū)間[0

17、,1]產(chǎn)生4個隨機數(shù)r1=0.45, r2=0.11, r3=0.57, r4=0.98按輪盤賭選擇法，染色體s1,s2，s3，s4依次選中次數(shù)為1，2，0，1選擇產(chǎn)生種群S1={s?1=11000(24),s?2=01101(13)， s?3=11000(24)， s?4=10011(19)},4.7 算法舉例,交叉設(shè)交叉率Pc=100%,即S1全部染色體參與交叉將s?1與s?2配對，s?3與s?4配對，交換后兩位基因新種群

18、S2={s?1=11001(25),s?2=01100(12)， s?3=11011(27)，s?4=10000(16)}變異設(shè)變異率Pm=0.001種群變異基因位數(shù)： Pm*L*N=0.001*5*4=0.020.02不足1，本輪不做變異--------------第一代遺傳操作完成----------------第二代種群S={s1=11001(25),s2=01100(12)， s3=11011(27)，s4=1000

19、0(16)},4.7 算法舉例,選擇設(shè)從區(qū)間[0,1]產(chǎn)生4個隨機數(shù)r1=0.25, r2=0.41, r3=0.77, r4=0.98按輪盤賭選擇法，染色體s1,s2，s3，s4依次選中次數(shù)為1，1，1，1選擇產(chǎn)生種群S1={s?1=11001(25),s?2=01100(12)， s?3=11011(27)， s?4=10000(16)},4.7 算法舉例,交叉將s?1與s?2配對，s?3與s?4配對，交換后三位基因

20、新種群S2={s?1=11100(28),s?2=01001(9)， s?3=11000(24)，s?4=10011(19)}變異種群變異基因位數(shù)： Pm*L*N=0.001*5*4=0.020.02不足1，本輪不做變異--------------第二代遺傳操作完成----------------第三代種群S={s1=11100(28),s2=01001(9)， s3=11000(24)，s4=10011(19)},4.7

21、 算法舉例,選擇設(shè)從區(qū)間[0,1]產(chǎn)生4個隨機數(shù)r1=0.25, r2=0.41, r3=0.77, r4=0.98按輪盤賭選擇法，染色體s1,s2，s3，s4依次選中次數(shù)為2，0，1，1選擇產(chǎn)生種群S1={s?1=11100(28),s?2=11100(28)， s?3=11000(24)， s?4=10011(19)},4.7 算法舉例,交叉將s?1與s?4配對，s?2與s?3配對，交換后兩位基因新種群S2={s?

22、1=11111(31),s?2=11100(28)， s?3=11000(24)，s?4=10000(16)}變異種群變異基因位數(shù)： Pm*L*N=0.001*5*4=0.020.02不足1，本輪不做變異--------------第三代遺傳操作完成----------------第四代種群S={s1=11111(31),s2=11100(28)， s3=11000(24)，s4=10000(16)},4.7 算法舉例,在這

23、一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體s1=11111。遺傳操作終止，將染色體“11111”作為最終結(jié)果輸出。將染色體“11111”解碼為表現(xiàn)型，得所求最優(yōu)解：31將31代入函數(shù)y=x2中，即得原問題的解，即函數(shù)y=x2的最大值為961,4.7 算法舉例,,Y,,,,,,小結(jié),遺傳算法模擬自然選擇和有性繁殖、遺傳變異的自然原理實現(xiàn)優(yōu)化搜索和問題求解遺傳操作選擇算子交叉算子變異算子,小結(jié),特點直接對結(jié)構(gòu)對象操作，不存在