粒子群優(yōu)化算法的性能分析和參數(shù)選擇

王東風(fēng)　孟麗

粒子群優(yōu)化算法的性能分析和參數(shù)選擇

王東風(fēng)1孟麗1

慣性權(quán)重和加速因子是影響粒子群算法優(yōu)化性能的重要參數(shù).基于常用的12個(gè)測試函數(shù)，本文通過實(shí)驗(yàn)研究了不同參數(shù)組合下粒子的探索能力和算法的優(yōu)化性能，在此基礎(chǔ)上推薦了一組固定的參數(shù)組合.通過慣性權(quán)重和加速因子的不同變化策略組合對算法性能影響的實(shí)驗(yàn)分析，推薦了一種變化的參數(shù)設(shè)置方法.基于CEC2015發(fā)布的15個(gè)基準(zhǔn)函數(shù)進(jìn)一步驗(yàn)證了本文推薦的參數(shù)選取方法的有效性.最后討論了粒子群優(yōu)化（Particle swarm optimization，PSO）算法在連續(xù)優(yōu)化和離散優(yōu)化方面的應(yīng)用問題.

粒子群優(yōu)化，探索能力，算法性能，參數(shù)選取

引用格式王東風(fēng)，孟麗.粒子群優(yōu)化算法的性能分析和參數(shù)選擇.自動化學(xué)報(bào)，2016，42（10）:1552-1561

粒子群優(yōu)化（Particle swarm optimization，PSO）算法是Kennedy和Eberhart在1995年提出的一種群智能優(yōu)化算法［1］，源于對鳥群捕食行為的研究.1998年，Shi等［2］在原始PSO中引入了慣性權(quán)重，后來被稱為標(biāo)準(zhǔn)PSO.由于PSO結(jié)構(gòu)簡單、易于實(shí)現(xiàn)，且不需要借助問題的特征信息，已受到眾多學(xué)者的關(guān)注，在算法的性能改進(jìn)和分析方面不斷取得新的成果［3-4］，在多個(gè)領(lǐng)域得到廣泛應(yīng)用［5］.

在PSO算法中，有一些需要調(diào)節(jié)的參數(shù)：種群規(guī)模（種群的個(gè)體數(shù)目）N，速度限值位置限值慣性權(quán)重w，加速因子c1和c2.其中，w，c1和c2對算法性能的影響較大，目前有很多學(xué)者對其設(shè)定和調(diào)節(jié)方式進(jìn)行了研究.在參數(shù)選取方面，文獻(xiàn)［6-9］通過實(shí)驗(yàn)或理論分析，推薦了一組固定參數(shù)值.在時(shí)變參數(shù)的調(diào)節(jié)方面，對于慣性權(quán)重的調(diào)整，文獻(xiàn)［2，10］提出了隨迭代次數(shù)減小慣性權(quán)重，文獻(xiàn)［11-12］給出了隨機(jī)慣性權(quán)重策略，文獻(xiàn)［13-15］根據(jù)種群的信息自適應(yīng)地調(diào)節(jié)慣性權(quán)重；對于加速因子的調(diào)整，文獻(xiàn)［16］提出在迭代的過程中，c1和c2線性遞減，文獻(xiàn)［17］則提出c1線性遞減、c2線性遞增，文獻(xiàn)［18］基于個(gè)體的更新信息給出了一種c1和c2的自適應(yīng)調(diào)整策略.以上這些參數(shù)的調(diào)整方法，都在一定程度上提高了算法的性能，但是，當(dāng)涉及到時(shí)變參數(shù)時(shí)，并沒有考慮到慣性權(quán)重和加速因子之間的配合作用.單獨(dú)依靠調(diào)整慣性權(quán)重或加速因子，并不能在種群的局部開發(fā)能力（Exploitation ability）和全局探索能力（Exploration ability）之間進(jìn)行平衡.事實(shí)上，各個(gè)參數(shù)之間需要相互配合，才能夠達(dá)到預(yù)定的效果.本文考慮了各個(gè)參數(shù)之間的配合，基于在感興趣的參數(shù)范圍內(nèi)進(jìn)行的優(yōu)化測試實(shí)驗(yàn)數(shù)據(jù)，通過定義最優(yōu)解超越次數(shù)，推薦了一組固定和時(shí)變的參數(shù)值.

本文其余部分安排如下：第1節(jié)先給出標(biāo)準(zhǔn)粒子群算法的形式；第2節(jié)通過仿真實(shí)驗(yàn)研究不同參數(shù)對粒子探索能力、算法成功率和算法性能的影響，推薦一組固定參數(shù)值；第3節(jié)研究算法中的認(rèn)知參數(shù)c1和社會參數(shù)c2的變化策略對算法性能的影響，并推薦一組變參數(shù)的組合設(shè)定方式；第4節(jié)基于CEC2015發(fā)布的15個(gè)基準(zhǔn)函數(shù)進(jìn)一步驗(yàn)證本文推薦的參數(shù)選取方法的有效性；第5節(jié)討論P(yáng)SO算法在連續(xù)優(yōu)化和離散優(yōu)化方面的應(yīng)用問題；第6節(jié)對全文進(jìn)行了總結(jié).

1　標(biāo)準(zhǔn)粒子群（SPSO）算法

