湘潭大學(xué) 人工智能課件 群智能

1、Artificial Intelligence (AI),第九章：群智能系統(tǒng),內(nèi)容提要,第九章：群智能系統(tǒng),內(nèi)容提要,第九章：群智能系統(tǒng),描述 群智能作為一種新興的演化計(jì)算技術(shù)已成為研究焦點(diǎn)，它與人工生命，特別是進(jìn)化策略以及遺傳算法有著極為特殊的關(guān)系。 特性 指無(wú)智能的主體通過(guò)合作表現(xiàn)出智能行為的特性，在沒(méi)有集中控制且不提供全局模型的前提下，為尋找復(fù)雜的分布式問(wèn)題求解方案提供了基礎(chǔ)。,群智能,優(yōu)點(diǎn) 靈活性：群體可以適應(yīng)隨時(shí)變化的環(huán)境；穩(wěn)健性：即使個(gè)體失敗，整個(gè)群體仍能完成任務(wù)； 自我組織：活動(dòng)既不受中央控制，也不受局部監(jiān)管。 典型算法 蟻群算法（螞蟻覓食） 粒子群算法（鳥群捕食）,群智能,粒子

2、群算法原理,粒子群算法（PSO）,粒子群算法原理,粒子群算法（PSO）,粒子群算法原理,粒子群算法（PSO）,粒子群算法原理,粒子群算法（PSO）,由James Kenney（社會(huì)心理學(xué)博士）和Russ Eberhart（電子工程學(xué)博士， /eberhart/ ）于1995年提出粒子群算法（Particle Swarm Optimization, PSO）,粒子群算法的提出,粒子群算法原理,粒子群算法原理,PSO的思想來(lái)源,粒子群算法原理,從生物現(xiàn)象到 PSO算法,鳥群覓食現(xiàn)象,粒子群優(yōu)化算法,粒子群算法原理,從生物現(xiàn)象到 PSO算法,源于對(duì)鳥群

3、捕食行為的研究，是基于迭代的方法 簡(jiǎn)單易于實(shí)現(xiàn)，需要調(diào)整的參數(shù)相對(duì)較少 在函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、工業(yè)系統(tǒng)優(yōu)化和模糊系統(tǒng)控制等領(lǐng)域得到了廣泛的應(yīng)用。,粒子群算法原理,粒子群算法的提出,鳥群： 假設(shè)一個(gè)區(qū)域，所有的鳥都不知道食物的位置，但是它們知道當(dāng)前位置離食物還有多遠(yuǎn)。 PSO算法 每個(gè)解看作一只鳥，稱為“粒子(particle)”，所有的粒子都有一個(gè)適應(yīng)值，每個(gè)粒子都有一個(gè)速度決定它們的飛翔方向和距離，粒子們追隨當(dāng)前最優(yōu)粒子在解空間中搜索。,粒子群算法的原理描述,粒子群算法原理,算法流程,PSO算法的相關(guān)定義 PSO中的個(gè)體，也叫粒子，在多維搜索空間中飛行。 PSO中的每個(gè)粒子維護(hù)兩個(gè)向量

4、位置向量xi ：粒子在解空間中的當(dāng)前位置 速度向量vi ：粒子在解空間中的飛行速度 pBest ：粒子自身的歷史最優(yōu)位置 gBest ：群體全局最優(yōu)向量 lBest ：鄰域中的最好位置,PSO算法 初始化為一群隨機(jī)粒子，通過(guò)迭代找到最優(yōu)。 每次迭代中，粒子通過(guò)跟蹤“個(gè)體極值（pbest）”和“全局極值(gbest)”來(lái) 更新自己的位置。,算法流程,算法流程,粒子速度與位置的更新,令 表示t時(shí)刻第i 個(gè)粒子 在超空間的位置。 把速度矢量 加至當(dāng)前位置，則 的位置變?yōu)椋?算法流程,PSO算法驅(qū)動(dòng)優(yōu)化過(guò)程的是速度vi(t)向量。 速度向量反映了粒子自身的經(jīng)驗(yàn)知識(shí)和來(lái)自鄰域粒子的社會(huì)交換信息。 粒子的

5、經(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算法收斂速度快，特別是在算法的早期，但也存在著精度較低，易發(fā)散等缺點(diǎn)。 若加速系數(shù)、最大速度等參數(shù)太大，粒子群可能錯(cuò)過(guò)最優(yōu)解，算法不收斂； 而在收斂的情況下，由于所有的粒子都向最優(yōu)解的方向飛去，所以粒子趨向同一化（失去了多樣性），使得后期收斂速度明顯變慢，同時(shí)算法收斂到一定精度時(shí)，

6、無(wú)法繼續(xù)優(yōu)化，所能達(dá)到的精度也不高。,內(nèi)容提要,第九章：群智能系統(tǒng),蟻群算法原理,蟻群的覓食行為,蟻群算法原理,蟻群的分工,蟻群算法原理,蟻穴的結(jié)構(gòu),蟻群算法原理,蟻穴的結(jié)構(gòu),育嬰室,儲(chǔ)備室,寢室,蟻后室,日光浴場(chǎng),入口,蟻群算法原理,蟻群覓食的“雙橋?qū)嶒?yàn)”,通過(guò)遺留在來(lái)往路徑上的信息素（Pheromone）的揮發(fā)性化學(xué)物質(zhì)來(lái)進(jìn)行 通信和協(xié)調(diào)。,蟻群算法,蟻群覓食過(guò)程,算法基本原理,自然界螞蟻覓食行為,蟻群優(yōu)化算法,蟻群,搜索空間的一組有效解,問(wèn)題的搜索空間,信息素濃度變量,一個(gè)有效解,問(wèn)題的最優(yōu)解,覓食空間,信息素,蟻巢到食物的一條路徑,找到的最短路徑,對(duì)應(yīng)關(guān)系,算法基本原理,蟻群優(yōu)化算法（

