第6章 遺傳算法及其應(yīng)用

人工智能原理及應(yīng)用第6章進(jìn)化算法PrinciplesandApplicationsofArtificialIntelligence問(wèn)題求解策略問(wèn)題求解：解空間搜索解的表示形式搜索的策略問(wèn)題求解策略構(gòu)造式求解:從部分解逐步構(gòu)造出完整解確定性算法:窮舉、動(dòng)態(tài)規(guī)劃、分支限界…

ABCDCDEEDECECD常常面臨組合爆炸問(wèn)題求解策略構(gòu)造式求解:從部分解逐步構(gòu)造出完整解確定性算法:窮舉、動(dòng)態(tài)規(guī)劃、分支限界…

非確定性算法:近似算法、概率算法…

ABCDCDEEDECECD問(wèn)題求解策略進(jìn)化式求解:對(duì)完整解進(jìn)行不斷改進(jìn)獨(dú)立進(jìn)化:禁忌搜索ABCDEAACBDEA問(wèn)題求解策略進(jìn)化式求解:對(duì)完整解進(jìn)行不斷改進(jìn)獨(dú)立進(jìn)化:禁忌搜索群體進(jìn)化:遺傳算法、差分進(jìn)化、粒子群優(yōu)化…

大多數(shù)進(jìn)化算法屬于非確定性算法ABCDEAABCEDAACEDBAACEBDA問(wèn)題求解策略啟發(fā)式算法利用問(wèn)題領(lǐng)域知識(shí):領(lǐng)域相關(guān)利用一般性啟發(fā)信息:領(lǐng)域獨(dú)立元啟發(fā)算法問(wèn)題求解策略啟發(fā)式算法示例:蟻群優(yōu)化算法基本思想:模擬蟻群在尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為信息素:螞蟻會(huì)優(yōu)先選擇信息素濃度較大的路徑信息素?fù)]發(fā)ABCDE。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。群體智能高等智能群體智能高等智能低等智能群體智能高等智能低等智能群體智能高等智能低等智能群智能(涌現(xiàn)智能)群體智能高等智能低等智能群智能(涌現(xiàn)智能)群體智能粒子群優(yōu)化蟻群優(yōu)化蜂群優(yōu)化魚群優(yōu)化…問(wèn)題求解策略構(gòu)造式求解:從部分解逐步構(gòu)造出完整解進(jìn)化式求解:對(duì)已有的完整解不斷進(jìn)行改進(jìn)(進(jìn)化)借鑒仿生學(xué)的思想，模擬自然界的進(jìn)化思想來(lái)求解工程優(yōu)化問(wèn)題問(wèn)題求解策略優(yōu)化問(wèn)題組合優(yōu)化問(wèn)題連續(xù)優(yōu)化問(wèn)題“任何控制與決策問(wèn)題本質(zhì)上均可歸結(jié)為優(yōu)化問(wèn)題?！薄猋u-ChiHo遺傳算法的基本概念遺傳算法中的基本思想借鑒自然進(jìn)化中“適者生存、優(yōu)勝劣汰”的規(guī)律，對(duì)一組個(gè)體（解）進(jìn)行不斷演化，最終得到問(wèn)題的最優(yōu)解或近似最優(yōu)解。遺傳算法的基本概念遺傳算法的生物學(xué)背景染色體：DNA中的主要遺傳物質(zhì)基因：構(gòu)成染色體的基本元素，能夠決定個(gè)體的某些特征個(gè)體：性狀由染色體決定適應(yīng)度：表示個(gè)體對(duì)環(huán)境的適應(yīng)程度種群：個(gè)體的集合遺傳算法的基本概念遺傳算法的建模思想染色體(個(gè)體)

優(yōu)化問(wèn)題的解基因

解向量的組成元素適應(yīng)度

解的優(yōu)劣程度種群

問(wèn)題的一組解集遺傳算法的基本概念遺傳算法中的建模思想編碼:問(wèn)題的解

染色體解碼:染色體

問(wèn)題的解適應(yīng)度函數(shù)設(shè)計(jì)遺傳算法的基本概念遺傳算法中的基本操作選擇:從當(dāng)前群體中選取較優(yōu)的個(gè)體準(zhǔn)備進(jìn)化遺傳算法的基本概念選擇(selection):適應(yīng)度越高的個(gè)體被選中的概率越大輪盤賭遺傳算法的基本概念選擇(selection):適應(yīng)度越高的個(gè)體被選中的概率越大輪盤賭錦標(biāo)賽Elitism策略遺傳算法的基本概念遺傳算法中的基本操作選擇:從當(dāng)前群體中選取較優(yōu)的個(gè)體準(zhǔn)備進(jìn)化交叉:將父代染色體按一定方式組合生成子代染色體遺傳算法的基本概念交叉(crossover):將父代的優(yōu)秀基因遺傳到子代單點(diǎn)交叉01101011001111000110110000110111遺傳算法的基本概念交叉(crossover):將父代的優(yōu)秀基因遺傳到子代單點(diǎn)交叉雙點(diǎn)交叉01101011001111000111000011101011遺傳算法的基本概念交叉(crossover):將父代的優(yōu)秀基因遺傳到子代單點(diǎn)交叉雙點(diǎn)交叉多點(diǎn)交叉遺傳算法的基本概念遺傳算法中的基本操作選擇:從當(dāng)前群體中選取較優(yōu)的個(gè)體準(zhǔn)備進(jìn)化交叉:將父代染色體按一定方式組合生成子代染色體變異:染色體的基因按一定概率發(fā)生變化遺傳算法的基本概念變異(mutation):引入新的特征位點(diǎn)變異逆轉(zhuǎn)變異互換變異移動(dòng)變異遺傳算法的基本概念遺傳算法的一般步驟選擇交叉變異適應(yīng)度評(píng)估初始化種群終止？輸出最優(yōu)解YN選擇交叉變異遺傳算法的應(yīng)用遺傳算法應(yīng)用示例:背包問(wèn)題適應(yīng)度評(píng)估初始化種群終止？輸出最優(yōu)解YN選擇交叉變異背包容量:35物品重量:10,12,8,7,6,8物品價(jià)值:15,13,12,9,8,7110000(28)011000(25)001100(21)000110(17)110000(28)011000(25)110100(37)001000(12)011010(33)110010(36)011100(34)110100(37)110000(28)011110(42)110110(45)011100(34)110110(45)011010(33)遺傳算法的應(yīng)用約束處理不選擇違反約束的解懲罰函數(shù):f(x)=v(x)-

(x)修補(bǔ)策略適應(yīng)度評(píng)估初始化種群終止？輸出最優(yōu)解YN選擇交叉變異背包容量:35物品重量:10,12,8,7,6,8物品價(jià)值:15,13,12,9,8,7遺傳算法的應(yīng)用遺傳算法應(yīng)用示例:旅行商問(wèn)題編碼:節(jié)點(diǎn)序列交叉,變異:保持解的有效性47861461532321543546787853212678遺傳算法的應(yīng)用遺傳算法應(yīng)用示例:旅行商問(wèn)題編碼:節(jié)點(diǎn)序列交叉,變異:保持解的有效性4582163736487521部分匹配交叉(PMX)4786153232154678遺傳算法的應(yīng)用遺傳算法應(yīng)用示例:旅行商問(wèn)題編碼:節(jié)點(diǎn)序列交叉,變異:保持解的有效性478XX53X321X46XX順序交叉(OX)8XX47X532XX43X168214765327843516遺傳算法的應(yīng)用遺傳算法應(yīng)用示例:旅行商問(wèn)題編碼:節(jié)點(diǎn)序列交叉,變異: