粒子群優化演算法求解指派問題

A. 粒子群優化演算法

姓名：楊晶晶  學號：21011210420  學院：通信工程學院

【嵌牛導讀】

傳統的多目標優化方法是將多目標問題通過加權求和轉化為單目標問題來處理的,而粒子演算法主要是解決一些多目標優化問題的（例如機械零件的多目標設計優化）,其優點是容易實現,精度高,收斂速度快。

【嵌牛鼻子】粒子群演算法的概念、公式、調參以及與遺傳演算法的比較。

【嵌牛提問】什麼是粒子群演算法？它的計算流程是什麼？與遺傳演算法相比呢？

【嵌牛正文】

1. 概念

        粒子群優化演算法(PSO：Particle swarm optimization) 是一種進化計算技術（evolutionary computation），源於對鳥群捕食的行為研究。

        粒子群優化演算法的基本思想：是通過群體中個體之間的協作和信息共享來尋找最優解。

        PSO的優勢：在於簡單容易實現並且沒有許多參數的調節。目前已被廣泛應用於函數優化、神經網路訓練、模糊系統控制以及其他遺傳演算法的應用領域。

2. 演算法

2.1 問題抽象

        鳥被抽象為沒有質量和體積的微粒(點)，並延伸到N維空間，粒子i在N維空間的位置表示為矢量Xi＝(x1，x2，…，xN)，飛行速度表示為矢量Vi＝(v1，v2，…，vN)。每個粒子都有一個由目標函數決定的適應值(fitness value)，並且知道自己到目前為止發現的最好位置(pbest)和現在的位置Xi。這個可以看作是粒子自己的飛行經驗。除此之外，每個粒子還知道到目前為止整個群體中所有粒子發現的最好位置(gbest)(gbest是pbest中的最好值)，這個可以看作是粒子同伴的經驗。粒子就是通過自己的經驗和同伴中最好的經驗來決定下一步的運動。

2.2 更新規則

      PSO初始化為一群隨機粒子(隨機解)。然後通過迭代找到最優解。在每一次的迭代中，粒子通過跟蹤兩個「極值」(pbest，gbest)來更新自己。在找到這兩個最優值後，粒子通過下面的公式來更新自己的速度和位置。

      公式(1)的第一部分稱為【記憶項】，表示上次速度大小和方向的影響；公式(1)的第二部分稱為【自身認知項】，是從當前點指向粒子自身最好點的一個矢量，表示粒子的動作來源於自己經驗的部分；公式(1)的第三部分稱為【群體認知項】，是一個從當前點指向種群最好點的矢量，反映了粒子間的協同合作和知識共享。粒子就是通過自己的經驗和同伴中最好的經驗來決定下一步的運動。

      以上面兩個公式為基礎，形成了PSO的標准形式。

      公式(2)和 公式(3)被視為標准PSO演算法。

2.3 標准PSO演算法流程

    標准PSO演算法的流程：

    1）初始化一群微粒(群體規模為N)，包括隨機位置和速度；

    2）評價每個微粒的適應度；

    3）對每個微粒，將其適應值與其經過的最好位置pbest作比較，如果較好，則將其作為當前的最好位置pbest；

    4）對每個微粒，將其適應值與其經過的最好位置gbest作比較，如果較好，則將其作為當前的最好位置gbest；

    5）根據公式(2)、(3)調整微粒速度和位置；

    6）未達到結束條件則轉第2）步。

        迭代終止條件根據具體問題一般選為最大迭代次數Gk或(和)微粒群迄今為止搜索到的最優位置滿足預定最小適應閾值。

      公式(2)和(3)中pbest和gbest分別表示微粒群的局部和全局最優位置。

    當C1＝0時，則粒子沒有了認知能力，變為只有社會的模型(social-only)：

被稱為全局PSO演算法。粒子有擴展搜索空間的能力，具有較快的收斂速度，但由於缺少局部搜索，對於復雜問題

比標准PSO 更易陷入局部最優。

    當C2＝0時，則粒子之間沒有社會信息，模型變為只有認知(cognition-only)模型：

      被稱為局部PSO演算法。由於個體之間沒有信息的交流，整個群體相當於多個粒子進行盲目的隨機搜索，收斂速度慢，因而得到最優解的可能性小。

