GQPSO算法在動態(tài)環(huán)境優(yōu)化問題中的應用

王夢梅

摘要：動態(tài)環(huán)境優(yōu)化問題求解是近年來優(yōu)化領域的研究熱點。為了解決動態(tài)環(huán)境優(yōu)化問題中種群的早熟收斂現(xiàn)象，尋找3種學習策略更新種群中的吸引子，提出一種基于高斯分布的量子行為粒子群優(yōu)化算法（GQPSO）。在改進算法中，種群中粒子的吸引子由高斯公式產生。通過對比3種吸引子對算法的影響，確定了產生吸引子的最佳更新公式。此外，GQPSO算法中粒子的位置由概率密度函數(shù)以一定概率分散在搜索空間內，處于束縛狀態(tài)，因此可以增加種群多樣性以達到全局搜索，從而提高GQPSO算法在求解動態(tài)環(huán)境優(yōu)化問題上的收斂能力。

關鍵詞：高斯分布；粒子群算法；動態(tài)環(huán)境；優(yōu)化問題

DOIDOI：10.11907/rjdk.173334

中圖分類號：TP311

文獻標識碼：A 文章編號：1672-7800（2018）008-0035-05

英文摘要Abstract：Solving dynamic optimization problems （DOPs） has become a hot research area in recent years.In order to solve the precocious convergence of population in dynamic environment optimization problem，a Gaussian particle swarm optimization algorithm （GQPSO） based on Gaussian distribution is proposed.In GQPSO，the attractors of particles in the population are produced by gauss formulas，and updated by three learning strategies.By comparing the effects of three kinds of attractors on the algorithm，the optimal formula for generating the attractor is determined.In addition，the particle's position in GQPSO algorithm is scattered by the probability density function at a certain probability in the search space，and the particle is in the bound state，so it can increase the diversity of population to achieve global searching optimization to improve the ability of convergence of GQPSO algorithm in dynamic environment.

英文關鍵詞Key Words：Gaussian distribution； particle swarm optimization； dynamic environment； optimization problem

0 引言

近年來，動態(tài)環(huán)境優(yōu)化問題[1]（dynamic optimization problems，DOPs）已經(jīng)成為一個新的研究熱點。不同于靜態(tài)優(yōu)化問題[2]，DOPs的最優(yōu)解隨著目標函數(shù)、環(huán)境參數(shù)以及約束條件的變化而改變，在當前時刻得到的最優(yōu)解不一定是下一時刻的最優(yōu)解。因此，優(yōu)化算法不僅要在一個特定環(huán)境中找到最優(yōu)解，而且需要對最優(yōu)解變化軌跡具有追蹤能力。

為了提高量子行為粒子群優(yōu)化算法[3]解決動態(tài)環(huán)境優(yōu)化問題中收斂速度與跟蹤定位的能力，提出一種改進的量子行為粒子群優(yōu)化算法。通過分析量子行為粒子群優(yōu)化算法中單個粒子的運動行為，構造3種吸引子公式，并給出最佳吸引子的產生條件。然后根據(jù)吸引子的產生公式，提出一種全局搜索策略，分析粒子群的搜索軌跡及算法的性能評價標準。通過對標準測試函數(shù)的實驗仿真，驗證了改進算法對復雜動態(tài)環(huán)境優(yōu)化問題的快速收斂能力及高效跟蹤定位能力。

1 量子行為粒子群算法

Sun等[4]從量子力學的角度出發(fā)，基于提高PSO算法的收斂能力，提出了一種新的PSO模型——量子行為粒子群優(yōu)化（Quantum-behaved particle swarm optimization，QPSO）算法。QPSO算法一直受到眾多學者的廣泛關注，許多基于QPSO算法的改進算法及應用相繼被提出。2005年Sun等[5]基于高斯概率分布產生隨機數(shù)替代算法參數(shù)的方法，提出了一種保持種群多樣性的參數(shù)選擇方法，改進粒子的早熟問題；2007年孫俊等[6]提出QPSO算法中已壓縮膨脹系數(shù)值小于1.78時才能保證算法收斂，并提出兩種選擇控制參數(shù)的方法：線性遞減和非線性遞減。QPSO算法的應用已經(jīng)滲透到計算科學的各個領域，包括組合優(yōu)化、動態(tài)優(yōu)化、圖像圖形、神經(jīng)網(wǎng)絡、機器學習等。

