一種Q學習的量子粒子群優(yōu)化方法

盛歆漪，孫俊，周頔，須文波

1.江南大學數(shù)字媒體學院，江蘇無錫 214021

2.江南大學物聯(lián)網(wǎng)學院，江蘇無錫 214021

一種Q學習的量子粒子群優(yōu)化方法

盛歆漪1，孫俊2，周頔1，須文波2

1.江南大學數(shù)字媒體學院，江蘇無錫 214021

2.江南大學物聯(lián)網(wǎng)學院，江蘇無錫 214021

分析了量子行為粒子群優(yōu)化算法，著重研究了算法中的收縮擴張參數(shù)及其控制方法，針對不同的參數(shù)控制策略對算法性能的影響特點，提出將Q學習方法用于算法的參數(shù)控制策略，在算法搜索過程中能夠自適應(yīng)調(diào)整選擇參數(shù)，提高算法的整體優(yōu)化性能；并將改進后的Q學習量子粒子群算法與固定參數(shù)選擇策略，線性下降參數(shù)控制策略和非線性下降參數(shù)控制策略方法通過CEC2005 benchmark測試函數(shù)進行了比較，對結(jié)果進行了分析。

粒子群算法；Q學習；參數(shù)選擇；量子行為

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）是Kennedy等人受鳥群覓食行為的啟發(fā)，提出的一種群體優(yōu)化算法[1]。自提出以來，PSO算法因其方法簡單、收斂速度快得到了廣泛的應(yīng)用；但從算法本身來講，PSO并不是一種全局優(yōu)化算法[2]，許多學者對此提出了許多改進方法，取得了一定的改進效果[3-4]。Sun等人在分析粒子群優(yōu)化算法的基礎(chǔ)上，深入研究了智能群體進化過程，將量子理論引入了PSO算法，提出了具有全局搜索能力的量子行為粒子群優(yōu)化算法（Quantum-behaved Particle Swarm Optimization，QPSO）[5-6]。QPSO算法自提出以來，由于計算簡單、編程易于實現(xiàn)、控制參數(shù)少等特點，引起了國內(nèi)外相關(guān)領(lǐng)域眾多學者的關(guān)注和研究[7-9]，也在一些實際問題中得到了應(yīng)用[10-13]。針對QPSO算法中的唯一參數(shù)（收縮擴張因子），Sun等人使用的是固定參數(shù)控制策略，后來Fang提出了隨著進化代數(shù)的增加，采用線性減小和非線性減小的參數(shù)控制方法，仿真結(jié)果表明，在大部分測試函數(shù)中都取得了較好的改進效果[14]；Xi等人針對QPSO算法中的粒子貢獻度的差別，提出了權(quán)重系數(shù)控制算法搜索過程的改進方法，也取得了一定的效果[15]。

在QPSO算法中，算法性能嚴重依賴于收縮擴張因子參數(shù)，在進化過程中采用單一的參數(shù)控制策略，使粒子缺乏靈活性，這些參數(shù)控制方法并不能在進化迭代的每一步中都有效。如果將QPSO算法中的多種參數(shù)控制策略同時應(yīng)用于進化過程中的參數(shù)控制，并根據(jù)多步進化（向前考察幾步）的效果來選擇其中一種最合適的參數(shù)選擇策略作為當前粒子進化的參數(shù)，則更有利于算法的整個進化過程。基于這種思想，同時受文獻[16-17]中提到的強化學習啟發(fā)，本文提出了一種基于強化學習的量子粒子群優(yōu)化算法（Reinforcement Learning QPSO，RLQPSO），改善算法的整體性能。

1 量子粒子群優(yōu)化算法

在粒子群優(yōu)化算法的群體中，個體（粒子）通過搜索多維問題解空間，在每一輪進化迭代中評價自身的位置信息（適應(yīng)值）；在整個群體搜索過程中，粒子共享它們“最優(yōu)”位置信息，然后使用它們的記憶調(diào)整它們自己的速度和位置，不斷比較和追隨候選的問題空間解，最終發(fā)現(xiàn)最優(yōu)解或者局部最優(yōu)解。

基本粒子群算法的進化方程為：

由粒子搜索路徑分析可知，為了保證粒子群算法的收斂性，在粒子搜索過程中，粒子不斷趨近于它們的局部吸引子pi=(pi，1，pi，2，…，pi，n)，方程定義為：

