一種慣性權重與種群多樣性協同調整的二進制粒子群優化算法

李浩君,張 廣,王萬良

1(浙江工業大學 教育科學與技術學院,杭州 310023) 2(浙江工業大學 計算機科學與技術學院,杭州 310023)

1 引 言

粒子群算法(Particle Optical Swarm)是由美國心理學家Kennedy和電氣工程師Eberhart[1]在1995年提出的一種演化計算技術,廣泛應用于電力、化工、經濟等工程領域的優化問題[2-4].由于實際當中很多問題并非是連續性的問題而是離散性的問題,Kennedy[5]又提出一種二進制粒子群算法,用來解決工程領域離散性的優化組合問題.不論是標準粒子群算法還是二進制粒子群算法,都是根據種群之間的信息來判斷搜索最優值,所以種群多樣性和搜索能力往往決定著粒子群算法的效率和準確度.但標準粒子群算法慣性權重值不能動態改變進而調整粒子群算法的搜索范圍,并隨著種群多樣性的下降,易過早陷入局部收斂,不能獲取最優值.針對粒子群算法的缺點,很多學者都提出了改進策略,首先Shi等學者[6,7]根據粒子群算法的迭代次數與多樣性之間的線性關系,動態改變標準粒子群的慣性權重值,權重值隨著迭代次數增加不斷下降,從而在算法前期以較大權重值提高粒子群算法全局搜索能力,在算法后期以較小權重值增加局部探索能力,但只根據粒子群與權重之間簡單的線性關系,還無法根據種群多樣性精確地調節權值.Riget等學者[8-10]提出基于粒子之間的歐氏距離判斷種群多樣性,動態調節算法的權重,但是又往往忽略的權重值與迭代次數之間的線性關系.目前有關二進制粒子群算法的種群多樣性與慣性權重相互影響的關系研究還比較少.部分學者[11-13]還引入混沌理論對粒子群的種群多樣性進行改進,但是缺少使用混沌理論對二進制粒子群算法的種群多樣性進行動態調整的研究.

本文提出一種基于種群多樣性與慣性權重協同調整的粒子群優化算法Coordinated Adjustment Binary Practical Swarm Optimization(CBPSO),根據二進制粒子群的海明距離均值和迭代次數變化動態調整權重值,再根據海明距離使用混沌理論動態調整種群多樣性,最后根據種群多樣性的變化在新的迭代中重新調整慣性權重值,從而改進種群無法有效探索以及隨著迭代次數增加種群多樣性過快下降的缺點,進而提高二進制粒子群算法的效率,實驗證明,該算法具有較好的準確性與魯棒性.

2 二進制粒子群算法優化的基本原理

粒子群算法以模擬鳥的群體智能為特征,每只鳥被稱之為一個粒子.粒子群優化算法首先初始化包含一群隨機的d維粒子的種群,每個粒子的每一維都由其速度和位置兩方面向量信息進行表示,第i個粒子的速度和位置表示如下:Vi=[vi1,vi2,…,vij],Xi=[xi1,xi2,…,xij].算法采用一個適應度函數來評價粒子當前位置的優劣,通過不斷迭代,最終找到最優解或近似最優解.在每次迭代中,粒子通過跟蹤個體最優解和群體最優解來更新自己的速度和位置.更新公式如下:

(1)

(2)

k迭代次數;c1、c2為學習因子;r1、r2是分布在[0,1]內的隨機數;pij為粒子本身找到的個體最優解;gij為整個粒子群中當前找到的群體最優解.

基本粒子群算法是針對連續域的問題設計的,但許多優化問題是針對離散的,因此文獻[5]對此進行了擴展,提出一種離散二進制BPSO算法,在二進制粒子群算法中,粒子運動的軌跡和速度是從概率角度定義的,每個粒子的每一位xi的取值為0或取1的概率 其基本公式如下:

(3)

S函數一般用Sigmoid函數表示,二進制粒子群算法的其他部分同基本粒子群算法.

3 協同調整的二進制粒子群優化算法

3.1 算法基本思想

