群智能學(xué)習(xí)筆記

群智能

【復(fù)習(xí)所用筆記，內(nèi)容來自老師的PPT】

定義概述

群，已知有蟻群、魚群、鳥群。它們是互相影響的個體，行為簡單。沒有一個集中控制中心。作為群體協(xié)作工作時，能夠突顯出非常復(fù)雜的行為特征——智能行為，群體智能。

任何一種由昆蟲群體或其它動物社會行為機制而激發(fā)設(shè)計出的算法或分布
式解決問題的策略均屬于群智能。

群智能（Swarm Intelligence）已經(jīng)成為有別于傳統(tǒng)人工智能中符號主義和鏈接主義的一種新的關(guān)于人工智能的研究路線。示例：有蟻群算法、粒子群算法等。

群智能為在沒有集中控制且不提供全局模型的前提下尋找復(fù)雜的分布式問題求解方案提供了基礎(chǔ)。在計算智能領(lǐng)域已取得成功的基于SI的優(yōu)化算法有蟻群算法、 粒子群算法、魚群算法、猴群算法等。

目前，已有的群智能理論和應(yīng)用研究證明群智能方法是一種能夠有效解決大多數(shù)優(yōu)化問題的新方法，更重要是,群智能潛在的并行性和分布式特點為處理大量的以數(shù)據(jù)庫形式存在的數(shù)據(jù)提供了技術(shù)保證。無論是從理論研究還是應(yīng)用研究的角度分析,群智能理論及應(yīng)用研究都是具有重要學(xué)術(shù)意義和現(xiàn)實價值的。

? 無智能或簡單智能的主體通過任何形式的聚集協(xié)同而表現(xiàn)出智能行為的特性。
? 基于分散的群體行為的自組織系統(tǒng)，通過一定數(shù)量的簡單個體之間以及和環(huán)境之間的相互交互從而實現(xiàn)群體表現(xiàn)一定的智能行為。
這里關(guān)心的不是個體之間的競爭，而是它們之間的協(xié)同（獲取并共享信息）

  • SI與GA

目前，已有的基于SI的優(yōu)化算法都是源于對動物社會通過協(xié)作解決問題行為的模擬，它主要強調(diào)對社會系統(tǒng)中個體之間相互協(xié)同作用的模擬。這一點與遺傳算法 Genetic Algorithms- -GA不同，GA是對生物演化中適者生存的模擬。與GA一樣的是，SI的目的并不是為了忠實地模擬自然現(xiàn)象，而是利用它們的某些特點去解決實際問題。另一個與GA的相同點是,基于SI的優(yōu)化算法也是概率搜索算法。

典型算法

在計算智能領(lǐng)域已取得成功的基于SI的優(yōu)化算法有蟻群算法、 粒子群算法、魚群算法、猴群算法等。

蟻群算法（螞蟻覓食）
粒子群算法（蜂群或鳥群覓食）
魚群算法（魚群的移動與覓食）
猴群算法（猴群的移動與覓食）
? 優(yōu)點
靈活性 穩(wěn)健性 自組織 潛在的并行和分布

蟻群算法

蟻群算法是模擬自然界中螞蟻尋找從巢穴到食物的最佳路徑的行為而設(shè)計的，螞蟻在遇到食物返回的路上會分泌（ 信息素 ），信息素會隨著時間慢慢揮發(fā)，且關(guān)鍵路徑上的信息素相對濃度（ 較高 ），蟻群算法已被廣泛應(yīng)用于許多優(yōu)化問題中，其中有（聚類問題）（ 路由算法設(shè)計）（ 圖著色）（ 車輛調(diào)度）（機器人路徑規(guī)劃）。

各種行為因子：