QPSO算法中的粒子不需要粒子的速度信息，與PSO算法相比，具有控制參數(shù)少、收斂速度快、運算簡單等特點，是一種通用的優(yōu)化技術。實踐證明QPSO算法是一種快速全局收斂算法，能夠應用于各種復雜的優(yōu)化問題。若PSO系統(tǒng)是一個量子系統(tǒng)，在量子空間中粒子的速度和位置不能同時確定，每個粒子的運行狀態(tài)都由波函數(shù)ψ確定，ψ2是粒子位置的概率密度函數(shù)。通過代數(shù)和數(shù)學分析方法，Clerc等[7]研究了PSO系統(tǒng)中粒子運行軌跡，假定在第t次迭代，粒子i在D維空間運動，該粒子在第d維的勢阱為pid（t），那么在第t+1次迭代可以得到粒子i的波函數(shù)如式（1）。

（5）比較當前迭代全局最好位置與前一次迭代的全局最好位置，如果當前全局最好位置較好，則群體的全局最好位置更新為它的值。

（6）計算得到一個隨機點的位置。

重復（2）至（6），直至滿足一定的結束條件。

2 量子行為粒子群優(yōu)化算法的動態(tài)優(yōu)化

2.1 分層聚類策略

傳統(tǒng)的聚類方法一般以大量可用數(shù)據(jù)為基礎進行信息挖掘和實踐驗證。但在求解動態(tài)多峰優(yōu)化問題中，算法對于規(guī)避早熟以及在收斂速度與精度上仍然存在不足。目前經(jīng)常采用隨機選取粒子的方法對種群進行預先處理，或者檢測到環(huán)境變化后對種群進行隨機選取。該隨機選取策略具有一定盲目性和不確定性，優(yōu)化結果往往依賴于初始化種群的位置。本文采用分層聚類策略解決動態(tài)環(huán)境優(yōu)化問題，是一種產生多種群的有效方法[9]。在移動峰問題中，最優(yōu)解的適應值隨著峰的位置變化而改變[10]。分層聚類能夠產生多種群從而檢測峰的變化，并跟蹤最優(yōu)值的變化軌跡。首先，將初始種群中每個粒子都當作一個子類，然后根據(jù)子種群之間的距離，合并兩個子類為一個新的子種群，直到找到最優(yōu)解的位置。

由高斯公式產生GQPSO中的吸引子，能夠充分利用種群中粒子的個體最優(yōu)位置信息，保持粒子多樣性，從而提高算法解決動態(tài)環(huán)境優(yōu)化問題的能力。

根據(jù)以上討論分析，本文所提算法GQPSO的偽代碼見表1。

3 實驗結果及分析

3.1 算法性能測試

為了測試本文算法的性能，實驗設置了9種粒子群群體規(guī)模M（10，30，50，70，100，120，150，200）和8種初始聚類子群中粒子數(shù)max_subsize（2，3，4，5，6，7，10，12，15）。

從圖2的實驗結果對比可知，離線性能指標越小，說明算法性能越好。當山峰數(shù)為一個特定的值時，離線性能指標隨著粒子群粒子數(shù)的增長而增加。這是因為搜索區(qū)域內的粒子數(shù)目增多，聚類的子群就會增加，隨著算法迭代進行，種群能搜索的峰的數(shù)目也會增加收斂的種群增加，從而導致離線性能指標有所增長。此外，當移動峰數(shù)一定時，每當粒子群不同，最優(yōu)算法也是不同的。比如：當max_subsizeN=3、M=100時，算法性能最佳，而當max_subsizeN=7、M=200時離線性能最小，說明算法最佳。因此，由圖3-圖5可知，GQPSO算法能夠適應多種移動峰問題的求解。

3.2 參數(shù)設置影響