粒子群算法運行時,在保持慣性權重不斷下降和粒子群逐漸收斂的趨勢下,當種群多樣性較差陷入局部最優時,需要對種群進行發散操作增加多樣性,慣性權重值也應該相應的增大,使粒子群在更大范圍內進行探索,從而能夠跳出局部最優;當種群多樣性較好,則通過海明距離均值和當前迭代狀態共同動態調整慣性權重值,從而平衡全局搜索和局部開發能力,使之逐步收斂至全局最優值.

本文采用這一研究思路對慣性權重和種群多樣性進行協同調整,提出根據每個粒子與最優粒子的海明距離均值與當前迭代狀態,動態協同調整粒子群慣性權重和多樣性的粒子群優化算法.首先使用混沌函數初始化種群;其次把海明距離均值與之前學者提出的慣性權重遞減方法結合,在保持慣性權重整體下降的前提下,根據海明距離均值變化更加有針對性的對慣性權重進行動態增減,從而更好平衡粒子群的全局搜索能力與局部開發能力;再次根據每個粒子和最優粒子的海明距離均值對種群多樣性進行動態調整,改善種群多樣性,防止過早收斂陷入局部最優,同時又不過度干擾粒子群算法不斷收斂的趨勢.最后根據種群多樣性的變化,在新的迭次過程中,對慣性權重值進行相應的調整.

3.1.1 混沌初始化

為了保持種群多樣性與遍歷性,用Logistic映射產生混沌序列X.

Xn+1=μXn(1-Xn)

(4)

X0=r and(0,1),μ=4且Xn≠0.25,0.75,0.5;如果Xn大于0.5,Xn等于1,反之等于0.

3.1.2 二進制粒子群多樣性和距離度量方法

為了表示兩個粒子之間的距離,引入了海明距離,定義粒子含有決策變量的個數即為粒子的維數,如Xij,其下標 i 表示群體中的第 i 個粒子,j 表示該粒子的第j個決策變量.若粒子的每一維決策變量用m個二進制位編碼表示,任意兩個粒子X1和X2的距離可由海明距離表示為:|X1-X2|=D(X1,X2).其中D是計算海明距離的函數,其值為兩個二進制位串中不同位的個數.為了降低計算的復雜度,計算每個粒子與全局最優粒子之間的海明距離均值來判斷種群的多樣性,并不是計算所有粒子之間的海明距離均值.

3.1.3 權重協同調整

通過海明距離均值、慣性權重與迭代次數之間的線性關系共同調節慣性權重,公式(5)的前半部分((1-e-HD/k)*a)為通過海明距離均值的權重調節公式,公式(5)后半部分((1- t/T )(Wmax-Wwin)+Wwin)為通過迭代次數調整的調節公式.

W=((1-e-HD/k)*a)*((1-t/T)*(Wmax-Wwin)+Wwin)

(5)

其中HD為當前粒子與最優值粒子之間的海明距離均值,其值隨著多樣性變化動態改變.T為粒子群算法的最大迭代次數,t當前迭代次數,Wmax和Wwin為權重最大值和最小值,k用來調節指數函數對HD變化的敏感度,a用來調整公式(5)前半部分和后半部分共同變化的速率.

公式(5)慣性權重隨著海明距離均值和迭代次數共同變化,在搜索初期慣性權重W較大,使粒子群在可以在全局范圍內進行探索;在搜索中后期,隨著海明距離均值與迭代次數動態調整,有利于平衡粒子群全局探索和局部開發能力.

3.1.4 種群多樣性自適應調整

計算每個粒子與全局最優粒子之間的海明距離均值HD,然后設定閾值D的變化區間.如果HD小于閾值,對種群多樣性進行發散調整,同時閾值動態減小.由于二進制粒子群算法的隨機性,其他算法如加速度調節算法、權重自適應調整[14,15],對參數的變化區間都是根據大量實驗觀察設定.本文根據大量實驗觀察設定閾值D的范圍.

3.2 算法步驟

步驟1.混沌初始化

對所有粒子用公式(4)混沌初始化位置.

步驟2.初始化種群參數

初始化粒子群的個體學習因子和社會學習因子值、迭代次數、Fitness數值精度、加速度值為位于區間(0,1)隨機值,初始權重值設為1.

步驟3.初始化閾值

