李龍澍，張效見

LI Longshu1，2,ZHANG Xiaojian2

1.安徽大學 計算智能與信號處理教育部重點實驗室，合肥 230039

2.安徽大學 計算機科學與技術(shù)學院，合肥 230601

1.Key Laboratory of Intelligent Computing and Signal Processing,Anhui University,Hefei 230039,China

2.School of Computer Science and Technology,Anhui University,Hefei 230601,China

1 引言

PSO算法是一種尋優(yōu)算法，于1995年由Eberhart和Kennedy首次提出[1-2]。它源于模擬魚類和鳥類的尋食行為[3]。PSO算法具有操作簡單、魯棒性強和易于實現(xiàn)等優(yōu)點，優(yōu)化性能較好，常用于解決多峰值、不可微和非線性等問題，并在工程和科學領(lǐng)域得到廣泛應用，如函數(shù)優(yōu)化[4]、排列[5]和神經(jīng)網(wǎng)絡(luò)[6]等。

雖然PSO算法優(yōu)化性能較好，但是在尋優(yōu)求解進程中，不能很好地平衡粒子的搜索行為，存在易陷入局部極值的缺陷。對此，研究人員提出了諸多改進方法，主要分為以下兩類：第一類是在PSO算法速度迭代公式中增加慣性權(quán)重ω，以更好地平衡粒子的搜索行為。近年來，研究人員對慣性權(quán)重進行了廣泛研究[7-10]。例如，文獻[7-8]提出慣性權(quán)重線性減少方法，以提高尋優(yōu)性能，并被廣泛應用，稱之為標準PSO算法。但在該算法中，如果粒子在尋優(yōu)初期搜索到的位置不夠好，易陷入局部極值。文獻[9-10]對慣性權(quán)重采用指數(shù)減少方法，減少了算法陷入局部極值的概率。另一類是引入其他優(yōu)化方法，文獻[11]在PSO算法中引入兩種混沌優(yōu)化策略，提高了收斂精度。文獻[12]在PSO算法中引入GA算法的變異和交叉操作，提高了收斂性。基于以上研究，本文針對PSO算法易陷入局部極值的缺陷，提出了一種新的自適應慣性權(quán)重混沌PSO算法（a New Chaos Particle Swarm Optimization based on Adaptive Inertia Weight，CPSO-NAIW）。實驗結(jié)果表明，CPSO-NAIW算法能有效避免陷入局部極值，提高算法性能。

2 PSO算法

PSO算法可具體表述如下：首先初始化種群粒子，然后每一個粒子通過追逐個體和群體極值位置，即粒子本身和整個粒子種群當前找到最優(yōu)解的位置，來更新粒子的位置和速度，最后不斷迭代直到找到在指定閾值的最優(yōu)位置。在種群規(guī)模為M，解空間為D維的PSO算法中，設(shè)第i粒子個體和群體極值位置分別為Pi和G，在d維的位置和速度分別為xid和vid，xid和vid的更新公式如下：

3 CPSO-NAIW算法

介紹了慣性權(quán)重線性減少方法的缺點，然后提出了一種根據(jù)粒子與群體極值位置距離進行權(quán)重調(diào)整的方法，該方法更好地平衡了粒子的搜索行為，減少了算法陷入局部極值的概率，最后針對算法如何擺脫局部極值的問題，提出了一種基于混沌優(yōu)化擺脫局部極值的方法，該方法通過引入混沌優(yōu)化策略，在算法陷入局部極值時，對群體極值位置進行調(diào)整，以使粒子經(jīng)歷新的搜索鄰域和路徑，增加算法擺脫局部極值的可能。

3.1 自適應慣性權(quán)重

在PSO算法尋優(yōu)迭代中，應用較多的是慣性權(quán)重線性減少方法，然而，PSO算法的尋優(yōu)進程是非線性且十分復雜的，線性減少的方法變化過于單一，造成其對非線性、復雜尋優(yōu)進程的調(diào)節(jié)和適應能力有限，易陷入局部極值。因此，本文提出了一種新的慣性權(quán)重自適應方法（New Adaptive Inertia Weight，NAIW），NAIW計算方法如式（3）所示。

