第十講 粒群優(yōu)化與蟻群算法

1、群智能（群智能（ Swarm Intelligence ）什么是群？什么是群？l蟻群l魚群l鳥群l蜂群“群群”的特征的特征l相互影響的相鄰的個體相互影響的相鄰的個體l個體的行為簡單個體的行為簡單l既有競爭又有協(xié)作既有競爭又有協(xié)作l智能化的集體行為智能化的集體行為l個體之間不僅可以交換信息個體之間不僅可以交換信息,而且而且可以處理信息，根據(jù)信息來改變自可以處理信息，根據(jù)信息來改變自身行為身行為l沒有一個集中控制中心，分布式，沒有一個集中控制中心，分布式，自組織。自組織。l作為群體協(xié)作工作時，能夠突顯出作為群體協(xié)作工作時，能夠突顯出非常復(fù)雜的行為特征非常復(fù)雜的行為特征-智能行為，智能行為，群智能群

2、智能群智能（群智能（ Swarm Intelligence ）的提出和發(fā)展的提出和發(fā)展l1989年加利福尼亞大學(xué)的年加利福尼亞大學(xué)的Beni（貝尼）、（貝尼）、Hackwood教授在其細胞自動機中首次提出群教授在其細胞自動機中首次提出群智能的概念。細胞自動機中的主體在一維或二智能的概念。細胞自動機中的主體在一維或二維網(wǎng)格空間中與相鄰個體相互作用，從而實現(xiàn)維網(wǎng)格空間中與相鄰個體相互作用，從而實現(xiàn)自組織。自組織。l任何一種由昆蟲群體或其它動物社會行為機制任何一種由昆蟲群體或其它動物社會行為機制而激發(fā)設(shè)計出的算法或分布式解決問題的策略而激發(fā)設(shè)計出的算法或分布式解決問題的策略均屬于群智能。均屬于群智能

3、。 1999年，年，Bonabeau（伯納（伯納堡）、堡）、Dorigo和和Theraulaz 在他們的著作在他們的著作“Swarm Intelligence: From Natural to Artificial Systems,群智能：從自然到人工系統(tǒng)群智能：從自然到人工系統(tǒng)”Beni（貝尼）Bonabeau（伯納堡）群智能（群智能（ Swarm Intelligence ）的提出和發(fā)展的提出和發(fā)展l2001年肯尼迪和艾伯哈特合寫了一本書年肯尼迪和艾伯哈特合寫了一本書“群智能群智能”l群智能發(fā)展的歷程碑群智能發(fā)展的歷程碑l贊同伯納堡關(guān)于群智能的基本定義精神贊同伯納堡關(guān)于群智能的基本定義精神

4、l最重要的觀點：智能源于社會性的相互作用最重要的觀點：智能源于社會性的相互作用-群智群智能發(fā)展的基石。能發(fā)展的基石。l認為暫時無法給出合適的定義認為暫時無法給出合適的定義l群智能已經(jīng)成為有別于傳統(tǒng)人工智能中符號主義和群智能已經(jīng)成為有別于傳統(tǒng)人工智能中符號主義和鏈接主義的一種新的關(guān)于人工智能的研究路線鏈接主義的一種新的關(guān)于人工智能的研究路線Swarm IntelligencelSwarm Intelligence最重要的觀點是：最重要的觀點是：Mind is social，也就是認為人的智能是源于社會性的相互作用，也就是認為人的智能是源于社會性的相互作用，文化和認知是人類社會性不可分割的重要部分

5、，這一觀點文化和認知是人類社會性不可分割的重要部分，這一觀點成為了群智能發(fā)展的基石。群智能已成為有別于傳統(tǒng)人工成為了群智能發(fā)展的基石。群智能已成為有別于傳統(tǒng)人工智能中連接主義和符號主義的一種新的關(guān)于智能的描述方智能中連接主義和符號主義的一種新的關(guān)于智能的描述方法。法。 l群智能的思路，為在沒有集中控制且不提供全局模型的前群智能的思路，為在沒有集中控制且不提供全局模型的前提下尋找復(fù)雜的分布式問題求解方案提供了基礎(chǔ)。在計算提下尋找復(fù)雜的分布式問題求解方案提供了基礎(chǔ)。在計算智能領(lǐng)域已取得成功的兩種基于智能領(lǐng)域已取得成功的兩種基于SI的優(yōu)化算法是蟻群算法的優(yōu)化算法是蟻群算法和粒子群算法。和粒子群算法。

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

