人工智能課件-老師2014年春22計(jì)算智能part

1、Artificial Intelligence (AI)人工智能主講：戚玉濤Email： 第五章：計(jì)算智能內(nèi)容提要第五章：計(jì)算智能1.概述2.神經(jīng)網(wǎng)絡(luò)3.模糊計(jì)算4.遺傳算法遺傳算法遺傳算法（Genetic Algorithm, GA）是模擬生物在自然環(huán)境種的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。遺傳算法最早由美國密西根大學(xué)的 J. Holland 教授提出，起源于20世紀(jì)60年代對(duì)自然和人工自適應(yīng)系統(tǒng)的研究。70年代，De Jong 基于遺傳算法的思想在計(jì)算機(jī)上進(jìn)行了大量的純數(shù)值函數(shù)優(yōu)化計(jì)算實(shí)驗(yàn)。在一系列研究工作的基礎(chǔ)上，80年代由Goldberg進(jìn)行歸納總結(jié)，形成了遺傳算法

2、的基本框架。遺傳算法遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解。遺傳算法從一組隨機(jī)初始化的候選解出發(fā)按某種指標(biāo)從解群中選取較優(yōu)的個(gè)體利用遺傳算子（選擇、交叉和變異）對(duì)這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解群重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。遺傳算法基本遺傳算法 （SGA）: 又稱簡單遺傳算法或標(biāo)準(zhǔn)遺傳算法，是由Goldberg總結(jié)出的一種最基本的遺傳算法，其遺傳進(jìn)化操作過程簡單，容易理解，是其它一些遺傳算法的雛形和基礎(chǔ)。 基本遺傳算法的組成：染色體的編碼（產(chǎn)生初始種群）染色體的適應(yīng)度函數(shù)遺傳算子（選擇、交叉、變異）運(yùn)行參數(shù)遺傳算法SGA流

3、程圖：遺傳算法染色體編碼GA是通過某種編碼機(jī)制把對(duì)象抽象為由特定符號(hào)按一定順序排成的串。SGA使用二進(jìn)制串進(jìn)行編碼。 遺傳算法染色體的適應(yīng)度函數(shù)（Affinity Function）：遺傳算法對(duì)一個(gè)染色體（候選解）的好壞用適應(yīng)度函數(shù)值來評(píng)價(jià)，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。適應(yīng)度函數(shù)是遺傳算法進(jìn)化過程的驅(qū)動(dòng)力，也是進(jìn)行自然選擇的重要標(biāo)準(zhǔn)（注意：并非唯一標(biāo)準(zhǔn)）。它的設(shè)計(jì)應(yīng)結(jié)合求解問題本身的要求而定。 遺傳算法遺傳算子選擇算子：實(shí)現(xiàn)對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰操作。適應(yīng)度高的個(gè)體被遺傳到下一代群體中的概率大；適應(yīng)度低的個(gè)體，被遺傳到下一代群體中的概率小。交叉算子：對(duì)兩個(gè)相互配對(duì)的染色體依據(jù)交叉概率

4、Pc 按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。變異算子：依據(jù)變異概率 Pm 將個(gè)體編碼串中的某些基因值用其它基因值替換，形成一個(gè)新的個(gè)體。遺傳算法選擇算子：選擇操作的任務(wù)就是按某種方法從父代群體中選取一些個(gè)體，遺傳到下一代群體。SGA中選擇算子采用輪盤賭選擇方法。 各個(gè)個(gè)體被選中的概率與其適應(yīng)度函數(shù)值大小成正比。 s40.31 s20.49 s10.14S30.06遺傳算法交叉算子：交叉運(yùn)算是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法。 SGA中的交叉算子采用單點(diǎn)交叉算子。交叉前：父代1: 00000|01110000000010000父

5、代2: 11100|00000111111000101交叉后：子代1: 00000|00000111111000101子代2: 11100|01110000000010000交叉點(diǎn)遺傳算法變異算子：遺傳算法中的變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法，它決定了遺傳算法的局部搜索能力，同時(shí)保持種群的多樣性。交叉運(yùn)算和變異運(yùn)算的相互配合，共同完成對(duì)搜索空間的全局搜索和局部搜索。 SGA中變異算子采用基本位變異算子?；疚蛔儺愃阕邮侵笇?duì)個(gè)體編碼串隨機(jī)指定的某一位或某幾位基因作變異運(yùn)算。變異運(yùn)算將被操作的基因位反置。遺傳算法遺傳算法的特點(diǎn) (1) 遺傳算法是對(duì)參數(shù)集合的編碼而非針對(duì)參數(shù)本身進(jìn)行進(jìn)化；(2)遺傳算

6、法是從問題解的編碼組（種群）開始而非從單個(gè)解開始搜索；(3)遺傳算法利用目標(biāo)函數(shù)的適應(yīng)度這一信息而非利用導(dǎo)數(shù)或其它輔助信息來指導(dǎo)搜索；(4)遺傳算法利用選擇、交叉、變異等算子而不是利用確定性規(guī)則進(jìn)行隨機(jī)操作。遺傳算法遺傳算法的優(yōu)勢 (1)適應(yīng)度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。(2)不容易陷入局部極值，能以很大的概率找到全局最優(yōu)解。(3)由于其固有的并行性，適合于大規(guī)模并行計(jì)算。(4)不是盲目窮舉，而是啟發(fā)式搜索。內(nèi)容提要第五章：計(jì)算智能（其他）1.粒子群算法2.蟻群算法內(nèi)容提要第五章：計(jì)算智能（其他）1.粒子群算法2.蟻群算法粒子群算法原理粒子群算法（PSO）粒子群算法原理粒子群

7、算法（PSO）粒子群算法原理粒子群算法（PSO）粒子群算法原理粒子群算法（PSO）粒子群算法原理粒子群算法（ Particle Swarm Optimization , PSO）粒子群優(yōu)化算法是進(jìn)化計(jì)算的一個(gè)分支，是一種模擬自然界的生物活動(dòng)的隨機(jī)搜索算法。粒子群優(yōu)化算法模擬了自然界鳥群捕食和魚群捕食的過程。通過群體中的協(xié)作尋找到問題的全局最優(yōu)解。它是1995年由美國學(xué)者Eberhart（電子電氣工程師）和Kennedy（社會(huì)心理學(xué)家）提出的，現(xiàn)在已經(jīng)廣泛應(yīng)用于各種工程領(lǐng)域的優(yōu)化問題之中。粒子群算法原理PSO的思想來源生物界現(xiàn)象群體行為群體遷徙生物覓食社會(huì)心理學(xué)群體智慧個(gè)體認(rèn)知社會(huì)影響粒子群優(yōu)化

8、算法 人工生命鳥群覓食魚群學(xué)習(xí)群理論粒子群算法原理從生物現(xiàn)象到 PSO算法鳥群覓食現(xiàn)象粒子群優(yōu)化算法粒子群算法原理從生物現(xiàn)象到 PSO算法鳥群覓食現(xiàn)象鳥群覓食空間飛行速度所在位置個(gè)體認(rèn)知與群體協(xié)作找到食物粒子群優(yōu)化算法搜索空間的一組有效解問題的搜索空間解的速度向量解的位置向量速度與位置的更新找到全局最優(yōu)解粒子群優(yōu)化算法類比關(guān)系鳥群覓食現(xiàn)象算法流程PSO算法的相關(guān)定義PSO中的個(gè)體，也叫粒子，在多維搜索空間中飛行。PSO中的每個(gè)粒子維護(hù)兩個(gè)向量位置向量xi ：粒子在解空間中的當(dāng)前位置速度向量vi ：粒子在解空間中的飛行速度pBest ：粒子自身的歷史最優(yōu)位置gBest ：群體全局最優(yōu)向量 lBe

9、st ：鄰域中的最好位置更新速度 自身速度個(gè)體認(rèn)知 社會(huì)引導(dǎo)算法流程粒子速度與位置的更新：慣性權(quán)重：加速系數(shù)（學(xué)習(xí)因子）：0,1區(qū)間上的隨機(jī)數(shù)算法流程PSO算法驅(qū)動(dòng)優(yōu)化過程的是速度vi(t)向量。速度向量反映了粒子自身的經(jīng)驗(yàn)知識(shí)和來自鄰域粒子的社會(huì)交換信息。粒子的經(jīng)驗(yàn)知識(shí)通常叫做認(rèn)知部分，它和粒子與其自身的歷史最優(yōu)位置（ pbest ）的距離成正比。社會(huì)交換信息叫做速度方程的社會(huì)部分。鄰域大小不同的兩種算法gbest PSO，全局最佳粒子群優(yōu)化lbest PSO，局部最佳粒子群優(yōu)化算法流程gbest PSO：全局最佳粒子群優(yōu)化粒子群算法粒子群算法的特點(diǎn)PSO算法收斂速度快，特別是在算法的早期，

10、但也存在著精度較低，易發(fā)散等缺點(diǎn)。若加速系數(shù)、最大速度等參數(shù)太大，粒子群可能錯(cuò)過最優(yōu)解，算法不收斂；而在收斂的情況下，由于所有的粒子都向最優(yōu)解的方向飛去，所以粒子趨向同一化（失去了多樣性），使得后期收斂速度明顯變慢，同時(shí)算法收斂到一定精度時(shí)，無法繼續(xù)優(yōu)化，所能達(dá)到的精度也不高。內(nèi)容提要第五章：計(jì)算智能（其他）1.粒子群算法2.蟻群算法蟻群算法原理蟻群的覓食行為蟻群算法原理蟻群的分工蟻群算法原理蟻穴的結(jié)構(gòu)蟻群算法原理蟻穴的結(jié)構(gòu)育嬰室儲(chǔ)備室寢室蟻后室日光浴場入口蟻群算法原理蟻群覓食的“雙橋?qū)嶒?yàn)”蟻群算法蟻群覓食過程算法基本原理自然界螞蟻覓食行為蟻群優(yōu)化算法蟻群搜索空間的一組有效解問題的搜索空間信息

