粒子群算法簡介優(yōu)缺點(diǎn)及其應(yīng)用.ppt

1、2020/8/17,1,粒子群算法,2020/8/17,2,粒子群算法的研究背景,粒子群算法(Particle Swarm Optimization，簡稱PSO)，是一種基于群體智能的進(jìn)化計(jì)算方法。PSO由Kennedy和Eberhart博士于1995年提出。,粒子群算法源于復(fù)雜適應(yīng)系統(tǒng)（Complex Adaptive System,CAS）。CAS理論于1994年正式提出，CAS中的成員稱為主體。比如研究鳥群系統(tǒng)，每個(gè)鳥在這個(gè)系統(tǒng)中就稱為主體。主體有適應(yīng)性，它能夠與環(huán)境及其他的主體進(jìn)行交流，并且根據(jù)交流的過程“學(xué)習(xí)”或“積累經(jīng)驗(yàn)”改變自身結(jié)構(gòu)與行為。整個(gè)系統(tǒng)的演變或進(jìn)化包括：新層次的產(chǎn)生（

2、小鳥的出生）；分化和多樣性的出現(xiàn)（鳥群中的鳥分成許多小的群）；新的主題的出現(xiàn)（鳥尋找食物過程中，不斷發(fā)現(xiàn)新的食物）。,2020/8/17,3,PSO的基本概念源于對鳥群捕食行為的研究： 一群鳥在隨機(jī)搜尋食物，在這個(gè)區(qū)域里只有一塊食物，所有鳥都不知道食物在哪里。但是他們知道當(dāng)前的位置離食物還有多遠(yuǎn)。 那么找到食物的最優(yōu)策略是什么呢?最簡單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域。,粒子群算法的基本原理,2020/8/17,4,PSO算法就從這種生物種群行為特性中得到啟發(fā)并用于求解優(yōu)化問題。 在PSO中，把一個(gè)優(yōu)化問題看作是在空中覓食的鳥群，那么“食物”就是優(yōu)化問題的最優(yōu)解，而在空中飛行的每一只

3、覓食的“鳥”就是PSO算法中在解空間中進(jìn)行搜索的一個(gè)“粒子”(Particle)。 “群”(Swarm)的概念來自于人工生命，滿足人工生命的五個(gè)基本原則。因此PSO算法也可看作是對簡化了的社會(huì)模型的模擬，這其中最重要的是社會(huì)群體中的信息共享機(jī)制，這是推動(dòng)算法的主要機(jī)制。,2020/8/17,5,粒子在搜索空間中以一定的速度飛行，這個(gè)速度根據(jù)它本身的飛行經(jīng)驗(yàn)和同伴的飛行經(jīng)驗(yàn)來動(dòng)態(tài)調(diào)整。所有的粒子都有一個(gè)被目標(biāo)函數(shù)決定的適應(yīng)值(fitness value)，這個(gè)適應(yīng)值用于評價(jià)粒子的“好壞”程度。 每個(gè)粒子知道自己到目前為止發(fā)現(xiàn)的最好位置(particle best，記為pbest)和當(dāng)前的位置，p

4、best就是粒子本身找到的最優(yōu)解，這個(gè)可以看作是粒子自己的飛行經(jīng)驗(yàn)。 除此之外，每個(gè)粒子還知道到目前為止整個(gè)群體中所有粒子發(fā)現(xiàn)的最好位置(global best，記為gbest)，gbest是在pbest中的最好值，即是全局最優(yōu)解，這個(gè)可以看作是整個(gè)群體的經(jīng)驗(yàn)。,2020/8/17,6,每個(gè)粒子使用下列信息改變自己的當(dāng)前位置： (1)當(dāng)前位置； (2)當(dāng)前速度； (3)當(dāng)前位置與自己最好位置之間的距離； (4)當(dāng)前位置與群體最好位置之間的距離。,2020/8/17,7,用隨機(jī)解初始化一群隨機(jī)粒子，然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個(gè)“極值”來更新自己： 一個(gè)是粒子本身所找到