（1 ）范圍：螞蟻觀察到的范圍是一個方格世界，螞蟻有一個參數(shù)為速度半徑，那么它能觀察到的范圍以及能夠移動的范圍都會發(fā)生在這樣的一個范圍之內(nèi)。
（2 ）環(huán)境：螞蟻所在的環(huán)境是一個虛擬的世界，其中有障礙物，有其他的螞蟻，還有信息素，信息素可以設(shè)計為單一種類也可以多種類（如兩種），一種是找到食物的螞蟻撒下的食物信息素，另外一種是找到食物的螞蟻灑下的蟻窩的信息素，或者其它目的的信息素。每個螞蟻都僅僅能感知它范圍內(nèi)的環(huán)境信息。同時環(huán)境也以一定的速率讓信息素消失。
（3 ）覓食規(guī)則：在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就直接過去。否則通過比較在能感知的范圍內(nèi)的信息素的多少，然后它會向信息素最多的方向移動。同時每只螞蟻還以小概率來進(jìn)行“犯錯”。從而并不總是向信息素最多的方向移動。螞蟻找到蟻巢的規(guī)則可以和覓食規(guī)則相同，只不過它只對蟻巢的信息素進(jìn)行反應(yīng)，而對食物信息素沒有任何反應(yīng)。
（4 ）移動規(guī)則：每只螞蟻都向信息素最多的方向前進(jìn)，并且在運動方向上有一個隨機的小擾動。為了防止螞蟻原地轉(zhuǎn)圈，它會記住剛才走過了那些點，如果發(fā)現(xiàn)要走的下一個點已經(jīng)走過了，它就會盡量避開。
（5 ）避障規(guī)則：如果螞蟻要移動的方向有障礙物擋住，它會隨機的選擇另一個方向，并且有信息素指引的話，它會按照覓食的規(guī)則或返回蟻巢規(guī)則進(jìn)行移動。
（6）信息素規(guī)則：每只螞蟻在剛找到食物或者蟻巢的時候散發(fā)的信息素最多，并隨著它走遠(yuǎn)的距離，散播的信息素越來越少。
根據(jù)需要還可以定義其它規(guī)則。

粒子群算法（PSO)

模擬鳥群或蜂群的覓食行為?；舅枷耄和ㄟ^群體中個體之間的協(xié)作和信息共享來尋找最優(yōu)解。

每個粒子有一個適應(yīng)度（評估）函數(shù)以模擬每只小鳥與食物的距離
? 每個粒子有一個速度決定它的飛行方向和距離，初始值可以隨機確定
? 每一次單位時間的飛行后，所有粒子分享信息，下一步將飛向自身最佳位置（個體極值（pbest）和全局最優(yōu)位置（全局極值(gbest)）的加權(quán)中心

初始化為一群隨機粒子，通過迭代找到最優(yōu)。
每次迭代中，粒子通過跟蹤“個體極值（pbest）”和“全局極值(gbest)”來更新自己的位置。

粒子速度和位置的更新

假設(shè)在D維搜索空間中，有m個粒子：

其中第i個粒子的位置為矢量 \vec{X_i}=(X_{i1},X_{i2},\dots,X_{iD})

其飛行速度也為一個矢量，記作\vec{v_i}=(v_{i1},v_{i2},\dots v_{iD})

第i個粒子搜索到的最優(yōu)位置為 \vec{p_i}=(p_{i1},p_{i2},\dots p_{iD})

整個粒子群搜索到的最優(yōu)位置為 \vec{p_{gbest}}=(p_{gbest1},p_{gbest2},\dots p_{gbestD})

k+1時刻第i個粒子的位置和速度更新為：

v^{k+1}_{id}=w\cdot v^k_{id}+c_1\cdot rand()\cdot (p_{id}-x_{id}^k)+c_2\cdot rand()(p_{gbest}-x^k_{id})

，，x^{k+1}_{id}=x^k_{id}+v_{id}^{k+1} i=1,2,…，m; d=1,2…，D

其中，w稱為慣性權(quán)重，c_1,c_2為兩個正常系數(shù)，稱為加速因子。將v_{id}^k限制在一個最大速度v_{max}內(nèi)。

v^{k+1}_{id}=w\cdot v^k_{id}+c_1\cdot rand()\cdot (p_{id}-x_{id}^k)+c_2\cdot rand()(p_{gbest}-x^k_{id})

，，x^{k+1}_{id}=x^k_{id}+v_{id}^{k+1} i=1,2,…，m; d=1,2…，D

w\cdot v^k_{id}：“慣性部分”，對自身運動狀態(tài)的信任

c_1\cdot rand()\cdot (p_{id}-x_{id}^k)：“認(rèn)知部分”，對粒子本身的思考，即來源于自己經(jīng)驗的部分

c_2\cdot rand()(p_{gbest}-x^k_{id}) ：“社會部分”，粒間子的信息共享，來源于群體中的其它優(yōu)秀微粒的經(jīng)驗。

  • w的作用 慣性權(quán)重w