2.4 參數分析

        參數：群體規模N，慣性因子 ，學習因子c1和c2，最大速度Vmax，最大迭代次數Gk。

        群體規模N：一般取20～40，對較難或特定類別的問題可以取到100～200。

        最大速度Vmax：決定當前位置與最好位置之間的區域的解析度(或精度)。如果太快，則粒子有可能越過極小點；如果太慢，則粒子不能在局部極小點之外進行足夠的探索，會陷入到局部極值區域內。這種限制可以達到防止計算溢出、決定問題空間搜索的粒度的目的。

        權重因子：包括慣性因子和學習因子c1和c2。使粒子保持著運動慣性，使其具有擴展搜索空間的趨勢，有能力探索新的區域。c1和c2代表將每個粒子推向pbest和gbest位置的統計加速項的權值。較低的值允許粒子在被拉回之前可以在目標區域外徘徊，較高的值導致粒子突然地沖向或越過目標區域。

        參數設置：

        1)如果令c1＝c2＝0，粒子將一直以當前速度的飛行，直到邊界。很難找到最優解。

        2)如果＝0，則速度只取決於當前位置和歷史最好位置，速度本身沒有記憶性。假設一個粒子處在全局最好位置，它將保持靜止，其他粒子則飛向它的最好位置和全局最好位置的加權中心。粒子將收縮到當前全局最好位置。在加上第一部分後，粒子有擴展搜索空間的趨勢，這也使得的作用表現為針對不同的搜索問題，調整演算法的全局和局部搜索能力的平衡。較大時，具有較強的全局搜索能力；較小時，具有較強的局部搜索能力。

        3)通常設c1＝c2＝2。Suganthan的實驗表明：c1和c2為常數時可以得到較好的解，但不一定必須等於2。Clerc引入收斂因子(constriction factor) K來保證收斂性。

      通常取為4.1,則K＝0.729.實驗表明，與使用慣性權重的PSO演算法相比，使用收斂因子的PSO有更快的收斂速度。其實只要恰當的選取和c1、c2，兩種演算法是一樣的。因此使用收斂因子的PSO可以看作使用慣性權重PSO的特例。

        恰當的選取演算法的參數值可以改善演算法的性能。

3. PSO與其它演算法的比較

3.1 遺傳演算法和PSO的比較

  1)共性：

  (1)都屬於仿生演算法。

  (2)都屬於全局優化方法。

  (3)都屬於隨機搜索演算法。

  (4)都隱含並行性。

  (5)根據個體的適配信息進行搜索，因此不受函數約束條件的限制，如連續性、可導性等。

  (6)對高維復雜問題，往往會遇到早熟收斂和收斂 性能差的缺點，都無法保證收斂到最優點。

    2)差異：   

    (1)PSO有記憶，好的解的知識所有粒子都保 存，而GA（Genetic Algorithm），以前的知識隨著種群的改變被改變。

    (2)PSO中的粒子僅僅通過當前搜索到最優點進行共享信息，所以很大程度上這是一種單共享項信息機制。而GA中，染色體之間相互共享信息，使得整個種群都向最優區域移動。

    (3)GA的編碼技術和遺傳操作比較簡單，而PSO相對於GA，沒有交叉和變異操作，粒子只是通過內部速度進行更新，因此原理更簡單、參數更少、實現更容易。

    (4)應用於人工神經網路(ANN)

    GA可以用來研究NN的三個方面：網路連接權重、網路結構、學習演算法。優勢在於可處理傳統方法不能處理的問題，例如不可導的節點傳遞函數或沒有梯度信息。

    GA缺點:在某些問題上性能不是特別好；網路權重的編碼和遺傳運算元的選擇有時較麻煩。

    已有利用PSO來進行神經網路訓練。研究表明PSO是一種很有潛力的神經網路演算法。速度較快且有較好的結果。且沒有遺傳演算法碰到的問題。

B. 優化演算法筆記（五）粒子群演算法（3）