在粒子群算法中，每個(gè)粒子代表尋優(yōu)空間中一個(gè)潛在的解，有一個(gè)由被優(yōu)化的函數(shù)決定的適應(yīng)值.在每一次迭代進(jìn)化中，粒子通過自身和群體的歷史最優(yōu)位置更新當(dāng)前的速度和位置.在任意t+1時(shí)刻，粒子群算法中第i個(gè)粒子第d維的速度和位置更新公式為

其中，vid和xid分別為粒子的速度和位置，w為慣性權(quán)值，c1和c2稱為加速因子，分別為認(rèn)知參數(shù)和社會參數(shù)，pid和pgd分別為個(gè)體和群體的歷史最優(yōu)位置，r1d和r2d為兩個(gè)相互獨(dú)立的服從［0，1］之間均勻分布的隨機(jī)數(shù)，正是這兩個(gè)隨機(jī)數(shù)的引入，使得算法的進(jìn)化過程具有一定的不確定性，也因此賦予了算法一定的空間探索能力，從而有利于找到問題的最優(yōu)解.

2　粒子群算法的性能分析

下面通過實(shí)驗(yàn)說明粒子的探索能力和算法的性能與參數(shù)之間的關(guān)系.我們感興趣的參數(shù)區(qū)域是w∈［-1，1］，c1+c2∈［0，8］，這也是絕大多數(shù)文獻(xiàn)研究的區(qū)域.所有的實(shí)驗(yàn)都基于以下12個(gè)常用的基準(zhǔn)函數(shù)，由于這些基準(zhǔn)函數(shù)被普遍應(yīng)用，在此只給出函數(shù)的名稱，即：Fun1：Sphere；Fun2：Rosenbrock；Fun3：Schwefel′s P2.21；Fun4：Schwefel′s P2.22；Fun5：Schwefel′s P1.2；Fun6：Rastrigin；Fun7：Griewank；Fun8：Ackley；Fun9：Schwefel；Fun10：Weierstrass；Fun11：Penalized1；Fun12：Penalized2.

2.1參數(shù)對粒子探索能力的影響

粒子群算法參數(shù)w，c1，c2的選取對算法的優(yōu)化性能有很大影響.不同的參數(shù)組合下，粒子的軌跡形式是不同的，決定了粒子探索能力的大小.在種群進(jìn)化過程中的第t代，若粒子能夠找到比t-1代的全局最優(yōu)解更好的解，那么則認(rèn)為粒子具有一定的探索能力.我們通過以下實(shí)驗(yàn)觀察不同的參數(shù)對粒子探索能力的影響.設(shè)種群規(guī)模為N，為每個(gè)粒子設(shè)置不同的參數(shù)，設(shè)置變量Pnumi記錄具有不同參數(shù)的粒子i在進(jìn)化的過程中超越上一代的全局最優(yōu)解的次數(shù)：

其中，t=2，3，···，tmax.

將上面定義的Pnumi稱為粒子i的第t代最優(yōu)解超越次數(shù)，它表征了粒子探索能力的大小.顯然，探索能力大的粒子更有可能找到全局最優(yōu)解.

對于所有的粒子設(shè)置相同參數(shù)的粒子群算法，則所有的粒子在統(tǒng)計(jì)意義上具有相同的探索能力；隨著算法進(jìn)化進(jìn)程的推進(jìn)，具有不同的狀態(tài)的粒子在當(dāng)前迭代步則具有不同的探索能力；被設(shè)置不同參數(shù)的粒子，一般則具有不同的探索能力.這已得到作者們進(jìn)行的大量仿真優(yōu)化計(jì)算實(shí)例的證實(shí).圖1為4組不同的PSO種群在優(yōu)化函數(shù)Sphere時(shí)每個(gè)粒子的Pnum值：種群大小均為50，函數(shù)設(shè)置為10維，最大迭代次數(shù)為500，每組種群運(yùn)行50次，記錄每個(gè)粒子Pnum值的平均值.圖1（a）為種群中粒子設(shè)置為相同的參數(shù)時(shí)（w=0.6，c1=c2=1.7）每個(gè)粒子的Pnum值；圖1（b）、圖1（c）和圖1（d）為種群中粒子設(shè)置不同參數(shù)時(shí)每個(gè)粒子的Pnum值，其中圖1（b）中，第1～50個(gè)粒子的w值均為0.6，c1=c2為0.04：0.04：2；圖1（c）中，第1～50個(gè)粒子的w值均為1.7，c1=c2分別為0.02：0.02：1，圖1（d）中，第1～10個(gè)粒子的w值均為0.2，c1=c2分別為0.2：0.2：2，第11～20個(gè)粒子的w均為0.4，c1=c2分別為0.2：0.2：2，依此類推，第41～50個(gè)粒子的w均為1.0，c1=c2分別為0.2：0.2：2.