（1） 使粒子保持運動慣性，使其有擴展搜索空間的趨勢，有能力探索新的區(qū)域。
（2 ）表示微粒對當(dāng)前自身運動狀態(tài)的信任，依據(jù)自身的速度進(jìn)行慣性運動。
（3 ）較大的w 有利于跳出局部極值，而較小的w有利于算法收斂。

  • 加速常數(shù)c_1 和c_2

（1)代表將粒子推向pbest 和gbest 位置的統(tǒng)計加速項的權(quán)重。
（ 2 ）表示粒子的動作來源于自己經(jīng)驗的部分和其它粒子經(jīng)驗的部分。
（ 3 ）較小的值允許粒子在被拉回之前可以在目標(biāo)區(qū)域外徘徊，而較大的值則導(dǎo)致粒子突然沖向或越過目標(biāo)區(qū)域。

將c 1 和c 2 統(tǒng)一為一個控制參數(shù)，φ= c 1 +c 2

如果φ 很小，粒子群運動軌跡將非常緩慢；
如果φ 很大，則粒子的位置變化非常快；
實驗表明，當(dāng)φ=4.1 （通常c 1 =2.0 ，c 2 =2.0 ）時，具有很好的 收斂效果

粒子數(shù)
一般取20 ～40 ，對較難或特定類別的問題可以取100 ～200。 。
? 最大速度v max
決定粒子在一個循環(huán)中最大的移動距離，通常設(shè)定為粒子的范圍寬度。
? 終止條件
最大循環(huán)數(shù)以及最小錯誤要求。

與遺傳算法的比較

? 共性
（ 1 ）都屬于仿生算法；（ 2 ）都屬于全局優(yōu)化方法；
（ 3 ）都屬于隨機搜索算法；（ 4 ）都隱含并行性；
（ 5 ）根據(jù)個體的適應(yīng)信息進(jìn)行搜索，因此不受函數(shù)約束條件的限制，如連續(xù)性、可導(dǎo)性等；
（ 6 ）對高維復(fù)雜問題，往往會遇到早熟收斂和收斂性能差的缺點，都無法保證收斂到最優(yōu)點。

差異
（ 1 ）PSO 有記憶，所有粒子都保存較優(yōu)解的知識，而GA ，以前的知識隨著種群的改變被改變；
（ 2 ）PSO 中的粒子是一種單向共享信息機制。而GA 中的染色體之間相互共享信息，使得整個種群都向最優(yōu)區(qū)域移動；
（ 3 ）GA 需要編碼和遺傳操作，而PSO 沒有交叉和變異操作，粒子只是通過內(nèi)部速度進(jìn)行更新，因此原理更簡單、參數(shù)更少、實現(xiàn)更容易。

粒子群優(yōu)化算法流程

1 、初始化一群粒子（群體規(guī)模），包括隨機的位置和速度
2 、評價每個粒子的適應(yīng)度
3 、對每個粒子更新個體最優(yōu)位置p_{id}
4 、更新全局最優(yōu)位置p_{gbest}
5 、根據(jù)速度和位置方程更新每個粒子的速度和位置(v_{id}和p_{id})
6 、如未滿足結(jié)束條件（通常為滿足足夠好的適應(yīng)值或達(dá)到設(shè)定的最大迭代次數(shù)），返回2

魚群算法

模擬魚群的覓食行為、集群行為、跟隨行為和隨機游動行為。
大多時間，魚會向有更多食物的方向游動，
同時它們會盡量的聚集在一起來（在某個區(qū)域不是太密集的前提下）并保持和魚群的中心位置的魚的游動方向一致

rand()可以產(chǎn)生從0到1之間的隨機數(shù)

聚集行為 覓食行為 跟隨行為 移動行為 都有公式

群智能優(yōu)化算法與進(jìn)化計算

相同點：
均為概率搜索算法
目的都是為了模擬自然現(xiàn)象，利用它們的某些特點去解決實際問題
區(qū)別：
智能優(yōu)化算法的靈感來源于群居動物的社會行為，強調(diào)對社會系統(tǒng)中個體之間相互協(xié)作的模擬。

基于群智能優(yōu)化算法的不足

數(shù)學(xué)理論基礎(chǔ)相對薄弱，涉及的各種參數(shù)
設(shè)置沒有確切的理論依據(jù)
帶有隨機性，每次的求解不一定一樣，當(dāng)處理突發(fā)事件時，系統(tǒng)的反映可能是不可預(yù)測的，這在一定程度上增加了其應(yīng)用風(fēng)險。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容