人工智能遺傳算法

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

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

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

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

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

6、計(jì)算按比例的適應(yīng)度計(jì)算(proportional fitness assignment)基于排序的適應(yīng)度計(jì)算(rank-based fitness assignment)個(gè)體選擇方法輪盤(pán)賭選擇(roulette wheel selection)隨機(jī)遍歷抽樣(stochastic universal sampling)局部選擇(local selection)截?cái)噙x擇(truncation selection)錦標(biāo)賽選擇

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

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

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

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

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

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

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

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

15、正數(shù)出現(xiàn)負(fù)數(shù)時(shí)應(yīng)進(jìn)行變換，常用變換方式有三種：線(xiàn)性比例法：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的最大值分析原問(wèn)題轉(zhuǎn)化為[0,31]中尋找能使y取最大值的點(diǎn)x區(qū)間[0,31]為論域空間/解空間x為個(gè)

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

17、,1]產(chǎn)生4個(gè)隨機(jī)數(shù)r1=0.45, r2=0.11, r3=0.57, r4=0.98按輪盤(pán)賭選擇法，染色體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配對(duì)，s?3與s?4配對(duì)，交換后兩位基因新種群

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個(gè)隨機(jī)數(shù)r1=0.25, r2=0.41, r3=0.77, r4=0.98按輪盤(pán)賭選擇法，染色體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配對(duì)，s?3與s?4配對(duì)，交換后三位基因

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個(gè)隨機(jī)數(shù)r1=0.25, r2=0.41, r3=0.77, r4=0.98按輪盤(pán)賭選擇法，染色體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配對(duì)，s?2與s?3配對(duì)，交換后兩位基因新種群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中，即得原問(wèn)題的解，即函數(shù)y=x2的最大值為961,4.7 算法舉例,,Y,,,,,,小結(jié),遺傳算法模擬自然選擇和有性繁殖、遺傳變異的自然原理實(shí)現(xiàn)優(yōu)化搜索和問(wèn)題求解遺傳操作選擇算子交叉算子變異算子,小結(jié),特點(diǎn)直接對(duì)結(jié)構(gòu)對(duì)象操作，不存在