在w∈［-1，1］，c1+c2∈［0，8］的參數(shù)區(qū)域上對所用的12個(gè)基準(zhǔn)函數(shù)進(jìn)行蒙特卡羅實(shí)驗(yàn).每個(gè)函數(shù)進(jìn)行兩組實(shí)驗(yàn)：1）種群中的個(gè)體取相同的w，c1=c2則取不同的數(shù)值.本組實(shí)驗(yàn)中，根據(jù)種群參數(shù)w的值分為51組子實(shí)驗(yàn)，w的取值按0.04的間隔從-1～1，每個(gè)子實(shí)驗(yàn)中，種群大小均為81，c1=c2按0.05的間隔從0～4取81個(gè)值分配給不同的粒子，函數(shù)運(yùn)行50次，記錄不同粒子在50次運(yùn)行中的Pnum的平均值.2）種群中的個(gè)體取不同的w，而c1=c2取相同的固定值.本組實(shí)驗(yàn)中，根據(jù)種群參數(shù)c1（c2）的值分為81組子實(shí)驗(yàn)，c1=c2的取值按0.05的間隔從0～4，每個(gè)子實(shí)驗(yàn)中，種群大小均為51，w按0.04的間隔從-1～1共取51個(gè)值分配給不同的粒子，函數(shù)運(yùn)行50次，記錄不同粒子在50次運(yùn)行中的Pnum的平均值.將兩組實(shí)驗(yàn)中得到的相同參數(shù)組合下粒子i的Pnumi進(jìn)行求和，得到此參數(shù)組合在不同種群環(huán)境中的綜合探索性能，進(jìn)而得到整個(gè)參數(shù)區(qū)域內(nèi)不同參數(shù)組合的綜合超越次數(shù).相比于超越次數(shù)的絕對值，我們更關(guān)心不同參數(shù)組合下粒子探索能力的相對關(guān)系，因此對每個(gè)函數(shù)得到的結(jié)果分別進(jìn)行歸一化處理，結(jié)果如圖2所示.值得注意的是，在6＜c1+c2≤8的區(qū)域中，對于任意的w運(yùn)行結(jié)果Pnumi均為0，因此，6＜c1+c2≤8的區(qū)域并未在圖中進(jìn)行展示.從圖2可以明顯地看到粒子群算法的參數(shù)取值對不同基準(zhǔn)函數(shù)的優(yōu)化性能的共性和特性，即對每個(gè)基準(zhǔn)函數(shù)來說，算法的探索能力對參數(shù)的取值表現(xiàn)出明顯的區(qū)域性，總體來說大同小異，這為PSO的參數(shù)選擇提供了很好的指導(dǎo)作用.

2.2參數(shù)對算法成功率的影響

在w∈［-1，1］，c1+c2∈［0，8］矩形域上按照等間隔的網(wǎng)格取點(diǎn)，（c1+c2）軸取點(diǎn)間隔為0.02，共101點(diǎn)，w軸取點(diǎn)間隔為0.04，共201點(diǎn)，共可得到20301組不同的參數(shù)組合.對每一組參數(shù)組合進(jìn)行蒙特卡羅仿真實(shí)驗(yàn)，優(yōu)化12個(gè)基準(zhǔn)函數(shù).種群規(guī)模N為50，最大迭代次數(shù)tmax為500，每個(gè)函數(shù)獨(dú)立運(yùn)行50次.為每個(gè)函數(shù)設(shè)置尋優(yōu)精度goal，記錄不同參數(shù)組合下達(dá)到所設(shè)置尋優(yōu)精度的成功率，繪制成灰度圖像.每個(gè)函數(shù)的尋優(yōu)精度為圖中的goal所示，是通過實(shí)驗(yàn)測試得到的，原則是不會使測試結(jié)果得到的最佳參數(shù)組合區(qū)域過大而失去指導(dǎo)意義，也不會使其過小而失去一般性參考價(jià)值.設(shè)置一定的尋優(yōu)精度，實(shí)驗(yàn)結(jié)果如圖3所示.

由圖3可以看到，除了Fun2、Fun6、Fun7和Fun9，其他8個(gè)函數(shù)的最優(yōu)參數(shù)區(qū)域在形狀上非常相似，并且都出現(xiàn)在靠近過渡區(qū)域的邊界部分.這一部分的參數(shù)使得粒子軌跡能夠以一定的幅值振蕩，使得探索能力和開發(fā)能力獲得很好的平衡.對于Fun2、Fun6、Fun7和Fun9這4個(gè)函數(shù)，F(xiàn)un2為很難極小化的典型病態(tài)二次函數(shù)；Fun6、Fun7為典型的具有大量局部最優(yōu)點(diǎn)的復(fù)雜多峰函數(shù)；Fun9的全局最優(yōu)點(diǎn)與第2最優(yōu)點(diǎn)相距很遠(yuǎn)，算法往往朝著錯(cuò)誤的方向（第2最優(yōu)點(diǎn)）收斂.這4個(gè)函數(shù)只靠調(diào)節(jié)算法參數(shù)很難得到滿意的解，運(yùn)行結(jié)果的規(guī)律性沒有其他函數(shù)那么明顯.

將圖2與圖3對比可以看到，圖2和圖3并不是完全對應(yīng)的.圖2中展示的粒子的探索能力為粒子的局部探索能力和全局探索能力的總和，而不同的函數(shù)具有不同的特性，對群體的局部探索能力和全局探索能力的要求是不同的.雖然總的探索能力與尋優(yōu)性能并不是完全對應(yīng)的，但是，沒有探索能力的參數(shù)區(qū)域，基本上是不可取的.

2.3幾種典型參數(shù)選取策略的性能對比及一組固定參數(shù)推薦值

