具備預(yù)判能力和向最小距離學(xué)習(xí)的粒子群算法

舒小麗，劉衍民，張倩

（1.貴州民族大學(xué)數(shù)據(jù)科學(xué)與信息工程學(xué)院，貴陽 550025；2.遵義師范學(xué)院數(shù)學(xué)學(xué)院，遵義 563006；3.貴州大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，貴陽 550025）

0 引言

粒子群算法［1］（PSO）是模擬了鳥類在群體中的捕食行為，它將群體中的鳥看作是無質(zhì)量的粒子，通過群體中粒子之間的相互合作和信息交流來尋找最佳食物的位置。由于粒子群算法相對簡單，易于實(shí)現(xiàn)，且沒有太多的控制參數(shù)需要調(diào)節(jié)。1995年由Kennedy和Eberhart正式提出以來，吸引了眾多研究者對此進(jìn)行研究。多次模擬實(shí)驗(yàn)結(jié)果顯示，該算法對于解決大多數(shù)優(yōu)化問題都有較好的優(yōu)化效果。目前被應(yīng)用于控制系統(tǒng)、預(yù)測時間、動態(tài)車輛路徑以及其他算法領(lǐng)域。但是，PSO算法在復(fù)雜的多峰問題上還存在多樣性差、易早熟收斂、精度低等一系列問題，為了解決這些問題，提升算法的運(yùn)行效果，研究者們提出了許多該算法的改進(jìn)。①參數(shù)改進(jìn)：Kennedy等［2］人在1998年提出了線性慣性權(quán)重因子，改進(jìn)了早期粒子群算法收斂性慢的問題；②拓?fù)浣Y(jié)構(gòu)：根據(jù)拓?fù)浣Y(jié)構(gòu)的不同對粒子群算法進(jìn)行改進(jìn)，比較經(jīng)典的是分為局部的拓?fù)浣Y(jié)構(gòu)和全局拓?fù)浣Y(jié)構(gòu)，它們的差異是學(xué)習(xí)樣本的選擇不同，該方法對于不同的問題表現(xiàn)出不同的優(yōu)化效果；③多群粒子群算法：VAN［3］和劉衍民［4］將種群分為多個種群，由種群之間信息共享，提高算法的運(yùn)行效率，它們與原始的粒子群算法相比性能有顯著提高。

本文在研究者研究的基礎(chǔ)上，結(jié)合SHI［2］和張津源［5］提出了具備預(yù)判能力和向最小距離學(xué)習(xí)的粒子群算法。該算法中首先粒子根據(jù)每個粒子的個體極值對自己下一代的尋優(yōu)做一個預(yù)判；其次，粒子的社會部分學(xué)習(xí)對象是從預(yù)判的方向上選取最小距離，這些策略可很大程度上提高粒子的尋優(yōu)精度。

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

標(biāo)準(zhǔn)的粒子群算法與最先提出的粒子群算法相比，前者在速度更新時的記憶項(xiàng)中多了一個慣性權(quán)重，即w。w的大小影響著粒子的搜尋能力。當(dāng)w較大時，具有很好的全局搜尋能力，而局部搜尋能力較弱；當(dāng)w較小時，局部搜尋能力較強(qiáng)，全局搜尋能力較弱。因此，選擇合適的w值有助于平衡PSO算法的全局尋化能力和局部尋優(yōu)化能力。PSO算法的速度和位置更新方程如下：

其中，a1、a2為學(xué)習(xí)因子；r1、r2為［0,1］中均勻分布的參數(shù)；Pit表示粒子i在尋優(yōu)過程中時刻t經(jīng)歷的最佳位置，稱為粒子的“自我認(rèn)知項(xiàng)”。Gt表示尋優(yōu)過程中群體在時刻t經(jīng)歷的最好位置，稱為粒子的“群體認(rèn)知項(xiàng)”，也稱為社會學(xué)習(xí)部分。

