粒子群算法課件

1、Particle Swarm Optimization(PSO),粒子群算法,Department of Industrial Engineering and Management,算法起源,粒子群算法源于復(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)生（小鳥的出生）；分化和多樣性的出現(xiàn)（鳥群中的鳥分成許多小的群）；新的主

2、題的出現(xiàn)（鳥尋找食物過程中，不斷發(fā)現(xiàn)新的食物）。,CAS系統(tǒng)中的主體具有4個(gè)基本特點(diǎn),首先，主體是主動(dòng)的、活動(dòng)的。 主體與環(huán)境及其他主體是相互影響、相互作用的，這種影響是系統(tǒng)發(fā)展變化的主要?jiǎng)恿Α?環(huán)境的影響是宏觀的，主體之間的影響是微觀的，宏觀與微觀要有機(jī)結(jié)合。 最后，整個(gè)系統(tǒng)可能還要受一些隨機(jī)因素的影響。,簡介,起源 生物社會(huì)學(xué)家對鳥群尋找食物行為的研究 原理 我們可以設(shè)想這樣的一個(gè)場景，一群鳥再隨機(jī)搜尋食物。這個(gè)區(qū)域里只有一塊食物。所有的鳥都不知道食物再哪里，但他們知道目前距離食物還有多遠(yuǎn)，那么找到食物的最佳策略是什么？最簡單的方法就是找尋距離食物最近的鳥之周圍區(qū)域及根據(jù)自己本身飛行的經(jīng)驗(yàn)

3、判斷食物的所在。,鳥群的覓食行為,Food,Global Best Solution,Past Best Solution,PSO算法,PSO算法就從這種生物種群行為特性中得到啟發(fā)并用于求解優(yōu)化問題。在PSO中，每個(gè)優(yōu)化問題的潛在解都可以想象成d維搜索空間上的一個(gè)點(diǎn)，我們稱之為“粒子”（Particle），所有的粒子都有一個(gè)被目標(biāo)函數(shù)決定的適應(yīng)值(Fitness Value )，每個(gè)粒子還有一個(gè)速度決定他們飛翔的方向和距離，然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索。Reynolds對鳥群飛行的研究發(fā)現(xiàn)。鳥僅僅是追蹤它有限數(shù)量的鄰居但最終的整體結(jié)果是整個(gè)鳥群好像在一個(gè)中心的控制之下.即復(fù)雜的

4、全局行為是由簡單規(guī)則的相互作用引起的。,特點(diǎn),分布式搜尋 具記憶性 組件較少，容易實(shí)現(xiàn) 適合在連續(xù)性的范圍內(nèi)搜尋,具體描述,PSO算法就是模擬一群鳥尋找食物的過程，每個(gè)鳥就是PSO中的粒子，也就是我們需要求解問題的可能解，這些鳥在尋找食物的過程中，不停改變自己在空中飛行的位置與速度。大家也可以觀察一下，鳥群在尋找食物的過程中，開始鳥群比較分散，逐漸這些鳥就會(huì)聚成一群，這個(gè)群忽高忽低、忽左忽右，直到最后找到食物。這個(gè)過程我們轉(zhuǎn)化為一個(gè)數(shù)學(xué)問題。尋找函數(shù) y=1-cos(3*x)*exp(-x)的在0,4最大值。該函數(shù)的圖形如下：,y=1-cos(3*x)*exp(-x),當(dāng)x=0.9350-0.

5、9450，達(dá)到最大值y=1.3706。為了得到該函數(shù)的最大值，我們在0，4之間隨機(jī)的灑一些點(diǎn)，為了演示，我們放置兩個(gè)點(diǎn)，并且計(jì)算這兩個(gè)點(diǎn)的函數(shù)值，同時(shí)給這兩個(gè)點(diǎn)設(shè)置在0，4之間的一個(gè)速度。下面這些點(diǎn)就會(huì)按照一定的公式更改自己的位置，到達(dá)新位置后，再計(jì)算這兩個(gè)點(diǎn)的值，然后再按照一定的公式更新自己的位置。直到最后在y=1.3706這個(gè)點(diǎn)停止自己的更新。,與粒子群算法對照,這兩個(gè)點(diǎn)就是粒子群算法中的粒子。 該函數(shù)的最大值就是鳥群中的食物 計(jì)算兩個(gè)點(diǎn)函數(shù)值就是粒子群算法中的適應(yīng)值，計(jì)算用的函數(shù)就是粒子群算法中的適應(yīng)度函數(shù)。 更新自己位置的一定公式就是粒子群算法中的位置速度更新公式。,第一次初始化,第一