由圖3可以看到，使得算法獲得優(yōu)良性能的參數(shù)區(qū)域因函數(shù)的不同而有一些差異，基本上沒有一組參數(shù)能夠使得所有的函數(shù)同時(shí)獲得最優(yōu)，尤其可以看到，F(xiàn)un2和Fun9的較優(yōu)參數(shù)區(qū)域的交集部分是非常小的.盡管如此，仍然可以選擇出一些參數(shù)，使算法在所有函數(shù)上獲得比較令人滿意的綜合性能.為了能夠更加容易地選擇出在12個(gè)函數(shù)上綜合性能較優(yōu)的參數(shù)，我們將不同函數(shù)下得到的運(yùn)行結(jié)果進(jìn)行整合，得到算法在不同參數(shù)下的綜合性能的示意圖，見圖4.

圖2　粒子探索能力與參數(shù)的關(guān)系Fig.2　Relationship between particle exploration ability and its parameters

圖4中標(biāo)示的PARA1和PARA2分別為文獻(xiàn)［6］和文獻(xiàn)［7］推薦的參數(shù)取值.其中，參數(shù)組合PARA1（w=0.7298，c1=c2=1.49618）是Eberhart等［6］將帶有慣性權(quán)重和帶有收縮因子的兩種形式的粒子群算法進(jìn)行比較后推薦的一組參數(shù)；參數(shù)組合PARA2（w=0.6，c1=c2=1.7）是Trelea［7］在分析粒子軌跡收斂域的基礎(chǔ)上推薦的參數(shù).參數(shù)組合PARA3是我們根據(jù)性能綜合圖，即圖4推薦的一組參數(shù)：w=0.4，c1=c2=2.在另外的工作中，Samal等［8］在理論分析的基礎(chǔ)上給出了一組具有較快收斂速度的參數(shù)：w=0.6，c1r1=0.103，c2r2=2.897（參數(shù)組合PARA4）；Carlisle等［9］在文獻(xiàn)［6］的基礎(chǔ)上進(jìn)行了進(jìn)一步的實(shí)驗(yàn)，考慮了的情況，通過仿真實(shí)驗(yàn)得到，當(dāng)時(shí)，算法的性能較優(yōu)，即w=0.7298，c1=2.0434，c2=0.9487（參數(shù)組合PARA5）.我們將這5組參數(shù)在12個(gè)函數(shù)上進(jìn)行測試，種群規(guī)模、最大迭代次數(shù)和每個(gè)函數(shù)獨(dú)立運(yùn)行的次數(shù)都與第2.2節(jié)一致.記錄運(yùn)行數(shù)次結(jié)果中的最小值（min）、最大值（max）、平均值±標(biāo)準(zhǔn)差（mean ±std），以及優(yōu)化成功率（Success rate，SR），并且記錄了不同參數(shù)在每個(gè)函數(shù)指定尋優(yōu)精度下的成功率，結(jié)果列于表1中.為了清晰地顯示參數(shù)對算法性能的影響，此處為12個(gè)函數(shù)指定的尋優(yōu)精度依次為：10-20，3，10-5，10-10，10-20，5，10-1，10-10，500，10-3，10-20，10-20.以下各測試試驗(yàn)中所用的尋優(yōu)精度均與此相同.首先來看參數(shù)PARA1～PARA3的運(yùn)行結(jié)果，這三個(gè)參數(shù)組合基本上都在圖4中的較優(yōu)區(qū)域里.三組參數(shù)在Fun1，F(xiàn)un3，F(xiàn)un4，F(xiàn)un8，F(xiàn)un11和Fun12上的運(yùn)行結(jié)果差別不大.在Fun2，F(xiàn)un5，F(xiàn)un6，F(xiàn)un7，F(xiàn)un9和Fun10上的差別相對較大，參數(shù)PARA1在Fun2，F(xiàn)un7上表現(xiàn)較優(yōu)，在Fun5上表現(xiàn)較差；參數(shù)PARA2在Fun6，F(xiàn)un9上表現(xiàn)較差；參數(shù)PARA3在Fun6，F(xiàn)un9和Fun10上表現(xiàn)較優(yōu)，在Fun2，F(xiàn)un7上表現(xiàn)較差.正如從圖3中看到的，每組參數(shù)都有其適應(yīng)的函數(shù).再來看參數(shù)PARA4和參數(shù)PARA5，同樣的，每組參數(shù)在不同函數(shù)上表現(xiàn)出的性能也是有差別的.參數(shù)PARA4的綜合性能在所有的參數(shù)中是比較差的.參數(shù)PARA5是在參數(shù)PARA1的基礎(chǔ)上發(fā)展而來的，保持c1與c2之和不變，改變c1和c2的比例，除了在Fun2上，參數(shù)PARA5的性能要優(yōu)于參數(shù)PARA1.

圖3　算法成功率與參數(shù)的關(guān)系Fig.3　Relationship between the algorithm success rate and particle parameters

圖4　算法在12個(gè)測試函數(shù)上的性能總和Fig.4　Total optimization performance on the 12 test functions

