01 算法起源
粒子群優化算法(PSO)是一種進化計算技術( )，1995 年由 博士和 博士提出，源于對鳥群捕食的行為研究 。該算法最初是受到飛鳥集群活動的規律性啟發，進而利用群體智能建立的一個簡化模型。粒子群算法在對動物集群活動行為觀察基礎上，利用群體中的個體對信息的共享使整個群體的運動在問題求解空間中產生從無序到有序的演化過程，從而獲得最優解。
02 什么是粒子群算法？2.1 官方定義（參照百科）
粒子群算法，也稱粒子群優化算法或鳥群覓食算法（ Swarm ），縮寫為 PSO， 是近年來由J. 和R. C. 等開發的一種新的進化算法( - EA)。PSO 算法屬于進化算法的一種，和模擬退火算法相似，它也是從隨機解出發，通過迭代尋找最優解，它也是通過適應度來評價解的品質，但它比遺傳算法規則更為簡單，它沒有遺傳算法的“交叉”() 和“變異”() 操作，它通過追隨當前搜索到的最優值來尋找全局最優。這種算法以其實現容易、精度高、收斂快等優點引起了學術界的重視，并且在解決實際問題中展示了其優越性。粒子群算法是一種并行算法。
2.2 通俗點描述
如同前面的描述，PSO模擬的是鳥群的捕食行為。設想這樣一個場景：一群鳥在隨機搜索食物。在這個區域里只有一塊食物。所有的鳥都不知道食物在那里。但是他們知道當前的位置離食物還有多遠。那么找到食物的最優策略是什么呢。最簡單有效的就是搜尋目前離食物最近的鳥的周圍區域。
鳥群在整個搜尋的過程中，通過相互傳遞各自的信息，讓其他的鳥知道自己的位置，通過這樣的協作，來判斷自己找到的是不是最優解，同時也將最優解的信息傳遞給整個鳥群，最終，整個鳥群都能聚集在食物源周圍，即找到了最優解。
PSO中，每個優化問題的解都是搜索空間中的一只鳥。我們稱之為“粒子”。所有的粒子都有一個由被優化的函數決定的適應值( value)，每個粒子還有一個速度決定他們飛翔的方向和距離。然后粒子們就追隨當前的最優粒子在解空間中搜索。
PSO 初始化為一群隨機粒子(隨機解)。然后通過迭代找到最優解。在每一次迭代中，粒子通過跟蹤兩個"極值"來更新自己。第一個就是粒子本身所找到的最優解，這個解叫做個體極值pBest。另一個極值是整個種群目前找到的最優解，這個極值是全局極值gBest。另外也可以不用整個種群而只是用其中一部分作為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。
2.3 再再再通俗點的描述
粒子群算法的基本思想是通過群體中個體之間的協作和信息共享來尋找最優解。如上的情景。試著想一下一群鳥在尋找食物，在這個區域中只有一只蟲子，所有的鳥都不知道食物在哪。但是它們知道自己的當前位置距離食物有多遠，同時它們知道離食物最近的鳥的位置。想一下這時候會發生什么？
同時各只鳥在位置不停變化時候離食物的距離也不斷變化，所以每個鳥一定有過離食物最近的位置，這也是它們的一個參考。
所以，粒子群算法就是把鳥看成一個個粒子，并且他們擁有位置和速度這兩個屬性，然后根據自身已經找到的離食物最近的解和參考整個共享于整個集群中找到的最近的解去改變自己的飛行方向，最后我們會發現，整個集群大致向同一個地方聚集。而這個地方是離食物最近的區域，條件好的話就會找到食物。
03 粒子抽象3.1 關于速度和位置
粒子群算法通過設計一種無質量的粒子來模擬鳥群中的鳥，粒子僅具有兩個屬性：速度和位置，速度代表移動的快慢，位置代表移動的方向。
鳥被抽象為沒有質量和體積的微粒(點)，并延伸到N維空間，粒子i在N維空間的位置表示為矢量Xi＝(x1粒子群算法的基本流程，x2，…，xN)，飛行速度表示為矢量Vi＝(v1，v2，…，vN)。每個粒子都有一個由目標函數決定的適應值( value)，并且知道自己到目前為止發現的最好位置(pbest)和現在的位置Xi。這個可以看作是粒子自己的飛行經驗。除此之外，每個粒子還知道到目前為止整個群體中所有粒子發現的最好位置(gbest)(gbest是pbest中的最好值)，這個可以看作是粒子同伴的經驗。粒子就是通過自己的經驗和同伴中最好的經驗來決定下一步的運動。
3.2 速度和位置的更新
PSO初始化為一群隨機粒子(隨機解)。然后通過迭代找到最優解。在每一次的迭代中，粒子通過跟蹤兩個“極值”(pbest，gbest)來更新自己。在找到這兩個最優值后，粒子通過下面的公式來更新自己的速度和位置。
對于公式(1)：
公式(1)的第①部分稱為【記憶項】，表示上次速度大小和方向的影響；
公式(1)的第②部分稱為【自身認知項】，是從當前點指向粒子自身最好點的一個矢量，表示粒子的動作來源于自己經驗的部分；
公式(1)的第③部分稱為【群體認知項】，是一個從當前點指向種群最好點的矢量，反映了粒子間的協同合作和知識共享。粒子就是通過自己的經驗和同伴中最好的經驗來決定下一步的運動。
以上面兩個公式為基礎，再來看一個公式：
公式(2)和 公式(3)被視為標準PSO算法。
04 標準PSO算法流程4.1 標準PSO算法的流程
1）初始化一群微粒(群體規模為N)，包括隨機位置和速度；
2）評價每個微粒的適應度；
3）對每個微粒，將其適應值與其經過的最好位置pbest作比較，如果較好，則將其作為當前的最好位置pbest；
4）對每個微粒，將其適應值與其經過的最好位置gbest作比較，如果較好，則將其作為當前的最好位置gbest；
5）根據公式(2)、(3)調整微粒速度和位置；
6）未達到結束條件則轉第2）步。
迭代終止條件根據具體問題一般選為最大迭代次數Gk或(和)微粒群迄今為止搜索到的最優位置滿足預定最小適應閾值。
4.2 PSO流程圖解4.3 學習因子c1、c2分析
公式(2)和(3)中pbest和gbest分別表示微粒群的局部和全局最優位置。
05 代碼實例講解5.1 先來看個簡單的實例
在這個例子中，我們選取了一個求解函數y=-x*(x-1) 在0,2上最大值的粒子群算法。然后通過步步跟蹤算法輸出結果，來給大家講解粒子運動的過程。
下面先看代碼和代碼注釋。
public class AlgorithmPSO {
int n=2; //粒子個數，這里為了方便演示，我們只取兩個，觀察其運動方向
double[] y;
double[] x;
double[] v;
double c1=2;
double c2=2;
double pbest[];
double gbest;
double vmax=0.1; //速度最大值
//適應度計算函數，每個粒子都有它的適應度
public void fitnessFunction(){
for(int i=0;igbest) gbest=y[i];
}
System.out.println("算法開始，起始最優解:"+gbest);
System.out.print("\n");
}
public double getMAX(double a,double b){
return a>b?a:b;
}
//粒子群算法
public void PSO(int max){
for(int i=0;ivmax) v[j]=vmax;//控制速度不超過最大值
x[j]+=v[j];
//越界判斷，范圍限定在[0, 2]
if(x[j]>2) x[j]=2;
if(x[j]<0) x[j]=0;
}
fitnessFunction();
//更新個體極值和群體極值
for(int j=0;jgbest) gbest=pbest[j];
System.out.println("粒子n"+j+": x = "+x[j]+" "+"v = "+v[j]);
}
System.out.println("第"+(i+1)+"次迭代，全局最優解 gbest = "+gbest);
System.out.print("\n");
}
}
//運行我們的算法
public static void main(String[] args){
AlgorithmPSO ts=new AlgorithmPSO();
ts.init();
ts.PSO(10);//為了方便演示，我們暫時迭代10次。
}
} 復制
輸出結果：
算法開始，起始最優解:0.0
粒子n0: x = 0.004 v = 0.004
粒子n1: x = 0.0 v = -4.065770842472382
第1次迭代，全局最優解 gbest = 0.007984
粒子n0: x = 0.01778510589090629 v = 0.013785105890906289
粒子n1: x = 0.0 v = -1.625639647649872
第2次迭代，全局最優解 gbest = 0.03525390179026183
粒子n0: x = 0.0610276658084214 v = 0.04324255991751511
粒子n1: x = 0.0 v = -0.6035255880722042
第3次迭代，全局最優解 gbest = 0.11833095562281844
粒子n0: x = 0.1610276658084214 v = 0.1
粒子n1: x = 0.0 v = -0.012719944703824898
第4次迭代，全局最優解 gbest = 0.29612542246113416
粒子n0: x = 0.2610276658084214 v = 0.1
粒子n1: x = 0.06231495466940402 v = 0.06231495466940402
第5次迭代，全局最優解 gbest = 0.4539198892994499
粒子n0: x = 0.3610276658084214 v = 0.1
粒子n1: x = 0.16231495466940402 v = 0.1
第6次迭代，全局最優解 gbest = 0.5917143561377656
粒子n0: x = 0.46102766580842136 v = 0.1
粒子n1: x = 0.262314954669404 v = 0.1
第7次迭代，全局最優解 gbest = 0.7095088229760813
粒子n0: x = 0.5610276658084213 v = 0.1
粒子n1: x = 0.362314954669404 v = 0.1
第8次迭代，全局最優解 gbest = 0.8073032898143969
粒子n0: x = 0.6610276658084213 v = 0.1
粒子n1: x = 0.462314954669404 v = 0.1
第9次迭代，全局最優解 gbest = 0.8850977566527127
粒子n0: x = 0.7610276658084213 v = 0.1
粒子n1: x = 0.562314954669404 v = 0.1
第10次迭代，全局最優解 gbest = 0.9428922234910285復制
現在我們來觀察兩個粒子的位移x在每一次迭代中的變化（離食物的距離）。
1) 初始狀態
粒子n0: x = 0.0 v = 0.01
粒子n1: x = 2.0 v = 0.02
image
兩個粒子位于區間兩端。
2) 第一次迭代
粒子n0: x = 0.004 v = 0.004
粒子n1: x = 0.0 v = -4.2382
兩個粒子都跑到原點了。
3) 第二、三……十次迭代
可以看到，兩個粒子在不斷靠近最優點。上面多個圈是他們聚集的過程，可以看出來，聚集過程是個越來越密集的過程。這才是10次迭代而已。如果我們加大迭代次數，很容易就找出最優解了。最后放上一個迭代100次的結果：
相信通過這個簡單的例子。大家已經對粒子群算法有了非常清晰的認識了。
06 PSO和GA比較6.1 共性
(1)都屬于仿生算法。
(2) 都屬于全局優化方法。
(3) 都屬于隨機搜索算法。
(4) 都隱含并行性。
(5) 根據個體的適配信息進行搜索，因此不受函數 約束條件的限制，如連續性、可導性等。
(6) 對高維復雜問題，往往會遇到早熟收斂和收斂 性能差的缺點，都無法保證收斂到最優點。
6.2 差異
(1) PSO有記憶，好的解的知識所有粒子都保 存，而GA，以前的知識隨著種群的改變被改變。
(2) PSO中的粒子僅僅通過當前搜索到最優點進行共享信息，所以很大程度上這是一種單共享項信息機制。而GA中，染色體之間相互共享信息，使得整個種群都向最優區域移動。
(3) GA的編碼技術和遺傳操作比較簡單，而PSO 相對于GA，沒有交叉和變異操作粒子群算法的基本流程，粒子只是通過內部速度進行更新，因此原理更簡單、參數更少、實現更容易。