Jun Sun等[5-6]認為在這種搜索機制下，粒子的隨機性就很有限，算法只能描述低智能的動物群體，而不能準確描述思維隨機性很強的人類群體，并且發(fā)現(xiàn)人類的智能行為與量子空間中粒子行為極為相似，因此在算法中引入了量子態(tài)粒子行為，則對粒子的每一維可以得到概率密度方程Q和分布函數(shù)F，方程定義如下：

這里，Li，j(t)決定了每個粒子的搜索范圍，使用Monte Carlo方法，可以得到粒子的位置方程：

這里u是在（0，1）之間的隨機數(shù)。

為了模擬人類群體行為的大眾思維（Main Thoughts），在QPSO算法中引入了最優(yōu)平均位置值概念，方程定義為：

這里M是算法粒子群體的大小，Pi是粒子i的局部最優(yōu)值，Li，j(t)和粒子的位置量就由以下的方程計算：

這里，參數(shù)β是QPSO算法中的唯一控制參數(shù)，稱作擴張收縮系數(shù)，調(diào)節(jié)它可以控制算法的收斂速度。則式（4）（8）（10）組成了具有量子行為粒子群算法的迭代方程組。量子粒子群算法在函數(shù)測試[4]、濾波器設(shè)計[10]、多階段金融規(guī)劃[11]、神經(jīng)網(wǎng)絡(luò)優(yōu)化[12]和H∞控制[13]等應(yīng)用中顯示了其優(yōu)越性。

2 QPSO算法中的參數(shù)控制策略

在QPSO算法中，收縮擴張系數(shù)β用來調(diào)節(jié)算法的收斂速度，通過大量的仿真測試，β≤1.781時能夠保證算法收斂[8]，在基本QPSO中，通過仿真測試，固定取值策略條件中，β=0.8在大多數(shù)的測試函數(shù)條件下能夠取得較好的測試結(jié)果。

為了改善QPSO算法的性能，方偉[14]提出了線性遞減的參數(shù)調(diào)整策略和非線性遞減的參數(shù)調(diào)整策略，即

（1）線性遞減策略

文獻[14]中的大量仿真測試表明，對于不同的測試函數(shù)，以上參數(shù)控制策略（包括固定值參數(shù)）各有優(yōu)勢，各自能夠在不同的問題中取得優(yōu)于其他參數(shù)控制策略的仿真結(jié)果。那么，對于一個未知問題，如何選擇參數(shù)的控制策略才能取得更好的尋優(yōu)結(jié)果，因此，受強化學習思路的啟發(fā)，將參數(shù)不同的選擇策略視為行動（action），在群體粒子進化過程的每一個迭代步，選擇一個合適的行動（參數(shù)）來控制粒子的搜索過程。并且，在作出行動決策之前，對行動的選擇多向前考慮幾步，則參數(shù)最終選擇結(jié)果正確的概率更高，更能提高算法的整體性能。因此，在粒子選擇行動時，可以通過粒子多步進化的效果評價各種行動（參數(shù)選擇策略）的優(yōu)劣。

3 Q學習的量子粒子群優(yōu)化算法（QLQPSO）

3.1 Q學習方法

Q學習是一種與問題模型無關(guān)的增強學習方法，通過選擇最大化代理帶折扣的累積收益的行動，學習到代理的最優(yōu)行動策略。在QPSO算法中，若把個體進化過程中的參數(shù)選擇策略看成行動，這樣個體選擇最優(yōu)參數(shù)策略就轉(zhuǎn)化為代理選擇最優(yōu)行動。

假設(shè)代理的狀態(tài)設(shè)為s，行動設(shè)為a；則代理在任何狀態(tài)下可選擇的行動集合均為A={a1，a2，…，an}，即代理在每個狀態(tài)都有n個可供選擇的行動。則代理的最大折扣回報基本形式為：

其中r(s，a)為代理在狀態(tài)s下選擇行動a后的立即收益；a′為代理在下一個狀態(tài)s′情況下可選擇的行動；表示代理在下一個狀態(tài)s′選擇不同行動所能得到的最大回報值；γ(0≤γ＜1)為折扣因子，γ決定滯后收益對最優(yōu)行動策略選擇的影響。根據(jù)式（14），如果向前看m+1步，個體開始選擇的參數(shù)策略為a，那么在忽略狀態(tài)變量的情況下，代理選擇行動a時的收益為：

其中，m表示向前看的步數(shù)；a，a(i)∈A，且1≤i≤m。由式（15）可知，當γ=0，Q值的計算值降為只向前看一步，γ接近于1時，滯后收益對最后參數(shù)選擇策略的影響將變得越來越大。

