(已合并粒子群算法（1）（2）（3）于此)
1. 粒子群算法簡(jiǎn)介
粒子群算法（Particle Swarm Optimization,PSO）是一種模仿鳥群、魚群覓食行為發(fā)展起來的一種進(jìn)化算法。其概念簡(jiǎn)單易于編程實(shí)現(xiàn)且運(yùn)行效率高、參數(shù)相對(duì)較少，應(yīng)用非常廣泛。粒子群算法于1995年提出，距今（2019）已有24年歷史。
粒子群算法中每一個(gè)粒子的位置代表了待求問題的一個(gè)候選解。每一個(gè)粒子的位置在空間內(nèi)的好壞由該粒子的位置在待求問題中的適應(yīng)度值決定。每一個(gè)粒子在下一代的位置有其在這一代的位置與其自身的速度矢量決定，其速度決定了粒子每次飛行的方向和距離。在飛行過程中，粒子會(huì)記錄下自己所到過的最優(yōu)位置 Ｐ，群體也會(huì)更新群體所到過的最優(yōu)位置Ｇ 。粒子的飛行速度則由其當(dāng)前位置、粒子自身所到過的最優(yōu)位置、群體所到過的最優(yōu)位置以及粒子此時(shí)的速度共同決定。
2. 算法流程
上面介紹了粒子群算法來歷，過程。沒有了解過的小伙伴肯定是一臉萌容。不過這已經(jīng)是優(yōu)化算法中最簡(jiǎn)單、最沒有心機(jī)的算法了，也是入門優(yōu)化算法的不二選擇。
好了，正篇開始。這是一個(gè)根據(jù)鳥群覓食行為衍生出的算法。現(xiàn)在，我們的主角是一群鳥。
小鳥們的目標(biāo)很簡(jiǎn)單，要在這一帶找到食物最充足的位置安家、休養(yǎng)生息。它們?cè)谶@個(gè)地方的搜索策略如下：
1． 每只鳥隨機(jī)找一個(gè)地方，評(píng)估這個(gè)地方的食物量。
2． 所有的鳥一起開會(huì)，選出食物量最多的地方作為安家的候選點(diǎn)G。
3． 每只鳥回顧自己的旅程，記住自己曾經(jīng)去過的食物量最多的地方P。
4． 每只鳥為了找到食物量更多的地方，于是向著G飛行，但是呢，不知是出于選擇困難癥還是對(duì)P的留戀，或者是對(duì)G的不信任，小鳥向G飛行時(shí)，時(shí)不時(shí)也向P飛行，其實(shí)它自己也不知道到底是向G飛行的多還是向P飛行的多。
5． 又到了開會(huì)的時(shí)間，如果小鳥們決定停止尋找，那么它們會(huì)選擇當(dāng)前的G來安家；否則繼續(xù)2->3->4->5來尋找它們的棲息地。
上圖描述的策略4的情況，一只鳥在點(diǎn)A處，點(diǎn)G是鳥群們找到過的食物最多的位置，點(diǎn)P是它自己去過的食物最多的地點(diǎn)。V是它現(xiàn)在的飛行速度（速度是矢量，有方向和大?。?，現(xiàn)在它決定向著P和G飛行，但是這是一只佛系鳥，具體飛多少隨緣。如果沒有速度V，它應(yīng)該飛到B點(diǎn)，有了速度V的影響，它的合速度最終使它飛到了點(diǎn)C，這里是它的下一個(gè)目的地。如果C比P好那么C就成了下一次的P，如果C比G好，那么就成了下一次的G。
具體的飛行過程如下圖所示：
算法的流程如下：
3.粒子群算法模型
介紹完了粒子群算法的流程,再來詳細(xì)介紹一下粒子群算法的模型。
鳥群有三個(gè)決定其搜索結(jié)果的參數(shù)
C1:自我學(xué)習(xí)因子
C2:全局學(xué)習(xí)因子
W:慣性系數(shù)
maxV:最大速率。
對(duì)于每只鳥，有兩個(gè)屬性：
位置：。
速度：。
其中t表示第t次迭代（第t次開會(huì)）,i表是這只鳥的序號(hào)是i，D表示搜索空間的維度，對(duì)于鳥群來說D=2（在平面內(nèi)搜尋）。
其速度更新公式如下：
表示均勻分布在（0,1）內(nèi)的隨機(jī)數(shù)。
位置更新公式如下：
4.實(shí)驗(yàn)初步
上面都是些什么鬼，完全看不懂……，很正常，下面我們來個(gè)例子看看上面那些都是什么東西。
C1：自我學(xué)習(xí)因子，就是一只鳥飛向自己到過的最優(yōu)位置的權(quán)重，可以理解為C1越大，該鳥飛向自己到過的最優(yōu)位置的意愿越強(qiáng)烈。
C2：全局學(xué)習(xí)因子，也叫社會(huì)學(xué)習(xí)因子，即一只鳥飛向群體到過的最優(yōu)位置的權(quán)重， C2越大，該鳥飛向群體到過的最優(yōu)位置的意愿越強(qiáng)烈。
如上圖，假設(shè)隨機(jī)變量r1=r2=1，如果該鳥當(dāng)前速度V=0,C1=C2=1時(shí)，,則該鳥的速度為A->B,它將飛到B點(diǎn)，若C1=0,C2=1,則該鳥將飛到G點(diǎn)，若C1=1,C2=0,則鳥將飛到P點(diǎn)。
一般，取C1=C2=2,由于r1和r2為（0-1）的隨機(jī)數(shù)，在速度V=0的情況下，該鳥可能從點(diǎn)A飛到平行四邊形ADEC內(nèi)的任一位置，其中AG=GD,AP=PC。點(diǎn)B為該鳥飛向的期望位置。
W為慣性系數(shù)，即鳥在下一次飛行時(shí)將會(huì)以上一次的速度為基礎(chǔ)，根據(jù)自己的意愿的出最終的速度。
舉個(gè)簡(jiǎn)單的例子，搜索平面內(nèi)距點(diǎn)M最近的點(diǎn)。這是一個(gè)二維的問題，假設(shè)M的坐標(biāo)為（a,b），我們可以該問題轉(zhuǎn)化為求使
實(shí)驗(yàn)開始了
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 鳥的數(shù)量(種群數(shù)) | 20 |
| 開會(huì)次數(shù)(最大迭代次數(shù)) | 50 |
| C1 | 2 |
| C2 | 2 |
| W | 1 |
| maxV | 5 |
| 取值范圍 | （-100，100） |
為了方便求解我們?cè)O(shè)M點(diǎn)為原點(diǎn)，即a=b=0。
此時(shí)問題為在上圖的區(qū)域內(nèi)尋找距原點(diǎn)最近的點(diǎn)的坐標(biāo)。我們看一下粒子群算法的尋找過程。
可以發(fā)現(xiàn)所有的小鳥都向著我們的目標(biāo)點(diǎn)不斷的靠近。它們最終收斂在了一個(gè)很小的范圍內(nèi)。我們所得到的最終的結(jié)果是（0.01559301434688，-0.113289020661651），該點(diǎn)距原點(diǎn)距離為的平方為0.014876507，雖然很近了，但這可不是一個(gè)較好的結(jié)果。
雖然小鳥們已經(jīng)聚集在了最優(yōu)點(diǎn)附近的小范圍內(nèi)，但卻沒有進(jìn)一步向原點(diǎn)靠近。這是為什么呢，下一節(jié)我們一起來研究一下。
5.參數(shù)實(shí)驗(yàn)
上一節(jié)中，我們看到小鳥們聚集到一個(gè)較小的范圍內(nèi)后，不會(huì)再繼續(xù)集中。這是怎么回事呢？
猜測(cè)：
1.與最大速度限制有關(guān)，權(quán)重w只是方便動(dòng)態(tài)修改maxV。
2.與C1和C2有關(guān)，這兩個(gè)權(quán)重限制了鳥兒的搜索行為。
還是上一節(jié)的實(shí)驗(yàn)，?，F(xiàn)在我們將maxV的值有5修改為50，即maxV=50，其他參數(shù)不變。參數(shù)如下
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 鳥的數(shù)量(種群數(shù)) | 20 |
| 開會(huì)次數(shù)(最大迭代次數(shù)) | 50 |
| C1 | 2 |
| C2 | 2 |
| W | 1 |
| maxV | 50 |
| 取值范圍 | （-100，100） |
此時(shí)得到的最優(yōu)位值的適應(yīng)度函數(shù)值為0.25571,可以看出與maxV=5相比，結(jié)果差了很多而且小鳥們聚集的范圍更大了。
現(xiàn)在我們?cè)O(shè)置maxV=1，再次重復(fù)上面的實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如下：
這次最終的適應(yīng)度函數(shù)值為，比之前的結(jié)果都要好0.00273。從圖中我們可以看出，小鳥們?cè)谙蛞粋€(gè)點(diǎn)集中，但是他們飛行的速度比之前慢多了，如果問題更復(fù)雜，可能無法等到它們聚集到一個(gè)點(diǎn)，迭代就結(jié)束了。
為什么maxV會(huì)影響鳥群的搜索結(jié)果呢？
我們依然以maxV=50為例，不過這次為了看的更加清晰，我們的鳥群只有2只鳥，同時(shí)將幀數(shù)放慢5倍以便觀察。
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 鳥的數(shù)量(種群數(shù)) | 2 |
| 開會(huì)次數(shù)(最大迭代次數(shù)) | 50 |
| C1 | 2 |
| C2 | 2 |
| W | 1 |
| maxV | 50 |
| 取值范圍 | （-100，100） |
可以看出若當(dāng)前的慣性速度V較大時(shí)，且P、G相距較近時(shí)（考慮極端情況P與G重合在一個(gè)點(diǎn)），我們來看看小鳥的飛行軌跡。
小鳥從A點(diǎn)出發(fā)，速度為A->B,這一次飛行過后，小鳥的期望位置為點(diǎn)D，將此次飛行記為第一次飛行。其中AG=GC,由于P=G,故
第二次飛行，小鳥由點(diǎn)D為起點(diǎn)，此時(shí)小鳥的慣性速度為A->D,而它向目標(biāo)飛行的速度為D->E,其中DG=GE,此次飛行的合速度為D->C,故C為此次飛行的期望點(diǎn)位置。
第三次飛行，小鳥由點(diǎn)C為起點(diǎn)，此時(shí)小鳥的慣性速度為D->C,而它向目標(biāo)飛行的速度為C->A,其中CG=GA,此次飛行的合速度為C->E,故E為此次飛行的期望點(diǎn)位置。
第四次飛行，小鳥由點(diǎn)E為起點(diǎn)，此時(shí)小鳥的慣性速度為C->E,而它向目標(biāo)飛行的速度為E->D其中EG=GD,此次飛行的合速度為E->A,故A為此次飛行的期望點(diǎn)位置。
可以看出如果G和P重合，那么小鳥的飛行軌跡的期望為A->D->C->E->A,如果這四個(gè)位置均差于全局最優(yōu)點(diǎn)G和自己的歷史最優(yōu)點(diǎn)P,那么小鳥將會(huì)一直圍著當(dāng)前最優(yōu)點(diǎn)打轉(zhuǎn)，這樣當(dāng)然無法繼續(xù)聚集在同一個(gè)點(diǎn)。
問題找到了，那應(yīng)該如何解決呢？先思考幾種方案，能不能行的通，實(shí)驗(yàn)之后見分曉。
思路一：限制鳥的最大飛行速率,由于慣性系數(shù)W的存在，使得控制最大速率和控制慣性系數(shù)的效果是等價(jià)的，取其一即可。
方案1：使慣性系數(shù)隨著迭代次數(shù)增加而降低，這里使用的是線性下降的方式，即在第1次迭代，慣性系數(shù)W=1,最后一次迭代時(shí)，慣性系數(shù)W=0，當(dāng)然，也可以根據(jù)自己的意愿取其他值。
實(shí)驗(yàn)參數(shù)如下：
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 鳥的數(shù)量(種群數(shù)) | 20 |
| 開會(huì)次數(shù)(最大迭代次數(shù)) | 50 |
| C1 | 2 |
| C2 | 2 |
| W | 1->0 |
| maxV | 50 |
| 取值范圍 | （-100，100） |
小鳥們的飛行過程如上圖，可以看到效果很好，最后甚至都聚集到了一個(gè)點(diǎn)。再看看最終的適應(yīng)度函數(shù)值8.61666413451519E-17，這已經(jīng)是一個(gè)相當(dāng)精確的值了，說明這是一個(gè)可行的方案，但是由于其最后種群過于集中，有陷入局部最優(yōu)的風(fēng)險(xiǎn)。
方案2：給每只鳥一個(gè)隨機(jī)的慣性系數(shù)，那么鳥的飛行軌跡也將不再像之前會(huì)出現(xiàn)周期性。每只鳥的慣性系數(shù)W為（0,2）中的隨機(jī)數(shù)（保持W的期望為1）。
實(shí)驗(yàn)參數(shù)如下：
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 鳥的數(shù)量(種群數(shù)) | 20 |
| 開會(huì)次數(shù)(最大迭代次數(shù)) | 50 |
| C1 | 2 |
| C2 | 2 |
| W | rand(0,2) |
| maxV | 50 |
| 取值范圍 | （-100，100） |
可以看到小鳥們并沒有像上一個(gè)實(shí)驗(yàn)一樣聚集于一個(gè)點(diǎn)，而是仍在一個(gè)較大的范圍內(nèi)進(jìn)行搜索。其最終的適應(yīng)度函數(shù)為0.01176，比最初的0.25571稍有提升，但并不顯著。什么原因造成了這種情況呢？我想可能是由于慣性系數(shù)成了期望為1的隨機(jī)數(shù)，那么小鳥的飛行軌跡的期望可能仍然是繞著一個(gè)四邊形循環(huán)，只不過這個(gè)四邊形相比之前的平行四邊形更加復(fù)雜，所以其結(jié)果也稍有提升，當(dāng)然對(duì)于概率算法，得到這樣的結(jié)果可能僅僅是因?yàn)檫\(yùn)氣不好
我們看到慣性系數(shù)W值減小，小鳥們聚攏到一處的速度明顯提升，那么，如果我們?nèi)サ魬T性系數(shù)這個(gè)參數(shù)會(huì)怎么樣呢。
方案3：取出慣性系數(shù)，即取W=0，小鳥們只向著那兩個(gè)最優(yōu)位置飛行。
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 鳥的數(shù)量(種群數(shù)) | 20 |
| 開會(huì)次數(shù)(最大迭代次數(shù)) | 50 |
| C1 | 2 |
| C2 | 2 |
| W | 0 |
| maxV | 50 |
| 取值范圍 | （-100，100） |
可以看見鳥群們迅速聚集到了一個(gè)點(diǎn)，再看看得到的結(jié)果，最終的適應(yīng)度函數(shù)值為2.9086886073362966E-30，明顯優(yōu)于之前的所有操作。
那么問題來了，為什么粒子群算法需要一個(gè)慣性速度，它的作用是什么呢？其實(shí)很明顯，當(dāng)鳥群迅速集中到了一個(gè)點(diǎn)之后它們就喪失了全局的搜索能力，所有的鳥會(huì)迅速向著全局最優(yōu)點(diǎn)飛去，如果當(dāng)前的全局最優(yōu)解是一個(gè)局部最優(yōu)點(diǎn)，那么鳥群將會(huì)陷入局部最優(yōu)。所以，慣性系數(shù)和慣性速度的作用是給鳥群提供跳出局部最優(yōu)的可能性，獲得這個(gè)跳出局部最優(yōu)能力的代價(jià)是它們的收斂速度減慢，且局部的搜索能力較弱（與當(dāng)前的慣性速度有關(guān)）。
為了平衡局部搜索能力和跳出局部最優(yōu)能力，我們可以人為的干預(yù)一下慣性系數(shù)W的大小，結(jié)合方案1和方案2，我們可以使每只鳥的慣性系數(shù)以一個(gè)隨機(jī)周期，周期性下降，若小于0，則重置為初始值。
這樣結(jié)合了方案1和方案2的慣性系數(shù)，也能得到不錯(cuò)的效果，大家可以自己一試。
思路二：改變小鳥們向群體最優(yōu)飛行和向歷史最優(yōu)飛行的權(quán)重。
方案4：讓小鳥向全局最優(yōu)飛行的系數(shù)C2線性遞減。
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 鳥的數(shù)量(種群數(shù)) | 20 |
| 開會(huì)次數(shù)(最大迭代次數(shù)) | 50 |
| C1 | 2 |
| C2 | 2->0 |
| W | 1 |
| maxV | 50 |
| 取值范圍 | （-100，100） |
小鳥們的飛行過程與之前好像沒什么變化，我甚至懷疑我做了假實(shí)驗(yàn)?？纯醋罱K結(jié)果，0.7267249621552874，這是到目前為止的最差結(jié)果。看來這不是一個(gè)好方案，讓全局學(xué)習(xí)因子C2遞減，勢(shì)必會(huì)降低算法的收斂效率，而慣性系數(shù)還是那么大，小鳥們依然會(huì)圍繞歷史最優(yōu)位置打轉(zhuǎn)，畢竟這兩個(gè)最優(yōu)位置是有一定關(guān)聯(lián)的。所以讓C1線性遞減的實(shí)驗(yàn)也不必做了，其效果應(yīng)該與方案4相差不大。
看來只要是慣性系數(shù)不變?cè)趺葱薷腃1和C2都不會(huì)有太過明顯的效果。為什么實(shí)驗(yàn)都是參數(shù)遞減，卻沒有參數(shù)遞增的實(shí)驗(yàn)?zāi)兀?br>
1.慣性系數(shù)W必須遞減，因?yàn)樗鼤?huì)影響鳥群的搜索范圍。
2.如果C1和C2遞增，那么小鳥的慣性速度V勢(shì)必會(huì)跟著遞增，這與W遞增會(huì)產(chǎn)生相同的效果。
6.總結(jié)
上面我們通過一些實(shí)驗(yàn)及理論分析了粒子群算法的特點(diǎn)及其參數(shù)的作用。粒子群作為優(yōu)化算法中模型最簡(jiǎn)單的算法，通過修改這幾個(gè)簡(jiǎn)單的參數(shù)也能夠改變算法的優(yōu)化性能可以說是一個(gè)非常優(yōu)秀的算法。
上述實(shí)驗(yàn)中，我們僅分析了單個(gè)參數(shù)對(duì)算法的影響，實(shí)際使用時(shí)（創(chuàng)新、發(fā)明、寫論文時(shí)）也會(huì)同時(shí)動(dòng)態(tài)改變多個(gè)參數(shù)，甚至是參數(shù)之間產(chǎn)生關(guān)聯(lián)。
實(shí)驗(yàn)中，為了展現(xiàn)實(shí)驗(yàn)效果，maxV取值較大，一般取值為搜索空間范圍的10%-20%，按上面（-100,100）的范圍maxV應(yīng)該取值為20-40，在此基礎(chǔ)上，方案1、方案2效果應(yīng)該會(huì)更好。
粒子群算法是一種概率算法，所以并不能使用一次實(shí)驗(yàn)結(jié)果來判斷算法的性能，我們需要進(jìn)行多次實(shí)驗(yàn)，然后看看這些實(shí)驗(yàn)的效果最終來判斷，結(jié)果必須使用多次實(shí)驗(yàn)的統(tǒng)計(jì)數(shù)據(jù)來說明，一般我們都會(huì)重復(fù)實(shí)驗(yàn)30-50次，為了發(fā)論文去做實(shí)驗(yàn)的小伙伴們不要偷懶哦。
粒子群算法的學(xué)習(xí)目前告一段落，如果有什么新的發(fā)現(xiàn)，后面繼續(xù)更新哦！
以下指標(biāo)純屬個(gè)人yy,僅供參考
| 指標(biāo) | 星數(shù) |
|---|---|
| 復(fù)雜度 | ★☆☆☆☆☆☆☆☆☆ |
| 收斂速度 | ★★★★★☆☆☆☆☆ |
| 全局搜索 | ★★★★☆☆☆☆☆☆ |
| 局部搜索 | ★★★★★★☆☆☆☆ |
| 優(yōu)化性能 | ★★★★★★☆☆☆☆ |
| 跳出局部最優(yōu) | ★★★★☆☆☆☆☆☆ |
| 改進(jìn)點(diǎn) | ★★★★☆☆☆☆☆☆ |
參考文獻(xiàn)
[1]J. Kennedy and R.C. Eberhart. “Particle swarm optimization.” In IEEE international Conference on Neural Networks, volume 4,IEEE Press, 1995, pp. 1942–1948.
目錄
上一篇 優(yōu)化算法筆記（二）優(yōu)化算法的分類
下一篇 優(yōu)化算法筆記（四）粒子群算法（2）
