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

智能控制課題報告粒子群優(yōu)化算法ParticleSwarmOptimization目錄CONTENT算法簡介

ALGORITHMINTRODUCTION01算法原理ALGORITHMPRINCIPLE02PSO和其他算法OTHERS03程序演示PROGRAMSHOW04算法簡介

ALGORITHMINTRODUCTION01粒子群算法設想這樣一個場景：一群鳥在隨機搜索食物。在這個區(qū)域里只有一塊食物。所有的鳥都不知道食物在那里。但是他們知道當前的位置離食物還有多遠。那么找到食物的最優(yōu)策略是什么呢？最簡單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域。算法介紹01算法介紹01PSO產(chǎn)生背景之一:CAS

我們把系統(tǒng)中的成員稱為具有適應性的主體(AdaptiveAgent)，簡稱為主體。所謂具有適應性，就是指它能夠與環(huán)境以及其它主體進行交流，在這種交流的過程中“學習”或“積累經(jīng)驗”，并且根據(jù)學到的經(jīng)驗改變自身的結(jié)構(gòu)和行為方式。整個系統(tǒng)的演變或進化，包括新層次的產(chǎn)生，分化和多樣性的出現(xiàn)，新的、聚合而成的、更大的主體的出現(xiàn)等等，都是在這個基礎上出現(xiàn)的。即CAS（復雜適應系統(tǒng)）理論的最基本思想算法介紹01CAS的四個基本特點：首先，主體(AdaptiveAgent)是主動的、活的實體；其次，個體與環(huán)境(包括個體之間)的相互影響，相互作用，是系統(tǒng)演變和進化的主要動力；再次，這種方法不象許多其他的方法那樣，把宏觀和微觀截然分開，而是把它們有機地聯(lián)系起來；最后，這種建模方法還引進了隨機因素的作用，使它具有更強的描述和表達能力。算法介紹01PSO產(chǎn)生背景之二：人工生命

研究具有某些生命基本特征的人工系統(tǒng)。包括兩方面的內(nèi)容：1、研究如何利用計算技術(shù)研究生物現(xiàn)象；2、研究如何利用生物技術(shù)研究計算問題。我們關(guān)注的是第二點。已有很多源于生物現(xiàn)象的計算技巧，例如神經(jīng)網(wǎng)絡和遺傳算法?，F(xiàn)在討論另一種生物系統(tǒng)---社會系統(tǒng)：由簡單個體組成的群落和環(huán)境及個體之間的相互行為。

Millonas在開發(fā)人工生命算法時(1994年)，提出群體智能概念并提出五點原則：

1、接近性原則：群體應能夠?qū)崿F(xiàn)簡單的時空計算；2、優(yōu)質(zhì)性原則：群體能夠響應環(huán)境要素；

3、變化相應原則：群體不應把自己的活動限制在一狹小范圍；

4、穩(wěn)定性原則：群體不應每次隨環(huán)境改變自己的模式；

5、適應性原則：群體的模式應在計算代價值得的時候改變。算法介紹01

社會組織的全局群行為是由群內(nèi)個體行為以非線性方式出現(xiàn)的。個體間的交互作用在構(gòu)建群行為中起到重要的作用。從不同的群研究得到不同的應用。最引人注目的是對蟻群和鳥群的研究。其中粒群優(yōu)化方法就是模擬鳥群的社會行為發(fā)展而來。對鳥群行為的模擬：Reynolds、Heppner和Grenader提出鳥群行為的模擬。他們發(fā)現(xiàn)，鳥群在行進中會突然同步的改變方向，散開或者聚集等。那么一定有某種潛在的能力或規(guī)則保證了這些同步的行為。這些科學家都認為上述行為是基于不可預知的鳥類社會行為中的群體動態(tài)學。在這些早期的模型中僅僅依賴個體間距的操作，也就是說，這種同步是鳥群中個體之間努力保持最優(yōu)的距離的結(jié)果。算法介紹01PSO（粒子群優(yōu)化算法（ParticleSwarmOptimization），縮寫為PSO）從這種模型中得到啟示并用于解決優(yōu)化問題。PSO中，每個優(yōu)化問題的解都是搜索空間中的一只鳥。我們稱之為“粒子”。所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適應值(fitnessvalue)，每個粒子還有一個速度決定他們飛翔的方向和距離。然后粒子們就追隨當前的最優(yōu)粒子在解空間中搜索。PSO初始化為一群隨機粒子(隨機解)。然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個"極值"來更新自己。第一個就是粒子本身所找到的最優(yōu)解，這個解叫做個體極值pBest。另一個極值是整個種群目前找到的最優(yōu)解，這個極值是全局極值gBest。另外也可以不用整個種群而只是用其中一部分作為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。算法介紹01PSO是近年來由J.Kennedy和R.C.Eberhart等開發(fā)的一種新的進化算法(EvolutionaryAlgorithm-EA)。PSO算法屬于進化算法的一種，和模擬退火算法相似，它也是從隨機解出發(fā)，通過迭代尋找最優(yōu)解，它也是通過適應度來評價解的品質(zhì)，但它比遺傳算法規(guī)則更為簡單，它沒有遺傳算法的“交叉”(Crossover)和“變異”(Mutation)操作，它通過追隨當前搜索到的最優(yōu)值來尋找全局最優(yōu)。這種算法以其實現(xiàn)容易、精度高、收斂快等優(yōu)點引起了學術(shù)界的重視，并且在解決實際問題中展示了其優(yōu)越性。粒子群算法是一種并行算法。算法原理

