王夢梅

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

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

DOIDOI：10.11907/rjdk.173334

中圖分類號(hào)：TP311

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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.

英文關(guān)鍵詞Key Words：Gaussian distribution； particle swarm optimization； dynamic environment； optimization problem

0 引言

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

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

1 量子行為粒子群算法

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

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

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

（6）計(jì)算得到一個(gè)隨機(jī)點(diǎn)的位置。

重復(fù)（2）至（6），直至滿足一定的結(jié)束條件。

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

2.1 分層聚類策略

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

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

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

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

3.1 算法性能測試

為了測試本文算法的性能，實(shí)驗(yàn)設(shè)置了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í)驗(yàn)結(jié)果對(duì)比可知，離線性能指標(biāo)越小，說明算法性能越好。當(dāng)山峰數(shù)為一個(gè)特定的值時(shí)，離線性能指標(biāo)隨著粒子群粒子數(shù)的增長而增加。這是因?yàn)樗阉鲄^(qū)域內(nèi)的粒子數(shù)目增多，聚類的子群就會(huì)增加，隨著算法迭代進(jìn)行，種群能搜索的峰的數(shù)目也會(huì)增加收斂的種群增加，從而導(dǎo)致離線性能指標(biāo)有所增長。此外，當(dāng)移動(dòng)峰數(shù)一定時(shí)，每當(dāng)粒子群不同，最優(yōu)算法也是不同的。比如：當(dāng)max_subsizeN=3、M=100時(shí)，算法性能最佳，而當(dāng)max_subsizeN=7、M=200時(shí)離線性能最小，說明算法最佳。因此，由圖3-圖5可知，GQPSO算法能夠適應(yīng)多種移動(dòng)峰問題的求解。

3.2 參數(shù)設(shè)置影響

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

3.3 3種高斯吸引子對(duì)比

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

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

3.4 算法比較實(shí)驗(yàn)

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

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

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

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

4 結(jié)語

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

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

參考文獻(xiàn)：

[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] 陳莉.動(dòng)態(tài)優(yōu)化問題的粒子群算法研究[D].武漢：武漢大學(xué)，2012.

[3] 孫俊.量子行為粒子群優(yōu)化算法研究[D].無錫：江南大學(xué)，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] 楊玉良.高分子科學(xué)中的Monte Carlo方法[M].上海：復(fù)旦大學(xué)出版社，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] 王洪峰，汪定偉，黃敏.求解動(dòng)態(tài)優(yōu)化問題的分叉PSO算法[J].系統(tǒng)仿真學(xué)報(bào)，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.

（責(zé)任編輯：何 麗）