5、的最好解，即個(gè)體極值(pbest)，另一個(gè)極值是整個(gè)粒子群中所有粒子在歷代搜索過程中所達(dá)到的最優(yōu)解(gbest)即全局極值。 找到這兩個(gè)最好解后，接下來是PSO中最重要的“加速”過程，每個(gè)粒子不斷地改變其在解空間中的速度，以盡可能地朝pbest和gbest所指向的區(qū)域“飛”去。,粒子群算法的基本思想,2020/8/17,8,假設(shè)在一個(gè)N維空間進(jìn)行搜索，粒子i的信息可用兩個(gè)N維向量來表示： 第i個(gè)粒子的位置可表示為 速度為 在找到兩個(gè)最優(yōu)解后，粒子即可根據(jù)下式來更新自己的速度和位置：,粒子群優(yōu)化算法的一般數(shù)學(xué)模型,：是粒子i在第k次迭代中第d維的速度； ：是粒子i在第k次迭代中第d維的當(dāng)前位置；

6、,(1),(2),2020/8/17,9,i=1，2，3，M：種群大小。 c1和c2：學(xué)習(xí)因子，或稱加速系數(shù)，合適的c1和c2既可加快收斂又不易陷入局部最優(yōu)。 rand1和rand2：是介于0,1之間的隨機(jī)數(shù)。 是粒子i在第d維的個(gè)體極值點(diǎn)的位置； 是整個(gè)種群在第d維的全局極值點(diǎn)的位置。,最大速度vmax：決定了問題空間搜索的力度，粒子的每一維速度vid都會(huì)被限制在vdmax，+vdmax 之間，假設(shè)搜索空間的第d維定義為區(qū)間xdmax，+xdmax ，則通常vdmax=kxdmax ， 0.1k1.0，每一維都用相同的設(shè)置方法。,2020/8/17,10,公式(1)主要通過三部分來計(jì)算粒子i

7、更新的速度： 粒子i前一時(shí)刻的速度 ； 粒子當(dāng)前位置與自己歷史最好位置之間的距離 ； 粒子當(dāng)前位置與群體最好位置之間的距離 。 粒子通過公式(2)計(jì)算新位置的坐標(biāo)。,更新公式的意義,2020/8/17,11,式(1)的第一部分稱為動(dòng)量部分，表示粒子對當(dāng)前自身運(yùn)動(dòng)狀態(tài)的信任，為粒子提供了一個(gè)必要?jiǎng)恿浚蛊湟罁?jù)自身速度進(jìn)行慣性運(yùn)動(dòng)； 第二部分稱為個(gè)體認(rèn)知部分，代表了粒子自身的思考行為，鼓勵(lì)粒子飛向自身曾經(jīng)發(fā)現(xiàn)的最優(yōu)位置； 第三部分稱為社會(huì)認(rèn)知部分，表示粒子間的信息共享與合作，它引導(dǎo)粒子飛向粒子群中的最優(yōu)位置。 公式(1)的第一項(xiàng)對應(yīng)多樣化(diversification)的特點(diǎn)，第二項(xiàng)、第三項(xiàng)對應(yīng)

8、于搜索過程的集中化(intensification)特點(diǎn)，這三項(xiàng)之間的相互平衡和制約決定了算法的主要性能。,2020/8/17,12,參數(shù)意義,(1)粒子的長度N：問題解空間的維數(shù)。 (2)粒子種群大小M：粒子種群大小的選擇視具體問題而定，但是一般設(shè)置粒子數(shù)為20-50。對于大部分的問題10個(gè)粒子已經(jīng)可以取得很好的結(jié)果，不過對于比較難的問題或者特定類型的問題，粒子的數(shù)量可以取到100或200。另外，粒子數(shù)目越多，算法搜索的空間范圍就越大，也就更容易發(fā)現(xiàn)全局最優(yōu)解。當(dāng)然，算法運(yùn)行的時(shí)間也較長。 (3)加速常數(shù)c1和 c2：分別調(diào)節(jié)向Pbest和Gbest方向飛行的最大步長，決定粒子個(gè)體經(jīng)驗(yàn)和群體