6、次更新位置,第二次更新位置,第21次更新,最后的結(jié)果（30次迭代）,算法介紹,每個(gè)尋優(yōu)的問題解都被想象成一只鳥，我們也稱為“Particle”粒子。 所有的Particle 都有一個(gè)fitness function 以判斷目前的位置之好壞。 每一個(gè)Particle必須賦予記憶性，能記得所搜尋到最佳位置。 每一個(gè)Particle 還有一個(gè)速度以決定飛行的距離與方向。,算法流程,Initial： 將群族做初始化，以隨機(jī)的方式求出每一Particle 之初始位置與速度。 Evaluation： 依據(jù)fitness function 計(jì)算出其fitness value 以作為判斷每一Particle之

7、好壞。 Fine the Pbest： 找出每一Particle 到目前為止的搜尋過程中最佳解，這個(gè)最佳解我們將之稱為Pbest。 Fine the Gbest： 找出所有Particle 到目前為止所搜尋到的整體最佳解，此最佳解我們稱之為Gbest。 Update the Velocity： 依據(jù)式(1) 與式(2) 更新每一Particle之速度與位置。 回到步驟2. 繼續(xù)執(zhí)行，直到獲得一個(gè)令人滿意的結(jié)果或符合終止條件為止。,1. Initial,將群族做初始化，以隨機(jī)的方式求出每一Particle 之初始位置與速度，這些隨機(jī)的Particle限定在規(guī)定的范圍內(nèi)。,2. 速度更新函數(shù),Vi

8、d：每一Particle在第d維之速度 i：Particle之編號 d：維度 w：Inertia Weight c1、c2：學(xué)習(xí)常數(shù) Rand()：一介于0至1的隨機(jī)數(shù) Pid：每一Particle到目前為止，所出現(xiàn)的最佳位置 Pgd：所有Particle到目前為止，所出現(xiàn)的最佳位置 xid：每一Particle目前之所在,3.更新位置,粒子群內(nèi)的每一個(gè)粒子點(diǎn)更新如下公式 更新之后的點(diǎn)也必須限定在規(guī)定范圍內(nèi),4.記憶更新,在符合限制下，更新PidPgd Pidpi IF f(p i) Pid Pgd pi IF f(p i) Pgd f (x) 是一個(gè)目標(biāo)函數(shù)受限于最大化,5.終止條件,重復(fù)步

9、驟到直到達(dá)到中止條件 最后會(huì)得到Pgd而f(Pgd) 就是解的結(jié)果,參數(shù)設(shè)定,c1、c2：學(xué)習(xí)常數(shù)一般設(shè)定為 c1 = c2 = 2 不過在文獻(xiàn)中也有其它的取值，一般設(shè)定c1 = c2 值介于04之間 粒子數(shù)：一般取 20 40個(gè)，大部分的問題用10 20個(gè)粒子就能取的不錯(cuò)的結(jié)果。 Vmax ：最大速度，決定粒子再一個(gè)循環(huán)中最大的移動(dòng)距離 例如: 問題fitness function : f(x)= x12+x22+x32 其中限制式為 -10= x1, x2, x3 = 10 則Vmax 的大小就是10-(-10) = 20,粒子群算法分類,標(biāo)準(zhǔn)粒子群算法的變形 在這個(gè)分支中，主要是對標(biāo)準(zhǔn)粒

10、子群算法的慣性因子、收斂因子（約束因子）、“認(rèn)知”部分的c1，“社會(huì)”部分的c2進(jìn)行變化與調(diào)節(jié)，希望獲得好的效果。,慣性因子的原始版本是保持不變的，后來有人提出隨著算法迭代的進(jìn)行，慣性因子需要逐漸減小的思想。算法開始階段，大的慣性因子可以是算法不容易陷入局部最優(yōu)，到算法的后期，小的慣性因子可以使收斂速度加快，使收斂更加平穩(wěn)，不至于出現(xiàn)振蕩現(xiàn)象。,動(dòng)態(tài)的減小慣性因子w，的確可以使算法更加穩(wěn)定，效果比較好。但是遞減慣性因子采用什么樣的方法呢？人們首先想到的是線型遞減，這種策略的確很好，但是是不是最優(yōu)的呢？于是有人對遞減的策略作了研究，研究結(jié)果指出：線型函數(shù)的遞減優(yōu)于凸函數(shù)的遞減策略，但是凹函數(shù)的遞

