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

湘潭大學(xué)人工智能課件群智能演示文稿目前一頁\總數(shù)四十一頁\編于十二點內(nèi)容提要第九章：群智能系統(tǒng)1.粒子群優(yōu)化算法2.蟻群算法……目前二頁\總數(shù)四十一頁\編于十二點內(nèi)容提要第九章：群智能系統(tǒng)1.粒子群優(yōu)化算法2.蟻群算法……目前三頁\總數(shù)四十一頁\編于十二點描述群智能作為一種新興的演化計算技術(shù)已成為研究焦點，它與人工生命，特別是進(jìn)化策略以及遺傳算法有著極為特殊的關(guān)系。特性指無智能的主體通過合作表現(xiàn)出智能行為的特性，在沒有集中控制且不提供全局模型的前提下，為尋找復(fù)雜的分布式問題求解方案提供了基礎(chǔ)。群智能目前四頁\總數(shù)四十一頁\編于十二點優(yōu)點靈活性：群體可以適應(yīng)隨時變化的環(huán)境；

穩(wěn)健性：即使個體失敗，整個群體仍能完成任務(wù)；自我組織：活動既不受中央控制，也不受局部監(jiān)管。典型算法蟻群算法（螞蟻覓食）粒子群算法（鳥群捕食）群智能目前五頁\總數(shù)四十一頁\編于十二點粒子群算法原理粒子群算法（PSO）目前六頁\總數(shù)四十一頁\編于十二點粒子群算法原理粒子群算法（PSO）目前七頁\總數(shù)四十一頁\編于十二點粒子群算法原理粒子群算法（PSO）目前八頁\總數(shù)四十一頁\編于十二點粒子群算法原理粒子群算法（PSO）目前九頁\總數(shù)四十一頁\編于十二點由JamesKenney（社會心理學(xué)博士）和RussEberhart（電子工程學(xué)博士，/~eberhart/

）于1995年提出粒子群算法（ParticleSwarmOptimization,PSO）

粒子群算法的提出粒子群算法原理目前十頁\總數(shù)四十一頁\編于十二點粒子群算法原理PSO的思想來源生物界現(xiàn)象群體行為群體遷徙生物覓食……社會心理學(xué)群體智慧個體認(rèn)知社會影響……粒子群優(yōu)化算法

人工生命鳥群覓食魚群學(xué)習(xí)群理論目前十一頁\總數(shù)四十一頁\編于十二點粒子群算法原理從生物現(xiàn)象到PSO算法鳥群覓食現(xiàn)象粒子群優(yōu)化算法目前十二頁\總數(shù)四十一頁\編于十二點粒子群算法原理從生物現(xiàn)象到PSO算法鳥群覓食現(xiàn)象鳥群覓食空間飛行速度所在位置個體認(rèn)知與群體協(xié)作找到食物粒子群優(yōu)化算法搜索空間的一組有效解問題的搜索空間解的速度向量解的位置向量速度與位置的更新找到全局最優(yōu)解粒子群優(yōu)化算法類比關(guān)系鳥群覓食現(xiàn)象目前十三頁\總數(shù)四十一頁\編于十二點源于對鳥群捕食行為的研究，是基于迭代的方法簡單易于實現(xiàn)，需要調(diào)整的參數(shù)相對較少在函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、工業(yè)系統(tǒng)優(yōu)化和模糊系統(tǒng)控制等領(lǐng)域得到了廣泛的應(yīng)用。粒子群算法原理

粒子群算法的提出目前十四頁\總數(shù)四十一頁\編于十二點鳥群：假設(shè)一個區(qū)域，所有的鳥都不知道食物的位置，但是它們知道當(dāng)前位置離食物還有多遠(yuǎn)。PSO算法

每個解看作一只鳥，稱為“粒子(particle)”，所有的粒子都有一個適應(yīng)值，每個粒子都有一個速度決定它們的飛翔方向和距離，粒子們追隨當(dāng)前最優(yōu)粒子在解空間中搜索。

粒子群算法的原理描述粒子群算法原理目前十五頁\總數(shù)四十一頁\編于十二點算法流程PSO算法的相關(guān)定義PSO中的個體，也叫粒子，在多維搜索空間中飛行。PSO中的每個粒子維護(hù)兩個向量位置向量xi：粒子在解空間中的當(dāng)前位置速度向量vi：粒子在解空間中的飛行速度pBest：粒子自身的歷史最優(yōu)位置gBest：群體全局最優(yōu)向量

lBest：鄰域中的最好位置目前十六頁\總數(shù)四十一頁\編于十二點PSO算法