9、經(jīng)驗(yàn)對粒子運(yùn)行軌跡的影響，反映粒子群之間的信息交流。 如果c1=0，則粒子只有群體經(jīng)驗(yàn)，它的收斂速度較快，但容易陷入局部最優(yōu)；,2020/8/17,13,如果c2 = 0，則粒子沒有群體共享信息，一個(gè)規(guī)模為M的群體等價(jià)于運(yùn)行了M個(gè)各行其是的粒子，得到解的幾率非常小，因此一般設(shè)置c1 = c2 。這樣，個(gè)體經(jīng)驗(yàn)和群體經(jīng)驗(yàn)就有了相同重要的影響力，使得最后的最優(yōu)解更精確。 改變這些常數(shù)會(huì)改變系統(tǒng)的“張力”，較低的c1 和 c2值使得粒子徘徊在遠(yuǎn)離目標(biāo)的區(qū)域，較高的c1 和 c2值產(chǎn)生陡峭的運(yùn)動(dòng)或越過目標(biāo)區(qū)域。 Shi和Eberhart建議，為了平衡隨機(jī)因素的作用，一般情況下設(shè)置c1 c2，大部分算法

10、都采用這個(gè)建議。,2020/8/17,14,(4)粒子的最大速度vmax ：粒子的速度在空間中的每一維上都有一個(gè)最大速度限制值vdmax ，用來對粒子的速度進(jìn)行鉗制，使速度控制在范圍vdmax，vdmax 內(nèi)，這決定問題空間搜索的力度，該值一般由用戶自己設(shè)定。 vmax是一個(gè)非常重要的參數(shù)，如果該值太大，則粒子們也許會(huì)飛過優(yōu)秀區(qū)域；另一方面如果該值太小，則粒子們可能無法對局部最優(yōu)區(qū)域以外的區(qū)域進(jìn)行充分的探測。實(shí)際上，它們可能會(huì)陷入局部最優(yōu)，而無法移動(dòng)足夠遠(yuǎn)的距離跳出局部最優(yōu)達(dá)到空間中更佳的位置。 (5) rand1和rand2是介于0,1之間的隨機(jī)數(shù)，增加了粒子飛行的隨機(jī)性。 (6)迭代終止條

11、件：一般設(shè)為最大迭代次數(shù)Tmax、計(jì)算精度或最優(yōu)解的最大停滯步數(shù)t。,2020/8/17,15,算法流程,2020/8/17,16,程序偽代碼,For each particle Initialize particle End Do For each particle Calculate fitness value If the fitness value is better than the best fitness value (pbest) in history set current value as the new pbest End Choose the particle with

12、 the best fitness value of all the particles as the gbest For each particle Calculate particle velocity according equation (1) Update particle position according equation (2) End While maximum iterations or minimum error criteria is not attained,2020/8/17,17,PSO的各種改進(jìn)算法,PSO收斂速度快，特別是在算法的早期，但也存在著精度較低，易