3.2 QLQPSO算法原理

根據(jù)Q學習方法，在QPSO算法中將群體中的粒子看作代理，擴張收縮系數(shù)β的選擇策略看作代理行動的集合，則可以實現(xiàn)量子粒子群優(yōu)化算法和Q學習方法之間的映射。定義fp(a)為群體中父代個體對應(yīng)的適應(yīng)度函數(shù)值，fo(a)為采用參數(shù)選擇策略a后個體對應(yīng)的適應(yīng)度函數(shù)值，那么個體的立即收益可以定義為r(a)= fp(a)-fo(a)。如果本例中粒子可選行動（參數(shù)選擇策略）個數(shù)為n，粒子一次進化后共產(chǎn)生n個后代，每個后代采用n個策略進化，二次進化后的后代個數(shù)為n2，同理m次進化后，產(chǎn)生的后代共有nm個，要確定一次參數(shù)選擇策略，需要進行指數(shù)級運算，計算量非常巨大，不適用。為此將問題簡化，粒子第一次進化后產(chǎn)生n個新粒子；該n粒子再次進化，每個個體又產(chǎn)生n個新粒子，通過計算每個個體產(chǎn)生的新粒子的立即收益，采用Boltzmann分布計算這組再次生成的新粒子被保留下來的概率。

根據(jù)計算出的概率，選擇其中一個新個體保留下來，被保留的后代再采用同樣的方式產(chǎn)生n個后代，并保留其中的一個后代。通過這種簡化后，則m次進化后，一個粒子累計產(chǎn)生的個體數(shù)為n+(m-1)·n2，用于計算Q值需要保留的個體數(shù)為m×n，那么問題時間復(fù)雜度降為多項式級。

將立即收益帶入式（15），并化簡后可得：

QLQPSO算法設(shè)計如下：

（1）初始化參數(shù)設(shè)置：包括群體個數(shù)；擴張收縮系數(shù)β取值范圍；算法迭代次數(shù)；折扣因子γ。計算Q值所需向前看的步數(shù)m；隨機產(chǎn)生的初始解x(i)，并設(shè)置pbest(i)=x(i)，并計算全局最優(yōu)值gbest。

（2）根據(jù)式（5）計算局部吸引子p(i)。（3）根據(jù)式（8）計算平均最優(yōu)值mbest。（4）根據(jù)QPSO算法迭代方程（9）（10）更新各個粒子的新位置。

（5）按照Q學習方法選擇最優(yōu)參數(shù)策略β：

①對于每個新粒子，使用給定的n個參數(shù)選擇策略產(chǎn)生n個新的后代粒子，并設(shè)定t=1；

②Do Whilet＜m

每個后代使用式（9）產(chǎn)生n個新后代，根據(jù)式（16）選擇其中一個保留，令t++；

③計算每個參數(shù)選擇策略對應(yīng)的Q值，選擇使Q最大化的參數(shù)選擇策略所對應(yīng)的β值為當前β值，同時舍棄其他n-1個β值。

（6）每個粒子按照式（8）～（10）更新位置值，并生成新的群體。

（7)回到（4）直至循環(huán)條件結(jié)束。

3.3 QLQPSO算法分析

張化祥等人[17]對基于Q學習的適應(yīng)性進化規(guī)劃算法（QEP）的收斂性進行了證明，QLQPSO算法收斂性的證明過程與此類似，本文在此不再對其收斂性進行證明。根據(jù)Q學習方法的原理，可以知道在QLQPSO算法執(zhí)行初期，在Boltzmann分布中，溫度T處于較大值，粒子在參數(shù)選擇進化策略空間進行探索；隨著進化步數(shù)的增加，T越來越小，粒子探索的成分逐步減小，越來越趨向于選擇適應(yīng)度函數(shù)值大的參數(shù)進化策略（本例中為最小化問題，因此為最優(yōu)化函數(shù)值小），此時粒子選擇最優(yōu)參數(shù)策略的概率逐步增加。

4 QLQPSO算法仿真分析

4.1 仿真設(shè)置