7、 Ant Colony Optimization , ACO） 螞蟻在尋找食物的過(guò)程中往往是隨機(jī)選擇路徑的，但它們能感知當(dāng)前地面上的信息素濃度，并傾向于往信息素濃度高的方向行進(jìn)。信息素由螞蟻?zhàn)陨磲尫?，是?shí)現(xiàn)蟻群內(nèi)間接通信的物質(zhì)。 由于較短路徑上螞蟻的往返時(shí)間比較短，單位時(shí)間內(nèi)經(jīng)過(guò)該路徑的螞蟻多，所以信息素的積累速度比較長(zhǎng)路徑快。因此，當(dāng)后續(xù)螞蟻在路口時(shí)，就能感知先前螞蟻留下的信息，并傾向于選擇一條較短的路徑前行。 這種正反饋機(jī)制使得越來(lái)越多的螞蟻在巢穴與食物之間的最短路徑上行進(jìn)。由于其他路徑上的信息素會(huì)隨著時(shí)間蒸發(fā)，最終所有的螞蟻都在最優(yōu)路徑上行進(jìn)。,蟻群算法流程,螞蟻系統(tǒng) (Ant Syst

8、em，AS ) 的螞蟻圈（Ant -cycle）版本是最基本的ACO算法，是以TSP作為應(yīng)用實(shí)例提出的。,蟻群算法流程,路徑構(gòu)建：偽隨機(jī)比例選擇規(guī)則 對(duì)于每只螞蟻k，路徑記憶向量Rk按照訪問(wèn)順序記錄了所有k已經(jīng)經(jīng)過(guò)的城市序號(hào)。 設(shè)螞蟻k當(dāng)前所在城市為i，則其選擇城市j作為下一個(gè)訪問(wèn)對(duì)象的概率如上式。Jk(i) 表示從城市i 可以直接到達(dá)的、且又不在螞蟻訪問(wèn)過(guò)的城市序列Rk中的城市集合。 (i, j) 是一個(gè)啟發(fā)式信息，通常由 (i, j)=1/dij 直接計(jì)算。 (i, j) 表示邊(i, j)上的信息素量。,蟻群算法流程,路徑構(gòu)建：偽隨機(jī)比例選擇規(guī)則 長(zhǎng)度越短、信息素濃度越大的路徑被螞蟻選擇

9、的概率越大。 和是兩個(gè)預(yù)先設(shè)置的參數(shù)，用來(lái)控制啟發(fā)式信息與信息素濃度作用的權(quán)重關(guān)系。 當(dāng) =0時(shí)，算法演變成傳統(tǒng)的隨機(jī)貪心算法，最鄰近城市被選中的概率最大。當(dāng) =0時(shí)，螞蟻完全只根據(jù)信息素濃度確定路徑，算法將快速收斂，這樣構(gòu)建出的最優(yōu)路徑與實(shí)際目標(biāo)差異較大，算法性能較差。,蟻群算法流程,信息素更新： (1) 在算法初始化時(shí)，問(wèn)題空間中所有的邊上的信息素都被初始化為0。 (2) 算法迭代每一輪，問(wèn)題空間中的所有路徑上的信息素都會(huì)發(fā)生蒸發(fā)，我們?yōu)樗羞吷系男畔⑺爻松弦粋€(gè)小于1的常數(shù)( : 信息素的蒸發(fā)率)。信息素蒸發(fā)是自然界本身固有的特征，在算法中能夠幫助避免信息素的無(wú)限積累，使得算法可以快速丟棄

10、之前構(gòu)建過(guò)的較差的路徑。 (3) 螞蟻根據(jù)自己構(gòu)建的路徑長(zhǎng)度在它們本輪經(jīng)過(guò)的邊上釋放信息素。螞蟻構(gòu)建的路徑越短、釋放的信息素就越多。一條邊被螞蟻爬過(guò)的次數(shù)越多、它所獲得的信息素也越多。 (4) 迭代 (2)，直至算法終止。,蟻群算法流程,信息素更新： 信息素的更新公式： m：螞蟻個(gè)數(shù)； ：信息素的蒸發(fā)率，規(guī)定0r1。 (i, j)：第k只螞蟻在它經(jīng)過(guò)的邊上釋放的信息素量，它等于螞蟻k本輪構(gòu)建路徑長(zhǎng)度的倒數(shù)。 Ck：路徑長(zhǎng)度，它是Rk中所有邊的長(zhǎng)度和。,蟻群算法流程,路徑構(gòu)建,信息素更新,蟻群算法的應(yīng)用,共同特點(diǎn) 基于概率計(jì)算的隨機(jī)搜索進(jìn)化算法，在結(jié)構(gòu)、研究?jī)?nèi)容、方法以及步驟上有較大的相似性； 存在的問(wèn)題 （1）數(shù)學(xué)理論基礎(chǔ)相對(duì)薄弱； （2）參數(shù)設(shè)置沒(méi)有確切的理論依據(jù)，對(duì)具體問(wèn)題和應(yīng)用環(huán)境的依賴性大；,群智能優(yōu)化的特點(diǎn)與不足,存在的問(wèn)題 （3）比較性研究不足，缺乏用于性能評(píng)估的標(biāo)準(zhǔn)測(cè)試集； （4）不具備絕對(duì)的可信性，存在應(yīng)用風(fēng)險(xiǎn)； 進(jìn)一步的工作 （1）進(jìn)一步研究真實(shí)群居動(dòng)物的行為特征； （2）進(jìn)一步研究算法的收斂性；,群智能優(yōu)化的特點(diǎn)與不足,存在的問(wèn)題 （3