1、粒子群優(yōu)化算法(Particle Swarm OptimizationPSO），是由J. Kennedy和R. C. Eberhart于1995年提出的一種基于種群的隨機(jī)的優(yōu)化算法。,背景知識(shí)：,James Kennedy,Russell Eberhart,PSO算法基于早期的 Boids模型，這個(gè)模型由Craig W. Reynolds建立，最初是為了圖形化的模擬鳥群的運(yùn)動(dòng)而設(shè)計(jì)的。該模型滿足三條基本規(guī)則： 1. 分隔規(guī)則： 當(dāng)個(gè)體與某些鄰居靠的太近的時(shí)候就會(huì)盡量避開。 2. 匹配規(guī)則： 每個(gè)個(gè)體的飛行方向盡量同周圍的鄰居的飛行方向保持一致。 3. 吸引規(guī)則： 每個(gè)個(gè)體都要盡量靠近他的鄰居所

2、在的中心位置。,基于這個(gè)模型，給每個(gè)個(gè)體一個(gè)隨機(jī)的初始速度和位置，程序運(yùn)行的每一步都根據(jù)以上三條規(guī)則迭代，很快就會(huì)使得所有點(diǎn)的速度變得一樣 。 由于Boids模型太簡(jiǎn)單而且遠(yuǎn)離真實(shí)情況，于是Heppner對(duì)該模型進(jìn)行了改進(jìn)，提出了一個(gè)“谷地”模型，用來(lái)模擬鳥類的覓食行為。 假設(shè)在平面上存在一個(gè)“谷地”，即食物所在地，鳥群開始時(shí)隨機(jī)的分散在平面上，尋找食物時(shí)鳥群按照如下三條規(guī)則運(yùn)動(dòng)：,1.每個(gè)個(gè)體都會(huì)被谷地的位置吸引； 2.每個(gè)個(gè)體會(huì)記住在運(yùn)動(dòng)過(guò)程中離“谷地”最近的點(diǎn)； 3.每個(gè)個(gè)體會(huì)將自己離“谷地”最近的點(diǎn)分享給其他個(gè)體。,用當(dāng)前位置到谷地的距離：來(lái)衡量當(dāng)前位置和速度的“好壞程度”，離谷地的距

3、離越近，則越“好”，反之越“壞”。 由于每只鳥都能記住自己到達(dá)的最優(yōu)位置pbest，并且每只鳥都能同種群中其他鳥通信，能夠知道種群中的最優(yōu)位置gbest，則它們的速度會(huì)按照如下公式變化：,在計(jì)算機(jī)上模擬該模型的結(jié)果顯示：當(dāng)g_increment較大時(shí)，所有的個(gè)體很快地聚集到“谷地”上；反之，粒子緩慢地?fù)u擺著聚集到“谷地”的四周。 受此模型啟發(fā)Kennedy和Eberhart設(shè)計(jì)出了一種演化優(yōu)化算法，并通過(guò)不斷的試驗(yàn)和試錯(cuò)，最后將此算法的基本型固定為：,形成了PSO算法的最初版本。,對(duì)公式的說(shuō)明：,分別稱為“認(rèn)知學(xué)習(xí)因子”和“社會(huì)學(xué)習(xí)因子 ”取值一般取2；,為0-1之間的一個(gè)隨機(jī)值。,對(duì)公式的說(shuō)

4、明：,第一部分為微粒先前行為的慣性 。表示微粒依據(jù)自身的速度進(jìn)行慣性運(yùn)動(dòng) 。,對(duì)公式的說(shuō)明：,第二部分取決于微粒當(dāng)前位置與自身最優(yōu)位置之間的距離，為 “認(rèn)知(cognition)”部分，表示微粒本身的思考。,對(duì)公式的說(shuō)明：,第三部分取決于微粒當(dāng)前位置與群體中全局（或局部）最優(yōu)位置之間的距離，為“社會(huì)(social)”部分，表示微粒間的信息共享與相互合作。,算法思想：,1.初始化種群數(shù)量，使他們隨機(jī)的分布在平面上； 2.根據(jù)模型評(píng)估每個(gè)粒子的位置； 3.如果一個(gè)粒子當(dāng)前的位置比它之前的的位置好，則記錄下新位置，記為pbest； 4.確定種群中最好的粒子的位置，記為gbest；,5.根據(jù)公式： 更

5、新每個(gè)粒子的速度；,6.根據(jù)公式： 更新每個(gè)粒子的位置；,7.返回第2步重新迭代，直到滿足停止條件； 2.根據(jù)模型評(píng)估每個(gè)粒子的位置； 3.如果一個(gè)粒子當(dāng)前的位置比它之前的的位置好，則記錄下新位置，記為pbest； 4.確定種群中最好的粒子的位置，記為gbest；,5.根據(jù)公式： 更新每個(gè)粒子的速度；,6.根據(jù)公式： 更新每個(gè)粒子的位置；,7.返回第2步迭代，直到滿足停止條件。,算法改進(jìn)：,初始算法提出不久之后就出現(xiàn)了一種改進(jìn)算法，在速度迭代公式中引入了慣性權(quán)重 ，速度迭代公式變?yōu)椋?慣性權(quán)重在迭代過(guò)程中一般在0.9-0.4之間呈線性遞減。 雖然該改進(jìn)算法與初始版本相比復(fù)雜程度并沒(méi)有太大的增加

6、，但是性能卻有了很大的提升，因而被廣泛使用。,帶收縮因子的PSO算法：,收縮因子保證了收斂性并提高了收斂速度。 顯然，該迭代公式和標(biāo)準(zhǔn)迭代公式相比并無(wú)本質(zhì)區(qū)別，只要適當(dāng)選取參數(shù)，二者完全相同。,局部PSO算法：,在全局版本中，微粒跟蹤的兩個(gè)極值為自身最優(yōu)位置pbest和種群最優(yōu)位置gbest。 對(duì)應(yīng)的，在局部版本中，微粒除了追隨自身最優(yōu)位置pbest之外，不跟蹤種群最優(yōu)位置gbest，而是跟蹤拓?fù)溧徲蛑械乃形⒘５淖顑?yōu)位置lbest。,PSO算法的優(yōu)缺點(diǎn)：,PSO算法的優(yōu)點(diǎn)在于不要求被優(yōu)化函數(shù)具有可微、可導(dǎo)、連續(xù)等性質(zhì)，收斂速度較快，算法簡(jiǎn)單，容易編程實(shí)現(xiàn)。 該算法也存在很明顯的缺點(diǎn)： 1.對(duì)于有多個(gè)局部極值點(diǎn)的函數(shù)，容易陷入到局部極值點(diǎn)中，得不到正確的結(jié)果； 2.PSO算法并沒(méi)有很充分地利用計(jì)算過(guò)程中獲得的信息 ，因此，往往不能得到精確的結(jié)