其中，ωmax和ωmin分別為慣性權(quán)重的最大和最小值，ωmax=0.9，ωmin=0.4[16]；Δxi為第 i個粒子與群體極值位置的距離，利用式（4）計算得到；為Δxi在t代中的值；iterNum為最大迭代次數(shù)；k為迭代系數(shù)，利用式（5）計算得到。NAIW方法通過粒子相對于群體極值位置的距離對權(quán)重進行動態(tài)調(diào)整，把權(quán)重的變化與粒子的位置狀態(tài)信息關(guān)聯(lián)起來，以更加精確地調(diào)整慣性權(quán)重。當較大時，即粒子距當前最優(yōu)解位置的距離較遠，則利用式（3）會賦予速度更新式（1）中較大的值，以使粒子獲得較大飛行速度，進而可以使其更快速地向當前最優(yōu)解位置靠近并保證了種群全局“探索”能力，當較小時，即粒子距當前最優(yōu)解位置的距離較近，則利用式（3）會賦予速度更新式（1）中較小的值，以使粒子獲得較小飛行速度，進而可以使其更加精細地搜索最優(yōu)解位置鄰域，保證了種群局部“開發(fā)”能力。同時，式（3）中的k值隨迭代次數(shù)的增加而減少，以保證算法在迭代初期和后期分別對較大和較小的需要[7-8]。通過以上調(diào)整權(quán)重的方法，增強了權(quán)重的自適應性，更好地平衡了粒子的搜索行為，減少了算法陷入局部極值的概率，提高了PSO算法的收斂性。

3.2 基于混沌優(yōu)化擺脫局部極值的方法

混沌是一種非線性的自然現(xiàn)象，具有隨機性、遍歷性等特點，可進行尋優(yōu)搜索[17-19]。

一個常用的混沌模型Logistic方程如下：

其中，μ為控制參量，當 0≤z0≤1，μ=4時，Logistic處于完全混沌狀態(tài)。式（7）為Logistic方程的一種演化形式[20]。

本文借鑒混沌現(xiàn)象隨機性和遍歷性的特點，提出了基于混沌優(yōu)化擺脫局部極值的方法。該方法通過群體極值位置連續(xù)未更新的代數(shù)SG與局部極值判定閾值SGmax進行比較來判定算法是否陷入局部極值[14]。若SG≥SGmax，則認為算法已經(jīng)或即將陷入局部極值；反之，則認為算法沒有陷入局部極值。當算法被判定為陷入局部極值時，首先利用式（8）把群體極值位置G映射到混沌變量定義域[0,1]內(nèi)，然后利用式（7）進行迭代運算，得到 M 個混沌位置(CG1,CG2,CG3,…,CGm)，最后利用式（9）進行逆映射，獲得 M 個新群體極值位置（G1',G2',G3',…,Gm'）。由于粒子通過追逐個體和群體極值位置來完成自我更新，當算法陷入局部極值時，群體極值位置一定在局部極值位置上，此時，采用混沌映射得到具有較強隨機性和遍歷性的新群體極值位置，并結(jié)合式（1）就可以改變粒子的尋優(yōu)軌跡，使得粒子i通過追逐新群體極值位置Gi'進行自我更新時，可在局部極值位置鄰域外的其他區(qū)域進行尋優(yōu)搜索，搜索新的鄰域和路徑。因此可以較大概率地發(fā)現(xiàn)更優(yōu)解，進而增加了算法擺脫局部極值的可能。

3.3 CPSO-NAIW算法執(zhí)行流程

本文從慣性權(quán)重的調(diào)整和如何擺脫局部極值兩個方面對PSO算法進行改進，提出了CPSO-NAIW算法，該算法的具體執(zhí)行流程如下。

輸入：算法迭代次數(shù)T、種群規(guī)模M。

輸出：最優(yōu)位置G。

（1）隨機初始化種群中粒子的速度和位置，初始化迭代次數(shù)、計數(shù)器和局部極值判定閾值為t=0、SG=0和SGmax=10[14]。

（2）初始化P為粒子當前位置，G為初始群體最優(yōu)粒子位置。

（3）對種群中所有粒子執(zhí)行以下操作：

②根據(jù)式（1）和式（2）更新粒子速度和位置。

③計算粒子適應度值 f，并更新粒子的P和G，如果G未更新，SG=SG+1，否則SG=0。

（4）如果 SG≥SGmax，利用式（7）～（9）對 G 進行混沌優(yōu)化生成G1',G2',Gi',…,Gm'，SG=0。

（5）t=t+1，如果 t＜T ，轉(zhuǎn)（3），否則，執(zhí)行（6）。

