混合分層自主學習量子粒子群優化算法*

王文豐，徐燈，傅晶，韓龍哲，方宗華，董健華，章香

1. 南昌工程學院江西省水信息協同感知與智能處理重點實驗室，江西南昌 330099

2. 南昌工程學院信息工程學院，江西南昌 330099

粒子群算法因借鑒鳥群集體捕食的特性，便于理解、參數少且易實現，在科學研究與工程實踐中備受關注，譬如在路徑規劃、圖像處理［1］和洪水預報［2］等眾多領域中都得到了廣泛應用。然而，PSO 算法卻也存在著一些不足之處，如：前期因粒子的搜索范圍固定易陷入局部最優使其早熟、后期因粒子的搜索方式單一而導致粒子收斂速度較慢從而無法保證搜索精度等。

針對上述問題，國內外專家學者研究并提出了多種改進方法和策略。孫輝等［3］提出從維度值角度出發來提高種群的多樣性，為得到變異的新維度值，首先選取優質粒子，然后將粒子隨機的散落到不同的維度空間中，用列維飛行的方式從一個維度移動到另一個維度中，最終獲得了變異新維度。張鵬威等［4］為了加強離散型二進制板塊中粒子的全局搜索能力，采用了正弦映射和擴張算子的方法。Chen 等［5］采用基于位置的學習方法對種群進行初始化，并引入正余弦加速度系數來控制局部搜索范圍和全局最優解收斂速度。Hakl等［6］利用Levy 飛行策略改變固定步長的特性與PSO 算法結合來提高粒子的收斂精度。Liang 等［7］為加強粒子間信息交流能力使其多個小種群頻繁重組交流并使用擬牛頓法來增強局部搜索能力。上述研究對PSO 算法在種群跳出局部最優、粒子多樣性和參數設置等方面進行了改進，在一定程度上提高了算法的整體性能，但是依然有大部分的算法都有收斂速度慢，精確度低，過早成熟的各種問題，這些問題最常發生在高維函數優化問題上。

文獻［8］提出基于分層自主學習的粒子群優化算法HCPSO。該算法在一定數量種群粒子迭代過程中對種群進行階層劃分，并對劃分出的各粒子階層匹配合適的學習策略，從而提高粒子的學習效率，但同時由于中層粒子數較多，因此限制了粒子搜索能力。本文認為可以使用混合分層自主學習量子粒子群優化算法（HHQPSO）來解決問題，在保證粒子學習自主性的同時提升了算法全局搜索能力，提高了算法的穩定性以及收斂速度和精度，且在高維函數上有較好的適應性。

1 量子粒子群算法

量子粒子群算法［9］是信息學科交叉融合產生的一種新型粒子群算法，其引入量子力學的特性增強粒子間的信息交流，將粒子的搜索范圍明確化，從而使量子的搜索能力提升。量子粒子群算法相對于傳統粒子群算法來說多了一個量子空間概念，增加了一個引力場δ勢阱，在引力場的作用之下，所有的粒子向某一中心點靠近。在此過程中粒子的速度和位置出現的概率是確定的，而運動軌跡則可以使用波函數ψ來表示。因為有δ勢阱引力場的作用，所以粒子的運動方向就是朝著吸引點不斷地前進，粒子可以通過薛定諤方程來確定概率密度，而粒子的運動軌跡可以通過蒙特卡洛隨機模擬方式來描述，表示如下：

2 混合分層自主學習量子粒子群優化算法

2.1 混合量子粒子模型

2.1.1 粒子隨機位置更新策略的改進差分進化是根據生物進化理論，經過雜交、交叉和變異等行為之后，進化成能夠適應當前環境的優質粒子，進化之后的粒子具有更好的魯棒性。粒子的隨機位置會隨時改變，自然就導致了局部搜索能力較低的問題，為了解決這一問題，本文在差分策略的基礎上加入了縮放因子的方法，其計算公式如下

其中f表示的是當前粒子最優適應度值。

把小f和適應度均值對比，若f小于均值，就需要減少縮放因子，這樣在均值的附近就會分布更多的粒子，從而提高搜索的能力；相反，如果f大于均值，需要增大縮放因子，擴張了縮放因子，提高最優質的獲取幾率。查閱相關文獻之后發現文獻［11］，本文選取Fmax和Fmin的值分別為0.9和0.4。

2.1.2 粒子位置更新策略的改進Levy 飛行策略［12，13］是效仿生物尋找新食物的一種行為，其隨機的出現在某一地點且到下一地點的移動距離不確定，因此這一特征可以防止粒子容易陷入局部最優。粒子群中粒子的位置在更新的過程中經常會有固定步長變化的問題存在，所以本文用Levy 飛行策略來進一步的擴大搜索范圍，提高局部搜索的能力。