為了能夠比較全面地了解c1和c2的比例對算法的影響，我們保持參數(shù)PARA1中的w=0.7298，c1+c2=2.992，將c1在c1+c2的總和中所占的比率由0逐漸增加到1，在12個(gè)函數(shù)上的運(yùn)行結(jié)果如圖5所示.Fun2，F(xiàn)un6，F(xiàn)un7和Fun9在整個(gè)比率范圍內(nèi)的變化情況較為復(fù)雜，圖5（a）為這4個(gè)函數(shù)的變化情況，另外8個(gè)函數(shù)的優(yōu)化情況展示在圖5（b）中.當(dāng)c1在c1與c2之和中所占比例c1/（c1+c2）在0.6～0.8之間時(shí)，圖5（b）中的8個(gè)函數(shù)都獲得了很好的性能，而圖5（a）中，算法在Fun6，F(xiàn)un7和Fun9上的成功率隨c1/（c1+c2）的增加而增大，在0.8附近到達(dá)最好值；Fun2則相反，成功率隨著c1/（c1+c2）的增加而減小，在0.8時(shí)的成功率非常低.當(dāng)c1/（c1+c2）取為0.683時(shí)，便可得到參數(shù)組合PARA5，對于圖5（b）的8個(gè)函數(shù)來說，是最好的選擇.而對于圖5（a）的4個(gè)函數(shù)來說，是綜合考慮的折中選擇.

圖5　c1所占比率對算法成功率的影響Fig.5　The influence of ratio c1on algorithm′s success rate

表1　5組參數(shù)的運(yùn)行結(jié)果對比Table 1　Comparison of running results on 5 parameters

3　幾種典型參數(shù)變化策略的性能對比及一種變化參數(shù)推薦值

以上的實(shí)驗(yàn)和討論都是基于在種群進(jìn)化過程中c1和c2為定值的情形下進(jìn)行的，從表1和圖5的運(yùn)行結(jié)果可以看到，無論c1和c2是否相等，采用c1和c2定值的調(diào)節(jié)算法在算法性能上是有局限性的.為了進(jìn)一步提高算法的性能，下面觀察在迭代的過程中c1和c2按照不同的方式變化時(shí)對算法性能的影響.實(shí)驗(yàn)仍然基于12個(gè)測試函數(shù)，對于固定的w，c1和c2有9種不同的調(diào)整策略，為簡潔表示，引入3個(gè)符號：“→”表示參數(shù)c1或c2保持不變，為1.5；“↑”表示參數(shù)c1或c2在迭代的過程中線性地由0.5上升到2.5；“↓”表示參數(shù)c1或c2在迭代的過程中線性地由2.5下降到0.5.則c1和c2的9種調(diào)節(jié)策略表示為：

對于每個(gè)函數(shù)，進(jìn)行如下實(shí)驗(yàn)：w從0逐漸增加到1，對于每個(gè)w的值，分別用以上9種策略進(jìn)行實(shí)驗(yàn).每個(gè)優(yōu)化實(shí)驗(yàn)運(yùn)行50次.記錄最終結(jié)果到達(dá)指定精度的成功率.運(yùn)行結(jié)果如圖6所示，縱軸為算法尋優(yōu)的成功率，橫軸為w值，每個(gè)子圖中的9條曲線，分別對應(yīng)上述c1和c2的9種取值策略.

圖6　變化的c1和c2取值策略對算法成功率的影響Fig.6　The influence of varying c1and c2on algorithm′s success rate

由圖6可以看到，每一種c1和c2的取值策略都有與其對應(yīng)的w的最佳取值范圍.除了Fun2，F(xiàn)un6，F(xiàn)un7和Fun9，各種策略的性能隨著w的變化情況是類似的，即：沿著w軸的正方向，w的整個(gè)區(qū)間可以分為5個(gè)區(qū)域：1）初始階段，成功率幾乎為0；2）緊隨其后的很小的區(qū)域內(nèi)，成功率由0迅速上升達(dá)到曲線的最大值；3）在一段區(qū)域內(nèi)，成功率保持為最大值；4）緊隨其后的很小的區(qū)域內(nèi)，成功率迅速下降；5）最后區(qū)域，成功率幾乎為零.區(qū)域1和區(qū)域3的大小與參數(shù)的取值策略緊密相關(guān).而所有的策略在w＞0.68時(shí)，成功率幾乎均為0.區(qū)域3正是我們需要的部分.在這8個(gè)函數(shù)上，策略3、策略7和策略9使得區(qū)域3較為寬廣.再來看Fun6，F(xiàn)un7和Fun9，策略2取得了最好的成功率，其次為策略8.在Fun6和Fun7上，對于某些c1和c2的取值策略，w的取值可以比較小，也能夠使算法獲得不錯(cuò)的性能.在Fun2上，各個(gè)策略相適應(yīng)的w值范圍都很小.相比較而言，不論是從w的適用范圍的大小還是從成功率的高低來看，策略4、策略5和策略6都是不可取的，即增大的調(diào)節(jié)方式總是不可取的.綜合12個(gè)測試函數(shù)來看，策略8在Fun6，F(xiàn)un7和Fun9上，在w=0.68時(shí)具有很突出的效果，并且，在其他8個(gè)函數(shù)上，雖然策略8的w的適用范圍并不寬廣，但在w=0.68時(shí)，恰恰都具有很好的性能，因此，w=0.68，c1在迭代過程中由2.5線性減小到0.5，c2由0.5線性增加到2.5，是一種很好的參數(shù)設(shè)置方式.這與Ratnaweera等［17］提出的c1遞減和c2遞增的調(diào)整策略是相符的，在文獻(xiàn)［17］中，c1和c2的變化范圍與本文相同，而w的取值由0.9隨迭代線性減小到0.4.本文提出的和文獻(xiàn)［17］中的參數(shù)設(shè)置方法在12個(gè)函數(shù)上的運(yùn)行結(jié)果如表2所示.在表2中，Method-ours指本文推薦的w=0.68，c1在迭代過程中由2.5線性減小到0.5，c2由0.5線性增加到2.5.Method-［17］是指文獻(xiàn)［17］給出的w的取值由0.9隨迭代線性減小到0.4，c1和c2的變化范圍與Method-ours相同.由表2的運(yùn)行結(jié)果可以看到，本文的參數(shù)設(shè)置方法要優(yōu)于文獻(xiàn)［17］中的方法.值得注意的是，c1和c2的變化范圍，與使其獲得較優(yōu)性能的w也是相互配合的，在我們的實(shí)驗(yàn)中發(fā)現(xiàn)，當(dāng)變化范圍為［0.5，2.05］時(shí)，w取0.75的性能要優(yōu)于0.68.因此，3個(gè)參數(shù)之間的相互配合是非常重要的.