為了測試和比較Q學習的QPSO算法性能，本文和固定系數(shù)QPSO（BQPSO）算法、系數(shù)線性下降的QPSO算法（LDQPSO）、系數(shù)開口向上的非線性遞減QPSO算法（UPQPSO）和系數(shù)開口向下的非線性遞減QPSO算法（DNQPSO）進行了測試比較，測試函數(shù)使用CEC2005 benchmark測試函數(shù)[18]，其中F1到F6為單峰函數(shù)，F(xiàn)7到F12為多峰函數(shù)。優(yōu)化問題分別設(shè)置為：BQPSO算法的β值為0.8，LDQPSO算法、UPQPSO算法、DNQPSO算法的β從1.0下降到0.5，QLQPSO算法的參數(shù)選擇行動策略為上述四種算法的參數(shù)選擇方法，滯后因子γ為0.5，T的初始溫度為100℃。問題維數(shù)為30，算法對應(yīng)的最大迭代次數(shù)為5 000，粒子數(shù)為40；每個問題的求解都應(yīng)用算法隨機獨立運行50次。

4.2 仿真結(jié)果與討論

表1給出了五種算法對各測試函數(shù)在不同粒子數(shù)、不同維數(shù)及不同迭代次數(shù)的情況下得到的50次仿真結(jié)果的目標函數(shù)值的平均值和標準方差。圖1中給出了不同算法在40個粒子30維的情況下50次仿真的平均收斂曲線。從表1中各種算法的仿真結(jié)果看，QLQPSO在12個測試函數(shù)中，9個取得了最好的結(jié)果，LDQPSO、UPQPSO、DNQPSO各取得了一次最優(yōu)值。在QLQPSO取得的8次最優(yōu)的情況下，對于Shifted Schwefel’s Problem 1.2函數(shù)（F2）、Shifted Rotated High Conditioned Elliptic函數(shù)（F3）、Shifted Schwefel’s Problem 1.2 with Noise in Fitness（F4）、Shifted Rastrigin’s函數(shù)（F9）、Shifted Rotated Weierstrass函數(shù)（F11），QLQPSO取得了明顯的優(yōu)勢。另外從圖1的收斂曲線可以得知，對于Shifted Sphere函數(shù)（F1）、Shifted Rotated Griewank’s Function without Bounds函數(shù)（F7）和Shifted Rotated Ackley’s函數(shù)（F8），QLQPSO算法取得了最優(yōu)值，雖然結(jié)果和其他算法比較接近，但算法表現(xiàn)出初期的收斂速度遠高于其他算法；對于Schwefel’s Problem 2.6 with Global Optimum on the Bounds函數(shù)（F5）、Shifted Rosenbrock函數(shù)（F6）、Shifted Rotated Rastrigin’s（F10）和Schewefel’s Problem 2.13函數(shù)（F12），LDQPSO算法和UPQPSO分別取得了最優(yōu)值，但是QLQPSO的結(jié)果和它們很接近，但是在初期（1 000次迭代）的收斂速度是最快的。以上說明，提出的Q學習QPSO算法大大提高了算法的收斂速度，并且在大多數(shù)測試函數(shù)中表現(xiàn)了優(yōu)異的性能。

5 結(jié)束語

分析了QPSO算法的進化方程，并研究了算法中的控制參數(shù)選擇方式對參數(shù)性能的影響，不同的參數(shù)選擇方式針對不同電費優(yōu)化問題有各自的優(yōu)化特點，這對控制參數(shù)選擇提出了更高的要求。針對算法參數(shù)選擇上的限制，提出了引入Q學習的思想來根據(jù)優(yōu)化問題自適應(yīng)調(diào)整參數(shù)的選擇，并給出了改進后的算法執(zhí)行過程。最后應(yīng)用CEC2005測試函數(shù)對改進后的算法和其他幾種不同的控制參數(shù)選擇策略進行了仿真比較，仿真結(jié)果顯示改進后的算法在大部分測試函數(shù)上能夠取得更優(yōu)的結(jié)果，其他函數(shù)也能夠取得和其他方法相近的結(jié)果，因此改進后的算法能夠提高QPSO算法的整體性能。

表1 不同算法運行50輪后的平均最優(yōu)值及方差

圖1 五種算法優(yōu)化不同標準測試函數(shù)的目標函數(shù)值的收斂曲線比較

[1]Kennedy J，Eberhart R.Particle Swarm Optimization[C]// Proceedings of IEEE International Conference on Neural Network，1995：1942-1948.

[2]van den Bergh F.An analysis of Particle Swarm Optimizers[D].University of Pretoria，2001.

[3]Zheng Yongling，Ma Longhua，Zhang Liyan.Empirical study of particle swarm optimizer with an increasing inertiaweight[C]//Proceedings of IEEE Congress on Evolutionary Computation 2003（CEC 2003），Canbella，Australia，2003：221-226.

[4]Clerc M.Discrete Particle Swarm Optimization[M]//New Optimization Techniques in Engineering.[S.l.]：Springer-Verlag，2004.