Levy飛行策略的分布方式是根據Levy規律來完成的，通過化簡與Fourier變換后，概率密度函數如下所示

式（8）中的概率分布是有寬尾的，尾翼的寬度比高斯分布和柯西分布要更大一些，所以從擾動能力上來看，這種概率分布要更強一點。通常使用Mantegna提出的Levy飛行路徑表達式：

2.2 分層自主學習

2.2.1 分層核心思想算法在一定數量種群粒子迭代過程中對種群進行階層劃分，并對劃分出的各粒子階層選擇合適的學習方法。在算法初始階段中，種群粒子是按照正態分布來確定搜索范圍的，最終集合的位置是唯一的，所以在最優的位置，粒子一般都比較稀少，同時也很難找到，只有很少部分的最優位置的粒子真正地能夠達到最優的位置上，而且也有一些粒子因為找不到最優的位置，所以在其他的地方徘徊。所以把處于最優位置附近的少數例子看成是上層粒子，為了提高局部范圍的搜索精度，使用局部學習模型；距離最優位置較遠的粒子叫做中層粒子，它通過混合量子粒子模型連接了群體信息中的粒子，這不僅僅是提高了局部的搜索精度，而且對全局的搜索精度也能起到優化的作用；而下層粒子指的是距離最優位置最遠的部分，而粒子的分布規律和位置的選擇是根據正態分布來完成的，可以有效地提高粒子搜索最優位置的速度。這種分層方式不僅能夠使種群類型更加豐富，同時粒子的收斂速度也得到了提升。

2.2.2 粒子分層策略及學習模型記fi表示第i個粒子適應度值，按照粒子適應度值大小，對粒子按照從小到大的方式排序，適應度值越接近最優位置，那么就越小，將更新之后的粒子序列記為X=｛x1，x2，…，xN｝，N表示的是粒子總數。下界和上界分別用low和up來表示，此時種群動態的三個階層就由圖1所示。

圖1 粒子分層示意圖Fig.1 Particle classification diagram

根據參考文獻［8］的內容，選取合適的low和up值，取值公式動態更新如下

其中countstart和countend分別為N/8和7N/8，t和T分別表示當前迭代次數和最大迭代次數。

據此，粒子分層策略和學習模型可以通過以下一些方式來表達。

1） 如果xi∈{x1，x2，…，xlow}，表示的是上層粒子，速度更新學習模型為

2.3 算法關鍵步驟

Step 1 粒子的參數設定，設置好隨機初始化種群中N個粒子的數值；

Step 2 粒子適應度值計算，確定并保存好局部和全局最優粒子的位置；

Step 3 將適應度值按照升值的方式排序，然后利用式（12）計算出粒子分層的下界和上界low、up值，將種群分成了上中下三層；

Step 4 粒子學習模型的選擇。參考粒子所在階層自適應的情況來選擇相應的學習模式：分布在上層階段的粒子，通過式（13）來計算粒子的速度和位置，找到最優粒子的位置和適應度值，然后按照要求保存好；分布在中層階段的粒子，使用式（6）和式（11）確定好隨機點的位置和粒子更新之后的位置，將最優的適應度值和位置確定下來，并且保存；處于下層階段的粒子，利用式（14）憂患粒子的位置，確定最優粒子的適應度值和位置，并且保存；

Step 5 對比這三個階層的最優適度值，選擇最小的，如果這一個粒子的全局最優值要比之前的要好，那么就保留更新之后的適應度值和位置，如果不如迭代前的適應度值，那么保留的是迭代前的粒子是適應度值以及位置；

Step 6 繼續根據Step 3～Step 5 的步驟來操作，直到迭代次數達到最大值，或者達到了其他的算法終止需求，就可以輸出，此時是最優解。

3 仿真實驗及分析

3.1 測試函數和參數設置

本文選取了單峰和多峰函數共9 個，都是CEC 2005 基準函數中的測試函數，如表1 所示。算法的參數設置：種群規模為40，c=1.5～3，c1=0.5～2.5，c2=0.5～2.5.

表1 基準測試函數Table 1 Benchmark function

3.2 仿真實驗及結果分析

PSO 算法選擇了最具代表性的5 個，分別是HPSO-TVC［14］、CLPSO［15］、LFPSO［6］、DMS-PSO［7］和RP‐SOLF［16］，參考文獻［17］是對比這些算法的結果之后得到的結果。本文選取的評價指標為最優適應值的平均值Mean和標準差SD，實驗結果見表2。

表2 算法實驗結果對比Table 2 Comparison of experimental results