設定閾值下限為粒子維度的1/7,上限為粒子維度的4/7.

步驟4.計算初始化適應度值

根據初始化的粒子位置與速度,帶入適應度函數,求出適應度值.如能滿足要求則終止,不能滿足要求則繼續執行.

步驟5.計算海明距離均值并排序

計算每個粒子與全局最優粒子之間的海明距離均值,并按與最優粒子之間的海明距離對粒子群從小到大排序.

步驟6.慣性權重協同調整

按公式(5)計算慣性權重的值,并且判斷慣性權重w的值是否在范圍Wmax和Wwin之間,如果大于Wmax,則值為如果小于Wwin,則值為Wwin,根據慣性權重調整策略對權重進行動態調整.

步驟7.粒子位置速度更新策略

速度更新公式:

(6)

位置更新公式:

(7)

步驟8.種群多樣性自適應調整

如果海明距離均值HD小于動態閾值,對種群按海明距離由小到大排序,取前50%種群再次進行混沌化處理,如果海明距離均值HD大于閾值下限,D減去1.

步驟9.終止條件判斷

判斷算法是否達到最大迭代次數或者適應度值滿足要求,如果滿足就轉步驟十.否則就轉步驟五,并重新計算海明距離均值,并根據海明距離均值重新計算新的慣性權重值;

步驟10.輸出數據

輸出全局最優解,并求出相應的目標函數值,算法結束.

圖1 函數均值收斂曲線Fig.1 Convergence curve of function mean

表1 算法在Sphere函數上實驗結果Table 1 Algorithm results on the Sphere function

表2 算法在Rosenbrock函數上實驗結果
Table 2 Algorithm results on the Rosenbrock function

F4D=30，M=10，Imax=100D=50，M=30，Imax=300D=100，M=50，Imax=10000均值方差成功率耗時/s均值方差成功率耗時/s均值方差成功率耗時/sCBPSOBPSOIBPSO760088009700268E+05308E+05368E+050．370．280．253．02．62．6414004600052300134E+06160E+06196E+060．050．020．019．19．59．776E+0499E+0495E+04706E+05886E+05871E+050．030．010．00656679690

表3 算法在Rastrigrin函數上實驗結果
Table 3 Algorithm results on the Rastrigrin function

F2D=30，M=10，Imax=100D=50，M=30，Imax=300D=100，M=50，Imax=10000均值方差成功率耗時/s均值方差成功率耗時/s均值方差成功率耗時/sCBPSOBPSOIBPSO0．070．130．10605E?04983E?04810E?040．930．870．902．72．32．30．080．150．14677E?041083E?041035E?040．900．850．867．27．57．50．991．081．03204E?04110E?03518E?040．060．010．02635650652

表4 算法在Griewank函數上實驗結果
Table 4 Algorithm results on the Griewank function

F3D=30，M=10，Imax=100D=50，M=30，Imax=300D=100，M=50，Imax=10000均值方差成功率耗時/s均值方差成功率耗時/s均值方差成功率耗時/sCBPSOBPSOIBPSO0．00130．00190．0022263E?07198E?07335E?070．920．860．842．82．52．60．0070．0100．009354E?07867E?07565E?070．880．830．807．37．57．90．00010．00030．0002102E?08203E?08201E?080．050．010．01665671686

4 試驗及分析

4.1 實驗設置

二進制粒子群算法常用的實驗方法有基于Benchmark函數和背包問題兩種測試方法,本文選用基準函數進行測試,基本粒子群算法粒子初始值為實數,不同于基本粒子群算法,二進制粒子群算法初始粒子初始值為二進制值.選用廣泛使用的Sphere、Rastrigrin、Griewank、Rosenbrock函數對算法進行測試,其中Sphere、Rosenbrock為單峰函數,其它兩個函數為復雜的多峰函數.具體函數參數如表5所示.

表5 測試函數
Table 5 Test functions

函數名稱表達式極值SphereF1=∑Di=1x2i0RastrigrinF2=∑Di=1[x2i-10cos(2πxi)+10]0GriewankF3=1/400∑Di=1x2i-∏Di=1cosxii+10RosenbrockF4=∑Di=1(1-xi)2+100(xi+1-x2)20

