湘潭大學 人工智能 群智能

1、Artificial Intelligence (AI)人工智能人工智能第九章：群智第九章：群智能系統(tǒng)能系統(tǒng)內容提要第九章：群智能系統(tǒng)第九章：群智能系統(tǒng)1.1.粒子群優(yōu)化算法粒子群優(yōu)化算法2.2.蟻群算法蟻群算法內容提要第九章：群智能系統(tǒng)第九章：群智能系統(tǒng)1.1.粒子群優(yōu)化算法粒子群優(yōu)化算法2.2.蟻群算法蟻群算法編輯課件n描述描述 群智能作為一種新興的演化計算技術已成為研究焦群智能作為一種新興的演化計算技術已成為研究焦點，它與人工生命，特別是進化策略以及遺傳算法點，它與人工生命，特別是進化策略以及遺傳算法有著極為特殊的關系。有著極為特殊的關系。n特性特性 指無智能的主體通過合作表現出智能行為

2、的特性，指無智能的主體通過合作表現出智能行為的特性，在沒有集中控制且不提供全局模型的前提下，為尋在沒有集中控制且不提供全局模型的前提下，為尋找復雜的分布式問題求解方案提供了基礎。找復雜的分布式問題求解方案提供了基礎。群智能編輯課件n優(yōu)點優(yōu)點 靈活性：群體可以適應隨時變化的環(huán)境；靈活性：群體可以適應隨時變化的環(huán)境；穩(wěn)健性：即使個體失敗，整個群體仍能完成任務；穩(wěn)健性：即使個體失敗，整個群體仍能完成任務； 自我組織：活動既不受中央控制，也不受局部監(jiān)管。自我組織：活動既不受中央控制，也不受局部監(jiān)管。n典型算法典型算法 蟻群算法（螞蟻覓食）蟻群算法（螞蟻覓食） 粒子群算法（鳥群捕食）粒子群算法（鳥群捕食

3、）群智能粒子群算法原理粒子群算法原理粒子群算法原理粒子群算法原理編輯課件n由由James Kenney（社會心理學博士）和（社會心理學博士）和Russ Eberhart（電子工程學博士，（電子工程學博士， /eberhart/ ）于）于1995年提年提出粒子群算法（出粒子群算法（Particle Swarm Optimization, PSO） 粒子群算法原理粒子群算法原理生物界現象生物界現象群體行為群體行為群體遷徙群體遷徙生物覓食生物覓食社會心理學社會心理學群體智慧群體智慧個體認知個體認知社會影響社會影響 人工生命人工生命鳥群覓食鳥群覓食魚群學

4、習魚群學習群理論群理論粒子群算法原理粒子群算法原理鳥群覓食現象鳥群覓食現象鳥群鳥群覓食空間覓食空間飛行速度飛行速度所在位置所在位置個體認知與群體協(xié)作個體認知與群體協(xié)作找到食物找到食物粒子群優(yōu)化算法粒子群優(yōu)化算法搜索空間的一組有效解搜索空間的一組有效解問題的搜索空間問題的搜索空間解的速度向量解的速度向量解的位置向量解的位置向量速度與位置的更新速度與位置的更新找到全局最優(yōu)解找到全局最優(yōu)解粒子群優(yōu)化算法粒子群優(yōu)化算法類比關系類比關系鳥群覓食現象鳥群覓食現象編輯課件n源于對鳥群捕食行為的研究，是基于迭代的方法源于對鳥群捕食行為的研究，是基于迭代的方法n簡單易于實現，需要調整的參數相對較少簡單易于實現，

5、需要調整的參數相對較少n在函數優(yōu)化、神經網絡訓練、工業(yè)系統(tǒng)優(yōu)化和模糊在函數優(yōu)化、神經網絡訓練、工業(yè)系統(tǒng)優(yōu)化和模糊系統(tǒng)控制等領域得到了廣泛的應用。系統(tǒng)控制等領域得到了廣泛的應用。粒子群算法原理編輯課件n鳥群：鳥群： 假設一個區(qū)域，所有的鳥都不知道食物的位置，但假設一個區(qū)域，所有的鳥都不知道食物的位置，但是它們知道當前位置離食物還有多遠。是它們知道當前位置離食物還有多遠。nPSO算法算法 每個解看作一只鳥，稱為每個解看作一只鳥，稱為“粒子粒子(particle)”，所有，所有的粒子都有一個適應值，每個粒子都有一個速度決的粒子都有一個適應值，每個粒子都有一個速度決定它們的飛翔方向和距離，粒子們追隨當