2 具備預(yù)判能力和向最小距離學(xué)習(xí)的粒子群算法

2.1 預(yù)判

在尋優(yōu)過程中，PSO算法的粒子根據(jù)式（1）和式（2）更新其速度和位置。由于粒子在尋優(yōu)過程中受個體極值和群體最優(yōu)的整體指導(dǎo)，使得對粒子的每一維度過程的關(guān)注極少，特別在復(fù)雜的多峰問題上。又由于粒子在尋優(yōu)過程中產(chǎn)生很大的隨機(jī)性，使得粒子收斂到最佳位置更加艱難。比如在群體尋優(yōu)過程中：粒子剛開始運(yùn)動的方向是向著群體最優(yōu)解的方向前進(jìn)的，但由于尋優(yōu)過程的復(fù)雜性和隨機(jī)性，在進(jìn)行到某代時可能會偏離最優(yōu)解的方向，如若繼續(xù)使用式（1）更新速度，由于上一代錯誤信息的指導(dǎo)，必將導(dǎo)致收斂速度慢、精度不高等問題。

為解決這個問題，粒子在下一次更新迭代時會進(jìn)行一個預(yù)判，即通過監(jiān)督粒子在進(jìn)化過程中的運(yùn)動方向以及運(yùn)動位置，對下一代實(shí)施干預(yù)，以防被錯誤信息指導(dǎo)。本文的預(yù)判策略是：首先規(guī)定個體極值的維度為正時是該維度較好的方向，反之，故粒子在下一次尋優(yōu)時對各個粒子的個體極值每一維度進(jìn)行預(yù)判，對維度為正的，則不改變方向，對維度為負(fù)的則改變該維度的方向。即面對個體極值中維度較差的方向時，則向反方向?qū)?yōu)。面對個體極值中維度較好的方向時，尋優(yōu)方向不變。

2.2 具備預(yù)判能力和向最小距離學(xué)習(xí)的粒子群算法（MDPSO）

當(dāng)前的研究者所做的研究中，種群速度更新的社會部分都采用了整個維度的更新策略。但在面對復(fù)雜的多維函數(shù)優(yōu)化問題時，該方法可能會因?yàn)榫S間的相互干擾導(dǎo)致某些正確的尋優(yōu)維度的信息被掩蓋。從文獻(xiàn)［3］推斷出，如果每個粒子速度更新都向群體最優(yōu)學(xué)習(xí)，將會造成“steps foward，one step back”的現(xiàn)象。雖然下一代的函數(shù)值更好了，但可能有的維度信息比上一代更差了，這造成了好的維度信息的丟失。

根據(jù)粒子群算法的特點(diǎn)，個體極值既然是粒子歷史過程中經(jīng)歷的最好的位置，并且全局最優(yōu)也是從個體極值中挑選出來的，那么每個粒子的個體極值中都隱藏著較好的解的信息。又因?yàn)槊總€粒子的個體極值各不相同，在尋優(yōu)時為群體提供了多種選擇。在以上實(shí)施預(yù)判的基礎(chǔ)上，粒子從每個粒子的個體極值中逐一挑選距離最小值作為粒子在該維度的學(xué)習(xí)對象。在每一維度都確定后，就組成了一個新的維度，稱為“最小距離”，用Z表示。由于新的Z是從每個個體極值的每一維度挑選出最小距離組成的。故該策略能有效的提高算法的尋優(yōu)速度。新的學(xué)習(xí)策略速度更新如下：

2.3 MDPSO算法流程

MDPSO算法在尋優(yōu)過程中，每個粒子根據(jù)個體極值與最小距離Z調(diào)整其飛行方向，并逐步逼近最優(yōu)解。

（1）初始化種群，設(shè)置a1、a2和w，并計(jì)算其適應(yīng)值。

（2）粒子實(shí)施預(yù)判，確保向正確的方向飛行，并找出Z。

（3）使用式（3）、式（2）更新粒子的速度與位置。

