進化狀態判定與學習策略協同更新的二進制粒子群優化算法

李浩君，何佳樂，聶新邦，楊 琳

(浙江工業大學 教育科學與技術學院，浙江 杭州 310023)

粒子群優化算法(PSO)是一種模擬鳥類群體社會行為的智能搜索算法[1]，通過群體內個體之間的信息共享對問題的解進行協同搜索。該算法除了具有結構簡單、控制參數少、全局尋優能力突出等優點，還具備計算速度快、參數較少、實現方便等特點[2]，自提出以來便引起了國內外學者的廣泛關注，在不同領域都得到快速廣泛的應用。但是該算法在搜索過程中存在過早收斂或陷入局部極優的問題，因此需要對PSO算法進行優化研究。對粒子群算法的優化，最初都是通過對速度、位置更新公式中的參數進行修改，以達到算法優化的目的，如：Zhang等[3]通過在標準粒子群速度更新公式中引入活躍目標點，提出了具有新學習目標點的粒子群優化算法(APSO)，種群在進化過程中，構成了基于三目標點的速度迭代機制，使個體同時向三個優化位置學習。由于不同的算法優化的強度不同，可以學習或結合其使用的策略來進行優化與改進。Liang等[4]提出三種學習策略的粒子群算法：精英粒子群算法(ELPSO)、多標榜學習粒子群算法(MELPSO)和全面學習粒子群算法(CLPSO)，每種算法使種群中每個粒子向其余不同粒子的歷史最優位置的不同維數學習，隨機進行獨立升級，保證了種群收斂過程中的多樣性；劉衍民等[5]提出一種基于自適應動態鄰居廣義學習粒子群算法(ADPSO)，使種群粒子向全局、自身和鄰域最優粒子學習，并在新產生的粒子位置上添加隨機位置以增加粒子跳出局部最優區域的概率；高潁麗等[6]提出了一種融合分類優化與拓展策略的粒子群優化算法，采取一種正態演化變異策略，搜索當前最優粒子的鄰域空間，增強局部開采能力以避免算法陷入局部最優；何通能等[7]設計了一種改進型粒子群算法，通過引入遺傳算法中的交叉變異策略來增強算法收斂速度和精度得到近似最優解，提高算法優化的準確性。

除了考慮單個粒子的優化，學者針對全局粒子以及鄰域內的其他粒子的影響因素對粒子群算法進行了優化。Peram等[8]提出了一種基于適應度值與粒子距離之比的粒子群優化算法(FDRPSO)，算法選擇當前鄰域中適應度值之差與粒子距離比值最大的個體作為種群新的全局學習目標nbest，使整個種群同時向pbest，gbest和nbest學習，從而增加種群多樣性，提高了尋優性能；Mendes等[9]認為在進化過程中種群個體行為并非僅受某個特定粒子個體的影響，而是會受其所有鄰域中的個體最優點影響，并根據該理論提出了全信息粒子群優化算法(FIPSO)，改善了整個種群的學習能力；Zhan等[10]提出了一種正交學習粒子群算法(OLPSO)，通過正交試驗設計來尋求粒子個體的歷史最佳位置和鄰域最佳位置的最優組合，引導粒子更加快速地穩定，向全局最優位置靠近；董輝等[11]在傳統的粒子群算法中引入小生境思想對各子群進行單獨優化，并取出最好粒子形成新群體，再運用蛙跳算法進行優化；彭建新等[12]提出了一種基于全局信息的改進粒子群優化算法，采用所有粒子的歷史最優平均值作為引導個體飛行速度的一個因素，形成全局信息，增強了種群的多樣性。PSO算法存在早熟、易陷入局部最優的問題，其主要原因是在優化過程中種群喪失多樣性。保持種群多樣性是增強算法全局搜索能力、避免出現早熟現象的重要措施，因此筆者在粒子群優化算法迭代過程中采用基于進化狀態信息判定的學習策略更新機制，提出一種進化狀態判定與學習策略協同更新的二進制粒子群優化算法。進化狀態判定的收斂階段采用全信息學習策略，粒子i速度和位置的更新受適應度值更優鄰域粒子的影響，提高了收斂速度；進化狀態判定的跳出局部最優階段采用局部信息學習策略，維持種群多樣性避免算法陷入局部最優。

1 進化狀態判定與學習策略協同更新的二進制粒子群優化算法

與傳統粒子群算法不同，改進算法利用種群進化狀態信息選擇合適的學習策略。當進化狀態大于固定閾值時，判定算法處于收斂階段，采用全信息學習策略，依據更優鄰域粒子的信息更新速度和位置，以加快算法收斂速度；當進化狀態小于固定閾值時，判定算法處于跳出局部最優階段，算法采用局部信息學習策略，依據局部最優和最佳鄰域粒子的信息更新速度和位置，以維持種群多樣性，使算法不易陷入局部最優。

