人工智能及其應(yīng)用chapter6_071103課件

1、6.1 遺傳算法及其數(shù)學(xué)基礎(chǔ)標(biāo)準(zhǔn)遺傳算法及基本術(shù)語 模式定理人工智能及其應(yīng)用1標(biāo)準(zhǔn)遺傳算法及基本術(shù)語標(biāo)準(zhǔn)遺傳算法基本流程：參數(shù)編碼初始群體設(shè)定適應(yīng)度函數(shù)的設(shè)計(jì)遺傳操作: 選擇、交叉、變異控制參數(shù)設(shè)定進(jìn)化停止準(zhǔn)則 人工智能及其應(yīng)用2模式定理模式 基于三值字符集0,1,*所產(chǎn)生的可描述某種結(jié)構(gòu)相似性的字符串稱為模式。模式是描述個(gè)體字符串集的模板。模式的階 模式H中確定位置（位）的個(gè)數(shù)稱為該模式的階，記為O(H)。 模式的定義距 模式H中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離稱為該模式的定義距，記為 。人工智能及其應(yīng)用3模式定理選擇操作對(duì)模式的影響 交叉操作對(duì)模式的影響變異操作對(duì)模式的影響人工智

2、能及其應(yīng)用4模式定理經(jīng)選擇、交叉、變異操作后,子代中模式H的數(shù)目為： 模式定理： 在遺傳算子選擇、交叉和變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模式，在子代中將以指數(shù)級(jí)增長。人工智能及其應(yīng)用5模式定理積木塊假設(shè)： 低階、短距、高平均適應(yīng)度的模式（積木塊）在遺傳算子的作用下相互結(jié)合，能生成高階、長距、高平均適應(yīng)度的模式，并最終生成全局最優(yōu)解。 模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)級(jí)增長，從而滿足了尋找最優(yōu)解的必要條件，即遺傳算法存在著尋找全局最優(yōu)解的可能性。而積木塊假設(shè)則指出，遺傳算法具備尋找到全局最優(yōu)解的能力，即積木塊在遺傳算子的作用下，能生成高階、長距、高平均適應(yīng)度

3、的模式，并最終生成全局最優(yōu)解。人工智能及其應(yīng)用66.2 遺傳算法的設(shè)計(jì) 編碼 初始群體設(shè)定 適應(yīng)度函數(shù)選擇算子交叉算子變異算子人工智能及其應(yīng)用7編碼二進(jìn)制編碼十進(jìn)制編碼Gray編碼多參數(shù)映射編碼可變長度染色體編碼多維染色體編碼人工智能及其應(yīng)用8初始群體設(shè)定群體規(guī)模的確定:群體規(guī)模大個(gè)體多樣性高陷入局部解的危險(xiǎn)小。但是規(guī)模太大計(jì)算量加大。如果群體規(guī)模小遺傳算法在搜索空間中的分布范圍受限搜索過程可能提前停止于未成熟階段(引起未成熟收斂) 必須保持群體的多樣性。人工智能及其應(yīng)用9初始群體設(shè)定初始群體的生成：遺傳算法中，初始群體中的個(gè)體可以根據(jù)具體的編碼方法、在盡可能滿足群體多樣性的前提下隨機(jī)產(chǎn)生。先

4、隨機(jī)生成一定數(shù)目的個(gè)體，然后從中挑選出性能優(yōu)良的個(gè)體加入到群體中。重復(fù)該過程，直至滿足群體規(guī)模。 人工智能及其應(yīng)用10適應(yīng)度函數(shù)將目標(biāo)函數(shù)映射為適應(yīng)度函數(shù)：如果待求解問題是使目標(biāo)函數(shù)最小，則GA中可采用如下變換：當(dāng)原目標(biāo)函數(shù)是求最大化的利潤或效用函數(shù)時(shí)，可以按照下式變換： 人工智能及其應(yīng)用11適應(yīng)度函數(shù)適應(yīng)度調(diào)整： 線性調(diào)整 線性調(diào)整出現(xiàn)非負(fù)現(xiàn)象 人工智能及其應(yīng)用12選擇算子適應(yīng)度比例法: 也稱為輪盤賭法。群體中適應(yīng)度值大的個(gè)體被選擇的概率大，而適應(yīng)度值低的個(gè)體被選擇概率低。人工智能及其應(yīng)用13選擇算子最佳個(gè)體保存法(精英選擇法): 群體中適應(yīng)度最高的個(gè)體不經(jīng)過遺傳操作，直接復(fù)制到下一代群體中

5、群體中。排序選擇方法: 根據(jù)適應(yīng)度的大小對(duì)個(gè)體進(jìn)行排序，然后把事先設(shè)計(jì)好的概率表分配給個(gè)體，作為各自的選擇概率。 個(gè)體的選擇概率與其適應(yīng)度無直接關(guān)系，僅與其在群體中的排序相關(guān)。 人工智能及其應(yīng)用14選擇算子聯(lián)賽選擇方法: 從群體中任意選擇一定數(shù)量的個(gè)體（稱為聯(lián)賽規(guī)模），將其中適應(yīng)度最高的個(gè)體保存到下一代。反復(fù)執(zhí)行該過程，直到保存到下一代的個(gè)體數(shù)目達(dá)到預(yù)先設(shè)定的數(shù)目為止。聯(lián)賽規(guī)模一般取2。人工智能及其應(yīng)用15交叉算子單點(diǎn)交叉多點(diǎn)交叉 人工智能及其應(yīng)用16交叉算子一致交叉 通過屏蔽字來決定新個(gè)體對(duì)父輩個(gè)體基因位的繼承。 屏蔽字可以隨機(jī)生成，由于概率的因素，會(huì)使模式被破壞的機(jī)率增加。人工智能及其應(yīng)用

