粒子群算法綜述

1、k一論文發(fā)表專冢一)中國學術期刊網www.qikanwang.nel粒子群算法綜述【摘要】：粒子群算法(pso)是一種新興的基于群體智能的啟發(fā)式全局搜索算法，具有易理解、易實現、全局搜索能力強等特點，倍受科學與工程領域的廣泛關注，已得到廣泛研究和應用。為了進一步推廣應用粒子群算法并為深入研究該算法提供相關資料，本文對目前國內外研究現狀進行了全面分析，在論述粒子群算法基本思想的基礎上，圍繞pso的運算過程、特點、改進方式與應用等方面進行了全面綜述，并給出了未來的研究方向展望。【關鍵詞】：粒子群算法優(yōu)化綜述優(yōu)化理論的研究一直是一個非?；钴S的研究領域。它所研究的問題是在多方案中尋求最優(yōu)方案。人們關于

2、優(yōu)化問題的研究工作，隨著歷史的發(fā)展不斷深入，對人類的發(fā)展起到了重要的推動作用。但是，任何科學的進步都受到歷史條件的限制，直到二十世紀中期，由于高速數字計算機日益廣泛應用，使優(yōu)化技術不僅成為迫切需要，而且有了求解的有力工具。因此，優(yōu)化理論和算法迅速發(fā)展起來，形成一門新的學科。至今已出現線性規(guī)劃、整數規(guī)劃、非線性規(guī)劃、幾何規(guī)劃、動態(tài)規(guī)劃、隨機規(guī)劃、網絡流等許多分支。這些優(yōu)化技術在諸多工程領域得到了迅速推廣和應用，如系統(tǒng)控制、人工智能、生產調度等。隨著人類生存空間的擴大，以及認識世界和改造世界范圍的拓寬，常規(guī)優(yōu)化法如牛頓法、車輛梯度法、模式搜索法、單純形法等已經無法處理人們所面的復雜問題，因此高效的

3、k一論文發(fā)表專冢一）中國學術期刊網www.qikanwang.nel優(yōu)化算法成為科學工作者的研究目標之一。1 .粒子群算法的背景粒子群算法（particleswarmoptimization,pso）是一種新興的演化算法。該算法是由j.kennedy和r.c.eberhart于1995年提出的一種基于群智能的隨機優(yōu)化算法。這類算法的仿生基點是：群集動物（如螞蟻、鳥、魚等）通過群聚而有效的覓食和逃避追捕。在這類群體的動物中，每個個體的行為是建立在群體行為的基礎之上的，即在整個群體中信息是共享的，而且在個體之間存在著信息的交換與協作。如在蟻群中，當每個個體發(fā)現食物之后，它將通過接觸或化學信號來招募

4、同伴，使整個群落找到食源；在鳥群的飛行中，每只鳥在初始狀態(tài)下處于隨機位置，且朝各個方向隨機飛行，但隨著時間推移，這些初始處于隨機狀態(tài)的鳥通過相互學習（相互跟蹤）組織的聚集成一個個小的群落，并以相同的速度朝著相同的方向飛行，最終整個群落聚集在同一位置一一食源。這些群集動物所表現的智能常稱為“群體智能”，它可表述為：一組相互之間可以進行直接通訊或間接通訊（通過改變局部環(huán)境）的主體，能夠通過合作對問題進行分布求解。換言之，一組無智能的主體通過合作表現出智能行為特征。粒子群算法就是以模擬鳥的群集智能為特征，以求解連續(xù)變量優(yōu)化問題為背景的一種優(yōu)化算法。因其概念簡單、參數較少、易于實現等特點，自提出以來已

5、經受到國內外研究者的高度重視并被廣泛應用于許多領域。k一論文發(fā)表專冢一)中國學術期刊網www.qikanwang.nel2 .國內外研究現狀粒子群算法一經提出就吸引了各國學者的注意，各種關于pso算法的理論與應用研究的成果不斷涌現，有力地推動了pso算法的研究。研究主要從下面兩個方向開展：一個是從具體優(yōu)化的應用著手，根據具體情況，對算法進行改進，以滿足應用要求；另外一個是粒子群算法的理論方面著手，分析算法的收斂性能，提高算法的優(yōu)化性。3 .粒子群算法概述3.1 粒子群算法的基本思想粒子群算法是基于群體的演化算法。reynolds對鳥群飛行的研究發(fā)現，鳥僅僅是追蹤它有限數量的鄰居，但最終的整體結

6、果是整個鳥群好像在一個中心的控制之下，即復雜的全局行為是由簡單規(guī)則的相互作用引起的。pso即源于對鳥群捕食行為的研究，一群鳥在隨機搜尋食物，如果這個區(qū)域里只有一塊食物，那么找到食物的最簡單有效的策略就是搜尋目前離食物最近的鳥的周圍區(qū)域。pso就是從這種模型中得到啟示而產生的，并用于解決優(yōu)化問題。另外，人們通常是以他們自己及他人的經驗作為決策的依據，這就構成了pso的基本概念。算法采用速度一位置搜索模型，每個粒子代表解空間的一個候選解，解的優(yōu)劣程度由適應度函數決定。速度vi=(vi1,vi2,，vid)決定粒子在搜索空間迭代時的位移。其中，適應度函數根據優(yōu)化目k一論文發(fā)表專冢一）中國學術期刊網w