6、前最優(yōu)粒定它們的飛翔方向和距離，粒子們追隨當前最優(yōu)粒子在解空間中搜索。子在解空間中搜索。粒子群算法原理算法流程PSO中的個體，也叫中的個體，也叫粒子粒子，在多維搜索空間中飛行。，在多維搜索空間中飛行。PSO中的每個粒子維護兩個向量中的每個粒子維護兩個向量 位置向量位置向量xi ：粒子在解空間中的當前位置：粒子在解空間中的當前位置 速度向量速度向量vi ：粒子在解空間中的飛行速度：粒子在解空間中的飛行速度pBest ：粒子自身的歷史最優(yōu)位置：粒子自身的歷史最優(yōu)位置gBest ：群體全局最優(yōu)向量：群體全局最優(yōu)向量 lBest ：鄰域中的最好位置：鄰域中的最好位置編輯課件nPSO算法算法 初始化為一

7、群隨機粒子，通過迭代找到最優(yōu)。初始化為一群隨機粒子，通過迭代找到最優(yōu)。 每次迭代中，粒子通過跟蹤每次迭代中，粒子通過跟蹤“個體極值（個體極值（pbest）”和和“全局極值全局極值(gbest)”來來 更新自己的位置。更新自己的位置。算法流程算法流程(t)iv 令令 表示表示t t時刻第時刻第i i 個粒子個粒子 在超空間的位置。在超空間的位置。把速度矢量把速度矢量 加至當前位置，則加至當前位置，則 的位置變?yōu)椋旱奈恢米優(yōu)椋?t)ixiP(t)(t1)(t)iiixxviP算法流程速度向量反映了粒子速度向量反映了粒子自身的經驗知識自身的經驗知識和和來自鄰域粒子來自鄰域粒子的社會交換信息的社會交換

8、信息。粒子的經驗知識通常叫做粒子的經驗知識通常叫做認知部分認知部分，它和粒子與其，它和粒子與其自自身的身的歷史最優(yōu)位置（歷史最優(yōu)位置（ pbest ）的距離成正比。）的距離成正比。社會交換信息叫做速度方程的社會交換信息叫做速度方程的社會部分社會部分。gbest PSO，全局最佳粒子群優(yōu)化，全局最佳粒子群優(yōu)化lbest PSO，局部最佳粒子群優(yōu)化，局部最佳粒子群優(yōu)化算法流程粒子群算法v粒子群算法的特點粒子群算法的特點PSO算法收斂速度快，特別是在算法的早期，但也存在算法收斂速度快，特別是在算法的早期，但也存在著精度較低，易發(fā)散等缺點。著精度較低，易發(fā)散等缺點。若加速系數、最大速度等參數太大，粒子

9、群可能錯過若加速系數、最大速度等參數太大，粒子群可能錯過最優(yōu)解，算法不收斂；最優(yōu)解，算法不收斂；而在收斂的情況下，由于所有的粒子都向最優(yōu)解的方而在收斂的情況下，由于所有的粒子都向最優(yōu)解的方向飛去，所以粒子趨向同一化（失去了多樣性），使向飛去，所以粒子趨向同一化（失去了多樣性），使得后期收斂速度明顯變慢，同時算法收斂到一定精度得后期收斂速度明顯變慢，同時算法收斂到一定精度時，無法繼續(xù)優(yōu)化，所能達到的精度也不高。時，無法繼續(xù)優(yōu)化，所能達到的精度也不高。內容提要第九章：群智能系統(tǒng)第九章：群智能系統(tǒng)1.1.粒子群優(yōu)化算法粒子群優(yōu)化算法2.2.蟻群算法蟻群算法蟻群算法原理蟻群算法原理蟻群算法原理蟻群算法

10、原理育嬰室育嬰室儲備室儲備室寢室寢室蟻后室蟻后室日光浴場日光浴場入口入口蟻群算法原理 通過遺留在來往路徑上的信息素（通過遺留在來往路徑上的信息素（Pheromone）的揮發(fā)性化學物質來進行的揮發(fā)性化學物質來進行 通信和協(xié)調。通信和協(xié)調。蟻群算法v蟻群覓食過程蟻群覓食過程算法基本原理自然界螞蟻覓食行為自然界螞蟻覓食行為蟻群優(yōu)化算法蟻群優(yōu)化算法蟻群蟻群搜索空間的一組有效解搜索空間的一組有效解問題的搜索空間問題的搜索空間信息素濃度變量信息素濃度變量一個有效解一個有效解問題的最優(yōu)解問題的最優(yōu)解覓食空間覓食空間信息素信息素蟻巢到食物的一條路徑蟻巢到食物的一條路徑找到的最短路徑找到的最短路徑對對應應關關系