(已合並本篇內容至粒子群演算法（1）)

上一節中，我們看到小鳥們聚集到一個較小的范圍內後，不會再繼續集中。這是怎麼回事呢？
猜測：
1.與最大速度限制有關，權重w只是方便動態修改maxV。
2.與C1和C2有關，這兩個權重限制了鳥兒的搜索行為。
還是上一節的實驗， 。現在我們將maxV的值有5修改為50，即maxV=50，其他參數不變。參數如下

此時得到的最優位值的適應度函數值為0.25571,可以看出與maxV=5相比，結果差了很多而且小鳥們聚集的范圍更大了。
現在我們設置maxV=1，再次重復上面的實驗，實驗結果如下：

這次最終的適應度函數值為，比之前的結果都要好0.00273。從圖中我們可以看出，小鳥們在向一個點集中，但是他們飛行的速度比之前慢多了，如果問題更復雜，可能無法等到它們聚集到一個點，迭代就結束了。
為什麼maxV會影響鳥群的搜索結果呢？
我們依然以maxV=50為例，不過這次為了看的更加清晰，我們的鳥群只有2隻鳥，同時將幀數放慢5倍以便觀察。

思路一：限制鳥的最大飛行速率,由於慣性系數W的存在，使得控制最大速率和控制慣性系數的效果是等價的，取其一即可。
方案1：使慣性系數隨著迭代次數增加而降低，這里使用的是線性下降的方式，即在第1次迭代，慣性系數W=1,最後一次迭代時，慣性系數W=0，當然，也可以根據自己的意願取其他值。
實驗參數如下：

小鳥們的飛行過程如上圖，可以看到效果很好，最後甚至都聚集到了一個點。再看看最終的適應度函數值8.61666413451519E-17，這已經是一個相當精確的值了，說明這是一個可行的方案，但是由於其最後種群過於集中，有陷入局部最優的風險。
方案2：給每隻鳥一個隨機的慣性系數，那麼鳥的飛行軌跡也將不再像之前會出現周期性。每隻鳥的慣性系數W為（0,2）中的隨機數（保持W的期望為1）。
實驗參數如下：

可以看到小鳥們並沒有像上一個實驗一樣聚集於一個點，而是仍在一個較大的范圍內進行搜索。其最終的適應度函數為0.01176，比最初的0.25571稍有提升，但並不顯著。什麼原因造成了這種情況呢？我想可能是由於慣性系數成了期望為1的隨機數，那麼小鳥的飛行軌跡的期望可能仍然是繞著一個四邊形循環，只不過這個四邊形相比之前的平行四邊形更加復雜，所以其結果也稍有提升，當然對於概率演算法，得到這樣的結果可能僅僅是因為運氣不好
我們看到慣性系數W值減小，小鳥們聚攏到一處的速度明顯提升，那麼，如果我們去掉慣性系數這個參數會怎麼樣呢。
方案3：取出慣性系數，即取W=0，小鳥們只向著那兩個最優位置飛行。

可以看見鳥群們迅速聚集到了一個點，再看看得到的結果，最終的適應度函數值為2.9086886073362966E-30，明顯優於之前的所有操作。
那麼問題來了，為什麼粒子群演算法需要一個慣性速度，它的作用是什麼呢？其實很明顯，當鳥群迅速集中到了一個點之後它們就喪失了全局的搜索能力，所有的鳥會迅速向著全局最優點飛去，如果當前的全局最優解是一個局部最優點，那麼鳥群將會陷入局部最優。所以，慣性系數和慣性速度的作用是給鳥群提供跳出局部最優的可能性，獲得這個跳出局部最優能力的代價是它們的收斂速度減慢，且局部的搜索能力較弱（與當前的慣性速度有關）。
為了平衡局部搜索能力和跳出局部最優能力，我們可以人為的干預一下慣性系數W的大小，結合方案1和方案2，我們可以使每隻鳥的慣性系數以一個隨機周期，周期性下降，若小於0，則重置為初始值。

這樣結合了方案1和方案2的慣性系數，也能得到不錯的效果，大家可以自己一試。