1.1 進化狀態分析

利用進化狀態可以有效提高算法的性能[13-14]。種群多樣性減少是粒子群算法陷入局部最優的主要原因，針對這一特性和迭代次數與種群多樣性的線性關系定義進化因子E，其計算式為

(1)

(2)

(3)

1.2 鄰域選擇策略

迭代過程中，針對二進制粒子群算法編碼特性計算各粒子與其他粒子的海明距離，并對其進行排序，依據排序結果求出給定粒子指定個數的鄰居。

Dij=H(xi,xj)j=1，…，N;j≠i

(4)

S=sort(D)

(5)

Neighbors=S(1∶T)

(6)

式中：Dij表示第i個粒子與種群中第j個粒子之間的海明距離；H為計算海明距離的函數；S為對排序結果的集合；Neighbors表示當前鄰域粒子；T為指定鄰居數量。

1.3 全信息學習策略

全信息粒子群算法(FIPSO)具有較快的收斂速度，但在算法后期容易陷入局部最優[9，15]。為更好地解決離散問題，在BPSO的基礎上采用全信息學習策略以保證算法的尋優能力和收斂性能。算法迭代過程中，粒子i從適應度值更優的鄰域粒子處獲取信息，同時避免受不良鄰域粒子的影響，適應度值越優的鄰域粒子對粒子i的影響越大[16]。基于以上思想，ELBPSO采用全信息學習策略，其速度與位置更新表達式為

(7)

(8)

(9)

依據相關文獻，采用收斂系數X和加速度系數φ調節粒子速度，算法性能較佳[9,17]，其中X=0.729，φ=4.1；ki為粒子i更優鄰域粒子的個數；im為粒子i的第m個更優鄰域粒子；pim為粒子im的位置，f(pim)為的適應度值，sumi為更優鄰域粒子適應度值的總和；rm表示均勻分布于[0,1]之間的數。

1.4 局部信息學習策略

采用局部信息學習策略可以很好地維持種群多樣性[17-18]。粒子i依據局部最優和最佳鄰域粒子的信息更新速度和位置，受其他粒子的影響較小，可以在搜索空間更加自由地移動，有利于維持種群多樣性。ELBPSO采用局部信息學習策略其速度與位置更新的表達式為

(10)

式中：pi為粒子i的局部最優位置；pinb為粒子i鄰域的最優位置；r1和r2表示均勻分布于[0,1]之間的數。

1.5 進化狀態判定與學習策略協同更新的二進制粒子群優化算法

理想的粒子群算法應當在保證較快收斂速度的同時不易陷入局部最優，采用單一學習策略很難實現這種狀態，因此筆者提出一種進化狀態判定與學習策略協同更新的二進制粒子群優化算法，在不同的進化狀態下采用不同的學習策略來解決復雜的最優化問題。Zhan等[19]將種群迭代過程的進化狀態分類為收斂、探索、開發、跳出局部最優4 個階段，并以進化因子0.7為界點對跳出局部最優階段進行區分。針對粒子群算法存在早熟、易陷入局部最優的問題，將粒子群迭代過程分為跳出局部最優和收斂兩個階段。Zhan等[19]同時對進化狀態進行劃分，若進化因子E<0.7，判定算法處于跳出局部最優階段，表明種群多樣性較差，應選擇局部信息學習策略，保證粒子可以在搜索空間更加自由地移動，以維持種群多樣性；若進化因子E>0.7或E=0.7，判定算法處于收斂階段，表明種群多樣性較好，應選擇全信息學習策略，保證粒子從適應度值更優的鄰域粒子處獲取信息以加速收斂。改進算法的步驟為

步驟1種群初始化。種群規模設置為20，學習因子均固定為2，迭代次數300，維度300。

步驟2進化狀態判定。計算進化因子E，若E<0.7，則判定算法處于跳出局部最優階段；若E≥0.7，則判定算法處于收斂階段。

步驟3粒子速度更新。若算法處于跳出局部最優階段，采用式(10)更新粒子速度；若算法處于收斂階段，采用式(7，8)更新粒子速度。

步驟4粒子位置更新。采用式(9)更新粒子位置。

步驟5重復步驟2～5，直到滿足終止條件。

步驟6滿足終止條件(達到最大迭代次數)，輸出最優值并求出相應目標函數值，算法結束。

ELBPSO算法中進化狀態判定是平衡收斂與跳出局部最優的關鍵，進化狀態判定與學習策略協同更新的二進制粒子群優化算法的優化機制如圖1所示。

圖1 算法優化機制Fig.1 Algorithm optimization mechanism

2 實驗仿真及分析