11、系算法基本原理 螞蟻在尋找食物的過程中往往是螞蟻在尋找食物的過程中往往是隨機選擇路徑隨機選擇路徑的，但它們能的，但它們能感知當前地面上的信息素濃度感知當前地面上的信息素濃度，并傾向于往信息素濃度高的并傾向于往信息素濃度高的方向行進方向行進。信息素由螞蟻自身釋放，是實現蟻群內間接通信。信息素由螞蟻自身釋放，是實現蟻群內間接通信的物質。的物質。 由于較短路徑上螞蟻的往返時間比較短，單位時間內經過該由于較短路徑上螞蟻的往返時間比較短，單位時間內經過該路徑的螞蟻多，所以信息素的積累速度比較長路徑快。因此，路徑的螞蟻多，所以信息素的積累速度比較長路徑快。因此，當后續(xù)螞蟻在路口時，就能感知先前螞蟻留下的信

12、息，并傾當后續(xù)螞蟻在路口時，就能感知先前螞蟻留下的信息，并傾向于選擇一條較短的路徑前行。向于選擇一條較短的路徑前行。 這種這種正反饋機制正反饋機制使得越來越多的螞蟻在巢穴與食物之間的最使得越來越多的螞蟻在巢穴與食物之間的最短路徑上行進。由于其他路徑上的信息素會短路徑上行進。由于其他路徑上的信息素會隨著時間蒸發(fā)隨著時間蒸發(fā)，最終所有的螞蟻都在最優(yōu)路徑上行進。最終所有的螞蟻都在最優(yōu)路徑上行進。蟻群算法流程路徑構建路徑構建每只螞蟻都隨機選擇每只螞蟻都隨機選擇一個城市作為其出發(fā)一個城市作為其出發(fā)城市，并維護一個路城市，并維護一個路徑記憶向量，用來存徑記憶向量，用來存放該螞蟻依次經過的放該螞蟻依次經過的

13、城市。螞蟻在構建路城市。螞蟻在構建路徑的每一步中，按照徑的每一步中，按照一個隨機比例規(guī)則選一個隨機比例規(guī)則選擇下一個要到達的城擇下一個要到達的城市。市。ACO基本要素基本要素信息素更新信息素更新當所有螞蟻構建完路當所有螞蟻構建完路徑后，算法將會對所徑后，算法將會對所有的路徑進行全局信有的路徑進行全局信息素的更新。注意，息素的更新。注意，我們所描述的是我們所描述的是AS的的ant-cycle版本版本，更新，更新是在全部螞蟻均完成是在全部螞蟻均完成了路徑的構造后才進了路徑的構造后才進行的，信息素的濃度行的，信息素的濃度變化與螞蟻在這一輪變化與螞蟻在這一輪中構建的路徑長度相中構建的路徑長度相關。關。

14、 螞蟻系統(tǒng)螞蟻系統(tǒng) (Ant System，AS ) 的螞蟻圈（的螞蟻圈（Ant -cycle）版本是最基本的）版本是最基本的ACO算法，是以算法，是以TSP作作為應用實例提出的。為應用實例提出的。蟻群算法流程偽隨機比例選擇規(guī)則偽隨機比例選擇規(guī)則 對于每只螞蟻對于每只螞蟻k，路徑記憶向量，路徑記憶向量Rk按照訪問順序記錄了所有按照訪問順序記錄了所有k已經已經經過的城市序號。經過的城市序號。 設螞蟻設螞蟻k當前所在城市為當前所在城市為i，則其選擇城市，則其選擇城市j作為下一個訪問對象的作為下一個訪問對象的概率如上式。概率如上式。Jk(i) 表示從城市表示從城市i 可以直接到達的、且又不在螞蟻訪可