實驗主要測試算法中壓縮膨脹系數(shù)[13]對算法性能的影響，黑體數(shù)據(jù)則表示在不同峰值下，最佳壓縮膨脹系數(shù)得到的離線性能指標。由表2可知，對比所有數(shù)據(jù)，當算法中壓縮膨脹系數(shù)值設置為靜態(tài)值0.4時，得到離線性能指標最小，說明壓縮膨脹系數(shù)對算法求解動態(tài)優(yōu)化問題的全局搜索能力有一定影響；其值范圍越大，即當壓縮膨脹系數(shù)設置為線性遞減策略或者非線性遞減策略時，對應的離線性能指標的值比靜態(tài)參數(shù)策略大，也就說明短發(fā)的全局搜索能力越弱。當壓縮擴張系數(shù)的值設置為固定值0.4時，有3個最優(yōu)值存在（P=5、P=15、P=30），算法的全局搜索能力越強，算法快速找到峰數(shù)的能力就越強。

3.3 3種高斯吸引子對比

本組實驗旨在比較3種高斯分布吸引子[14]對算法的影響。表3中L1是第一種高斯分布，更新公式為式（16）；L2為第二種高斯分布，更新公式為式（17）；L3是第三種高斯分布，更新公式為式（19）。為對比每種吸引子算法的適應能力，本組實驗還給出了6種移動峰問題，從而證明GQPSO算法對復雜動態(tài)環(huán)境優(yōu)化問題的有效性。由表3所示，當吸引子確定時，隨著山峰數(shù)的增加，算法離線性能指標的值反而減小，說明該算法能夠適應復雜的移動峰問題，證明了算法的有效性和魯棒性。

對比3種吸引子的衰減趨勢（見圖3），第二種高斯分布吸引子L2的離線性能指標最低，說明當吸引子的方差為Cid（t）到pid（t）與pg_nearest，d（t）中點之間的距離時，算法結果最佳。因此，實驗結果證明，本文提出的高斯分布量子行為粒子群優(yōu)化算法在求解動態(tài)環(huán)境優(yōu)化問題中具有較好的性能。

3.4 算法比較實驗

該組實驗考察GQPSO算法處理不同環(huán)境變化頻率和變化強度的MPB性能。算法參數(shù)設置如下：粒子群數(shù)為120，環(huán)境變化設置為10、50、100、200，峰變化強度設置為0.05、0.5、1.0、2.0。環(huán)境變化強度是指峰的頂點位置移動的劇烈程度。表4是GQPSO與其它5種算法（CQPSO、FPSO、mIPSO1、mIPSO2、mIPSO3）的對比。從表4中數(shù)據(jù)可知，當環(huán)境變化強度較大（0.5、1.0）或很大（20）時，算法能夠快速對環(huán)境變化作出反應，具有較強的收斂性能和適應能力。

從圖4和表4中可以看出，首先，在不同的變化劇烈程度下，GQPSO算法的性能遠遠好于列出的所有算法。

其次，環(huán)境變化強度對算法GQPSO的影響與其它算法是相似的。環(huán)境變化強度增加反而導致算法性能降低，這是因為環(huán)境變化強度越大，函數(shù)適應值曲面變化越大，相應地，變化后峰與原來峰的距離也就越遠。因此，算法很難重新定位和跟蹤到變化的峰。然而，環(huán)境變化強度對算法GQPSO性能的影響并不是很大，說明算法具有很好的魯棒性，能夠適應不同程度峰位置移動的變化。

圖4給出了實驗設置下GQPSO解決不同變化劇烈程度和變化周期的MPB離線性能指標與其它算法比較結果。環(huán)境變化周期是指每隔一定的評價次數(shù)，環(huán)境就會發(fā)生變化，成為環(huán)境變化頻率。由圖4可知，對于相同峰數(shù)的MPB，當環(huán)境變化周期逐漸增加時，粒子群能在一個變化周期內收斂，粒子的數(shù)量會減少，子群的數(shù)目也會隨之下降，意味著算法有充足的時間進行重新定位和追蹤最優(yōu)解的位置，說明粒子群的收斂性很好，動態(tài)環(huán)境中參數(shù)的變化會影響算法的性能。環(huán)境變化得越慢，算法的性能越好；環(huán)境強度變化越大，算法求解動態(tài)環(huán)境優(yōu)化問題的能力越差。顯然當環(huán)境頻率變化較小時，算法需要更長時間獲取更好的解；當環(huán)境頻率變化較大時，問題的適應度函數(shù)值便會很大，算法則需要花費更長時間尋找改變后的最優(yōu)解。