2.1 實驗設置

2.1.1 測試函數

為了評估改進算法的性能，筆者選擇廣泛使用的8 種基準函數進行測試，包括單峰函數F1，F2，F3，復雜的多峰函數F4，F5，F6，最優值不為0 的函數F7和F8。與連續空間中的粒子群優化算法不同，用于離散空間的二進制粒子群算法中粒子的取值只有0和1，具體基準函數及其參數如表1所示。

表1 基準函數及其參數Table1 Benchmark function and its parameters

2.1.2 對比算法參數設置

為了進一步驗證所提算法性能，筆者選擇以下3 種算法作為對比算法：BPSO，FIBPSO和SIBPSO算法，并從最優值、均值、平均誤差、P值4 個方面判斷這4 種算法的優劣。BPSO屬于基本的二進制粒子群算法；FIBPSO為采用全信息學習策略的二進制粒子群優化算法；SIBPSO為采用局部信息學習策略的二進制粒子群優化算法；筆者所提出的ELBPSO算法依據種群進化狀態選擇合適的信息學習策略。

拓撲結構的密集程度會影響粒子群算法的性能[15,18]，當鄰域粒子數量為5時可以很好地平衡粒子群算法的探索與開發過程。參照對比算法文獻，本次實驗所有算法的粒子種群規模均為20，最大迭代次數300，領域粒子數量5，維度300，BPSO采用線性遞減的慣性權重調整方案。4 種算法的參數設置如表2所示。

表2 算法參數設置Table 2 Algorithm parameters set

2.2 實驗結果及分析

表3為BPSO，FIBPSO，SIBPSO和FIBPSO算法求解F1～F88個基準函數所獲得的均值和方差，最優值用加粗表示，所需算法的實驗數據均為在實驗平臺上獨立運行30 次獲得。

表3 仿真實驗結果Table 3 Simulation experimental results

由表3可知：從整體來看，不管在單峰、多峰還是最優值不為0的測試函數中，BPSO算法方差均最小，表現出良好的穩定性，ELBPSO次之，其他算法穩定性較差，這是因為BPSO采用傳統學習策略不易受其他粒子影響，求解穩定，而其他算法依據鄰域粒子來更新速度和位置，接收的信息較多，導致最優解波動較大。在F1～F88個基準函數上，ELBPSO算法得到的均值最小，對問題的適應能力更強。該算法依據種群進化狀態選擇合適的信息學習策略，在保證收斂精度的同時不易陷入局部最優，優化了算法性能。

圖2為4 種算法在8 種基準函數上、維度為300的情況下所生成的函數值收斂曲線。

圖2 算法收斂曲線Fig.2 Algorithm convergence curve

圖2可以更加直觀地了解這4 種算法的收斂過程。由圖2可知：FIBPSO采用全信息學習策略，受其他粒子的影響較大，前期收斂快但適應度值較大且不再變化，容易陷入局部最優；SIBPSO采用局部信息學習策略，受其他粒子的影響較小，前期收斂速度較慢但后期全局探索能力較強；ELBPSO算法在幾乎所有的單峰函數、多峰函數上都顯示出了極佳的搜索性能，全局探索和局部開發能力優于對比算法。這是因為在迭代過程中算法依據種群進化狀態選擇合適的信息學習策略，在保證算法收斂性能的同時維持了種群多樣性，增強了算法的全局搜索能力，使其跳出局部最優。對于不為0的測試函數F7，F8，改進算法ELBPSO的尋優優勢不夠明顯，但從總體來看其具有更強的適應性和尋優性。基于進化狀態判定的學習策略更新機制可以有效平衡BPSO的全局和局部搜索能力，提高算法的尋優能力和尋優精度。

為對比4 種算法所得結果是否具有統計學意義上的顯著性差異，對4 種算法結果進行了威爾科克森符號秩檢驗，檢驗結果如表4所示。

表4 威爾科克森符號秩檢驗結果Table 4 The result of Wilcoxon signed-rank test

由表4可知：除了BPSO與FIBPSO在少部分函數不存在顯著性差異外，其他任意算法之間都存在顯著差異。對比實驗結果均值及P值可以證實筆者所提出的ELBPSO算法性能明顯優于其他對比算法，說明基于進化狀態判定的學習策略更新機制對二進制粒子群算法性能的提升是有效的。

圖3為4 種算法在8 個基準函數上的解集箱圖。

圖3 算法最優解統計分布圖Fig.3 Algorithm optimal data distribution map

