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