基于群體智能的算法研究

摘要：計算機技術不斷發展，從而帶動著算法技術不斷更新，尤其是在模仿社會性動物的行為領域，產生了很多的智能算法。本文主要介紹當前幾種熱門研究的算法，闡述了其工作原理和特點，同時對其發展進行了展望。

關鍵詞：群體智能；蟻群算法；粒子群優化算法；人工魚群算法

中圖分類號：TP183文獻標識碼：A文章編號：1009-3044(2008)11-20318-02

1 引言

在人工智能的研究領域，基于群體智能(Swarm Intelligence)的算法的研究成為了眾多專家研究的熱點。群體智能中的群體(Swarm)指的是“一組相互之間可以進行直接通信或者間接通信(通過改變局部環境)的主體，這組主體能夠合作進行分布問題求解”。而所謂群體智能指的是“無智能的主體通過合作表現出智能行為的特性”[1]。群體智能在沒有集中控制并且不提供全局模型的前提下，為尋找復雜的分布式問題的解決方案提供了基礎。本文的工作是闡述幾種基于群體智能的算法基本原理和模型及其展望。

2 基于群體智能的算法的特點

群體智能是基于種群行為對給定的目標進行尋優的啟發式搜索算法，群體中相互合作的個體是分布式的(Distributed)，這樣更能夠適應當前網絡環境下的工作狀態；沒有中心的控制與數據，這樣的系統更具有魯棒性(Robust)，不會由于某一個或者某幾個個體的故障而影響整個問題的求解?？梢圆煌ㄟ^個體之間直接通信而是通過非直接通信進行合作，這樣的系統具有更好的可擴充性(Scalability)。由于系統中個體的增加而增加的系統的通信開銷在這里十分小。系統中每個個體的能力十分簡單，這樣每個個體的執行時間比較短，并且實現也比較簡單，具有簡單性(Simplicity)。但是對于每個個體，其定義本身是相對的，其大小和功能根據所求解的問題而定，所以其智能的尋優方式的實現是通過整個智能群的總體特征來體現的。

雖然現在的研究還處在初級階段，但是從一些實驗來看，他代表了智能算法的研究方向。目前，比較成熟的群體智能算法有，蟻群算法(Ant Colony Algorithm，ACA)、粒子群優化算法(Particle Swarm Optimization，PSO)和人工魚群算法(Artificial Fish—Swarm Algorithm，AFSA)。

2 基于群體智能的算法的研究現狀

2.1 蟻群算法

蟻群算法是由20世紀90年代意大利的M．Dorigo等學者提出的。這種算法源于取食行為中的通信機制啟發而研究得來。螞蟻這類群居動物，單個螞蟻在運動過程中會留下一種稱之為“信息激素”(pheromone)的分泌物，后面的螞蟻可以感知前邊螞蟻所留下的信息激素的存在及其強度，并選擇自己要走的方向。螞蟻傾向于朝著該物質強度高的方向移動。因此，由大量螞蟻組成的蟻群的集體行為便表現出一種信息正反饋現象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。螞蟻個體之間就是通過這種信息的交流達到搜索食物的目的。而且，螞蟻還能夠適應環境的變化，如在蟻群運動路線上突然出現障礙物時，螞蟻能夠很快地重新找到最優路徑。

2.1.1 蟻群算法基本模型

蟻群算法[2]的核心是：選擇機制，信息素越多的路徑，被選擇的概率越大；更新機制，路徑上面的信息素會隨螞蟻的經過而增長，而且同時也隨時間的推移逐漸揮發消失；協調機制，螞蟻間實際上是通過分泌物來互相通信、協同工作的。

蟻群算法的首先成功應用于TSP問題，現就簡單描述其基本方法：給定一個有n個城市的TSP問題，人工螞蟻的數量為m。每個人工螞蟻的行為符合下列規律：根據路徑上的激素濃度，以相應的概率來選取下一步路徑；不再選取自己本次循環已經走過的路徑為下一步路徑。用一個數據來控制這一點，當完成了一次循環后，根據整個路徑長度來釋放相應濃度的信息素，并更新走過的路徑上的信息濃度。其基本流程是：初始化的時候，m個螞蟻被放置在不同的城市，賦予每條邊上的信息濃度都為零，每個螞蟻的數據庫的第一元素賦值為他所在的城市，當螞蟻們完成一次完整的尋徑過程后，計算信息素濃度，并且更新每條邊上的信息素濃度。然后開始新一輪的循環。當循環次數達到事先定義好的次數時或者所以的螞蟻都選擇了同一種路徑方式時，整個程序終止。

2.2 粒子群優化算法