從表中可以看出，如果評估次數固定，那么最優位置一般是在f1、f2、f3、f4、f5、f6、f8、f9中，求得的最優值精度也是最高的，這也就意味著粒子經過Levy 飛行策略的優化之后，粒子能夠抵抗干擾的能力得到了大幅度的增加。從標準差的穩定線上來看，LFPSO 要更好，但是f5（單峰）f6、f8、f9（多峰）的適應度值為0，為最佳的理論狀態。LFPSO 在多峰函數f9上求得的最優值精確度比HPSO-TVAC 和DMSPSO 算法求解要高出14個數量級，但是能夠達到最優值的測試函數，也只有f6，而RPSOLF算法求解得到的理論最優質值在多峰函數f6、f8、f9上都可以得出，這也就是說LFPSO 算法只有Levy 飛行策略在高危復雜度問題計算的過程中是不可行的。RPSOLF 通過三個測試函數求出理論最優質，但是從精確度上來看，HPSOTVAC 和DMSPSO 相對于函數f1、f2來說要更高一些。本文的最優值求解是通過函數f5、f6、f8、f9求出的，而最優的精確度最好的是函數f1、f3，這也就說明了本文所使用的算法分層策略更能夠求出最優粒子。

通過尋優曲線圖可以直接對比各算法在不同函數的收斂趨勢，本文把上述9個測試函數在6種算法上做收斂情況對比，如圖2所示，圖中FEs代表的是評估的次數，而每次評估之后得到的適應值用fitness表示。

從迭代曲線圖中可以了解到，在收斂速度和精度的問題上，f1、f2、f3、f4（單峰）和f7（多峰）的效果是最好的，這些函數得到的結果會更優（圖2 的（a）～（d）、（g））。雖然CLPSO 的收斂速度在f5（單峰）上表現的非常好，但是也無法比得上本次的算法（圖2 的（e）），所以下層粒子的最優位置，尋找速度最快的可以使用全局學習模型，并且是使用多峰函數f6、f8、f9求解，本次上最優理論值的過程中，當評估次數在5 000次之前就已經無限接近了（圖2的（f）、（h）、（i）），說明本分層策略的解決效率是最好的，并且中層粒子按照混合量子學習模型和改進位置之后，粒子之間的信息交流得到了進一步的加強和改善，使得粒子在前期不易陷入早熟，提高全局搜索能力從而找到更好的解。

圖2 各算法收斂效果對比Fig.2 Comparison of six algorithms on convergence

如前所述，HHQPSO 結合了HCPSO 和混合量子粒子策略，通過實踐表明，這種模型能夠使粒子的搜索特性得到加強，本文同時測試了單峰函數Sphere 和多峰函數Griewank，并且在實驗過程中出現的結果記錄下來，進行對比。實驗中的參數設置按照上述的要求來完成，得到了圖3的尋優曲線圖。

圖3 HHQPSO與HCPSO收斂效果比較Fig.3 Comparison of HHQPSO and HCPSO on convergence

由圖可知，單峰函數f1中，兩個算法在中前期的收斂情況基本一致，而在評估2.6萬次后，本文算法在收斂精度與速度上明顯優于HCPSO 算法，說明文中提出的混合量子粒子模型有效解決了粒子陷入局部最優位置的問題，因此該模型提高了粒子勘探能力；在多峰函數f9中，HHQPSO 算法在評估前期4 000 次左右時就求解得到理論最優值且收斂速度極快，反觀HCPSO 算法的收斂情況在前期也保持穩定的收斂速度，但在評估5 000 次左右時收斂速度變慢最后在評估2.5 萬次時陷入了局部最優。通過實驗表明，從全局搜索能力、收斂速度、精確度上來看，本文所使用的算法要更好一些，而且高維函數的開發能力要更好一點。

4 結 語

為了找到PSO 粒子分布過程中早熟，過于單一，迭代后期的收斂速度變緩的各種問題的解決方法，本文通過以下兩點方式來進行改進：第一，采用混合量子粒子自適應學習模型，中層粒子的數量和種類都得到了優化和充實，粒子的抗干擾能力也得到了進一步的加強，而且相對于普通的粒子來說，可以更快地獲得最優解；第二，使用的是粒子自主分層學習策略，根據距離最優位置的適應度值將種群分為上中下三層，在不同階層的粒子最優位置都不一樣，以此作為學習模型選擇的依據，有針對性地去提高粒子所在區域的搜索精度。這兩種方式的結合更好地開發種群的能力，同時還能夠提高種群的勘探能力。然后對比基準測試函數和HHQPSO 算法，從結果可以明顯看到基準測試函數的穩定性、收斂速度和精度都要更好一些。