初始化為一群隨機粒子，通過迭代找到最優(yōu)。每次迭代中，粒子通過跟蹤“個體極值（pbest）”和“全局極值(gbest)”來更新自己的位置。算法流程目前十七頁\總數(shù)四十一頁\編于十二點算法流程粒子速度與位置的更新令表示t時刻第i個粒子在超空間的位置。把速度矢量加至當(dāng)前位置，則的位置變?yōu)椋耗壳笆隧揬總數(shù)四十一頁\編于十二點算法流程PSO算法驅(qū)動優(yōu)化過程的是速度vi(t)向量。速度向量反映了粒子自身的經(jīng)驗知識和來自鄰域粒子的社會交換信息。粒子的經(jīng)驗知識通常叫做認(rèn)知部分，它和粒子與其自身的歷史最優(yōu)位置（pbest）的距離成正比。社會交換信息叫做速度方程的社會部分。鄰域大小不同的兩種算法gbestPSO，全局最佳粒子群優(yōu)化lbestPSO，局部最佳粒子群優(yōu)化目前十九頁\總數(shù)四十一頁\編于十二點算法流程gbestPSO：全局最佳粒子群優(yōu)化目前二十頁\總數(shù)四十一頁\編于十二點粒子群算法粒子群算法的特點PSO算法收斂速度快，特別是在算法的早期，但也存在著精度較低，易發(fā)散等缺點。若加速系數(shù)、最大速度等參數(shù)太大，粒子群可能錯過最優(yōu)解，算法不收斂；而在收斂的情況下，由于所有的粒子都向最優(yōu)解的方向飛去，所以粒子趨向同一化（失去了多樣性），使得后期收斂速度明顯變慢，同時算法收斂到一定精度時，無法繼續(xù)優(yōu)化，所能達(dá)到的精度也不高。目前二十一頁\總數(shù)四十一頁\編于十二點內(nèi)容提要第九章：群智能系統(tǒng)1.粒子群優(yōu)化算法2.蟻群算法……目前二十二頁\總數(shù)四十一頁\編于十二點蟻群算法原理蟻群的覓食行為目前二十三頁\總數(shù)四十一頁\編于十二點蟻群算法原理蟻群的分工目前二十四頁\總數(shù)四十一頁\編于十二點蟻群算法原理蟻穴的結(jié)構(gòu)目前二十五頁\總數(shù)四十一頁\編于十二點蟻群算法原理蟻穴的結(jié)構(gòu)育嬰室儲備室寢室蟻后室日光浴場入口目前二十六頁\總數(shù)四十一頁\編于十二點蟻群算法原理蟻群覓食的“雙橋?qū)嶒灐蓖ㄟ^遺留在來往路徑上的信息素（Pheromone）的揮發(fā)性化學(xué)物質(zhì)來進(jìn)行通信和協(xié)調(diào)。目前二十七頁\總數(shù)四十一頁\編于十二點蟻群算法蟻群覓食過程目前二十八頁\總數(shù)四十一頁\編于十二點算法基本原理自然界螞蟻覓食行為蟻群優(yōu)化算法蟻群搜索空間的一組有效解問題的搜索空間信息素濃度變量一個有效解問題的最優(yōu)解覓食空間信息素蟻巢到食物的一條路徑找到的最短路徑對應(yīng)關(guān)系目前二十九頁\總數(shù)四十一頁\編于十二點算法基本原理蟻群優(yōu)化算法（AntColonyOptimization

,ACO）螞蟻在尋找食物的過程中往往是隨機選擇路徑的，但它們能感知當(dāng)前地面上的信息素濃度，并傾向于往信息素濃度高的方向行進(jìn)。信息素由螞蟻自身釋放，是實現(xiàn)蟻群內(nèi)間接通信的物質(zhì)。由于較短路徑上螞蟻的往返時間比較短，單位時間內(nèi)經(jīng)過該路徑的螞蟻多，所以信息素的積累速度比較長路徑快。因此，當(dāng)后續(xù)螞蟻在路口時，就能感知先前螞蟻留下的信息，并傾向于選擇一條較短的路徑前行。這種正反饋機制使得越來越多的螞蟻在巢穴與食物之間的最短路徑上行進(jìn)。由于其他路徑上的信息素會隨著時間蒸發(fā)，最終所有的螞蟻都在最優(yōu)路徑上行進(jìn)。目前三十頁\總數(shù)四十一頁\編于十二點蟻群算法流程路徑構(gòu)建每只螞蟻都隨機選擇一個城市作為其出發(fā)城市，并維護(hù)一個路徑記憶向量，用來存放該螞蟻依次經(jīng)過的城市。螞蟻在構(gòu)建路徑的每一步中，按照一個隨機比例規(guī)則選擇下一個要到達(dá)的城市。ACO基本要素信息素更新當(dāng)所有螞蟻構(gòu)建完路徑后，算法將會對所有的路徑進(jìn)行全局信息素的更新。注意，我們所描述的是AS的ant-cycle版本，更新是在全部螞蟻均完成了路徑的構(gòu)造后才進(jìn)行的，信息素的濃度變化與螞蟻在這一輪中構(gòu)建的路徑長度相關(guān)。