粒子群優化算法[3]是一種進化計算技術(Evolutionary Computation)，由Eberhart博士和Kennedy博士發明。源于對鳥群捕食的行為而研究所得。一群鳥在隨機搜索食物的飛行過程中會通過參考同伴的運動信息來調整自己的運動狀態，在運動中，每個個體的信息都是共享的，正是通過這種相互借鑒可以是個體運動達到最優狀態。PSO中，空間中的一只鳥。我們稱之為“粒子”。所有的粒子都有一個由被優化的函數決定的適應值(fitness value)，每個粒子還有一個速度決定他們飛翔的方向和距離。然后粒子們就追隨當前的最優粒子在解空間中搜索。PSO初始化為一群隨機粒子(隨機解)，然后通過疊代找到最優解，在每一次疊代中，粒子通過跟蹤兩個“極值”來更新自己。第一個就是粒子本身所找到的最優解，這個解叫做個體極值pBest，另一個極值是整個種群目前找到的最優解，這個極值是全局極值gBest。另外也可以不用整個種群而只是用其中一部分最優粒子的鄰居，那么在所有鄰居中的極值就是局部極值。

2.2.1 PSO算法過程

①種群隨機初始化。

②對種群內的每一個個體計算適應值(fitness value)。適應值與最優解的距離直接有關。

③種群根據適應值進行復制。

④如果終止條件滿足的話，就停止，否則轉步驟②。

從以上步驟，算法使用適應值來評價系統，根據適應值來進行一定的隨機搜索。粒子還有一個重要的特點，就是有記憶。在PSO中，只gBest(or IBest)給出信息給其他的粒子，這是單向的信息流動。整個搜索更新過程是跟隨當前最優解的過程。與遺傳算法比較，在大多數的情況下，所有的粒子可能更快的收斂于最優解。

2.3 人工魚群算法

人工魚群算法[4]是李曉磊等在前人對群體智能行為研究的基礎上提出的一種新型仿生優化算法．這種算法源于魚群的覓食行為。在一片水域中，魚往往能自行或尾隨其它魚，找到營養物質多的地方，因而魚生存數目最多的地方一般就是本水域中營養物質最多的地方．人工魚群算法根據這一特點，通過構造人工魚來模仿魚群的覓食、聚群、追尾及隨機行為，從而實現尋優。

2.3.1 魚群算法的基本模型

（1）覓食行為：一般情況下魚在水中隨機、自由地游動，當發現附近有食物時，則會向著食物逐漸增多的方向游去。

（2）聚群行為：為了保證生存和躲避危害，魚會自然地聚集成群．魚聚群時所遵守的規則有3條。① 分隔規則，盡量避免與臨近伙伴過于擁擠；② 對準規則，盡量與臨近伙伴的平均方向一致；③ 內聚規則，盡量朝臨近伙伴的中心移動．

（3）追尾行為：當某條魚發現食物時，其他魚會尾隨其臨近的伙伴快速到達食物點。

（4）隨機行為：當閑暇無事時，魚在水中隨機、自由地游動尋找。

（5）約束行為：在尋優過程中，由于聚群行為，隨機行為等操作，可能出現不是可行解的情況，這時需要加人相應的約束條件來調整，使它們由無效狀態變為可行解。

（6）公告板：公告板用來記錄最優人工魚個體的狀態。各人工魚個體在尋優過程中，每次行動完畢就檢驗自身狀態與公告板的狀態，如果自身狀態優于公告板狀態，就將公告板的狀態改寫為自身狀態，這樣就使公告板記錄下歷史最優的狀態。

（7）移動策略：對人工魚當前所處的環境進行評價，即模擬執行聚群、追尾行為，然后選擇行動后食物濃度值較高的動作來執行，缺省行為方式為覓食行為。

本算法實質上是一種序列覆蓋算法，利用魚群算法具有良好的克服局部極值和獲取全局最優值（在這里是規則的質量）的能力，搜索出一個質量最好的規則，然后移去該規則所正確覆蓋的樣例，直至最后不能被覆蓋的樣例數小于允許最大未覆蓋的樣例數，則整個訓練算法結束，最終算法將得到一組最優的分類規則．

3 展望

基于智能的算法為解決一類優化問題提供了新思路，并且通過改進的算法在很多的領域得到應用，如構建網站，優化搜索引擎，構建電力系統，優化選擇和配送等。但是單純的對優化算法的研究很難再有其他大的突破。但是，生物群體擁有巨大的潛力供人們研究，目前還沒有形成系統的理論。以下幾個方面將是研究的熱點：（1）刺激產生新的算法的生物體的行為模型；（2）各種算法的完善和結合在實際問題上的應用；（3）充分挖掘智能算法在實際應用中的潛力；（4）系統的建模、仿真以及實際應用。

參考文獻：

[1] Kennedy J，Eberhart R C.Swarm intelligence[M].San Francisco: Morgan Kaufmann，2001．

[2] 段海濱，王道波，朱家強，等.蟻群算法理論及應用研究的進展[J].控制與決策，2004，19(12):1321-1326.

[3] 康琦.微粒群優化算法的研究與應用[D].上海：同濟大學，2005.

[4] 李曉磊，邵之江，錢積新.一種基于動物自治的尋優模式：魚群算法[J].系統工程理論與實踐，2002.

[5] 段海濱，王道波，于秀芬.幾種新型仿生優化算法的比較研究[J].計算機仿真，2007，03-0169-04.

[6] 王玫，朱云龍，何小賢.群體智能研究綜述[J].計算機工程，2005，22-0194-03.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文