（6）輸出G，算法結(jié)束。

在CPSO-NAIW算法中，第（1）、（2）步對算法各個參數(shù)進行初始化，第（3）～（6）步對求解問題進行尋優(yōu)搜索。其中，第（3）步利用本文提出的新慣性權(quán)重自適應方法（NAIW）對粒子進行更新，第（4）步判斷算法是否陷入局部極值，若SG≥SGmax，則認為算法已經(jīng)或即將陷入局部極值，并利用本文提出的基于混沌優(yōu)化擺脫局部極值的方法來進行擺脫。

4 實驗結(jié)果與分析

首先介紹了實驗環(huán)境和算法參數(shù)設(shè)置，然后為了驗證本文提出的改進方法的有效性，采用6個經(jīng)典基準函數(shù)對算法性能進行測試?；鶞屎瘮?shù)信息見表1。并設(shè)計如下方案進行對比。方案1：對兩種改進方法分開進行測試，首先在標準PSO算法[7]（Standard Particle Swarm Optimization，SPSO）即線性減少慣性權(quán)重PSO算法的基礎(chǔ)上，對權(quán)重的調(diào)整采用本文提出的新自適應慣性權(quán)重方法，形成PSO-NAIW算法，然后在SPSO算法基礎(chǔ)上，加入本文提出的基于混沌擺脫局部極值方法，形成CPSO算法，最后把本文提出的兩種改進方法綜合起來，形成CPSO-NAIW算法并把它們與SPSO算法進行對比測試。方案2：為展示本文CPSO-NAIW算法的先進性，將CPSO-NAIW算法與一些具有代表性的新近改進PSO算法，即IAW-PSO[21]、高速收斂PSO算法（表示為FPSO）[14]、PDNPO-PSO算法[22]和SPSO算法進行對比測試。

表1 基準函數(shù)

4.1 實驗環(huán)境與參數(shù)設(shè)置

實驗采用C#編寫，實驗環(huán)境為（M490）CPU 3.20 GHz Inter core i5和4 GB RAM。PSO-NAIW、CPSO、CPSONAIW以及SPSO算法參數(shù)設(shè)置如下：慣性權(quán)重最大和最小值分別為ωmax=0.9和ωmin=0.4；IAW-PSO算法參數(shù)設(shè)置如下[21]：慣性權(quán)重最大和最小值分別為ωmax=0.9和ωmin=0.2；迭代步數(shù)K1=60，K2=10；最大初始化次數(shù)kmax=200；FPSO算法參數(shù)設(shè)置如下[14]：慣性權(quán)重最大和最小值分別為ωmax=0.9和ωmin=0.4；停滯上限MAX=10；PDNPO-PSO算法參數(shù)設(shè)置如下[22]：慣性權(quán)重最大和最小值分別為ωmax=0.9和ωmin=0.4；慣性權(quán)重取值范圍中間值ωs=0.65；上限控制參數(shù)k1=2；調(diào)節(jié)能力控制參數(shù)k2=1；個體學習因子的最大和最小值分別為c1max=2和c1min=0；群體學習因子的最大和最小值分別為c2max=2和c2min=0；振蕩周期L=300。所有算法的種群規(guī)模M為30；學習因子c1=c2=2。

4.2 PSO-NAIW、CPSO、CPSO-NAIW和SPSO算法對比測試

為了測試PSO-NAIW、CPSO和CPSO-NAIW算法性能，本文設(shè)置以下實驗進行對比分析。

實驗1 PSO-NAIW、CPSO、CPSO-NAIW和SPSO算法在迭代1 000次的情況下，對6個基準函數(shù)進行尋優(yōu)搜索，每個算法進行20次獨立實驗，取各個函數(shù)最終結(jié)果的平均（Mean）和最優(yōu)（Opt）值進行比較。實驗結(jié)果如表2所示。

實驗2 PSO-NAIW、CPSO、CPSO-NAIW和SPSO算法在固定目標精度下（各個函數(shù)目標精度如表1），對6個基準函數(shù)進行尋優(yōu)搜索，每個算法進行20次獨立實驗，取各個算法達到目標精度時的平均迭代次數(shù)(Itr)、平均運行時間(t)及收斂率(CR)。其中，收斂率=達到目標精度次數(shù)/總實驗次數(shù)。算法2 000次迭代內(nèi)不收斂即視為當次實驗失敗，實驗結(jié)果如表3所示。