思路二：改變小鳥們向群體最優飛行和向歷史最優飛行的權重。
方案4：讓小鳥向全局最優飛行的系數C2線性遞減。

小鳥們的飛行過程與之前好像沒什麼變化，我甚至懷疑我做了假實驗。看看最終結果，0.7267249621552874，這是到目前為止的最差結果。看來這不是一個好方案，讓全局學習因子C2遞減，勢必會降低演算法的收斂效率，而慣性系數還是那麼大，小鳥們依然會圍繞歷史最優位置打轉，畢竟這兩個最優位置是有一定關聯的。所以讓C1線性遞減的實驗也不必做了，其效果應該與方案4相差不大。
看來只要是慣性系數不變怎麼修改C1和C2都不會有太過明顯的效果。為什麼實驗都是參數遞減，卻沒有參數遞增的實驗呢？
1.慣性系數W必須遞減，因為它會影響鳥群的搜索范圍。
2.如果C1和C2遞增，那麼小鳥的慣性速度V勢必會跟著遞增，這與W遞增會產生相同的效果。

上面我們通過一些實驗及理論分析了粒子群演算法的特點及其參數的作用。粒子群作為優化演算法中模型最簡單的演算法，通過修改這幾個簡單的參數也能夠改變演算法的優化性能可以說是一個非常優秀的演算法。
上述實驗中，我們僅分析了單個參數對演算法的影響，實際使用時（創新、發明、寫論文時）也會同時動態改變多個參數，甚至是參數之間產生關聯。
實驗中，為了展現實驗效果，maxV取值較大，一般取值為搜索空間范圍的10%-20%，按上面（-100,100）的范圍maxV應該取值為20-40，在此基礎上，方案1、方案2效果應該會更好。
粒子群演算法是一種概率演算法，所以並不能使用一次實驗結果來判斷演算法的性能，我們需要進行多次實驗，然後看看這些實驗的效果最終來判斷，結果必須使用多次實驗的統計數據來說明，一般我們都會重復實驗30-50次，為了發論文去做實驗的小夥伴們不要偷懶哦。
粒子群演算法的學習目前告一段落，如果有什麼新的發現，後面繼續更新哦！
以下指標純屬個人yy,僅供參考

目錄
上一篇 優化演算法筆記（四）粒子群演算法（2）
下一篇 優化演算法筆記（六）遺傳演算法

C. 粒子群演算法

粒子群演算法（particle swarm optimization，PSO）是計算智能領域中的一種生物啟發式方法，屬於群體智能優化演算法的一種，常見的群體智能優化演算法主要有如下幾類：

除了上述幾種常見的群體智能演算法以外，還有一些並不是廣泛應用的群體智能演算法，比如螢火蟲演算法、布穀鳥演算法、蝙蝠演算法以及磷蝦群演算法等等。

而其中的粒子群優化演算法（PSO）源於對鳥類捕食行為的研究，鳥類捕食時，找到食物最簡單有限的策略就是搜尋當前距離食物最近的鳥的周圍。

設想這樣一個場景：一群鳥在隨機的搜索食物。在這個區域里只有一塊食物，所有的鳥都不知道食物在哪。但是它們知道自己當前的位置距離食物還有多遠。那麼找到食物的最優策略是什麼？最簡單有效的就是搜尋目前離食物最近的鳥的周圍區域。

Step1:確定一個粒子的運動狀態是利用位置和速度兩個參數描述的，因此初始化的也是這兩個參數；
Step2:每次搜尋的結果（函數值）即為粒子適應度，然後記錄每個粒子的個體歷史最優位置和群體的歷史最優位置；
Step3:個體歷史最優位置和群體的歷史最優位置相當於產生了兩個力，結合粒子本身的慣性共同影響粒子的運動狀態，由此來更新粒子的位置和速度。

位置和速度的初始化即在位置和速度限制內隨機生成一個N x d 的矩陣，而對於速度則不用考慮約束，一般直接在0~1內隨機生成一個50x1的數據矩陣。

此處的位置約束也可以理解為位置限制，而速度限制是保證粒子步長不超限制的，一般設置速度限制為[-1,1]。