7、們的某些特點去解決實際問題。另一個與GA的的相同點是相同點是,基于基于SI的優(yōu)化算法也是概率搜索算法。的優(yōu)化算法也是概率搜索算法。Swarm Intelligencel 目前，已有的群智能理論和應(yīng)用研究證明群智能方法目前，已有的群智能理論和應(yīng)用研究證明群智能方法是一種能夠是一種能夠有效解決大多數(shù)優(yōu)化問題的新方法有效解決大多數(shù)優(yōu)化問題的新方法，更重要是，更重要是,群智能潛在的并行性和分布式特點為處理大量的以數(shù)據(jù)庫群智能潛在的并行性和分布式特點為處理大量的以數(shù)據(jù)庫形式存在的數(shù)據(jù)提供了技術(shù)保證。無論是從理論研究還是形式存在的數(shù)據(jù)提供了技術(shù)保證。無論是從理論研究還是應(yīng)用研究的角度分析應(yīng)用研究的角度分析

8、,群智能理論及應(yīng)用研究都是具有重群智能理論及應(yīng)用研究都是具有重要學(xué)術(shù)意義和現(xiàn)實價值的。要學(xué)術(shù)意義和現(xiàn)實價值的。Swarm Intelligence 由于由于SI的理論依據(jù)是源于對生物群社會性的模擬，因的理論依據(jù)是源于對生物群社會性的模擬，因此其相關(guān)數(shù)學(xué)分析還比較薄弱，這就導(dǎo)致了現(xiàn)有研究此其相關(guān)數(shù)學(xué)分析還比較薄弱，這就導(dǎo)致了現(xiàn)有研究還存在一些問題。還存在一些問題。數(shù)學(xué)理論基礎(chǔ)薄弱數(shù)學(xué)理論基礎(chǔ)薄弱：群智能算法的數(shù)學(xué)理論基礎(chǔ)相對?。喝褐悄芩惴ǖ臄?shù)學(xué)理論基礎(chǔ)相對薄弱，缺乏具備普遍意義的理論性分析，算法中涉及的弱，缺乏具備普遍意義的理論性分析，算法中涉及的各種參數(shù)設(shè)置一直沒有確切的理論依據(jù)，通常都是按各

9、種參數(shù)設(shè)置一直沒有確切的理論依據(jù)，通常都是按照經(jīng)驗型方法確定，對具體問題和應(yīng)用環(huán)境的依賴性照經(jīng)驗型方法確定，對具體問題和應(yīng)用環(huán)境的依賴性比較大。比較大。結(jié)果的可信性結(jié)果的可信性：同其它的自適應(yīng)問題處理方法一樣，群：同其它的自適應(yīng)問題處理方法一樣，群智能也不具備絕對的可信性，當處理突發(fā)事件時智能也不具備絕對的可信性，當處理突發(fā)事件時,系統(tǒng)系統(tǒng)的反應(yīng)可能是不可測的的反應(yīng)可能是不可測的,這在一定程度上增加了其應(yīng)用這在一定程度上增加了其應(yīng)用風險。風險。另外另外,群智能與其它各種先進技術(shù)群智能與其它各種先進技術(shù)(如如:神經(jīng)網(wǎng)絡(luò)、模糊邏神經(jīng)網(wǎng)絡(luò)、模糊邏輯、支持向量機等輯、支持向量機等) 的融合還不足的融合

10、還不足。 l無智能或簡單智能的主體通過任何形式的聚集無智能或簡單智能的主體通過任何形式的聚集協(xié)同而表現(xiàn)出智能行為的特性。協(xié)同而表現(xiàn)出智能行為的特性。 這里關(guān)心的不是個體之間的競爭，而是它們之間的協(xié)同（獲取并共享信息）。 螞蟻：信息素 魚群：速度、方向、位置等，群體最佳和個體最佳位置 鳥群：速度、方向、位置等。 Swarm Intelligence(續(xù)續(xù))基于群智能的優(yōu)化算法基于群智能的優(yōu)化算法l典型算法蟻群算法（螞蟻覓食）粒子群算法（蜂群或鳥群覓食）魚群算法（魚群覓食）l優(yōu)點靈活性穩(wěn)健性自組織潛在的并行和分布 已有的群智能理論的研究和應(yīng)用證明群智能方法是一已有的群智能理論的研究和應(yīng)用證明群智能