11、素濃度變量一個(gè)有效解問題的最優(yōu)解覓食空間信息素蟻巢到食物的一條路徑找到的最短路徑對(duì)應(yīng)關(guān)系算法基本原理蟻群優(yōu)化算法（ Ant Colony Optimization , ACO）螞蟻在尋找食物的過程中往往是隨機(jī)選擇路徑的，但它們能感知當(dāng)前地面上的信息素濃度，并傾向于往信息素濃度高的方向行進(jìn)。信息素由螞蟻?zhàn)陨磲尫?，是?shí)現(xiàn)蟻群內(nèi)間接通信的物質(zhì)。由于較短路徑上螞蟻的往返時(shí)間比較短，單位時(shí)間內(nèi)經(jīng)過該路徑的螞蟻多，所以信息素的積累速度比較長路徑快。因此，當(dāng)后續(xù)螞蟻在路口時(shí)，就能感知先前螞蟻留下的信息，并傾向于選擇一條較短的路徑前行。這種正反饋機(jī)制使得越來越多的螞蟻在巢穴與食物之間的最短路徑上行進(jìn)。由于其他

12、路徑上的信息素會(huì)隨著時(shí)間蒸發(fā)，最終所有的螞蟻都在最優(yōu)路徑上行進(jìn)。蟻群算法流程路徑構(gòu)建每只螞蟻都隨機(jī)選擇一個(gè)城市作為其出發(fā)城市，并維護(hù)一個(gè)路徑記憶向量，用來存放該螞蟻依次經(jīng)過的城市。螞蟻在構(gòu)建路徑的每一步中，按照一個(gè)隨機(jī)比例規(guī)則選擇下一個(gè)要到達(dá)的城市。ACO基本要素信息素更新當(dāng)所有螞蟻構(gòu)建完路徑后，算法將會(huì)對(duì)所有的路徑進(jìn)行全局信息素的更新。注意，我們所描述的是AS的ant-cycle版本，更新是在全部螞蟻均完成了路徑的構(gòu)造后才進(jìn)行的，信息素的濃度變化與螞蟻在這一輪中構(gòu)建的路徑長度相關(guān)。 螞蟻系統(tǒng) (Ant System，AS ) 的螞蟻圈（Ant -cycle）版本是最基本的ACO算法，是以TS

13、P作為應(yīng)用實(shí)例提出的。蟻群算法流程路徑構(gòu)建：偽隨機(jī)比例選擇規(guī)則對(duì)于每只螞蟻k，路徑記憶向量Rk按照訪問順序記錄了所有k已經(jīng)經(jīng)過的城市序號(hào)。設(shè)螞蟻k當(dāng)前所在城市為i，則其選擇城市j作為下一個(gè)訪問對(duì)象的概率如上式。Jk(i) 表示從城市i 可以直接到達(dá)的、且又不在螞蟻訪問過的城市序列Rk中的城市集合。(i, j) 是一個(gè)啟發(fā)式信息，通常由 (i, j)=1/dij 直接計(jì)算。 (i, j) 表示邊(i, j)上的信息素量。蟻群算法流程路徑構(gòu)建：偽隨機(jī)比例選擇規(guī)則長度越短、信息素濃度越大的路徑被螞蟻選擇的概率越大。和是兩個(gè)預(yù)先設(shè)置的參數(shù)，用來控制啟發(fā)式信息與信息素濃度作用的權(quán)重關(guān)系。當(dāng) =0時(shí)，算法

14、演變成傳統(tǒng)的隨機(jī)貪心算法，最鄰近城市被選中的概率最大。當(dāng) =0時(shí)，螞蟻完全只根據(jù)信息素濃度確定路徑，算法將快速收斂，這樣構(gòu)建出的最優(yōu)路徑與實(shí)際目標(biāo)差異較大，算法性能較差。蟻群算法流程信息素更新：(1) 在算法初始化時(shí)，問題空間中所有的邊上的信息素都被初始化為0。(2) 算法迭代每一輪，問題空間中的所有路徑上的信息素都會(huì)發(fā)生蒸發(fā)，我們?yōu)樗羞吷系男畔⑺爻松弦粋€(gè)小于1的常數(shù)( : 信息素的蒸發(fā)率)。信息素蒸發(fā)是自然界本身固有的特征，在算法中能夠幫助避免信息素的無限積累，使得算法可以快速丟棄之前構(gòu)建過的較差的路徑。(3) 螞蟻根據(jù)自己構(gòu)建的路徑長度在它們本輪經(jīng)過的邊上釋放信息素。螞蟻構(gòu)建的路徑越短、釋放的信息素就越多。一條邊被螞蟻爬過的次數(shù)越多、它所獲得的信息素也越多。(4) 迭代 (2)，直至算法終止。蟻群算法流程信息素更新：信息素的更新公式：m：螞蟻個(gè)數(shù)；：信息素的蒸發(fā)率，規(guī)定0r1。 (i, j)：第k只螞蟻在它經(jīng)過的邊上釋放的信息素量，它等于螞蟻k本輪構(gòu)建路徑長度的倒數(shù)。Ck：路徑長度，它是Rk中所