粒子群的另一個特點就是記錄每個個體的歷史最優和種群的歷史最優，因此而二者對應的最優位置和最優值也需要初始化。其中每個個體的歷史最優位置可以先初始化為當前位置,而種群的歷史最優位置則可初始化為原點。對於最優值，如果求最大值則初始化為負無窮，相反地初始化為正無窮。

每次搜尋都需要將當前的適應度和最優解同歷史的記錄值進行對比，如果超過歷史最優值，則更新個體和種群的歷史最優位置和最優解。

速度和位置更新是粒子群演算法的核心，其原理表達式和更新方式：

每次更新完速度和位置都需要考慮速度和位置的限制，需要將其限制在規定范圍內，此處僅舉出一個常規方法，即將超約束的數據約束到邊界（當位置或者速度超出初始化限制時，將其拉回靠近的邊界處）。當然，你不用擔心他會停住不動，因為每個粒子還有慣性和其他兩個參數的影響。

粒子群演算法求平方和函數最小值，由於沒有特意指定函數自變數量綱，不進行數據歸一化。

D. 粒子群演算法簡單介紹

粒子群演算法（也稱粒子群優化演算法（particle swarm optimization, PSO）），模擬鳥群隨機搜索食物的行為。粒子群演算法中，每個優化問題的潛在解都是搜穗穗索空間中的一隻鳥，叫做「粒子」。所有的粒子都有一個由被優化的函數決定的適應值（fitness value），每個粒子還有一個速度決定它們「飛行」的方向和距離。

粒子群演算法初始化為一群隨機的粒子（隨機解），然後根據迭代找到最優解。每一次迭代中，粒子通過跟蹤兩個極敏擾值來更新自己：第1個是粒子本身所找到的最優解，這個稱為個體極值；第2個是整個種群目前找到的最優解，這個稱為全局極值。也可以不用整個種群，而是用其中的一部分作為粒子的鄰居猜拿卜，稱為局部極值。

假設在一個D維搜索空間中，有N個粒子組成一個群落，其中第i個粒子表示為一個D維的向量：

第i個粒子的速度表示為：

還要保存每個個體的已經找到的最優解 ，和一個整個群落找到的最優解 。

第i個粒子根據下面的公式更新自己的速度和位置：

其中， 是個體已知最優解， 是種群已知最優解， 為慣性權重， , 為學習因子（或加速常數 acceleration constant)， , 是[0,1]范圍內的隨機數。

式(1)由三部分組成：

E. 粒子群演算法原理

粒子群算悉銀法原理如下：

粒子群優化（Particle Swarm Optimization,PSO)演算法是1995年由美國學者Kennedy等人提出的，該演算法是模擬鳥類覓食等群體智能行為的智能優化演算法。在自然界中，鳥群在覓食的時候，一般存在個體和群體協同的行為。

每個粒子都旦薯會向兩個值學習，一個值是個體的歷史最優值 ;另一個值是群體的歷史最優值（全局最優值） 。粒子會根據這兩個值來調整自身的速度和位置，而每個位置的優劣都是根據適應度值來確定的。適應度函數是優化的目標函數。

F. 什麼是粒子群演算法