表2　本文與文獻(xiàn)［17］參數(shù)設(shè)置的優(yōu)化結(jié)果比較Table 2　Comparison of optimization results between the parameters set in this paper and［17］

4　本文參數(shù)設(shè)置方式優(yōu)化性能的進(jìn)一步驗(yàn)證

為進(jìn)一步驗(yàn)證本文參數(shù)設(shè)置方法的有效性，將第2節(jié)的一組固定參數(shù)推薦值和第3節(jié)的時(shí)變參數(shù)設(shè)置方式，應(yīng)用于2015年的進(jìn)化計(jì)算世界大會，即CEC2015發(fā)布的15個(gè)基準(zhǔn)函數(shù)［19］.

對于參數(shù)優(yōu)化能力的驗(yàn)證，種群大小與前面所有試驗(yàn)設(shè)置相同（設(shè)置為50），函數(shù)維數(shù)為10，最大迭代次數(shù)為5000，每個(gè)函數(shù)運(yùn)行次數(shù)為100.試驗(yàn)僅記錄達(dá)到指定精度的成功率（Success rate，SR），其中，F(xiàn)1～F15的指定精度分別為：3000，1500，20，10，500，1000，10，200，110，1000，500，110，30，3000，110.

對圖4給出的3種典型固定參數(shù)，即文獻(xiàn)［6］和文獻(xiàn)［7］推薦的參數(shù)取值PARA1和PARA2，以及本文的參數(shù)推薦取值PARA3，表3給出了應(yīng)用于CEC2015的15個(gè)基準(zhǔn)函數(shù)上運(yùn)行結(jié)果的對比.可以看出，本文的參數(shù)推薦值PARA3在15個(gè)函數(shù)上的表現(xiàn)略優(yōu)于PARA1和PARA2.

對第3節(jié)推薦的時(shí)變參數(shù)設(shè)置方式和文獻(xiàn)［17］的參數(shù)設(shè)置方式，表4給出了應(yīng)用于CEC2015的15個(gè)基準(zhǔn)函數(shù)上運(yùn)行結(jié)果的對比.可以看出，本文推薦的時(shí)變參數(shù)設(shè)置方式在15個(gè)函數(shù)上的表現(xiàn)優(yōu)于文獻(xiàn)［17］的參數(shù)設(shè)置方式.

5　本文推薦的PSO參數(shù)應(yīng)用于連續(xù)優(yōu)化問題和離散優(yōu)化問題的討論

PSO算法最初是針對連續(xù)優(yōu)化問題提出的，相關(guān)研究也主要集中在連續(xù)函數(shù)優(yōu)化方面［20-22］，即第1節(jié)描述的標(biāo)準(zhǔn)算法被廣泛研究和應(yīng)用.本文研究的出發(fā)點(diǎn)也主要是針對連續(xù)優(yōu)化問題，文中給出的12個(gè)標(biāo)準(zhǔn)測試函數(shù)和CEC2015發(fā)布的15個(gè)基準(zhǔn)函數(shù)［19］的優(yōu)化測試，驗(yàn)證了本文方法在連續(xù)優(yōu)化問題上的有效性.

表3　本文給出的固定參數(shù)推薦值在CEC2015基準(zhǔn)函數(shù)F1～F15上的運(yùn)行結(jié)果Table 3　Running results on CEC2015 Benchmark functions F1～F15 with fixed parameters

表4　本文給出的時(shí)變參數(shù)設(shè)置方式在CEC2015基準(zhǔn)函數(shù)F1～F15上的運(yùn)行結(jié)果Table 4　Running results on CEC2015 Benchmark functions F1～F15 with time-varying parameters

對于離散優(yōu)化（或組合優(yōu)化）問題而言，解空間是離散點(diǎn)的集合，而非連續(xù)區(qū)域，因此利用PSO算法解決離散優(yōu)化問題，一般需要修正位置和速度更新公式，或者對問題進(jìn)行變形，這方面的工作大致可分為如下三類［21-22］：1）直接將連續(xù)PSO用于離散優(yōu)化問題的求解；2）將速度作為位置變化的概率；3）重新定義PSO算法的操作算子.對于前兩種情形，本文推薦的參數(shù)取值方法仍然適用，因?yàn)樗惴ㄔ诒举|(zhì)上依然遵從標(biāo)準(zhǔn)的PSO連續(xù)問題求解規(guī)則.但對于第三種情形，一般都是針對要求解的具體問題，定義不同的PSO操作算子，使得PSO算法在形式上與標(biāo)準(zhǔn)PSO算法差別較大，從而本文推薦的參數(shù)取值方法難以保證其優(yōu)化效果，這方面的問題有待進(jìn)一步研究.