算法的參數設置如下:Wmax=1.5,Wmin=0.5.Dmax=n/7,Dmax=4n/7,a=2,k=4.表1至表4中,D代表維度,M代表種群數量,Imax代表迭代次數.本文引入Shi和Eberhart提出的慣性權重改進算法[6]進行對比,文中命名此算法為IBPSO.

本次實驗采用以下評價標準判斷三種算法的效率,評價標準如下:

1)最優值:算法迭代t次收斂后,適應度函數的最小值即最優值.

2)均值:算法執行n次后,n個最優值的均值.

3)方差:算法執行n次后,n個最優值的方差.

4)成功率:算法收斂至全局最優解次數與實驗次數的比值,再乘以100%.

5)耗時:算法執行n次后,收斂至全局最優解時,執行時間的均值.

算法仿真實驗環境為Windows10操作系統,編程語言環境Python3.3.硬件環境為intel酷睿處理器i5-2250,主頻為 2.50GHz,內存為4GB.

4.2 實驗結果及分析

表1-表4分別為四個基準函數在維度為30、50、100,不同迭代次數條件下,算法執行50次的均值、方差、耗時和成功率.對于復雜度不高的單峰函數Sphere,三種算法在不同維度下均能取得了較好的成功率,其中CBPSO算法成功率最高,均值和方差最小,BPSO和IBPSO算法相近,IBPSO算法效果稍好于BPSO算法,但效率提升并不大.

對于較難尋優的復雜函數及多峰函數,F3,F4,由表2至表4可以看出CBPSO算法均值最小,尋優成功率高.原因是CBPSO算法根據種海明距離均值和迭代次數兩種因素協同調整慣性權重,在迭代初期能以較大的慣性權重進行全局搜索,在迭代中后期慣性權重值能根據種群多樣性變化更加精準調整,且不會下降過早造成全局搜索能力過早下降.而IBPSO算法的尋優成功率不如BPSO,原因是IBPSO在迭代次數較少的情況下,如果權重值設置較小,權重值會根據迭代次數下降過快,在算法需要在全局搜索最優值的時候,不能在全局進行探索.

由于文中對Rosenbrock函數采用二進制方式編碼進行優化,適應度值呈階梯狀下降,所以均值和方差數值較大.

圖1為三種算法在維度為50的情況下,平均適應度值的收斂曲線.可以看出在相同的參數下,IBPSO算法收斂的平均代數最少,平均收斂值最小.由于迭代過程中通過對種群多樣性和慣性權重值的動態調整,單峰函數函數通過CBPSO算法尋優的過程中,適應度值變化較快,在提高收斂精度的情況下,尋優成功率也提高.對于其他函數,由于極值點分布在多峰的谷底,難以尋優,而CBPSO算法通過對多樣性調整,重新增加了種群多樣性,增大了慣性權重值,使算法可以跳出局部最優,重新探索全局最優值;在粒子群不斷收斂在局部尋找最優值時,慣性權重可以動態增減,使函數在谷底進行更好的局部探索.改變了IBPSO算法慣性權重下降過快、不夠準確的缺點.能更加精確根據對慣性權重和粒子群多樣性進行變化控制.

對比CBPSO、BPSO和IBPSO算法在種群數量為30,50,100時算法收斂時執行時間,對算法執行50次,得到算法收斂至全局最優解的平均執行時間,如表2所示:CBPSO算法執行時間開始略高于IBPSO、BPSO算法,原因是CBPSO 算法增加了種群多樣性,一定程度干擾了粒子群不斷收斂的趨勢,對于海明距離均值的計算增加了算法時間復雜度.但隨著資源數量增加帶來問題復雜度的增長,CBPSO算法對種群多樣性和慣性權重進行動態協同調整,從而使收斂更為準確的優勢展現出來,尤其在其他兩種算法陷入局部最優難以逃離的時,CBPSO算法更為快速的收斂至最優值,CBPSO算法在準確率提高的情況下,收斂至全局最優解的平均執行時間也逐步優于其他算法.

5 結束語