7、ww.qikanwang.nel標定義。粒子群算法隨機初始化為一群粒子，其中第i個粒子在d維解空間的位置表示為xi=（xi1,xi2,，xin）。與進化算法比較，粒子群算法保留了基于種群的全局搜索策略，但是其采用的速度一位置模型，操作簡單，避免了復雜的遺傳操作。它特有的記憶使其可以動態(tài)跟蹤當前整個種群的最優(yōu)粒子。3.2 粒子群算法的運算過程粒子群算法的主要運算過程描述如下：種群初始化。隨機生成m個個體作為初始群體p（0）。由于粒子群群體為運算對象，所以我們必須為粒子群操作準備一個由若干初始解組成群體。個體評價（適應度評價）。計算群體中各個個體的適應度。粒子群算法在搜索進化過程中一般不需要其他外

8、部信息，僅用評估函數值來評價個體或優(yōu)劣，并作為以后粒子群操作的依據。評估函數值又稱為適應度。根據圖11、圖12更新粒子群的速度和位置。這是整個粒子群最關鍵的一步，種群的“個體學習”和“社會學習”都在這一步實現。終止條件判斷。若滿足終止條件（達到最大迭代次數或滿足最?。瑒t以進化過程中所得到的具有最大適應度的個體作為最優(yōu)解輸出，終止計算；否則，轉至第一步，繼續(xù)迭代。3.3 粒子群算法的特點粒子群算法有很強的魯棒性，與傳統(tǒng)的優(yōu)化技術相比，它采用了許多獨特的方法和技術。傳統(tǒng)的優(yōu)化算法都是從一個初始點出發(fā)，再逐步迭代以求最優(yōu)解。pso則不然，它是以一個群體，多點同時出發(fā)經過不斷迭代求得滿意解。傳統(tǒng)的優(yōu)

9、化算法不僅需要利用目標函數值，而且往往需要目標函數的導數值等其它一些輔助信息才能確定搜索方向。粒子群算法僅使用由目標函數值變換來的適應度函數值就可以確定進一步的搜索方向和搜索范圍，無需目標函數的導數值等其他一些輔助信息。傳統(tǒng)的優(yōu)化算法大都采用確定性的搜索方法，一個點到另一個點的搜索轉移有確定的轉移關系和轉移方向，這種確定性往往使得搜索可能永遠達不到最優(yōu)點，因而限制了算法的應用范圍。而粒子群算法屬于一種群體搜索方法，具有潛在的自適應性。4 .粒子群算法的幾種改進方式現在的粒子群算法大都在收斂速度與擺脫局部最優(yōu)這兩個方面下功夫，其實這又是兩個矛盾的方面。如何平衡這兩方面，各國研究人員相繼提出了各種

10、改進措施，概括起來主要有以下四點：變更公式法、分群方法、混合算法和擾動方法。5 .粒子群算法的應用kennedy和eberhart首先將pso算法應用到非線性函數優(yōu)化及神中國學術期刊網經網絡的訓練。在隨后的應用中，eberhart等又將粒子群算法與神經網絡進行結合用于分析人的顫抖。此后pso算法的應用領域不斷擴大，如將pso算法應用到各類連續(xù)問題和離散問題的參數優(yōu)化，包括模糊控制器的設計、機器人路徑規(guī)劃和模式識別等；將離散pso算法應用到0-1規(guī)劃問題及帶有排序關系的優(yōu)化問題，包括背包問題、電網機組控制、數據挖掘、tsp問題、vrp問題、job-shop及資源分配等。如wang等將量子理論應用

11、到粒子群算法中，提出了離散化量子群算法，對背包問題進行設計和求解，得到較滿意的結果。此后，呂強等提出了基于信息素機制的離散粒子群算法，利用蟻群的信息素機制來設計0-1背包問題，也取得不錯的效果；ting使用混合粒子群算法處理機組的開關控制并求解經濟負載分配問題，效果理想；elon利用bpso算法解決了生物信息數據集中的屬性選擇問題；clerc設計的tsp-dpso算法求解14個城市的tsp問題時，只搜索了問題空間的0.064%就找到了最優(yōu)值。此后肖健梅對粒子的速度分三次進行更新，每次都以更新后的結果代替原式中的位置進行比較，提高了算法求解tsp問題的計算速度和尋優(yōu)能力；對于車輛路徑問題，學者們

12、大都通過近似取整的方法，將粒子連續(xù)位置空間映射到離散排序空間，再通過粒子在連續(xù)空間的位置遷移引發(fā)離散狀態(tài)的變化；cagnina等用隨機鍵表示法表示粒子的位置解決單一機器調度問題；tasgetiren也用相同的方式把pso算法應用于排列流水作業(yè)調度及單一機器人調度問題上。除此之外，pso算法的應用包括系統(tǒng)設計、多目標優(yōu)化、自動目標檢測、時頻分析等。6 .總結粒子群算法(pso)是一種新興的基于群體智能的啟發(fā)式全局隨機搜索算法，具有易理解、易實現、全局搜索能力強等特點，為各個領域的研究人員提供了一種有效的全局優(yōu)化技術。本文對pso的基本思想、運算過程、特點、改進方式與應用等方面進行了全面綜述。在科學與工程實踐領域，關心pso的讀者的共同興趣所在是pso本身，即“pso是什么”和“有些什么樣的改進形式”，而“用pso怎樣解決某個具體問題”則依賴于相應領域的專業(yè)知識，為了讓盡可能多的國內讀者從中受益而不局限于具體的工作背景，綜述內容側重于對pso基本思想、算法改進方式，特別是相關國外國內發(fā)展現狀進行分析，pso應用列出了典型的一些主要應用對象。參考文獻：1最優(yōu)化理論與算法m,陳寶林，清華大學出版社