一種動態鄰域自適應粒子群優化算法

楊穎穎，陳壽文

粒子群優化算法（Particle Swarm Optimization，PSO）［1］是由 Eberhart和 Kennedy于 1995 年提出的一種隨機優化算法，該算法源于對鳥群和魚群覓食行為的模擬，因為它具有工作原理簡單、程序實現簡易、以及計算參數少［2］等優點，所以被廣泛地應用于科學和工程領域［3］.然而，迭代過程中群體多樣性逐漸降低，使得算法易于陷入局部最優解.針對PSO算法的這一缺陷，很多學者開展了增強群體多樣性以平衡算法全局搜索能力和局部搜索能力的研究，在一定程度上既提高了PSO算法尋優精度又加快了算法收斂速度，例如：湯可宗等［4］引入了廣義中心粒子和狹義中心粒子，設計了個體極值和全局極值的更新策略，提出了增強群體多樣性的雙中心粒子群優化算法，改善了PSO算法的收斂速度和精度；陶新民等［5］利用小尺度變異算子完成搜索局部精確解，大尺度變異算子實現快速發現全局最優解，均勻算子維護種群多樣性，設計了一種結合多尺度變異算子和均勻算子來實現局部解逃逸的協同變異機制，提出了粒子群優化算法MAEPSO，提高了算法的收斂速度及穩定性；唐娜等［6］通過設計部分群體跟蹤適應度值較高優秀個體來保持群體多樣性的搜索機制，多種群之間通過全局最優解來實現信息交換，提出了自適應混沌搜索的雙粒子群優化算法，提高了算法的收斂速度和精度.上述研究結果表明增強群體多樣性在一定程度上既提高了PSO算法尋優精度又加快了算法收斂速度.本文運用粒子聚集度因子［7］來監測群體多樣性，利用全局版PSO和局部版PSO這兩種算法各自優點，通過監測粒子聚集度因子實現了一種動態鄰域調度策略（Dynamic Neighborhood Scheduling Strategy，DNSS），進而基于DNSS設計了一種動態鄰域自適應粒子群優化算法（Adaptive PSO based on DNSS，APSOD）.用Sphere等六個函數來測試，通過與算法DIWPSO等的比較，實驗結果顯示APSOD算法具有較強的尋優能力和穩定性.

1 粒子群優化算法及群體反饋參數

1.1 粒子群優化算法

粒子群優化算法中，每個個體被抽象為一個具有位置和速度的粒子，粒子位置代表待求解問題的一個候選解.記為第i粒子直到第t次迭代為止所發現的最優位置，gbest為群體迄今為止所發現的最優位置.粒子分別用（1）式和（2）式來更新自身速度和位置，習慣上稱這種算法為全局版PSO.

其中，和分別為第t次搜索中第i粒子位置和速度，c1為粒子自身學習因子，c2為粒子社會學習因子，r1和r2均為[0,1]中的隨機數，ω為慣性權重，Shi等［8］所提出的DIWPSO算法中ω按照（3）式來計算.

其中，ωmax和ωmin分別為慣性權重的初始值和終止值，t和T分別為當前迭代次數和最大迭代次數.

1999年，Suganthan［9］提出了一種基于鄰域操作的局部版PSO（Local version PSO，LPSO），其基本思想是隨著迭代次數的增加，各個粒子鄰域從自身開始增至整個群體，粒子分別用（4）式和（2）式來更新自身的速度和位置.

1999年，Clerc［10］提出了帶有約束因子的PSO算法（記為CPSO），粒子分別用（5）式和（2）式來更新自身的速度和位置.

Eberhart和Shi對算法DIWPSO和CPSO進行了比較研究，驗證了后者是前者對應慣性權重為0.729的一種特殊表現形式［11］.

1.2 粒子聚集度因子

群體進化過程中的多樣性可由群體聚集程度來體現，群體多樣性越大則越分散分布，多樣性越小越密集.通過監測群體聚集程度可以觀察到群體多樣性的動態變化，張選平等［7］定義了按照（6）式來計算的粒子聚集度因子s，并用該因子來監測群體聚集程度.