（4）更新個體極值和全局最優(yōu)。每次迭代后，如果粒子當(dāng)前位置的適應(yīng)值小于該粒子歷史最佳位置的適應(yīng)值，則用當(dāng)前的位置更新個體極值，否則不更新；如果粒子當(dāng)前位置的適應(yīng)值小于群體最優(yōu)位置的適應(yīng)值，則用當(dāng)前位置更新群體最優(yōu)位置，否則不更新。

（5）如果沒有達(dá)到給定閾值，則返回（2），反之，算法結(jié)束。群體最優(yōu)位置即是全局最優(yōu)解。

2.4 算法的復(fù)雜性分析

為了研究MDPSO算法復(fù)雜度是否比PSO算法的更加復(fù)雜，用T表示最大的迭代次數(shù)，po p表示種群規(guī)模，D表示粒子的維數(shù)，MDPSO算法在PSO算法的基礎(chǔ)上給粒子增加了一個預(yù)判行為，并對算法中社會部分的學(xué)習(xí)做了調(diào)整。其中MDPSO算法的復(fù)雜度計(jì)算為K1=O（po p×D×T），PSO算法的復(fù)雜度計(jì)算為k2=O（pop×D×T）。由于K1=K2，故從以上的推導(dǎo)可得MDPSO算法與PSO算法的復(fù)雜度相比并無差別。

3 實(shí)驗(yàn)設(shè)置與討論

3.1 檢測函數(shù)和算法的參數(shù)設(shè)置

本文選擇CEC2017年版中的檢測函數(shù)，具體如下：

Sum-of-different-power（F1），Zakharov（F2），High-condition-elliptic（F3），Ackley（F4），Rastrgin（F5），Expanded-sxhaffer-F6（F6），Bent-cigar（F7），Schaffer-f7（F8），Non-continypus-rataed-rastrigin（F9），Griewank（F10），并將MDPSO算法與5種具有代表性的改進(jìn)PSO算法進(jìn)行比較，這些算法分別 是：PSO1［2］、UPSO［6］、CLPSO［7］、CPSO［2］和wFIPS［8］。

為了使各算法的實(shí)驗(yàn)結(jié)果對比顯著，本文實(shí)驗(yàn)的相關(guān)數(shù)據(jù)設(shè)置如下：種群規(guī)模都為30，各算法在每個檢測函數(shù)上獨(dú)立運(yùn)行30次，每個檢測函數(shù)每次運(yùn)行6×104次函數(shù)評價，其他實(shí)驗(yàn)相關(guān)參數(shù)與算法在提出時一致。

3.2 實(shí)驗(yàn)結(jié)果及分析

3.2.1 收斂特性

為了展現(xiàn)各算法在上述參數(shù)設(shè)置下的收斂特性，圖1給出了這些算法在6×104次函數(shù)評價后的收斂特征曲線圖。

同時，為了檢驗(yàn)各種算法運(yùn)行結(jié)果之間的差異是否具有統(tǒng)計(jì)學(xué)意義，采用Wilcoxon秩和檢驗(yàn)對MDPSO算法得到的結(jié)果與其他五種改進(jìn)PSO算法中最好的一組結(jié)果進(jìn)行檢驗(yàn)。表1右側(cè)給出了檢驗(yàn)結(jié)果。其中h=1表示運(yùn)行結(jié)果有差異，h=0表示運(yùn)行結(jié)果沒有差異。

表1 各算法實(shí)驗(yàn)對比結(jié)果（平均值）

從表1和表2可以看出，本文提出的MDPSO算法在10個檢測函數(shù)上的性能表現(xiàn)相比其他5種PSO算法更加優(yōu)秀。其中在函數(shù)F1、F3、F7、F8上表現(xiàn)較為明顯，函數(shù)的均值與其他的各種算法中最好的結(jié)果分別降低了97、58、59和30個數(shù)量級，說明MDPSO算法在改善粒子群的尋優(yōu)能力較為顯著，在規(guī)避早熟問題上更加具有優(yōu)勢。