11、方法是一種能夠有效解決大多數(shù)優(yōu)化問題的新方法。種能夠有效解決大多數(shù)優(yōu)化問題的新方法。粒子群優(yōu)化算法粒子群優(yōu)化算法（Particle Swarm Optimization, PSO）l由James Kenney（社會心理學(xué)（社會心理學(xué)博士）博士）肯尼迪和Russ Eberhart（電子工程學(xué)博士（電子工程學(xué)博士）艾伯哈特，1995年提出l模擬鳥群或蜂群的覓食行為l基本思想：通過群體中個體之間的協(xié)作和信息共享來尋找最優(yōu)解, 肯尼迪鳥類的覓食鳥類的覓食l一群鳥在隨機的搜索食物，在一塊區(qū)域里只有一塊食物，所有的鳥都不知道食物在哪。但是它們知道自己的當前位置距離食物有多遠。l那么這群鳥找到食物的最優(yōu)策略

12、是什么？群體協(xié)作群體協(xié)作-獲取信息、共享信息獲取信息、共享信息粒子群優(yōu)化算法粒子群優(yōu)化算法粒子群優(yōu)化算法粒子群優(yōu)化算法l每個鳥抽象為一個無質(zhì)量，無體積的“粒子”l每個粒子有一個適應(yīng)度函數(shù)以模擬每只鳥與食物的距離l每個粒子有一個速度決定它的飛行方向和距離，初始值可以隨機確定l每一次單位時間的飛行后，所有粒子分享信息，下一步將飛向自身最佳位置和全局最優(yōu)位置的加權(quán)中心粒子群優(yōu)化算法流程粒子群優(yōu)化算法流程wPSO算法算法 初始化為一群隨機粒子，通過迭代找到最優(yōu)。 每次迭代中，粒子通過跟蹤“個體極值（pbest）”和“全局極值(gbest)”來 更新自己的位置。粒子群優(yōu)化算法粒子群優(yōu)化算法w粒子速度和位