ALGORITHMPRINCIPLE02抽象鳥被抽象為沒有質(zhì)量和體積的微粒(點)，并延伸到N維空間，粒子I在N維空間的位置表示為矢量Xi＝(x1，x2，…，xN)，飛行速度表示為矢量Vi＝(v1，v2，…，vN)．每個粒子都有一個由目標函數(shù)決定的適應值(fitnessvalue)，并且知道自己到目前為止發(fā)現(xiàn)的最好位置(pbest)和現(xiàn)在的位置Xi．這個可以看作是粒子自己的飛行經(jīng)驗．除此之外，每個粒子還知道到目前為止整個群體中所有粒子發(fā)現(xiàn)的最好位置(gbest)(gbest是pbest中的最好值)．這個可以看作是粒子同伴的經(jīng)驗．粒子就是通過自己的經(jīng)驗和同伴中最好的經(jīng)驗來決定下一步的運動。算法原理02PSO初始化為一群隨機粒子(隨機解)。然后通過迭代找到最優(yōu)解。在每一次的迭代中，粒子通過跟蹤兩個“極值”(pbest,gbest)來更新自己。在找到這兩個最優(yōu)值后，粒子通過下面的公式來更新自己的速度和位置。(1)式(2)式在式(1)、(2)中，i＝1，2，…，M，M是該群體中粒子的總數(shù)算法原理02Vi是粒子的速度；pbest和gbest如前定義；rand()是介于（0、1）之間的隨機數(shù)；Xi是粒子的當前位置。c1和c2是學習因子，通常取c1＝c2＝2在每一維，粒子都有一個最大限制速度Vmax，如果某一維的速度超過設定的Vmax，那么這一維的速度就被限定為Vmax。（Vmax

>0）以上面兩個公式為基礎，形成了后來PSO的標準形式算法原理02

從社會學的角度來看，公式(1)的第一部分稱為記憶項，表示上次速度大小和方向的影響；公式第二部分稱為自身認知項，是從當前點指向粒子自身最好點的一個矢量，表示粒子的動作來源于自己經(jīng)驗的部分；公式的第三部分稱為群體認知項，是一個從當前點指向種群最好點的矢量，反映了粒子間的協(xié)同合作和知識共享。粒子就是通過自己的經(jīng)驗和同伴中最好的經(jīng)驗來決定下一步的運動。以上面兩個公式為基礎，形成了后來PSO的標準形式算法原理02

標準PSO算法的流程：Step1:初始化一群微粒(群體規(guī)模為m)，包括隨機位置和速度；Step2:評價每個微粒的適應度；Step3:對每個微粒，將其適應值與其經(jīng)過的最好位置pbest作比較，如果較好，則將其作為當前的最好位置pbest;Step4:對每個微粒，將其適應值與其經(jīng)過的最好位置gbest作比較，如果較好，則將其作為當前的最好位置gbest;Step5:根據(jù)(2)、(3)式調(diào)整微粒速度和位置；Step6：未達到結(jié)束條件則轉(zhuǎn)Step2。算法原理021998年shi等人在進化計算的國際會議上發(fā)表了一篇論文《Amodifiedparticleswarmoptimizer》對前面的公式(1)進行了修正。引入慣性權(quán)重因子。（3）式