圖3可以更加直觀地對比4 種算法解集的分布情況。由圖3可知：從整體來看，所有算法中ELBPSO更加接近橫坐標軸，與圖2的檢驗、收斂曲線一致，驗證了該算法的收斂性能遠優于其他算法；從解集分布來看，BPSO分布較小而其他算法分布較廣，與表3的方差一致；BPSO，FIBPSO以及SIBPSO在最優值不為0的F7，F8函數表現穩定，但在其他函數出現了異常值，且有時不止一個，ELBPSO在最優值不為0的F7，F8函數都出現了一定的異常值，在最優值為0的F1，F3函數雖出現了異常值，但數量不多，說明對大多數測試函數來說ELBPSO的穩定性和收斂性效果較佳，BPSO雖穩定性較好，但解集質量尋優性遠不及ELBPSO算法。因此，ELBPSO算法具有收斂快、尋優強、穩定性較好的優點，是一種有效的算法。

2.3 參數敏感性檢驗

2.3.1 控制系數k檢驗

為了檢驗式(3)中調整系數k的敏感性，采用相同實驗條件選取函數F1，F5，對筆者所提ELBPSO算法進行30 次實驗，觀察k變化時算法最優解均值的變化，結果如表5，6所示。

表5 k變化時F1函數最優解均值

表6 k變化時F5函數最優解均值

圖4為不同k值下F1，F5函數最優解均值的變化情況。

圖4 不同k值下算法最優解變化情況Fig.4 Algorithm optimal solution average change for different k values

由圖4可知：隨著k值的變化ELBPSO算法的收斂精度發生了很大的改變，k的取值在1～2時改進算法最優解均值較為良好，否則尋優性能下降，不具備明顯優勢，說明ELBPSO算法對k值具有一定的敏感性。實驗中取k=2。

2.3.2 進化因子檢驗

依據進化因子對種群進化狀態進行判定是信息學習策略更新的關鍵。ELBPSO中進化因子判定值越小，采用全信息學習策略的機會就越大，利于算法收斂，但易陷入局部最優；判定值越大算法選擇局部信息學習策略的機會就越大，利于維持種群多樣性，使算法跳出局部最優，但收斂性能不佳。為了檢驗進化因子判定的最佳狀態和敏感性，在相同實驗條件下調整E的判定值，對所提ELBPSO算法進行30 次試驗，觀察E值變化。計算F1，F5函數最優解均值，結果如表7，8所示。

表7 E變化時F1函數最優解均值

表8 E變化時F5函數最優解均值

由表7，8可知：當進化因子E=0.7時ELBPSO在F1，F5函數最優解均值最小，算法性能最好。

圖5為不同E值下F1，F5函數最優解均值的變化情況。

圖5 不同E值下算法最優解變化情況Fig.5 Algorithm optimal solution average change for different E values

由圖5可知：ELBPSO的最優解均值隨著E的變化而發生波動，說明進化因子判定值的變化對函數求解影響較大。E為0.7時可以很好地平衡收斂并跳出局部最優，因此實驗取E=0.7。

3 算例分析

為檢驗優化方法的實踐性能，筆者從網絡上挑選部分學習資源，利用以上算法給學習者進行推薦。學習資源包含媒介類型、難度水平、內容類型屬性，學習者包含學習風格、能力水平、認知水平屬性，學習資源推薦本質是對學習資源屬性、學習者屬性進行匹配，求出差異最小解，確保推薦資源的屬性與學習者特征屬性相匹配。為提高算法求解效率，構建目標函數將資源推薦問題抽象為數學問題，問題求解的適應度值越低表明學習資源越符合學習者特征，利于個性化學習。實驗設置124 個學習資源，各算法尋優得出的推薦資源序列結果如圖6所示，1表示向學習者推薦對應序號的學習資源，0表示不推薦。

圖6 不同算法下學習資源推薦結果Fig.6 Learning resource recommendation result under different algorithm

由圖6可知：改進算法能準確求解優化問題，表明了算法執行邏輯的正確性；不同算法推薦資源的序號、數量各不相同，推薦結果存在較大差異。

圖7為各算法求解資源推薦問題的適應度值。

圖7 學習資源推薦適應度值Fig.7 Learning resource recommendation fitness value

由圖7可知：ELBPSO算法求解的適應度值最低，SIBPSO算法和BPSO算法次之，FIBPSO算法的求解結果最大，表明筆者改進的算法不僅能對優化問題成功尋優，同時也具備良好的尋優性能。

4 結 論

筆者依據種群進化狀態采用學習策略更新機制對二進制粒子群算法進行優化，有效平衡了收斂與跳出局部最優的狀態，在保證算法具有較強開發能力的同時，提高了算法后期全局探索的能力，避免陷入局部最優。實驗結果表明：ELBPSO算法對單峰函數和多峰函數具有更高收斂速度和精度，但對復雜的最優值不為0的函數改進優勢不夠明顯，仍有很大的改進空間，今后將對這類問題的優化進行更加深入的研究。