15、以直接到達的、且又不在螞蟻訪問過的城市序列問過的城市序列Rk中的城市集合。中的城市集合。(i, j) 是一個啟發(fā)式信息，通常由是一個啟發(fā)式信息，通常由 (i, j)=1/dij 直接計算。直接計算。 (i, j) 表示邊表示邊(i, j)上的信息素量。上的信息素量。 ( )( , )( , ), if ( )( , )( , )( , ) 0, otherwisekkku Jii ji jjJipi ji ui u蟻群算法流程偽隨機比例選擇規(guī)則偽隨機比例選擇規(guī)則 長度越短、信息素濃度越大的路徑被螞蟻選擇的概率越大。長度越短、信息素濃度越大的路徑被螞蟻選擇的概率越大。 和和是兩個預先設置的參數，

16、用來是兩個預先設置的參數，用來控制啟發(fā)式信息與信息素濃度控制啟發(fā)式信息與信息素濃度作用的權重關系作用的權重關系。 當當 =0時，算法演變成傳統(tǒng)的隨機貪心算法，最鄰近城市被選中時，算法演變成傳統(tǒng)的隨機貪心算法，最鄰近城市被選中的概率最大。當的概率最大。當 =0時，螞蟻完全只根據信息素濃度確定路徑，時，螞蟻完全只根據信息素濃度確定路徑，算法將快速收斂，這樣構建出的最優(yōu)路徑與實際目標差異較大，算法將快速收斂，這樣構建出的最優(yōu)路徑與實際目標差異較大，算法性能較差。算法性能較差。 ( )( , )( , ), if ( )( , )( , )( , ) 0, otherwisekkku Jii ji j

17、jJipi ji ui u蟻群算法流程 (1) 在算法初始化時，問題空間中所有的邊上的信息素都被在算法初始化時，問題空間中所有的邊上的信息素都被初始化初始化為為0。 (2) 算法迭代每一輪，問題空間中的算法迭代每一輪，問題空間中的所有路徑上的信息素都所有路徑上的信息素都會發(fā)生蒸發(fā)會發(fā)生蒸發(fā)，我們?yōu)樗羞吷系男畔⑺爻松弦粋€小于，我們?yōu)樗羞吷系男畔⑺爻松弦粋€小于1的常的常數數( : 信息素的蒸發(fā)率信息素的蒸發(fā)率)。信息素蒸發(fā)是自然界本身固有的特。信息素蒸發(fā)是自然界本身固有的特征，在算法中能夠幫助避免信息素的無限積累，使得算法可征，在算法中能夠幫助避免信息素的無限積累，使得算法可以快速丟棄之前構建

18、過的較差的路徑。以快速丟棄之前構建過的較差的路徑。 (3) 螞蟻根據自己構建的路徑長度在它們本輪經過的邊上釋螞蟻根據自己構建的路徑長度在它們本輪經過的邊上釋放信息素。放信息素。螞蟻構建的路徑越短、釋放的信息素就越多螞蟻構建的路徑越短、釋放的信息素就越多。一。一條邊被螞蟻爬過的次數越多、它所獲得的信息素也越多。條邊被螞蟻爬過的次數越多、它所獲得的信息素也越多。 (4) 迭代迭代 (2)，直至算法終止。，直至算法終止。蟻群算法流程信息素的更新公式：信息素的更新公式： m：螞蟻個數；：螞蟻個數； ：信息素的蒸發(fā)率，規(guī)定：信息素的蒸發(fā)率，規(guī)定0r1。 (i, j)：第第k只螞蟻在它經過的邊上釋放的信息

19、素量，它等只螞蟻在它經過的邊上釋放的信息素量，它等于螞蟻于螞蟻k本輪構建路徑長度的倒數。本輪構建路徑長度的倒數。 Ck：路徑長度，它是：路徑長度，它是Rk中所有邊的長度和。中所有邊的長度和。11( , )(1)( , )( , ),(), if ( , ) ( , ) 0, otherwisemkkkkki ji ji jCi jRi j蟻群算法流程路徑構建路徑構建信息素更新信息素更新蟻群算法的應用車輛路徑問題車輛路徑問題（Vehicle Routing Problem，VRP）車間作業(yè)調度問題車間作業(yè)調度問題（Job-Shop Scheduling Problem，JSP）分配問題分配問題（Assignment problem, AP）網絡路由網絡路由（ Network Routing）其他其他子集問題子集問題（Set Problem）ACO編輯課件n共同特點共同特點 基于概率計算的隨機搜索進化算法，在結構、研究基于概率計算的隨機搜