13、發(fā)散等缺點(diǎn)。 若加速系數(shù)、最大速度等參數(shù)太大，粒子群可能錯(cuò)過最優(yōu)解，算法不收斂； 而在收斂的情況下，由于所有的粒子都向最優(yōu)解的方向飛去，所以粒子趨向同一化（失去了多樣性），使得后期收斂速度明顯變慢，同時(shí)算法收斂到一定精度時(shí)，無法繼續(xù)優(yōu)化，所能達(dá)到的精度也不高。 因此很多學(xué)者都致力于提高PSO算法的性能。,2020/8/17,18,慣性權(quán)重法（Inertia Weight）,慣性權(quán)重法是由Shi等提出的，其速度更新公式為：,為非負(fù)數(shù)，稱為慣性因子，慣性權(quán)重，是控制速度的權(quán)重,如果沒有公式(1)的第一部分，PSO的搜索過程是一個(gè)通過迭代搜索空間逐漸收縮的過程，展現(xiàn)出一種局部搜索(exploitat

14、ion)能力；反之，如果增加了第一部分，粒子就有能力擴(kuò)展搜索空間，展現(xiàn)出一種全局搜索(exploration)的能力。在搜索過程中，全局搜索能力與局部搜索能力的平衡對于算法的成功起著至關(guān)重要的作用。 引入一個(gè)慣性權(quán)重到公式(1)， 是與前一次速度有關(guān)的一個(gè)比例因子，較大的可以加強(qiáng)PSO的全局探測能力，而較小的能加強(qiáng)局部搜索能力，也就是這個(gè)執(zhí)行了全局搜索和局部搜索之間的平衡角色。,(3),2020/8/17,19,(1)線性調(diào)整的策略 允許的最大速度vmax實(shí)際上作為一個(gè)約束，控制PSO能夠具有的最大全局搜索能力。如果vmax較小，那么最大的全局搜索能力將被限制，不論慣性權(quán)重的大小，PSO只支持

15、局部搜索；如果設(shè)置vmax較大，那么PSO通過選擇 ，有一個(gè)可供很多選擇的搜索能力范圍。 由此可以看出，允許的最大速度間接地影響全局搜索能力，而慣性權(quán)重直接影響全局搜索能力，所以希望找到一個(gè)非常好的慣性權(quán)重來達(dá)到全局搜索和局部搜索之間的平衡。 類似于人的“原動(dòng)力”，如果原動(dòng)力比較大，當(dāng)達(dá)到某個(gè)目標(biāo)的時(shí)候，會(huì)繼續(xù)向前實(shí)現(xiàn)更高的目標(biāo)：如果原動(dòng)力較小，到達(dá)某個(gè)目標(biāo)就停滯。,2020/8/17,20,Shi和Eberhart提出了一種隨著算法迭代次數(shù)的增加慣性權(quán)重線性下降的方法。 慣性權(quán)重的計(jì)算公式如下：,max和min分別表示權(quán)重的最大及最小值，kn為當(dāng)前迭代次數(shù)，kmax表示最大迭代次數(shù)。 文獻(xiàn)試

16、驗(yàn)了將設(shè)置為從0.9到0.4的線性下降，使得PSO在開始時(shí)探索較大的區(qū)域，較快地定位最優(yōu)解的大致位置，隨著逐漸減小，粒子速度減慢，開始精細(xì)的局部搜索。該方法使PSO更好地控制exploration和exploitation能力，加快了收斂速度，提高了算法的性能，稱之為權(quán)重線性下降的粒子群算法，簡記為LDW(Linearly Decreasing Inertia Weight)。,2020/8/17,21,(2)模糊調(diào)整的策略 PSO搜索過程是一個(gè)非線性的復(fù)雜過程，讓線性下降的方法并不能正確反映真實(shí)的搜索過程。因而，Shi等提出用模糊推理機(jī)來動(dòng)態(tài)地調(diào)整慣性權(quán)重的技術(shù)。 即構(gòu)造一個(gè)2輸入、1輸出的

17、模糊推理機(jī)來動(dòng)態(tài)地修改慣性因子。模糊推理機(jī)的兩個(gè)輸入分別是當(dāng)前值，以及規(guī)范化后的當(dāng)前最好性能評價(jià)值(The Normalized Current Best Performance Evaluation，NCBPE)；而輸出是的增量。 CBPE (The Current Best Performance Evaluation，CBPE) 是PSO迄今為止發(fā)現(xiàn)的最好候選解的性能測度。由于不同的優(yōu)化問題有不同的性能評價(jià)值范圍，所以為了讓該模糊系統(tǒng)有廣泛的適用性，通常使用標(biāo)準(zhǔn)化的CBPE (NCBPE)。,2020/8/17,22,假定優(yōu)化問題為最小化問題，則規(guī)范化后的評價(jià)值,其中，CBPEmax和C

