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

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

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

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

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

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

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

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

3、變化相應(yīng)原則：群體不應(yīng)把自己的活動(dòng)限制在一狹小范圍；

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

5、適應(yīng)性原則：群體的模式應(yīng)在計(jì)算代價(jià)值得的時(shí)候改變。算法介紹01

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

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

>0）以上面兩個(gè)公式為基礎(chǔ)，形成了后來PSO的標(biāo)準(zhǔn)形式算法原理02

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

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

非負(fù)，稱為慣性因子。公式(2)和(3)被視為標(biāo)準(zhǔn)pso算法。算法原理02算法原理02算法原理02

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

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

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