[5]Sun J，F(xiàn)eng B，Xu W.Particle Swarm Optimization with particles having quantum behavior[C]//IEEE Proc of Congress on Evolutionary Computation，2004：325-331.

[6]Sun J，Xu W，F(xiàn)eng B.A global search strategy of quantum-behaved Particle Swarm Optimization[C]//Cybernetics and Intelligent Systems，Proceedings of the 2004 IEEE Conference，2004：111-116.

[7]Sun J，Wu X，Palade V，et al.Convergence analysis and improvements of quantum-behaved particle swarm optimization[J].Information Sciences，2012，193：81-103.

[8]Sun J，F(xiàn)ang W，Wu X，et al.Quantum-behaved particle swarm optimization analysis of individual particle behavior and parameter selection[J].Evolutionary Computation，2012，20（3）.

[9]Omranpour H，Ebadzadeh M，Shiry S，et al.Dynamic Particle Swarm Optimization for multimodal function[J].International Journal of Artificial Intelligence，2012，1（1）：1-10.

[10]Chen W，Sun J，Ding Y R.Clustering of gene expression data with Quantum-behaved Particle Swarm Optimization[C]//IEA/AIE.Zurich：Springer-Verlag，2008：388-396.

[11]Chai Zhilei，Sun Jun，Cai Rui，et al.Implementing Quantum-behaved Particle Swarm Optimization algorithm in FPGA for embedded real-time applications[C]//2009 Fourth International Conference on Computer Sciences and Convergence Information Technology，2009：886-890.

[12]Omkar S N，Khandelwal R，Ananth T V S，et al.Quantum behaved Particle Swarm Optimization（QPSO）for multi-objective design optimization of composite structures[J].Expert Systems with Applications，2009，36（8）：11312-11322.

[13]Goh C K，Tan K C，Liu D S，et al.A competitive and cooperative co-evolutionary approach to multi-objective particle swarm optimization algorithm design[J].European Journal of Operational Research，2010，202：42-54.

[14]Fang W.Swarm intelligence and its application in the optimal design of digital filters[D].2008.

[15]Xi M，Sun J，Xu W.An improved quantum-behaved particle swarm optimization algorithm with weighted mean best position[J].Applied Mathematics and Computation，2008，205（2）.

[16]Sutton R S，Barto A G.Reinforcement learning：an introduction[M].Cambridge：MIT Press，1998.

[17]張化祥，陸晶.基于Q學習的適應(yīng)性進化規(guī)劃算法[J].自動化學報，2008，34（7）：819-822.

[18]Suganthan P，Hansen N，Liang J J，et al.Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization[R].Singapore：Nanyang Technological University，2005.

SHENG Xinyi1,SUN Jun2,ZHOU Di1,XU Wenbo2

1.School of Digital Media,Jiangnan University,Wuxi,Jiangsu 214021,China
2.School of Internet of Things,Jiangnan University,Wuxi,Jiangsu 214021,China

Quantum-behaved Particle Swarm Optimization algorithm is analyzed;contraction-expansion coefficient and its control method are studied.To the different performance characteristics with different coefficients control strategies,a control method of coefficient with Q-learning is proposed.The proposed method can tune the coefficient adaptively and the whole optimization performance is increased.The comparison and analysis of results with the proposed method,constant coefficient control method,linear decreased coefficient control method and non-linear decreased coefficient control method based on CEC2005 benchmark function is given.

Particle Swarm Optimization（PSO）algorithm;Q-learning;parameter selection;quantum behavior

A

TP301

10.3778/j.issn.1002-8331.1402-0206

SHENG Xinyi,SUN Jun,ZHOU Di,et al.Quantum-behaved particle swarm optimization method based on Q-learning. Computer Engineering and Applications,2014,50（21）：8-13.

國家自然科學基金（No.61170119，No.60973094）；江蘇省自然科學基金（No.BK20130160）。

盛歆漪（1975—），女，博士研究生，講師，主要研究方向：智能控制，優(yōu)化算法，交互設(shè)計；孫?。?973—），男，博士，副教授，主要研究方向：優(yōu)化算法，機器學習；周頔（1983—），女，博士，副教授，主要研究方向：優(yōu)化算法，圖像識別；須文波（1944—），男，教授，博導(dǎo)，主要研究方向：智能控制，先進算法。E-mail：sheng-xy@163.com

2014-02-20

2014-05-04

1002-8331（2014）21-0008-06

CNKI出版日期：2014-05-22，http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1402-0206.html