6　結(jié)論

粒子群算法的可調(diào)參數(shù)共同影響著算法的優(yōu)化性能，本文將研究重點(diǎn)放在了慣性權(quán)重w和加速因子c1，c2的設(shè)定和調(diào)節(jié)上.基于12個(gè)常用的、不同類型的基準(zhǔn)函數(shù)，在w∈［-1，1］，c1+c2∈［0，8］的參數(shù)區(qū)域內(nèi)進(jìn)行了全面的仿真研究.通過實(shí)驗(yàn)結(jié)果可以看到，常常被提到的“慣性權(quán)重起著調(diào)節(jié)種群全局搜索能力和局部搜索能力”的說法是欠全面的，種群的搜索能力和算法的性能，是依靠w，c1和c2的相互配合來調(diào)節(jié)的，并不是僅靠一個(gè)參數(shù)可以決定的.在對固定參數(shù)的情形進(jìn)行仿真并給出參數(shù)推薦值后，還研究了時(shí)變參數(shù)對算法的影響，給出了一種推薦的時(shí)變參數(shù)設(shè)置方法.最后通過CEC2015發(fā)布的15個(gè)基準(zhǔn)函數(shù)進(jìn)一步驗(yàn)證了本文推薦的參數(shù)選取方法的有效性，并討論了PSO算法在連續(xù)優(yōu)化問題和離散優(yōu)化問題方面的應(yīng)用.

References

1 Kennedy J，Eberhart R.Particle swarm optimization.In: Proceedings of the 1995 IEEE International Conference on Neural Networks.Perth，Australia:IEEE，1995.1942-1948

2 Shi Y，Eberhart R.A modified particle swarm optimizer. In:Proceedings of the 1998 IEEE International Conference on Evolutionary Computation.Anchorage，AK，USA:IEEE，1998.69-73

3 Zhang Yong，Gong Dun-Wei，Zhang Wan-Qiu.A simplex method based improved particle swarm optimization and analysis on its global convergence.Acta Automatica Sinica，2009，35（3）:289-298（張勇，鞏敦衛(wèi)，張婉秋.一種基于單純形法的改進(jìn)微粒群優(yōu)化算法及其收斂性分析.自動化學(xué)報(bào)，2009，35（3）:289-298）

4 Pan Feng，Zhou Qian，Li Wei-Xing，Gao Qi.Analysis of standard particle swarm optimization algorithm based on Markov chain.Acta Automatica Sinica，2013，39（4）:381-389（潘峰，周倩，李位星，高琪.標(biāo)準(zhǔn)粒子群優(yōu)化算法的馬爾科夫鏈分析.自動化學(xué)報(bào)，2013，39（4）:381-389）

5 Liu Zhao-Hua，Zhou Shao-Wu，Liu Kan，Zhang Jing.Permanent magnet synchronous motor multiple parameter identification and temperature monitoring based on binary-modal adaptive wavelet particle swarm optimization.Acta Automatica Sinica，2013，39（12）:2121-2130（劉朝華，周少武，劉侃，章兢.基于雙模態(tài)自適應(yīng)小波粒子群的永磁同步電機(jī)多參數(shù)識別與溫度監(jiān)測方法.自動化學(xué)報(bào)，2013，39（12）: 2121-2130）

6 Eberhart R C，Shi Y.Comparing inertia weights and constriction factors in particle swarm optimization.In:Proceedings of the 2000 Congress on Evolutionary Computation.La Jolla，CA:IEEE，2000.84-88

7 Trelea I C.The particle swarm optimization algorithm:convergence analysis and parameter selection.Information Processing Letters，2003，85（6）:317-325

8 Samal N R，Konar A，Das S，Abraham A.A closed loop stability analysis and parameter selection of the particle swarm optimization dynamics for faster convergence.In:Proceedings of the 2007 IEEE Congress on Evolutionary Computation.Singapore:IEEE，2007.1769-1776

9 Carlisle A，Dozier G.An off-the-shelf PSO.In:Proceedings of the 2001 Workshop on Particle Swarm Optimization.Indianapolis，USA，2001.1-6

10 Hu Jian-Xiu，Zeng Jian-Chao.Selection on inertia weight of particle swarm optimization.Computer Engineering，2007，33（11）:193-195（胡建秀，曾建潮.微粒群算法中慣性權(quán)重的調(diào)整策略.計(jì)算機(jī)工程，2007，33（11）:193-195）

11 Yan Li-Ping，Zeng Jian-Chao.Particle swarm optimization with self-adaptive stochastic inertia weight.Computer Engineering and Design，2006，27（24）:4677-4679，4706（延麗平，曾建潮.具有自適應(yīng)隨機(jī)慣性權(quán)重的PSO算法.計(jì)算機(jī)工程與設(shè)計(jì)，2006，27（24）:4677-4679，4706）