11、減策略又優(yōu)于線型的遞減。,對于收斂因子，經(jīng)過證明如果收斂因子取0.729,可以確保算法的收斂，但是不能保證算法收斂到全局最優(yōu)。對于社會(huì)與認(rèn)知的系數(shù)c2,c1也有人提出：c1先大后小，而c2先小后大的思想，因?yàn)樵谒惴ㄟ\(yùn)行初期，每個(gè)鳥要有大的自己的認(rèn)知部分而又比較小的社會(huì)部分，這個(gè)與我們自己一群人找東西的情形比較接近，因?yàn)樵谖覀冋覗|西的初期，我們基本依靠自己的知識(shí)取尋找，而后來，我們積累的經(jīng)驗(yàn)越來越豐富，于是大家開始逐漸達(dá)成共識(shí)（社會(huì)知識(shí)），這樣我們就開始依靠社會(huì)知識(shí)來尋找東西了。,2007年希臘的兩位學(xué)者提出將收斂速度比較快的全局版本的粒子群算法與不容易陷入局部最優(yōu)的局部版本的粒子群算法相結(jié)合的

12、辦法，利用的公式是 vn*v(全局版本)（1n）*v(局部版本) 速度更新公式，v代表速度 w（k1）w(k)v 位置更新公式 該算法在文獻(xiàn)中討論了系數(shù)n取各種不同情況的情況，并且運(yùn)行來了20000次來分析各種系數(shù)的結(jié)果。,（2）粒子群算法的混合,這個(gè)分支主要是將粒子群算法與各種算法相混合，有人將它與模擬退火算法相混合，有些人將它與單純形方法相混合。但是最多的是將它與遺傳算法的混合。根據(jù)遺傳算法的三種不同算子可以生成3中不同的混合算法。,粒子群算法與選擇算子的結(jié)合，這里相混合的思想是：在原來的粒子群算法中，我們選擇粒子群群體的最優(yōu)值作為pg，但是相結(jié)合的版本是根據(jù)所有粒子的適應(yīng)度的大小給每個(gè)粒

13、子賦予一個(gè)被選中的概率，然后依據(jù)概率對這些粒子進(jìn)行選擇，被選中的粒子作為pg，其它的情況都不變。這樣的算法可以在算法運(yùn)行過程中保持粒子群的多樣性，但是致命的缺點(diǎn)是收斂速度緩慢。,粒子群算法與雜交算子的結(jié)合，結(jié)合的思想與遺傳算法的基本一樣，在算法運(yùn)行過程中根據(jù)適應(yīng)度的大小，粒子之間可以兩兩雜交，比如用一個(gè)很簡單的公式 ： w（新）nw1（1n）w2； w1與w2就是這個(gè)新粒子的父輩粒子。這種算法可以在算法的運(yùn)行過程中引入新的粒子，但是算法一旦陷入局部最優(yōu)，那么粒子群算法將很難擺脫局部最優(yōu)。,粒子群算法與變異算子的結(jié)合，結(jié)合的思想：測試所有粒子與當(dāng)前最優(yōu)的距離，當(dāng)距離小于一定的數(shù)值的時(shí)候，可以拿出

14、所有粒子的一個(gè)百分比（如10）的粒子進(jìn)行隨機(jī)初始化，讓這些粒子重新尋找最優(yōu)值。,（3）二進(jìn)制粒子群算法,最初的PSO是從解決連續(xù)優(yōu)化問題發(fā)展起來的.Eberhart等又提出了PSO的離散二進(jìn)制版.用來解決工程實(shí)際中的組合優(yōu)化問題。他們在提出的模型中將粒子的每一維及粒子本身的歷史最優(yōu)、全局最優(yōu)限制為1或0，而速度不作這種限制。用速度更新位置時(shí)，設(shè)定一個(gè)閾值，當(dāng)速度高于該閾值時(shí)，粒子的位置取1，否則取0。二進(jìn)制PSO與遺傳算法在形式上很相似，但實(shí)驗(yàn)結(jié)果顯示，在大多數(shù)測試函數(shù)中，二進(jìn)制PSO比遺傳算法速度快，尤其在問題的維數(shù)增加時(shí),（4）協(xié)同粒子群算法,協(xié)同PSO，該方法將粒子的D維分到D個(gè)粒子群中，每個(gè)粒子群優(yōu)化一維向量，評價(jià)適應(yīng)度時(shí)將這些分量合并為一個(gè)完整的向量。例如第i個(gè)粒子群，除第i個(gè)分量外，其他D-1個(gè)分量都設(shè)為最優(yōu)值，不斷用第i個(gè)粒子群中的粒子替換第i個(gè)分量，直到得到第i維的最優(yōu)值，其他維相同。為將有聯(lián)系的分量劃分在一個(gè)群，可將D維向量分配到m個(gè)粒子群優(yōu)化，則前D mod m個(gè)粒子群的維數(shù)是D/m的向上取整。后m(D mod m)個(gè)粒子群的維數(shù)是D/m的向下取整。協(xié)同PSO在某些問題上有更快的收斂速度，但該算法容易被欺騙。,結(jié)論,簡單的概念 容易實(shí)做 運(yùn)算效能佳 未來可發(fā)展: 模糊粒子群 平行粒子群 排程方面的應(yīng)用