6、17變異算子基本變異算子 對(duì)二值編碼，隨機(jī)選擇c個(gè)基因位作為待變異位置，然后根據(jù)設(shè)定的變異概率pm 對(duì)這些基因位的值進(jìn)行取反操作，即1變?yōu)?，0變?yōu)?。逆轉(zhuǎn)變異算子 隨機(jī)挑選兩個(gè)逆轉(zhuǎn)點(diǎn)，然后將兩個(gè)逆轉(zhuǎn)點(diǎn)之間的基因值按變異概率逆向排列。 人工智能及其應(yīng)用18變異算子自適應(yīng)變異算子 變異概率不固定，它隨群體中個(gè)體的多樣性自適應(yīng)調(diào)整。群體多樣性越大，變異概率越小；多樣性越差，變異概率越大。 如：可根據(jù)交叉所得的兩個(gè)新個(gè)體的Hamming距進(jìn)行變異概率的調(diào)整，Hamming距越小，變異概率越大；Hamming距越大，變異概率越小。 人工智能及其應(yīng)用196.3 改進(jìn)的遺傳算法 微種群算法 雙種群算法 自

7、適應(yīng)遺傳算法人工智能及其應(yīng)用20微種群算法算法步驟:(1) 在群體中隨機(jī)選擇n個(gè)個(gè)體組成微群體。(2) 計(jì)算適應(yīng)度并確定最好的個(gè)體，直接遺傳到下一代，保證優(yōu)良的模式信息不致丟失。(3) 按照聯(lián)賽選擇策略確定其余個(gè)體。(4) 以概率1進(jìn)行交叉運(yùn)算，以加速產(chǎn)生確定位高的模式。這樣處理之后可以保證有足夠多的種類。(5) 檢驗(yàn)收斂條件，如果收斂則轉(zhuǎn)(1)；否則轉(zhuǎn)至(2)。人工智能及其應(yīng)用21雙種群算法基本思想:用兩個(gè)群體分工協(xié)作解決多模態(tài)函數(shù)尋優(yōu)時(shí)的矛盾。 (1)全局種群，用于尋找可能存在最優(yōu)解的區(qū)域； (2)局部種群，用于搜索全局種群劃分的區(qū)域，找到 該區(qū)域中的最優(yōu)解。兩個(gè)種群的特點(diǎn)：全局搜索種群注

8、重搜索未知區(qū)域，要求被處理的信息多、處理速度快，但對(duì)精度要求不高，不能陷入局部最小點(diǎn)；局部種群注重搜索有局部最優(yōu)解的區(qū)域，搜索范圍較小，要求搜索速度快。人工智能及其應(yīng)用22自適應(yīng)遺傳算法基本思想：當(dāng)個(gè)體適應(yīng)度趨于一致或局部最優(yōu)時(shí)，增加交叉和變異概率；當(dāng)群體個(gè)體適應(yīng)度比較分散時(shí)，減少交叉和變異概率。對(duì)于適應(yīng)度高于群體平均適應(yīng)度值的個(gè)體，選擇較低的交叉和變異概率；對(duì)于適應(yīng)度低于群體平均適應(yīng)度的個(gè)體，選擇較高的交叉和變異概率。人工智能及其應(yīng)用236.4 協(xié)進(jìn)化算法 協(xié)進(jìn)化算法基本流程代表個(gè)體的選擇人工智能及其應(yīng)用24協(xié)進(jìn)化算法基本流程特點(diǎn): 協(xié)進(jìn)化算法包含多個(gè)群體，分別表示不同的物種，進(jìn)化過程中各群

9、體間相互關(guān)聯(lián)。協(xié)進(jìn)化算法分為:協(xié)作型協(xié)進(jìn)化競爭型協(xié)進(jìn)化人工智能及其應(yīng)用25協(xié)進(jìn)化算法基本流程協(xié)進(jìn)化算法流程協(xié)進(jìn)化算法與傳統(tǒng)的遺傳算法基本相同。差異在于各群體中個(gè)體適應(yīng)度的計(jì)算方法。人工智能及其應(yīng)用26協(xié)進(jìn)化算法基本流程協(xié)進(jìn)化算法中個(gè)體適應(yīng)度的計(jì)算：(1) 選擇待評(píng)價(jià)群體P ；(2) 從其它群體中選擇代表個(gè)體；(3) 對(duì)群體P中每個(gè)個(gè)體i，進(jìn)行如下操作： 1) 將個(gè)體i與其它種群中挑選出的代表個(gè)體組合形成問題的解； 2) 根據(jù)定義的適應(yīng)度函數(shù)計(jì)算組合解的適應(yīng)度f ； 3) 將f 賦值給個(gè)體i 。(4) 判斷是否所有群體均被評(píng)價(jià)，若是則結(jié)束；否則選擇未評(píng)價(jià)的群體，轉(zhuǎn)(1)。人工智能及其應(yīng)用27代表個(gè)體的選擇最優(yōu)選擇法方法：選擇當(dāng)前群體中適應(yīng)度值最高的個(gè)體為代表個(gè)體。優(yōu)點(diǎn)：進(jìn)化效率比較高。缺點(diǎn)：容易陷入局部