表2 各算法實(shí)驗(yàn)對比結(jié)果（最小值）

表1右側(cè)給出了Wilcoxon秩和檢驗(yàn)結(jié)果分析。除F6外，其余5種改進(jìn)的PSO算法中最好結(jié)果集與MDPSO算法的結(jié)果集的數(shù)據(jù)差異在95%置信區(qū)間內(nèi)具有統(tǒng)計(jì)學(xué)意義。

從圖1可以看出，除Ackley函數(shù)外，MDPSO算法在逐漸尋優(yōu)過程中取得了最好的運(yùn)行效果。尤其對于Zakharov，Schaffer-f7從一開始就表現(xiàn)出明顯的優(yōu)勢。這主要是預(yù)判行為找出了食物在每個維度上的較好方向，指導(dǎo)粒子向好的方向飛行，使粒子更容易找到較好的解。

圖1 檢測函數(shù)收斂特征圖

3.2.2 魯棒性分析

為了測試各種改進(jìn)的PSO算法在不同的函數(shù)上運(yùn)行是否具有穩(wěn)定性，選擇了3個單峰函數(shù)（Zakharov，High-condition-elliptic和Ackley）和3個多峰函數(shù)（Bent-cigar，Schaffer-f7和Griewank）。根據(jù)表1與表2的數(shù)據(jù)可以看出，wFIPS與其他算法相比效果不明顯。所以表3給出了MDPSO與4種算法獨(dú)立運(yùn)行60次的魯棒性分析結(jié)果，其中“FES”表示在算法達(dá)到給定閾值時的函數(shù)評價次數(shù)，“S”表示算法達(dá)到給定閾值的比例（單位：100%），各函數(shù)的閾值分別為1.81e+06、3.95e-04、3.7e-05、0.095、0.05和7.1e-05。

從表3可以看出：在單峰檢測函數(shù)中，對于Zakharov函數(shù)，僅僅只有MDPSO算法達(dá)到了給定閾值的比例是100%，但PSO和CLPSO也顯示了其較為穩(wěn)定。對于Expanded-sxhaffer-F6函數(shù)，UPSO和MDPSO達(dá)到給定閾值的比例是100%，但MDPSO運(yùn)用了較少的函數(shù)評價，另外PSO和CLPSO也顯示了其較為穩(wěn)定。對于Ackley函數(shù)，PSO和MDPSO達(dá)到閾值的比例是100%，UPSO和CLPSO也顯示了其穩(wěn)定性。在3個多峰函數(shù)中，僅僅只有MDPSO達(dá)到閾值的比例是100%。但UPSO在Bent-cigar也表現(xiàn)其穩(wěn)定性，且CLPSO和CPSO在Schaffer-f7也表現(xiàn)了其穩(wěn)定性。

表3 各種算法的魯棒性分析

從以上可知，不管從算法的收斂特性、尋優(yōu)能力還是從算法的魯棒性分析結(jié)果看，MDPSO算法都表現(xiàn)出一定的優(yōu)勢。

4 結(jié)語

為了解決由于PSO算法尋優(yōu)過程中的隨機(jī)性和在更新時對粒子的整體指導(dǎo)而導(dǎo)致粒子在尋優(yōu)過程中易早熟收斂、精度不高等問題。本文提出了MDPSO算法。該算法是由粒子預(yù)判出較好方向，再從個體極值中提取每個粒子的有效信息指導(dǎo)粒子的社會部分學(xué)習(xí)。并通過Wilcoxon秩和檢驗(yàn)和基準(zhǔn)函數(shù)尋優(yōu)實(shí)驗(yàn)表明，該算法不管在單峰函數(shù)還是多峰函數(shù)相比其他算法都表現(xiàn)出一定有效性和優(yōu)越性。因此，MDPSO算法可以作為求解多峰和單峰問題的一種有效的方法。