13、置的更新粒子速度和位置的更新 假設(shè)在假設(shè)在D維搜索空間中，有維搜索空間中，有m個粒子；個粒子； 其中第其中第i個粒子的位置為矢量個粒子的位置為矢量 其飛翔速度也是一個矢量，記為其飛翔速度也是一個矢量，記為 第第i個粒子搜索到的最優(yōu)位置為個粒子搜索到的最優(yōu)位置為 整個粒子群搜索到的最優(yōu)位置為整個粒子群搜索到的最優(yōu)位置為 第第i個粒子的位置和速度更新為：個粒子的位置和速度更新為：Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid, 2 , 1 ;, 2 , 1 )()()()(11211),(21iDiiipppp),(21gbestDgbes

14、tgbestgbestpppp),(21iDiiixxxx),(21iDiiivvvv粒子群優(yōu)化算法粒子群優(yōu)化算法w粒子速度和位置的更新粒子速度和位置的更新 其中，其中，w稱為慣性權(quán)重，稱為慣性權(quán)重， c1和和c2為兩個正常系數(shù)，稱為加速因子。為兩個正常系數(shù)，稱為加速因子。 將將 vidk 限制在一個最大速度限制在一個最大速度 vmax 內(nèi)。內(nèi)。Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid, 2 , 1 ;, 2 , 1 )()()()(11211Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkid

15、idkidkid, 2 , 1 ;, 2 , 1 )()()()(11211“慣性部分慣性部分”，對自身運動狀對自身運動狀態(tài)的信任態(tài)的信任“認知部分認知部分”，對粒子，對粒子本身的思考，即來源本身的思考，即來源于自己經(jīng)驗的部分于自己經(jīng)驗的部分“社會部分社會部分”，粒間子的，粒間子的信息共享，來源于群體中信息共享，來源于群體中的其它優(yōu)秀微粒的經(jīng)驗的其它優(yōu)秀微粒的經(jīng)驗粒子群優(yōu)化算法粒子群優(yōu)化算法w算法流程算法流程 StartInitialize particles with random position and velocity vectors.For each particles positi

16、on (xi) evaluate fitnessIf fitness(xi) better than fitness(p) then p= xiLoop until all particles exhaustSet best of Ps as gBestUpdate particles velocity and positionLoop until max iterStop: giving gBest, optimal solution.基本粒子群算法描述基本粒子群算法描述粒子群優(yōu)化算法粒子群優(yōu)化算法w慣性權(quán)重慣性權(quán)重w 使粒子保持運動慣性，使其有擴展搜索空間的趨勢，使粒子保持運動慣性，使其有

17、擴展搜索空間的趨勢，有能力探索新的區(qū)域。有能力探索新的區(qū)域。 表示微粒對當前自身運動狀態(tài)的信任，依據(jù)自身的表示微粒對當前自身運動狀態(tài)的信任，依據(jù)自身的速度進行慣性運動。速度進行慣性運動。 較大的較大的w有利于跳出局部極值，而較小的有利于跳出局部極值，而較小的w有利于有利于算法收斂。算法收斂。Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid, 2 , 1 ;, 2 , 1 )()()()(11211粒子群優(yōu)化算法粒子群優(yōu)化算法w加速常數(shù)加速常數(shù)c1和和c2 代表將粒子推向代表將粒子推向pbest和和gbest位置的統(tǒng)計加速項的位置的統(tǒng)計加速

18、項的權(quán)重。權(quán)重。 表示粒子的動作來源于自己經(jīng)驗的部分和其它粒子表示粒子的動作來源于自己經(jīng)驗的部分和其它粒子 經(jīng)驗的部分。經(jīng)驗的部分。 較小的值允許粒子在被拉回之前可以在目標區(qū)域外較小的值允許粒子在被拉回之前可以在目標區(qū)域外徘徊，而較大的值則導(dǎo)致粒子突然沖向或越過目標徘徊，而較大的值則導(dǎo)致粒子突然沖向或越過目標區(qū)域。區(qū)域。 Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid, 2 , 1 ;, 2 , 1 )()()()(11211粒子群優(yōu)化算法粒子群優(yōu)化算法w加速常數(shù)加速常數(shù)c1和和c2 將將c1和和c2統(tǒng)一為一個控制參數(shù)，統(tǒng)一為一個控制參

19、數(shù)，= c1+c2 如果如果很小，粒子群運動軌跡將非常緩慢；很小，粒子群運動軌跡將非常緩慢； 如果如果很大，則微粒位置變化非?？欤缓艽?，則微粒位置變化非?？?； 實驗表明，當實驗表明，當=4.1（通常（通常c1=2.0，c2=2.0）時，具）時，具有很好的有很好的收斂效果收斂效果。粒子群優(yōu)化算法粒子群優(yōu)化算法w粒子數(shù)粒子數(shù) 一般取一般取2040，對較難或特定類別的問題可以取，對較難或特定類別的問題可以取 100200。w最大速度最大速度vmax 決定粒子在一個循環(huán)中最大的移動距離，通常設(shè)定決定粒子在一個循環(huán)中最大的移動距離，通常設(shè)定為粒子的范圍寬度。為粒子的范圍寬度。w終止條件終止條件 最大循環(huán)

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

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

22、。原理更簡單、參數(shù)更少、實現(xiàn)更容易。粒子群優(yōu)化算法流程粒子群優(yōu)化算法流程1、初始化一群粒子（群體規(guī)模），包括隨機的位置和速度2、評價每個粒子的適應(yīng)度3、對每個粒子更新個體最優(yōu)位置4、更新全局最優(yōu)位置5、根據(jù)速度和位置方程更新每個粒子的速度和位置6、如未滿足結(jié)束條件（通常為滿足足夠好的適應(yīng)值或達到設(shè)定的最大迭代次數(shù)），返回2粒子群優(yōu)化算法的應(yīng)用粒子群優(yōu)化算法的應(yīng)用廣泛應(yīng)用于各類優(yōu)化問題上在軍事領(lǐng)域中的應(yīng)用對巡航導(dǎo)彈的飛行高度進行優(yōu)化不同的飛行高度對巡航導(dǎo)彈的創(chuàng)地概率和突破防空系統(tǒng)的成功概率有較大影響，通過優(yōu)化可以得到在防空階段損失最小的最佳飛行高度美國“戰(zhàn)斧”Block IV型攻陸巡航導(dǎo)彈粒子群

23、優(yōu)化算法的應(yīng)用粒子群優(yōu)化算法的應(yīng)用車輛路徑問題的應(yīng)用郵政投遞火車及汽車的調(diào)度港口裝卸集裝箱蟻群算法蟻群算法l1992年由意大利的學(xué)者多里戈提出l模擬自然界中螞蟻尋找從巢穴到食物的最佳路徑的行為l一種新型的優(yōu)化算法l蟻群的自組織行為蟻群的自組織行為 1989年，年，戈斯戈斯等研究螞蟻覓等研究螞蟻覓食的食的“雙橋?qū)嶒炿p橋?qū)嶒灐?通過遺留在來往路徑通過遺留在來往路徑 上的信息素上的信息素 （Pheromone）的揮）的揮 發(fā)性化學(xué)物質(zhì)來進行發(fā)性化學(xué)物質(zhì)來進行 通信和協(xié)調(diào)。通信和協(xié)調(diào)。蟻穴蟻穴食物食物神奇的信息素神奇的信息素l螞蟻覓食的過程l隨機移動l遇到食物返回的路上分泌信息素l信息素：易揮發(fā)性的化