4 結語

本文首先從原理上分析了量子行為粒子群優(yōu)化算法，其具有全局搜索能力能夠解決動態(tài)環(huán)境優(yōu)化問題。其次對當前粒子群優(yōu)化算法在動態(tài)環(huán)境優(yōu)化問題中存在的缺陷進行分析，在此基礎上，采用分層聚類策略產生多種群，擴大了種群粒子搜索區(qū)域范圍，增強了算法的局部搜索能力。針對復雜多變的動態(tài)環(huán)境采用一種有效的環(huán)境監(jiān)測辦法監(jiān)測環(huán)境的變化，提高了算法對變化強度較高和變化頻率較快的應變能力，通過與其它文獻算法的橫向對比，實驗表明算法解決動態(tài)環(huán)境優(yōu)化問題具有較強的適用性和魯棒性。

為增強全局搜索能力和局部搜索能力，對量子行為粒子算法進行了改進。首先，對算法中吸引子進行分析，提出3種吸引子公式，并通過對單個粒子的運動進行分析，證明了最佳吸引子公式的可靠性。然后根據(jù)吸引子的產生公式，提出一種全局搜索策略，分析了粒子群體的搜索軌跡與算法的性能評價標準。通過對動態(tài)環(huán)境優(yōu)化問題測試函數(shù)仿真，驗證了改進算法可對復雜動態(tài)環(huán)境優(yōu)化問題快速跟蹤，具有較強的動態(tài)適應性和較好的優(yōu)化性能。

參考文獻：

[1] FU H，LEWIS P R， SENDHOFF B，et al.What are dynamic optimization problems[C].2014 IEEE Congress on Evolutionary Computation，2014：1550-1557.

[2] 陳莉.動態(tài)優(yōu)化問題的粒子群算法研究[D].武漢：武漢大學，2012.

[3] 孫俊.量子行為粒子群優(yōu)化算法研究[D].無錫：江南大學，2009.

[4] SUN J，XU W，F(xiàn)ENG B.A global search strategy of quantum-behaved particle swarm optimization[C].Cybernetics and Intelligent Systems，2004：111-116.

[5] XU W，SUN J.Adaptive parameter selection of quantum-behaved particle swarm optimization on global level[J].International Conference on Advances in Intelligent Computing，2005，3612（23）：420-428.

[6] SUN J，XU W，LIU J.Parameter selection of quantum-behaved particle swarm optimization[J].Dynamics of Continuous Discrete & Impulsive Systems，2007，14（4）：603-607.

[7] CLERC M，KENNEDY J.The particle swarm：explosion，stability and convergence in a multi-dimensional complex space[J].IEEE Transactions on Evolutionary Computation，2002，6（1）：58-73.

[8] 楊玉良.高分子科學中的Monte Carlo方法[M].上海：復旦大學出版社，1993.

[9] YANG S.Evolutionary computation for dynamic optimization problems[C].Companion Publication of the 2015 Conference on Genetic and Evolutionary Computation，2015：629-649.

[10] KENNEDY J.Stereotyping：improving particle swarm performance with cluster analysis[J].Congress on Evolutionary Computation，2000，2：1507-1512.

[11] 王洪峰，汪定偉，黃敏.求解動態(tài)優(yōu)化問題的分叉PSO算法[J].系統(tǒng)仿真學報，2010，22（12）：2895-2899.

[12] TING T O，MAN K L，GUAN S U，et al.Weightless Swarm Algorithm （WSA） for dynamic optimization problems[J].Springer Berlin Heidelberg，2012，7513：508-515.

[13] FANG W，SUN J，WU X J，et al.Study on the compression-expansion coefficient in drift particle swarm optimization[C].WCCI 2012 IEEE World Congress on Computational Intelligence，2014：1-6.

（責任編輯：何 麗）