本文提出的CBPSO算法,利用海明距離均值提升粒子群的探索能力,實現了協同調整慣性權重值和粒子群種群多樣性的目標.實驗表明,本文提出的算法具有較高的精準度和較好的魯棒性,CBPSO算法在迭代過程中具有較好的跳出和探索能力,從而能在一定程度上提高種群多樣性與探索能力,提高搜索的準確度,獲得精確的適應度值.但本文的多樣性調整策略,在執行過程中存在調整次數過多導致時間復雜度較高的問題,在權重調整中,函數對海明距離變化敏感度不夠靈敏的問題,需要在以后工作中持續研究改進.

[1] Kennedy J,Eberhart R.Particle swarm optimization [C].IEEE International Conference on Neural Networks,Perth,Australia,Proceedings,IEEE,1995:1942-1948.

[2] Bharti K K,Singh P K.Opposition chaotic fitness mutation based adaptive inertia weight BPSO for feature selection in text clustering[J].Applied Soft Computing,2016,43(6):20-34.

[3] Li Tao-shen,Chen Song-qiao,Yang Ming,et al.Application of an improved particle swarm optimization algorithm in QoS anycast routing[J].Journal of Chinese Computer Systems,2010,31(1):67-71.

[4] Wu Yan-wen,Wang Jie,Wang Fei.Collaborative filtering recommendation model based on hybrid particle swarm optimization and genetic algorithm[J].Journal of Chinese Computer Systems,2017,38(3):527-530.

[5] Kennedy J,Eberhart R.A discrete binary version of the particle swarm algorithm[C].IEEE International Conference on Systems,Man,and Cybernetics,Computational Cybernetics and Simulation,IEEE,1997,5:4104-4108.

[6] Shi Y,Eberhart R.A modified particle swarm optimizer[C].IEEE International Conference on Evolutionary Computation Proceedings,IEEE World Congress on Computational Intelligence,IEEE,1998:69-73.

[7] Shi Y,Eberhart R C.Empirical study of particle swarm optimization[J].Frontiers of Computer Science in China,1999,3(1):31-37.

[8] Riget J,Vesterstr?m J S.A diversity-guided particle swarm optimizer-the ARPSO[J].Dept.Comput.Sci,Univ.of Aarhus,Aarhus,Denmark,Tech.Rep,2002,2:2002.

[9] Ursem R K.Diversity-guided evolutionary algorithms [C].International Conference on Parallel Problem Solving from Nature.Springer Berlin Heidelberg,2002:462-471.

[10] Ren Zi-hui,Wang Jian.An adaptive particle swarm optimization algorithm for dynamic change of inertia weight[J].Computer Science,2009,36(2):227-229.

[11] Cui X,Jiang M.Chaotic time series prediction based pn binary particle swarm optimization [J].Aasri Procedia,2012,1(3):377-383.

[12] Zhang T,Cai J D.A new chaotic PSO with dynamic inertia weight for economic dispatch problem[C].International Conference on Sustainable Power Generation and Supply,Supergen,IEEE,2009:1-6.

[13] Song Y,Chen Z,Yuan Z.New chaotic PSO-based neural network predictive control for nonlinear process[J].IEEE Transactions on Neural Networks,2007,18(2):595-600.

[14] Chih M.Self-adaptive check and repair operator based particle swarm optimization for the multidimensional knapsack problem [J].Applied Soft Computing,2015,26(1):378-389.

[15] Polprasert J,Ongsakul W,Dieu V N.Self-organizing hierarchical particle swarm optimization with time-varying acceleration coefficients for economic dispatch with valve point effects and multifuel options[C].Proceedings of the Fourth Global Conference on Power Control and Optimization,American Institute of Physics,2011:85-92.

附中文參考文獻：

[3] 李陶深,陳松喬,楊 明,等.改進的粒子群優化算法在QoS選播路由中的應用[J].小型微型計算機系統,2010,31(1):67-71.

[4] 吳彥文,王 潔,王 飛.混合粒子群遺傳算法的協同過濾推薦模型[J].小型微型計算機系統,2017,38(3):527-530.

[10] 任子暉,王 堅.一種動態改變慣性權重的自適應粒子群算法[J].計算機科學,2009,36(2):227-229.