其中，N為粒子總數為第i粒子第t次迭代時的適應度，f( )gbestt為直到第t次迭代粒子群所發現的最優解所對應的適應度.

倘若適應度函數值在搜索空間恒大于0，則s∈(0，1],由（6）式可知，粒子聚集度因子s值越大，粒子群聚集度越大；當粒子群中的所有粒子具有同一性，則s=1.

2 一種動態鄰域自適應粒子群優化算法

2.1 動態鄰域調度策略

群體多樣性是影響粒子個體行為的一個關鍵因素.張選平等［7］用粒子聚集度來監測群體多樣性.本文設計動態鄰域調度策略的思想是：結合局部版PSO收斂精度高和全局版PSO快速收斂各自優點，選用環形和星形拓撲結構來構建不同的粒子鄰域，通過監測粒子聚集度因子來自適應地確定粒子鄰域.

從PSO算法運行過程來看，初始時，隨機初始化各粒子位置使得粒子聚集度較低；隨著算法迭代運行次數的增加，粒子逐漸向某一個或多個位置聚集，使得粒子聚集度呈現上升趨勢；迭代后期，粒子聚集度趨于最高值，算法也趨于收斂.粒子聚集度較低和較高這兩種情形可用來區分群體進化過程中多樣性.粒子聚集度因子（s）值越大，粒子聚集度越高.劃分s隸屬度區間后，s0＜s≤1和0＜s≤s0可相應地指代粒子聚集度較高和較低等2種情形.其中，s0為閥值，后續測試中s0為0.45.

局部版PSO中，粒子同時跟蹤自身所發現的、以及鄰域中粒子所發現的迄今為止最優位置pbest和lbest來更新自身速度，粒子鄰域拓撲結構不同，鄰域中所包含的其他粒子也各異.圖1（a）為粒子與前后位置相鄰半徑R為2的環形拓撲結構粒子鄰域示意圖，其中，群體規模假定為8，L{i}記錄了第i個粒子的鄰域中所包含粒子的編號.全局版PSO中，第i個粒子的鄰域中所包含粒子是群體除自身以外的其他粒子.圖1（b）中L{i}標記了第i個粒子鄰域內其他粒子的編號.

圖1 環形和星形拓撲結構粒子鄰域示意圖

全局版PSO中粒子通過與群體中其他各個粒子通信來加速粒子群收斂速度，使得該算法具有快速收斂特點.局部版PSO中鄰域粒子位置鄰接的若干粒子發生信息交互以提高粒子群尋優精度，使得該算法具有高精度收斂特征.本文結合全局版和局部版PSO各自優點，在粒子聚集度較低時，用星形拓撲結構來確定粒子鄰域，在粒子聚集度較高時，用環形拓撲結構來確定粒子鄰域，通過監測粒子聚集度因子，提出一種動態鄰域調度策略（Dynamic Neighborhood Scheduling Strategy，DNSS），對應粒子速度更新式如（7）式.

其中，t為當前迭代次數，s為粒子聚集度因子，s0為閥值，χ為約束因子且設定為0.729，lbest是由相鄰半徑R為2的環形拓撲結構所確定的粒子鄰域最優位置，其他參數函數同（1）式、（4）式和（5）式.

2.2 自適應粒子群優化算法

按照（7）式來確定粒子鄰域拓撲結構并更新粒子速度，本文設計了一種基于DNSS的自適應粒子群優化算法（Adaptive PSO based on DNSS，APSOD）.該算法的執行過程為①設定約束因子χ、最大迭代次數T和群體規模N；②初始化粒子群，隨機產生每個粒子的位置Xti和速度Vti；③評價各個粒子的適應度，并確定各個粒子的pbest和lbest或種群對應的gbest；④用（6）式來計算粒子聚集度因子s；⑤用（7）式和（2）式分別來更新粒子速度和位置；⑥判定終止運行條件是否滿足，若滿足，終止；否則，轉步驟3.

3 仿真實驗及結果分析