粒子群演算法，也稱粒子群優化演算法（Partical Swarm Optimization），縮寫為 PSO， 是近年來發展起來的一種新的進化演算法(（Evolu2tionary Algorithm - EA）。PSO 演算法屬於進化演算法的一種，和遺傳演算法相似，它也是從隨機解出發，通過迭代尋找最優解，它也是通過適應度來評價解的品質，但它比遺傳演算法規則更為簡單，它沒有遺傳演算法的「交叉」(Crossover) 和「變異」(Mutation) 操作，它通過追隨當前搜索到的最優值來尋找全局最優。這種演算法以其實現容易、精度高、收斂快等優點引起了學術界的重視，並且在解決實際問題中展示了其優越性。設想這樣一個場景：一群鳥在隨機搜索食物。在這個區域里只有一塊食物。所有的鳥都不知道食物在那裡。但是他們知道當前的位置離食物還有多遠。那麼找到食物的最優策略是什麼呢。最簡單有效的就是搜尋目前離食物最近的鳥的周圍區域。 PSO從這種模型中得到啟示並用於解決優化問題。PSO中，每個優化問題的解都是搜索空間中的一隻鳥。我們稱之為「粒子」。所有的粒子都有一個由被優化的函數決定的適應值(fitness value)，每個粒子還有一個速度決定他們飛翔的方向和距離。然後粒子們就追隨當前的最優粒子在解空間中搜索。 PSO 初始化為一群隨機粒子(隨機解)。然後通過迭代找到最優解。在每一次迭代中，粒子通過跟蹤兩個"極值"來更新自己。第一個就是粒子本身所找到的最優解，這個解叫做個體極值pBest。另一個極值是整個種群目前找到的最優解，這個極值是全局極值gBest。另外也可以不用整個種群而只是用其中一部分作為粒子的鄰居，那麼在所有鄰居中的極值就是局部極值。 粒子公式 在找到這兩個最優值時，粒子根據如下的公式來更新自己的速度和新的位置： v[] = w * v[] + c1 * rand() * (pbest[] - present[]) + c2 * rand() * (gbest[] - present[]) (a) present[] = persent[] + v[] (b) v[] 是粒子的速度, w是慣性權重,persent[] 是當前粒子的位置. pbest[] and gbest[] 如前定義 rand () 是介於（0， 1）之間的隨機數. c1, c2 是學習因子. 通常 c1 = c2 = 2. 程序的偽代碼如下 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 the best fitness value of all the particles as the gBest ____For each particle ________Calculate particle velocity according equation (a) ________Update particle position according equation (b) ____End While maximum iterations or minimum error criteria is not attained 在每一維粒子的速度都會被限制在一個最大速度Vmax，如果某一維更新後的速度超過用戶設定的Vmax，那麼這一維的速度就被限定為Vmax

G. 粒子群演算法的演算法介紹

如前所述，PSO模擬鳥群的捕食行為。設想這樣一個場景：一群鳥在隨機搜索食物。在這個區域里只有一塊食物。所有的鳥都不知道食物在那裡。但是他們知道當前的位置離食物還有多遠。那麼找到食物的最優策略是什麼呢。最簡單有效的就是搜尋目前離食物最近的鳥的周圍區域。
PSO從這種模型中得到啟示並用於解決優化問題。PSO中，每個優化問題的解都是搜索空間中的一隻鳥。我們稱之為「粒子」。所有的粒子都有一個由被優化的函數決定的適應值(fitness value)，每個粒子還有一個速度決定他們飛翔的方向和距離。然後粒子們就追隨當前的最優粒子在解空間中搜索。
PSO 初始化為一群隨機粒子(隨機解)。然後通過迭代找到最優解。在每一次迭代中，粒子通過跟蹤兩個極值來更新自己。第一個就是粒子本身所找到的最優解，這個解叫做個體極值pBest。另一個極值是整個種群目前找到的最優解，這個極值是全局極值gBest。另外也可以不用整個種群而只是用其中一部分作為粒子的鄰居，那麼在所有鄰居中的極值就是局部極值。 在找到這兩個最優值時，粒子根據如下的公式來更新自己的速度和新的位置：
v[] = w * v[] + c1 * rand() * (pbest[] - present[]) + c2 * rand() * (gbest[] - present[]) (a)
present[] = present[] + v[] (b)
v[] 是粒子的速度, w是慣性權重,present[] 是當前粒子的位置. pbest[] and gbest[] 如前定義 rand () 是介於（0， 1）之間的隨機數. c1, c2 是學習因子. 通常 c1 = c2 = 2.
程序的偽代碼如下
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 the best fitness value of all the particles as the gBest
____For each particle
________Calculate particle velocity according equation (a)
________Update particle position according equation (b)
____End
While maximum iterations or minimum error criteria is not attained
在每一維粒子的速度都會被限制在一個最大速度Vmax，如果某一維更新後的速度超過用戶設定的Vmax，那麼這一維的速度就被限定為Vmax