24、學(xué)物質(zhì)l在回家的路上留下信息素l其它螞蟻發(fā)現(xiàn)留有信息素的路徑結(jié)束漫游，沿著該路徑移動，遇到食物同樣返回途中分泌信息素。l信息素會隨著時間慢慢揮發(fā)，關(guān)鍵路徑上的信息素相對濃度高初始運行一段時間螞蟻系統(tǒng)螞蟻系統(tǒng)l多里戈在其博士論文中提出了一種螞蟻系統(tǒng)（ANT SYSTEM AS）,以解決旅行商問題（TSP）l一個售貨員希望去訪問若干個城市，開始和結(jié)束于同一城市，每兩個城市之間都有一條直接通路，怎樣行走才能使走過的路徑最短？蟻群算法蟻群算法l螞蟻在兩個城市之間移動l兩個城市之間的信息素越多，螞蟻就越有可能選擇它們之間的路徑l能夠成功完成遍歷的螞蟻會在路徑上留下信息素，路徑越短留下的信息素會越多。蟻群

25、算法原理蟻群算法原理l基于螞蟻覓食時的最優(yōu)路徑選擇問題，可以構(gòu)造人工蟻群，來解決最優(yōu)問題。l人工蟻群中把具有簡單功能的工作單元看作螞蟻l人工螞蟻與自然蟻群l相似之處：優(yōu)先選擇信息素濃度大的路徑l區(qū)別：人工螞蟻有一定的記憶能力，能夠記憶已經(jīng)訪問過的節(jié)點l人工蟻群在選擇下一條路徑的時候是按一定的算法有意識的尋找最短路徑，而不是盲目的。蟻群算法中的各種行為因子蟻群算法中的各種行為因子范圍范圍：螞蟻觀察到的范圍是一個方格世界，螞蟻有一個參數(shù)為速度半徑，那么它能觀察到的范圍以及能夠移動的范圍都會發(fā)生在這樣的一個范圍之內(nèi)環(huán)境環(huán)境：螞蟻所在的環(huán)境是一個虛擬的世界，其中有障礙物，有其他的螞蟻，還有信息素，信息

26、素可以設(shè)計為單一種類也可以多種類（如兩種），一種是找到食物的螞蟻撒下的食物信息素，另外一種是找到食物的螞蟻灑下的蟻窩的信息素。每個螞蟻都僅僅能感知它范圍內(nèi)的環(huán)境信息。同時環(huán)境也以一定的速率讓信息素消失。蟻群算法中的各種行為因子蟻群算法中的各種行為因子覓食規(guī)則覓食規(guī)則：在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就直接過去。否則通過比較在能感知的范圍內(nèi)的信息素的多少，然后它會向信息素最多的方向移動。同時每只螞蟻還以小概率來進行“犯錯”。從而并不總是向信息素最多的方向移動。螞蟻找到窩的規(guī)則和上面的相同，只不過它只對窩的信息素進行反應(yīng)，而對食物信息素沒有任何反應(yīng)移動規(guī)則移動規(guī)則：每只螞蟻都向信息素最多的方向前進，并且在運動方向上有一個隨機的小擾動。為了防止螞蟻原地轉(zhuǎn)圈，它會記住剛才走過了那些點，