(已合并粒子群算法（1）（2）（3）于此)
1. 粒子群算法簡介
粒子群算法（Particle Swarm Optimization,PSO）是一種模仿鳥群、魚群覓食行為發(fā)展起來的一種進化算法。其概念簡單易于編程實現(xiàn)且運行效率高婉弹、參數(shù)相對較少焰络，應(yīng)用非常廣泛胧后。粒子群算法于1995年提出尊沸，距今（2019）已有24年歷史俊犯。
粒子群算法中每一個粒子的位置代表了待求問題的一個候選解妇多。每一個粒子的位置在空間內(nèi)的好壞由該粒子的位置在待求問題中的適應(yīng)度值決定。每一個粒子在下一代的位置有其在這一代的位置與其自身的速度矢量決定燕侠，其速度決定了粒子每次飛行的方向和距離者祖。在飛行過程中，粒子會記錄下自己所到過的最優(yōu)位置 Ｐ绢彤，群體也會更新群體所到過的最優(yōu)位置Ｇ 咸包。粒子的飛行速度則由其當(dāng)前位置、粒子自身所到過的最優(yōu)位置杖虾、群體所到過的最優(yōu)位置以及粒子此時的速度共同決定烂瘫。
2. 算法流程
上面介紹了粒子群算法來歷，過程。沒有了解過的小伙伴肯定是一臉萌容坟比。不過這已經(jīng)是優(yōu)化算法中最簡單芦鳍、最沒有心機的算法了，也是入門優(yōu)化算法的不二選擇葛账。
好了柠衅，正篇開始。這是一個根據(jù)鳥群覓食行為衍生出的算法〖眨現(xiàn)在菲宴，我們的主角是一群鳥。
小鳥們的目標很簡單趋急，要在這一帶找到食物最充足的位置安家喝峦、休養(yǎng)生息。它們在這個地方的搜索策略如下：
1． 每只鳥隨機找一個地方呜达，評估這個地方的食物量谣蠢。
2． 所有的鳥一起開會，選出食物量最多的地方作為安家的候選點G查近。
3． 每只鳥回顧自己的旅程眉踱，記住自己曾經(jīng)去過的食物量最多的地方P。
4． 每只鳥為了找到食物量更多的地方霜威，于是向著G飛行谈喳，但是呢，不知是出于選擇困難癥還是對P的留戀戈泼，或者是對G的不信任叁执，小鳥向G飛行時，時不時也向P飛行矮冬，其實它自己也不知道到底是向G飛行的多還是向P飛行的多。
5． 又到了開會的時間次哈，如果小鳥們決定停止尋找胎署，那么它們會選擇當(dāng)前的G來安家；否則繼續(xù)2->3->4->5來尋找它們的棲息地窑滞。
上圖描述的策略4的情況琼牧，一只鳥在點A處，點G是鳥群們找到過的食物最多的位置哀卫，點P是它自己去過的食物最多的地點巨坊。V是它現(xiàn)在的飛行速度（速度是矢量，有方向和大写烁摹）趾撵，現(xiàn)在它決定向著P和G飛行，但是這是一只佛系鳥，具體飛多少隨緣占调。如果沒有速度V暂题，它應(yīng)該飛到B點，有了速度V的影響究珊，它的合速度最終使它飛到了點C薪者，這里是它的下一個目的地。如果C比P好那么C就成了下一次的P剿涮，如果C比G好言津，那么就成了下一次的G。
具體的飛行過程如下圖所示：
算法的流程如下：
3.粒子群算法模型
介紹完了粒子群算法的流程,再來詳細介紹一下粒子群算法的模型取试。
鳥群有三個決定其搜索結(jié)果的參數(shù)
C1:自我學(xué)習(xí)因子
C2:全局學(xué)習(xí)因子
W:慣性系數(shù)
maxV:最大速率悬槽。
對于每只鳥，有兩個屬性：
位置：想括。
速度：陷谱。
其中t表示第t次迭代（第t次開會）,i表是這只鳥的序號是i，D表示搜索空間的維度瑟蜈，對于鳥群來說D=2（在平面內(nèi)搜尋）烟逊。
其速度更新公式如下：
表示均勻分布在（0,1）內(nèi)的隨機數(shù)。
位置更新公式如下：
4.實驗初步
上面都是些什么鬼铺根，完全看不懂……宪躯，很正常，下面我們來個例子看看上面那些都是什么東西位迂。
C1：自我學(xué)習(xí)因子访雪，就是一只鳥飛向自己到過的最優(yōu)位置的權(quán)重，可以理解為C1越大掂林，該鳥飛向自己到過的最優(yōu)位置的意愿越強烈臣缀。
C2：全局學(xué)習(xí)因子，也叫社會學(xué)習(xí)因子泻帮，即一只鳥飛向群體到過的最優(yōu)位置的權(quán)重精置， C2越大，該鳥飛向群體到過的最優(yōu)位置的意愿越強烈锣杂。
如上圖脂倦，假設(shè)隨機變量r1=r2=1，如果該鳥當(dāng)前速度V=0,C1=C2=1時元莫，,則該鳥的速度為A->B,它將飛到B點赖阻，若C1=0,C2=1,則該鳥將飛到G點，若C1=1,C2=0,則鳥將飛到P點踱蠢。
一般火欧，取C1=C2=2,由于r1和r2為（0-1）的隨機數(shù)，在速度V=0的情況下，該鳥可能從點A飛到平行四邊形ADEC內(nèi)的任一位置布隔，其中AG=GD,AP=PC离陶。點B為該鳥飛向的期望位置。
W為慣性系數(shù)衅檀，即鳥在下一次飛行時將會以上一次的速度為基礎(chǔ)招刨，根據(jù)自己的意愿的出最終的速度。
舉個簡單的例子哀军，搜索平面內(nèi)距點M最近的點沉眶。這是一個二維的問題，假設(shè)M的坐標為（a,b）杉适，我們可以該問題轉(zhuǎn)化為求使
實驗開始了
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 鳥的數(shù)量(種群數(shù)) | 20 |
| 開會次數(shù)(最大迭代次數(shù)) | 50 |
| C1 | 2 |
| C2 | 2 |
| W | 1 |
| maxV | 5 |
| 取值范圍 | （-100猿推，100） |
為了方便求解我們設(shè)M點為原點片习，即a=b=0。
此時問題為在上圖的區(qū)域內(nèi)尋找距原點最近的點的坐標蹬叭。我們看一下粒子群算法的尋找過程藕咏。
可以發(fā)現(xiàn)所有的小鳥都向著我們的目標點不斷的靠近。它們最終收斂在了一個很小的范圍內(nèi)秽五。我們所得到的最終的結(jié)果是（0.01559301434688孽查，-0.113289020661651），該點距原點距離為的平方為0.014876507坦喘，雖然很近了盲再，但這可不是一個較好的結(jié)果。
雖然小鳥們已經(jīng)聚集在了最優(yōu)點附近的小范圍內(nèi)瓣铣，但卻沒有進一步向原點靠近答朋。這是為什么呢，下一節(jié)我們一起來研究一下棠笑。
5.參數(shù)實驗
上一節(jié)中梦碗，我們看到小鳥們聚集到一個較小的范圍內(nèi)后，不會再繼續(xù)集中腐晾。這是怎么回事呢？
猜測：
1.與最大速度限制有關(guān)丐一，權(quán)重w只是方便動態(tài)修改maxV藻糖。
2.與C1和C2有關(guān)，這兩個權(quán)重限制了鳥兒的搜索行為库车。
還是上一節(jié)的實驗巨柒，。現(xiàn)在我們將maxV的值有5修改為50，即maxV=50洋满，其他參數(shù)不變晶乔。參數(shù)如下
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 鳥的數(shù)量(種群數(shù)) | 20 |
| 開會次數(shù)(最大迭代次數(shù)) | 50 |
| C1 | 2 |
| C2 | 2 |
| W | 1 |
| maxV | 50 |
| 取值范圍 | （-100，100） |
此時得到的最優(yōu)位值的適應(yīng)度函數(shù)值為0.25571,可以看出與maxV=5相比牺勾，結(jié)果差了很多而且小鳥們聚集的范圍更大了正罢。
現(xiàn)在我們設(shè)置maxV=1，再次重復(fù)上面的實驗驻民，實驗結(jié)果如下：
這次最終的適應(yīng)度函數(shù)值為翻具，比之前的結(jié)果都要好0.00273。從圖中我們可以看出回还，小鳥們在向一個點集中裆泳，但是他們飛行的速度比之前慢多了，如果問題更復(fù)雜柠硕，可能無法等到它們聚集到一個點工禾，迭代就結(jié)束了。
為什么maxV會影響鳥群的搜索結(jié)果呢蝗柔？
我們依然以maxV=50為例闻葵，不過這次為了看的更加清晰，我們的鳥群只有2只鳥诫咱，同時將幀數(shù)放慢5倍以便觀察笙隙。
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 鳥的數(shù)量(種群數(shù)) | 2 |
| 開會次數(shù)(最大迭代次數(shù)) | 50 |
| C1 | 2 |
| C2 | 2 |
| W | 1 |
| maxV | 50 |
| 取值范圍 | （-100，100） |
可以看出若當(dāng)前的慣性速度V較大時坎缭，且P竟痰、G相距較近時（考慮極端情況P與G重合在一個點），我們來看看小鳥的飛行軌跡掏呼。
小鳥從A點出發(fā)坏快，速度為A->B,這一次飛行過后，小鳥的期望位置為點D憎夷，將此次飛行記為第一次飛行莽鸿。其中AG=GC,由于P=G,故
第二次飛行，小鳥由點D為起點拾给，此時小鳥的慣性速度為A->D,而它向目標飛行的速度為D->E,其中DG=GE,此次飛行的合速度為D->C,故C為此次飛行的期望點位置祥得。
第三次飛行，小鳥由點C為起點蒋得，此時小鳥的慣性速度為D->C,而它向目標飛行的速度為C->A,其中CG=GA,此次飛行的合速度為C->E,故E為此次飛行的期望點位置级及。
第四次飛行，小鳥由點E為起點额衙，此時小鳥的慣性速度為C->E,而它向目標飛行的速度為E->D其中EG=GD,此次飛行的合速度為E->A,故A為此次飛行的期望點位置饮焦。
可以看出如果G和P重合怕吴，那么小鳥的飛行軌跡的期望為A->D->C->E->A,如果這四個位置均差于全局最優(yōu)點G和自己的歷史最優(yōu)點P,那么小鳥將會一直圍著當(dāng)前最優(yōu)點打轉(zhuǎn)，這樣當(dāng)然無法繼續(xù)聚集在同一個點县踢。
問題找到了转绷，那應(yīng)該如何解決呢？先思考幾種方案硼啤，能不能行的通议经，實驗之后見分曉。
思路一：限制鳥的最大飛行速率,由于慣性系數(shù)W的存在丙曙，使得控制最大速率和控制慣性系數(shù)的效果是等價的爸业，取其一即可。
方案1：使慣性系數(shù)隨著迭代次數(shù)增加而降低亏镰，這里使用的是線性下降的方式扯旷，即在第1次迭代，慣性系數(shù)W=1,最后一次迭代時索抓，慣性系數(shù)W=0钧忽，當(dāng)然，也可以根據(jù)自己的意愿取其他值逼肯。
實驗參數(shù)如下：
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 鳥的數(shù)量(種群數(shù)) | 20 |
| 開會次數(shù)(最大迭代次數(shù)) | 50 |
| C1 | 2 |
| C2 | 2 |
| W | 1->0 |
| maxV | 50 |
| 取值范圍 | （-100耸黑，100） |
小鳥們的飛行過程如上圖，可以看到效果很好篮幢，最后甚至都聚集到了一個點大刊。再看看最終的適應(yīng)度函數(shù)值8.61666413451519E-17，這已經(jīng)是一個相當(dāng)精確的值了三椿，說明這是一個可行的方案缺菌，但是由于其最后種群過于集中，有陷入局部最優(yōu)的風(fēng)險搜锰。
方案2：給每只鳥一個隨機的慣性系數(shù)伴郁，那么鳥的飛行軌跡也將不再像之前會出現(xiàn)周期性。每只鳥的慣性系數(shù)W為（0,2）中的隨機數(shù)（保持W的期望為1）蛋叼。
實驗參數(shù)如下：
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 鳥的數(shù)量(種群數(shù)) | 20 |
| 開會次數(shù)(最大迭代次數(shù)) | 50 |
| C1 | 2 |
| C2 | 2 |
| W | rand(0,2) |
| maxV | 50 |
| 取值范圍 | （-100焊傅，100） |
可以看到小鳥們并沒有像上一個實驗一樣聚集于一個點，而是仍在一個較大的范圍內(nèi)進行搜索狈涮。其最終的適應(yīng)度函數(shù)為0.01176狐胎，比最初的0.25571稍有提升，但并不顯著歌馍。什么原因造成了這種情況呢握巢？我想可能是由于慣性系數(shù)成了期望為1的隨機數(shù)，那么小鳥的飛行軌跡的期望可能仍然是繞著一個四邊形循環(huán)骆姐，只不過這個四邊形相比之前的平行四邊形更加復(fù)雜镜粤，所以其結(jié)果也稍有提升，當(dāng)然對于概率算法玻褪，得到這樣的結(jié)果可能僅僅是因為運氣不好
我們看到慣性系數(shù)W值減小肉渴，小鳥們聚攏到一處的速度明顯提升，那么带射，如果我們?nèi)サ魬T性系數(shù)這個參數(shù)會怎么樣呢同规。
方案3：取出慣性系數(shù)，即取W=0窟社，小鳥們只向著那兩個最優(yōu)位置飛行券勺。
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 鳥的數(shù)量(種群數(shù)) | 20 |
| 開會次數(shù)(最大迭代次數(shù)) | 50 |
| C1 | 2 |
| C2 | 2 |
| W | 0 |
| maxV | 50 |
| 取值范圍 | （-100，100） |
可以看見鳥群們迅速聚集到了一個點灿里，再看看得到的結(jié)果关炼，最終的適應(yīng)度函數(shù)值為2.9086886073362966E-30，明顯優(yōu)于之前的所有操作匣吊。
那么問題來了儒拂，為什么粒子群算法需要一個慣性速度，它的作用是什么呢色鸳？其實很明顯社痛，當(dāng)鳥群迅速集中到了一個點之后它們就喪失了全局的搜索能力，所有的鳥會迅速向著全局最優(yōu)點飛去命雀，如果當(dāng)前的全局最優(yōu)解是一個局部最優(yōu)點蒜哀，那么鳥群將會陷入局部最優(yōu)。所以吏砂，慣性系數(shù)和慣性速度的作用是給鳥群提供跳出局部最優(yōu)的可能性撵儿，獲得這個跳出局部最優(yōu)能力的代價是它們的收斂速度減慢，且局部的搜索能力較弱（與當(dāng)前的慣性速度有關(guān)）赊抖。
為了平衡局部搜索能力和跳出局部最優(yōu)能力统倒，我們可以人為的干預(yù)一下慣性系數(shù)W的大小，結(jié)合方案1和方案2氛雪，我們可以使每只鳥的慣性系數(shù)以一個隨機周期房匆，周期性下降，若小于0报亩，則重置為初始值浴鸿。
這樣結(jié)合了方案1和方案2的慣性系數(shù)，也能得到不錯的效果弦追，大家可以自己一試岳链。
思路二：改變小鳥們向群體最優(yōu)飛行和向歷史最優(yōu)飛行的權(quán)重。
方案4：讓小鳥向全局最優(yōu)飛行的系數(shù)C2線性遞減劲件。
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 鳥的數(shù)量(種群數(shù)) | 20 |
| 開會次數(shù)(最大迭代次數(shù)) | 50 |
| C1 | 2 |
| C2 | 2->0 |
| W | 1 |
| maxV | 50 |
| 取值范圍 | （-100掸哑，100） |
小鳥們的飛行過程與之前好像沒什么變化约急，我甚至懷疑我做了假實驗∶绶郑看看最終結(jié)果厌蔽，0.7267249621552874，這是到目前為止的最差結(jié)果摔癣∨看來這不是一個好方案，讓全局學(xué)習(xí)因子C2遞減择浊，勢必會降低算法的收斂效率戴卜，而慣性系數(shù)還是那么大，小鳥們依然會圍繞歷史最優(yōu)位置打轉(zhuǎn)琢岩，畢竟這兩個最優(yōu)位置是有一定關(guān)聯(lián)的投剥。所以讓C1線性遞減的實驗也不必做了，其效果應(yīng)該與方案4相差不大担孔。
看來只要是慣性系數(shù)不變怎么修改C1和C2都不會有太過明顯的效果薇缅。為什么實驗都是參數(shù)遞減，卻沒有參數(shù)遞增的實驗?zāi)兀?br>
1.慣性系數(shù)W必須遞減攒磨，因為它會影響鳥群的搜索范圍泳桦。
2.如果C1和C2遞增，那么小鳥的慣性速度V勢必會跟著遞增娩缰，這與W遞增會產(chǎn)生相同的效果灸撰。
6.總結(jié)
上面我們通過一些實驗及理論分析了粒子群算法的特點及其參數(shù)的作用。粒子群作為優(yōu)化算法中模型最簡單的算法拼坎，通過修改這幾個簡單的參數(shù)也能夠改變算法的優(yōu)化性能可以說是一個非常優(yōu)秀的算法浮毯。
上述實驗中，我們僅分析了單個參數(shù)對算法的影響泰鸡，實際使用時（創(chuàng)新债蓝、發(fā)明、寫論文時）也會同時動態(tài)改變多個參數(shù)盛龄，甚至是參數(shù)之間產(chǎn)生關(guān)聯(lián)饰迹。
實驗中，為了展現(xiàn)實驗效果余舶，maxV取值較大啊鸭，一般取值為搜索空間范圍的10%-20%，按上面（-100,100）的范圍maxV應(yīng)該取值為20-40匿值，在此基礎(chǔ)上赠制，方案1、方案2效果應(yīng)該會更好挟憔。
粒子群算法是一種概率算法钟些，所以并不能使用一次實驗結(jié)果來判斷算法的性能烟号，我們需要進行多次實驗，然后看看這些實驗的效果最終來判斷政恍，結(jié)果必須使用多次實驗的統(tǒng)計數(shù)據(jù)來說明褥符，一般我們都會重復(fù)實驗30-50次，為了發(fā)論文去做實驗的小伙伴們不要偷懶哦抚垃。
粒子群算法的學(xué)習(xí)目前告一段落，如果有什么新的發(fā)現(xiàn)趟大，后面繼續(xù)更新哦鹤树！
以下指標純屬個人yy,僅供參考
| 指標 | 星數(shù) |
|---|---|
| 復(fù)雜度 | ★☆☆☆☆☆☆☆☆☆ |
| 收斂速度 | ★★★★★☆☆☆☆☆ |
| 全局搜索 | ★★★★☆☆☆☆☆☆ |
| 局部搜索 | ★★★★★★☆☆☆☆ |
| 優(yōu)化性能 | ★★★★★★☆☆☆☆ |
| 跳出局部最優(yōu) | ★★★★☆☆☆☆☆☆ |
| 改進點 | ★★★★☆☆☆☆☆☆ |
參考文獻
[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）