本實驗的運行環境為內存16G，Inteli7-7500U CPU 2.7GHz，Windows 10操作系統，算法采用Matlab R2018a實現.為了檢驗算法APSOD的有效性，用Sphere等6個函數來測試，并與算法DIWPSO和相鄰半徑R為2的環形拓撲結構所確定粒子鄰域的局部版PSO（記為LPSO-R2）進行比較.粒子群的適應度函數選用各測試目標函數，對應各測試函數及其屬性描述如表1所示.

設定c1=c2=2，S=40，D=30，算法DIWPSO對應ωmin=0.4，ωmax=0.9.以達到最大迭代次數T為算法終止運行判定條件，算法獨立運行30輪，記錄算法所有輪最后一次迭代所對應的群體最優適應度的最小值（Min）、均值（Ave）、中位數（Median）、最大值（Max）及標準差（Std）如表2和表3所示.

表1 測試函數及其屬性描述

表2 不同算法測試結果（S=40,D=30,T=3 000）

從表2和表3可以看出，比較的三個算法均能夠求解到f5的最優解；在求解函數f1～f4和f6最優解時，算法APSOD的Ave指標和Median指標均要小于其他兩個算法，這表明所比較的3個算法中APSOD算法的尋優精度最高.在求解函數f1～f3最優解時，APSOD算法的Std指標比DIWPSO和LPSO-R2算法的均要小，求解f4和f6最優解時，APSOD算法的Std指標比LPSO-R2算法的稍大，但這兩個算法的該項指標均小于DIWPSO算法.總體上來看，APSOD算法的穩定性強于其他兩個算法.

依次設定函數f1～f6的容許精度為10-40、10-20、0.5、0.05、10-50和5×10-12，算法終止運行的判定條件設定為所求解的測試函數達到容許精度且不超過最大迭代次數，算法獨立運行30輪，記錄函數評估次數平均值和成功可達率如表4所示.

從表4可以看出，就成功可達率指標來說，求解f1～f6函數最優解時，算法APSOD均能夠達到可容許的尋優精度，算法DIWPSO僅在求解f4和f5時能夠達到可容許精度，在求解其他4個函數時均不能達到，除函數f1和f3外，LPSO-R2算法均能夠達到可容許精度；就函數評估次數平均值指標來說，除求解函數f5外，算法APSOD的該項指標均要低于算法DIWPSO和LPSO-R2的，這表明所比較的三個算法在求解函數f1～f4和f6時，APSOD算法的收斂速度是最快的；就算法運行時間平均值指標來說，算法APSOD的該項指標要低于其他兩個算法，這也在一定程度上說明了APSOD算法收斂速度較快.

表3 不同算法測試結果（S=40,D=30,T=5 000）

表4 三個算法的函數評估次數平均值和成功可達率

另外，以Sphere和Ellipsoid為例，APSOD等3個算法對應的平均最佳適應度（f）的迭代如圖2所示.

圖2 函數Sphere和Ellipsoid測試30輪所對應的平均最佳適應度進化

由圖2可以看出，APSOD算法的平均最佳適應度比算法DIWPSO和LPSO-R2都要小，這說明算法APSOD的尋優能力比其他兩個算法都要強.由以上實驗結果及其分析可知，總體來說，所比較的三個算法中，APSOD算法尋優能力最強，尋優過程最穩定.這說明使用粒子聚集度因子判定群體狀態后，通過自適應調整粒子鄰域拓撲結構可增強粒子群多樣性，進而增強粒子群的尋優能力，算法APSOD是有效的.

4 結論

為了提高PSO算法的尋優能力，本文選用環形和星形拓撲結構來構建粒子鄰域，提出了一種動態鄰域調度策略DNSS，進而設計了基于DNSS的自適應PSO算法APSOD.使用6個基本函數進行測試，實驗結果顯示算法APSOD能增強尋優能力，且具有較強的穩定性，表明粒子感知鄰域聚集度以調整鄰域拓撲結構利于提高PSO算法尋優性能.進一步的測試將在今后的實際工程問題展開，如組合優化問題、車間調度問題等.