非負，稱為慣性因子。公式(2)和(3)被視為標準pso算法。算法原理02算法原理02算法原理02

迭代終止條件根據(jù)具體問題一般選為最大迭代次數(shù)Gk或(和)微粒群迄今為止搜索到的最優(yōu)位置滿足預定最小適應閾值算法原理02

方程(2)和(3)中pbest和gbest分別表示微粒群的局部和全局最優(yōu)位置，當C1＝0時，則粒子沒有了認知能力，變?yōu)橹挥猩鐣哪Ｐ?social-only):被稱為全局PSO算法.粒子有擴展搜索空間的能力，具有較快的收斂速度，但由于缺少局部搜索，對于復雜問題比標準PSO更易陷入局部最優(yōu)。算法原理02

當C2＝0時，則粒子之間沒有社會信息，模型變?yōu)橹挥姓J知(cognition-only)模型：被稱為局部PSO算法。由于個體之間沒有信息的交流，整個群體相當于多個粒子進行盲目的隨機搜索，收斂速度慢，因而得到最優(yōu)解的可能性小。算法原理02參數(shù)有：群體規(guī)模m，慣性因子，學習因子c1和c2最大速度Vmax，迭代次數(shù)Gk。群體規(guī)模m一般取20～40，對較難或特定類別的問題可以取到100～200。最大速度Vmax決定當前位置與最好位置之間的區(qū)域的分辨率(或精度)。如果太快，則粒子有可能越過極小點;如果太慢，則粒子不能在局部極小點之外進行足夠的探索，會陷入到局部極值區(qū)域內(nèi)。這種限制可以達到防止計算溢出、決定問題空間搜索的粒度的目的。算法原理02權(quán)重因子包括慣性因子和學習因子c1和c2。使粒子保持著運動慣性，使其具有擴展搜索空間的趨勢，有能力探索新的區(qū)域。C1和c2代表將每個粒子推向Pbest和gbest位置的統(tǒng)計加速項的權(quán)值。較低的值允許粒子在被拉回之前可以在目標區(qū)域外徘徊，較高的值導致粒子突然地沖向或越過目標區(qū)域。算法原理02參數(shù)設置如果令c1＝c2＝0，粒子將一直以當前速度的飛行，直到邊界。很難找到最優(yōu)解。如果＝0，則速度只取決于當前位置和歷史最好位置，速度本身沒有記憶性。假設一個粒子處在全局最好位置，它將保持靜止，其他粒子則飛向它的最好位置和全局最好位置的加權(quán)中心。粒子將收縮到當前全局最好位置。在加上第一部分后，粒子有擴展搜索空間的趨勢，這也使得w的作用表現(xiàn)為針對不同的搜索問題，調(diào)整算法的全局和局部搜索能力的平衡。較大時，具有較強的全局搜索能力；較小時，具有較強的局部搜索能力。算法原理02通常設c1＝c2＝2。Suganthan的實驗表明：c1和c2為常數(shù)時可以得到較好的解，但不一定必須等于2。Clerc引入收斂(constrictionfactor)K來保證收斂性。其中算法原理02通常取為4.1,則K＝0.729.實驗表明，與使用慣性權(quán)重的PSO算法相比，使用收斂因子的PSO有更快的收斂速度。其實只要恰當?shù)倪x取和c1、c2，兩種算法是一樣的。因此使用收斂因子的PSO可以看作使用慣性權(quán)重PSO的特例。恰當?shù)倪x取算法的參數(shù)值可以改善算法的性能。算法原理02基本PSO是用于實值連續(xù)空間，然而許多實際問題是組合優(yōu)化問題，因而提出離散形式的PSO。速度和位置更新式為：elsethen算法原理02PSO和其他算法OTHERS03PSO和其他算法02遺傳算法和PSO的比較共性:(1)都屬于仿生算法。(2)都屬于全局優(yōu)化方法。(3)都屬于隨機搜索算法。(4)都隱含并行性。(5)根據(jù)個體的適配信息進行搜索，因此不受函數(shù)約束條件的限制，如連續(xù)性