螞蟻系統(tǒng)(AntSystem，AS)的螞蟻圈（Ant-cycle）版本是最基本的ACO算法，是以TSP作為應(yīng)用實例提出的。目前三十一頁\總數(shù)四十一頁\編于十二點蟻群算法流程路徑構(gòu)建：偽隨機比例選擇規(guī)則對于每只螞蟻k，路徑記憶向量Rk按照訪問順序記錄了所有k已經(jīng)經(jīng)過的城市序號。設(shè)螞蟻k當(dāng)前所在城市為i，則其選擇城市j作為下一個訪問對象的概率如上式。Jk(i)表示從城市i可以直接到達(dá)的、且又不在螞蟻訪問過的城市序列Rk中的城市集合。η(i,j)是一個啟發(fā)式信息，通常由η(i,j)=1/dij直接計算。τ

(i,j)表示邊(i,j)上的信息素量。目前三十二頁\總數(shù)四十一頁\編于十二點蟻群算法流程路徑構(gòu)建：偽隨機比例選擇規(guī)則長度越短、信息素濃度越大的路徑被螞蟻選擇的概率越大。α和β是兩個預(yù)先設(shè)置的參數(shù)，用來控制啟發(fā)式信息與信息素濃度作用的權(quán)重關(guān)系。當(dāng)α

=0時，算法演變成傳統(tǒng)的隨機貪心算法，最鄰近城市被選中的概率最大。當(dāng)β

=0時，螞蟻完全只根據(jù)信息素濃度確定路徑，算法將快速收斂，這樣構(gòu)建出的最優(yōu)路徑與實際目標(biāo)差異較大，算法性能較差。目前三十三頁\總數(shù)四十一頁\編于十二點蟻群算法流程信息素更新：(1)在算法初始化時，問題空間中所有的邊上的信息素都被初始化為τ0。(2)算法迭代每一輪，問題空間中的所有路徑上的信息素都會發(fā)生蒸發(fā)，我們?yōu)樗羞吷系男畔⑺爻松弦粋€小于1的常數(shù)(ρ:

信息素的蒸發(fā)率)。信息素蒸發(fā)是自然界本身固有的特征，在算法中能夠幫助避免信息素的無限積累，使得算法可以快速丟棄之前構(gòu)建過的較差的路徑。(3)螞蟻根據(jù)自己構(gòu)建的路徑長度在它們本輪經(jīng)過的邊上釋放信息素。螞蟻構(gòu)建的路徑越短、釋放的信息素就越多。一條邊被螞蟻爬過的次數(shù)越多、它所獲得的信息素也越多。(4)迭代(2)，直至算法終止。目前三十四頁\總數(shù)四十一頁\編于十二點蟻群算法流程信息素更新：信息素的更新公式：m：螞蟻個數(shù)；ρ：信息素的蒸發(fā)率，規(guī)定0<r≤1。Δτ

(i,j)：第k只螞蟻在它經(jīng)過的邊上釋放的信息素量，它等于螞蟻k本輪構(gòu)建路徑長度的倒數(shù)。Ck：路徑長度，它是Rk中所有邊的長度和。目前三十五頁\總數(shù)四十一頁\編于十二點蟻群算法流程路徑構(gòu)建信息素更新目前三十六頁\總數(shù)四十一頁\編于十二點蟻群算法的應(yīng)用車輛路徑問題（VehicleRoutingProblem，VRP）車間作業(yè)調(diào)度問題（Job-ShopSchedulingProblem，JSP）分配問題（Assignmentproblem,AP）網(wǎng)絡(luò)路由（NetworkRouting）其他……子集問題（SetProblem）ACO目前三十七頁\總數(shù)四十一頁\編于十二點共同特點基于概率計算的隨機搜索進(jìn)化算法，在結(jié)構(gòu)、研究內(nèi)容、方法以及步驟上有較大的相似性；存在的問題（1）數(shù)學(xué)理論基礎(chǔ)相對薄弱；（2）參數(shù)設(shè)置沒有確切的理論依據(jù)，對具體問題和應(yīng)用環(huán)境的依賴性大；群智能優(yōu)化的特點與不足目前三十八頁\總數(shù)四十一頁\編于十二點存在的問題（3）比較性研究不足，缺乏用于性能評估的標(biāo)準(zhǔn)測試集；（4）不具備絕對的可信性，存在應(yīng)用風(fēng)險；進(jìn)一步的工作（1）進(jìn)一步研究真實群居動物的行為特征；（2）進(jìn)一步研究算法的收斂性；

群智能優(yōu)化的特點與不足目前三十九頁\總數(shù)四十