12 Chalermchaiarbha S，Ongsakul W.Stochastic weight tradeoff particle swarm optimization for nonconvex economic dispatch.Energy Conversion and Management，2013，70:66-75

13 Ao Yong-Cai，Shi Yi-Bing，Zhang Wei，Li Yan-Jun.Improved particle swarm optimization with adaptive inertia weight.Journal of University of Electronic Science and Technology of China，2014，43（6）:874-880（敖永才，師奕兵，張偉，李焱駿.自適應(yīng)慣性權(quán)重的改進(jìn)粒子群算法.電子科技大學(xué)學(xué)報(bào)，2014，43（6）:874-880）

14 Zhan Z H，Zhang J，Li Y，Chung H S H.Adaptive particle swarm optimization.IEEE Transactions on Systems，Man，and Cybernetics，Part B（Cybernetics），2009，39（6）:1362-1381

15 Alfi A.PSO with adaptive mutation and inertia weight and its application in parameter estimation of dynamic systems. Acta Automatica Sinica，2011，37（5）:541-549

16 Suganthan P N.Particle swarm optimiser with neighbourhood operator.In:Proceedings of the 1999 Congress on Evolutionary Computation.Washington DC，USA:IEEE，1999.1958-1962

17 Ratnaweera A，Halgamuge S K，Watson H C.Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients.IEEE Transactions on Evolutionary Computation，2004，8（3）:240-255

18 Yamaguchi T，Yasuda K.Adaptive particle swarm optimization:self-coordinating mechanism with updating information.In:Proceedings of the 2006 IEEE International Conference on Systems，Man，and Cybernetics.Taipei，China: IEEE，2006.2303-2308

19 Liang J J，Qu B Y，Suganthan P N，Chen Q.Problem Definitions and Evaluation Criteria for the CEC 2015 Competition on Learning-based Real-parameter Single Objective Optimization.Technical Report 201411A，Computational Intelligence Laboratory，Zhengzhou University，Zhengzhou China，and Technical Report，Nanyang Technological University，Singapore，2014.

20 Cui Zhi-Hua，Zeng Jian-Chao.Particle Swarm Optimization.Beijing:Science Press，2011.（崔志華，曾建潮.微粒群優(yōu)化算法.北京:科學(xué)出版社，2011.）

21 Wang Ling，Liu Bo.Particle Swarm Optimization and Scheduling Algorithms.Beijing:Tsinghua University Press，2008.（王凌，劉波.微粒群優(yōu)化與調(diào)度算法.北京:清華大學(xué)出版社，2008.）

22 Guo Wen-Zhong，Chen Guo-Long.Discrete Particle Swarm Optimization Algorithm and Its Application.Beijing:Tsinghua University Press，2012.（郭文忠，陳國龍.離散粒子群優(yōu)化算法及其應(yīng)用.北京:清華大學(xué)出版社，2012.）

王東風(fēng)博士，華北電力大學(xué)控制與計(jì)算機(jī)工程學(xué)院教授.主要研究方向?yàn)槿褐悄軆?yōu)化算法和智能控制.

E-mail:wangdongfeng@ncepu.edu.cn

（WANG Dong-FengPh.D.，professor at the School of Control and Computer Engineering，North China Electric Power University.His research interest covers swarm intelligence-based optimization and intelligent control.）

孟 麗華北電力大學(xué)控制與計(jì)算機(jī)工程學(xué)院博士研究生.主要研究方向?yàn)橹悄軆?yōu)化算法及其應(yīng)用.本文通信作者.

E-mail:mengli2014@163.com

（MENG LiPh.D.candidate at the School of Control and Computer Engineering，North China Electric Power University.Her research interest covers swarm intelligence-based optimization and its application. Corresponding author of this paper.）

Performance Analysis and Parameter Selection of PSO Algorithms

WANG Dong-Feng1MENG Li1

Inertia weight and acceleration factors have significant impact on the performance of particle swarm optimization（PSO）algorithm.Through simulation experiments on twelve classical benchmark functions，this paper studies the algorithm′s exploitation ability and optimization performance with different parameters.Based on the experimental results，we recommend a setting for fixed parameters.Furthermore，we study the situation where inertia weight remains unchanged and acceleration factors change with iterations.Then a setting for varying parameters is recommended.The recommended parameters setting methods are verified through 15 benchmark functions that were published in CEC2015. At the end of the paper，a discussion of the PSO application issue on continuous optimization problems and discrete optimization problems is given.

Particle swarm optimization（PSO），exploitation ability，optimization performance，parameter selection

Manuscript November 18，2015；accepted March 26，2016

10.16383/j.aas.2016.c150774

Wang Dong-Feng，Meng Li.Performance analysis and parameter selection of PSO algorithms.Acta Automatica Sinica，2016，42（10）:1552-1561

2015-11-18錄用日期2016-03-26

國家自然科學(xué)基金（61203041），教育部高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金（20120036120013），中央高校基本科研基金（20140139）資助

Supported by National Natural Science Foundation of China（61203041），Specialized Research Fund for the Doctoral Program of Higher Education（20120036120013），and the Fundamental Research Funds for the Central Universities（20140139）

本文責(zé)任編委董海榮

Recommended by Associate Editor DONG Hai-Rong

1.華北電力大學(xué)自動化系保定071003

1.Department of Automation，North China Electric Power University，Baoding 071003