從表2中看出，雖然PSO-NAIW、CPSO和CPSONAIW算法在對函數(shù) f4和 f5測試時，與SPSO算法實驗結(jié)果相同，但是在其他4個函數(shù)上無論是最優(yōu)還是平均函數(shù)值都明顯優(yōu)于SPSO算法，并且CPSO-AIW算法實驗結(jié)果最優(yōu)。從表3中看出，雖然PSO-NAIW、CPSO和CPSO-NAIW算法在對函數(shù) f1～f5測試時，與SPSO算法的收斂率相同，但是PSO-NAIW和CPSO算法對于除函數(shù) f4外的其他4個函數(shù)，收斂速度更快、用時較少，并且，CPSO-NAIW算法對函數(shù) f1～f5的收斂速度最快、用時最少。同時在表3中還可以看出，PSO-NAIW、CPSO和CPSO-NAIW算法在對函數(shù) f6進行測試時，這三種算法相對于SPSO算法的收斂率更高、收斂速度更快、運行時間更短，并且CPSO-NAIW算法的收斂率最高、收斂速度最快、運行時間最短。綜上，可以得出，PSO-NAIW、CPSO和CPSO-NAIW算法在整體性能上優(yōu)于SPSO算法。這是因為PSO-NAIW算法根據(jù)粒子與群體極值位置距離來調(diào)整慣性權(quán)重，改善了權(quán)重的自適應性，更好地平衡種群的局部“開發(fā)”和全局“探索”能力，降低了算法陷入局部極值的可能。所以，算法用時較少、收斂精度和速度明顯提高。CPSO算法利用混沌現(xiàn)象隨機性及遍歷性的特點，在算法陷入局部極值時，對群體極值位置進行混沌優(yōu)化，以使粒子搜索局部極值外的新鄰域和新路徑，增強了算法跳出局部極值的可能。所以，算法運行時間短、收斂精度高且速度快。而CPSO-NAIW算法綜合了PSO-NAIW和CPSO算法的改進方法，所以具有最優(yōu)的收斂性能。

表2 實驗1結(jié)果

表3 實驗2結(jié)果

4.3 CPSO-NAIW、IAW-PSO、FPSO、PDNPOPSO和SPSO算法對比測試

為了驗證本文CPSO-NAIW算法性能，在6個基準函數(shù)上對本文CPSO-NAIW與IAW-PSO、PDNPO-PSO、FPSO和SPSO算法進行20次獨立實驗，每次實驗迭代1 000次。實驗結(jié)果如圖1～6所示。由圖1～3可知，對于函數(shù) f1～f3，本文CPSO-NAIW算法不僅求解精度高且收斂速度快。由圖4和圖5可知，本文CPSO-NAIW算法對函數(shù) f4和 f5的求解都達到了相應理論極值，并且對于函數(shù) f5，本文CPSO-NAIW算法收斂速度更快。由圖6可知，雖然5種算法對于函數(shù) f6求解效果都不理想，但是本文CPSO-NAIW算法的求解精度和收斂速度明顯優(yōu)于其他4種算法。因此本文提出的CPSO-NAIW算法具有很好的收斂性能。

圖1 f1函數(shù)

圖2 f2函數(shù)

圖3 f3函數(shù)

圖4 f4函數(shù)

圖5 f5函數(shù)

圖6 f6函數(shù)

5 結(jié)論

本文針對PSO算法易陷入局部極值的缺陷，提出了一種新的自適應慣性權(quán)重混沌PSO算法（CPSO-NAIW）。該算法首先采用新的權(quán)重自適應方法（NAIW），通過粒子與群體極值位置距離對權(quán)重進行調(diào)整，使權(quán)重的調(diào)整與粒子的狀態(tài)位置狀態(tài)信息相結(jié)合，更好地平衡粒子的全局和局部搜索行為，在提高算法自適應性的同時減少了其陷入局部極值的概率，然后采用基于混沌優(yōu)化擺脫局部極值的方法，該方法在算法陷入局部極值時，對群體極值進行混沌調(diào)整，以使各個粒子在追逐不同群體極值位置進行更新時，可以改變尋優(yōu)軌跡，提高了算法擺脫局部極值的能力。實驗結(jié)果表明，本文CPSO-NAIW算法，克服局部極值的能力更強，在收斂性能上更優(yōu)。然而，本文CPSO-NAIW算法存在著穩(wěn)定性不足問題，后續(xù)工作會針對該問題進行相關(guān)研究。

