粒子群算法綜述

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

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

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

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

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

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

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

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

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

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

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

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