18、BPEmin分別是CBPE可能取值的上下限，其值根據(jù)具體問題而定，且需事先得知或者可估計(jì)，這使得模糊自適應(yīng)策略的實(shí)現(xiàn)較為困難，無法廣泛使用，但其與線性減小策略相比，具有更好的性能。,2020/8/17,23,粒子群算法的優(yōu)缺點(diǎn)分析,PSO算法沒有交叉和變異運(yùn)算，依靠粒子速度完成搜索，并且在迭代進(jìn)化中只有最優(yōu)的粒子把信息傳遞給其它粒子，搜索速度快； PSO算法具有記憶性，粒子群體的歷史最好位置可以記憶并傳遞給其它粒子； 需調(diào)整的參數(shù)較少，結(jié)構(gòu)簡單，易于工程實(shí)現(xiàn)； 采用實(shí)數(shù)編碼，直接由問題的解決定，問題解的變量數(shù)直接作為粒子的維數(shù)。,（1）粒子群算法的優(yōu)點(diǎn),2020/8/17,24,（2）粒子群算

19、法的缺點(diǎn),缺乏速度的動(dòng)態(tài)調(diào)節(jié)，容易陷入局部最優(yōu)，導(dǎo)致收斂精度低和不易收斂； 不能有效解決離散及組合優(yōu)化問題； 不能有效求解一些非直角坐標(biāo)系描述問題，如有關(guān)能量場或場內(nèi)粒子運(yùn)動(dòng)規(guī)律的求解問題(這些求解空間的邊界大部分是基于極坐標(biāo)、球坐標(biāo)或柱坐標(biāo)的)； 參數(shù)控制，對于不同的問題，如何選擇合適的參數(shù)來達(dá)到最優(yōu)效果。,2020/8/17,25,粒子群算法的應(yīng)用范圍,函數(shù)優(yōu)化 PSO算法最初被應(yīng)用于函數(shù)優(yōu)化，但后來的學(xué)者經(jīng)過研究發(fā)現(xiàn)，粒子群算法在解決一些經(jīng)典的函數(shù)優(yōu)化問題，甚至一些非線性函數(shù)時(shí)也展示出了良好的性能。,粒子群優(yōu)化算法已提出就受到了廣泛的關(guān)注，各種粒子群算法應(yīng)用研究的成果不斷涌現(xiàn)，它的應(yīng)用領(lǐng)域已從最初的函數(shù)優(yōu)化和神經(jīng)網(wǎng)絡(luò)的訓(xùn)練擴(kuò)展到更加開闊的領(lǐng)域，有力地促進(jìn)了粒子群優(yōu)化算法的研究。目前粒子群優(yōu)化算法的主要應(yīng)用在如下幾個(gè)方面：,2020/8/17,26,神經(jīng)網(wǎng)絡(luò)訓(xùn)練 將PSO算法用于神經(jīng)網(wǎng)絡(luò)訓(xùn)練也取得了良好的效果，研究表明，PSO是一種很有潛力的神經(jīng)網(wǎng)絡(luò)訓(xùn)練算法，如用于市區(qū)環(huán)境狀況的分析和預(yù)測等取得了較高的成功率。 工程領(lǐng)域應(yīng)用 很多工程中的實(shí)際問題，本質(zhì)上都是優(yōu)化問題，因此PSO算法自然就可以應(yīng)用到實(shí)際的工程問題來，將PSO肅反和BP神經(jīng)網(wǎng)絡(luò)算法相結(jié)合訓(xùn)練神經(jīng)網(wǎng)絡(luò)已用于對電動(dòng)汽車燃料電池組充電情況的模擬。粒子群優(yōu)化算法和其它進(jìn)化算法