參考文獻：

[1]Zhang Y，Gong D W，Ding Z.A bare-bones multi-objective particle swarm optimization algorithm for environmental/economic dispatch[J].Information Sciences，2012，192（6）：213-227.

[2]湯可宗，柳炳祥，楊靜宇，等.雙中心粒子群優(yōu)化算法[J].計算機研究與發(fā)展，2012，49（5）：1086-1094.

[3]Nickabadi A，Ebadzadeh M M，Safabakhsh R.A novel particle swarm optimization algorithm with adaptive inertia weight[J].Applied Soft Computing，2011，11（4）：3658-3670.

[4]陳得寶，趙春霞.階梯型粒子群算法及在函數(shù)優(yōu)化中的應用[J].系統(tǒng)仿真學報，2007，19（24）：5659-5662.

[5]Goudos S K，Rekanos I T，Sahalos J N.EMI reduction and ICs optimal arrangement inside high-speed networking equipment using particle swarm optimization[J].IEEE Transactions on Electromagnetic Compatibility，2008，50（3）：586-596.

[6]Bashir Z A，El-Hawary M E.Applying wavelets to shortterm load forecasting using PSO-based neural networks[J].IEEE Transactions on Power Systems，2009，24（1）：20-27.

[7]Shi Y，Eberhart R C.Empirical study of particle swarm optimization[C]//Proceedings of the Congress on Evolutionary Computation，1999：32-49.

[8]Eberhart R C，Shi Y.Comparing inertia weights and constriction factors in particle swarm optimization[C]//Proceedings of the Congress on Evolutionary Computation，2000：84-88.

[9]Pediwal J，Mahor A，Khatri N.Exponential decreasing inertia weight particle swarm optimization in economic load dispatch[J].International Journal of Engineering Innovations&Research，2012，1（5）：380-384.

[10]Ting T O，Shi Y，Cheng S，et al.Exponential inertia weight for particle swarm optimization[C]//International Conference in Swarm Intelligence，2012：83-90.

[11]劉道華，原思聰，蘭洋，等.混沌映射的粒子群優(yōu)化方法[J].西安電子科技大學學報：自然科學版，2010，37（4）：764-769.

[12]雷秀娟，付阿利，孫晶晶，等.改進PSO算法的性能分析與研究[J].計算機應用研究，2010，27（2）：453-458.

[13]丁旭，吳曉蓓，黃成.基于改進粒子群算法和特征點集的無線傳感器網(wǎng)絡(luò)覆蓋問題研究[J].電子學報，2016，44（4）：967-973.

[14]朱海梅，吳永萍.一種高速收斂粒子群優(yōu)化算法[J].控制與決策，2010，25（1）：20-24.

[15]呂振肅，侯志榮.自適應變異的粒子群優(yōu)化算法[J].電子學報，2004，32（3）：416-420.

[16]敖永才，師奕兵，張偉，等.自適應慣性權(quán)重的改進粒子群算法[J].電子科技大學學報，2014，43（6）：874-880.

[17]Ying Song，Chen Zengqiang，Yuan Zhuzhi.New chaotic PSO-based neural network predictive control for nonlinear process[J].IEEE Transactions on Neural Networks，2007，18（2）：595-601.

[18]Zhou Keliang，Qin Jieqiong.PID controller parameters tuning of main steam temperature based on chaotic particle swarm optimization[C]//IEEE International Conference on Computer Science and Automation Engineering（CSAE），2011：647-650.

[19]唐賢倫，周維，張衡，等.一種基于多目標混沌PSO的機器人足球防守策略[J].系統(tǒng)仿真學報，2014，26（1）：51-55.

[20]莫愿斌，陳德釗，胡上序，等.混沌粒子群算法及其在生化過程動態(tài)優(yōu)化中的應用[J].化工學報，2006，57（9）：2123-2127.

[21]杜繼永，張鳳鳴，李建文，等.一種具有初始化功能的自適應慣性權(quán)重粒子群算法[J].信息與控制，2012，41（2）：165-169.

[22]朱喜華，李穎暉，李寧，等.基于群體早熟程度和非線性周期振蕩策略的改進粒子群算法[J].通信學報，2014，35（2）：182-189.