自適應收擴系數的雙中心協作QPSO算法

丁 穎，李 飛

?

自適應收擴系數的雙中心協作QPSO算法

丁 穎a，李 飛b

(南京郵電大學 a. 通信與信息工程學院；b. 信號處理與傳輸研究院，南京 210003)

針對量子粒子群優化(QPSO)算法迭代后期種群多樣性下降、收斂速度慢、易陷入局部最優的缺點，提出一種自適應收縮-擴張系數的雙中心協作量子粒子群優化算法。該算法從2個方面進行改進：(1)自適應調節收縮-擴張系數，其目的是幫助粒子跳出局部最優點，提高粒子的全局搜索能力；(2)雙重更新全局最優位置，即在每次迭代中，先后分別采用2種不同的方式更新全局最優位置。第1種方式與QPSO算法一致，第2種方式則引入雙中心粒子，使其和當前全局最優位置在相應維度上合作，從而達到更新全局最優位置的目的。從固定迭代次數和固定精度角度分析算法性能，仿真結果表明，相比于QPSO算法，該算法在保證復雜度較低的情況下，可提高收斂速度，增強全局和局部搜索能力。

量子粒子群優化算法；收縮-擴張系數；雙中心粒子；協作；全局最優位置

1 概述

量子粒子群優化(Quantum Particle Swarm Optimization, QPSO)算法[1]是Sun等人于2004年從量子力學的角度提出的一種新型的粒子群優化算法。相對于傳統的粒子群優化算法(Particle Swarm Optimization, PSO)，該算法具有搜索范圍廣、收斂速度快、尋優精度高的特點，但對于復雜問題仍然容易陷入局部最優。近年來，對QPSO的研究主要有以下3個方面：(1)理論的證明和研究[2-4]。(2)改進收縮-擴張系數[5-6]。文獻[5]提出系數非線性變化的策略，其尋優能力優于線性變化的情況。(3)與其他算法的融合[7-9]。文獻[7]提出將遺傳算法的選擇和變異操作融入到QPSO中，提高了收斂速度，改善了早熟問題。文獻[8]將一種調和算法和QPSO結合，提出一種改進的量子粒子群算法(HQPSO)。與標準QPSO算法相比，該算法搜索能力更強、收斂速度更快。

文獻[10]提出雙中心粒子的思想，并利用該思想優化粒子群算法，但并未充分利用該雙中心粒子。本文將該思想應用到量子粒子群優化中，提出自適應收擴系數的雙中心協作QPSO(AQPSO)算法，使雙中心粒子和當前全局最優位置在相應維度上合作[11]，并設計雙重更新全局最優位置的策略，以提高算法的尋優能力和收斂速度。

2 QPSO的基本原理

PSO是一種模擬鳥群捕食的群智能算法[12]，具有參數少、效果好的優點，但也存在不足，如搜索范圍受限，不能保證以概率1收斂到全局最優點等。QPSO是Sun等人于2004年在PSO的基礎上從量子力學的角度提出的一種新型的優化算法，不僅具有PSO的優點，而且理論上能夠保證全局收斂。

在QPSO中，用波函數(,)描述粒子的狀態，粒子的位置由波函數來決定：

其中，表示粒子在時刻出現在點(,,)的概率密度，通過求解薛定諤(Schr dinger)方程可以得到。粒子位置通過蒙特卡羅(Monte Carlo)隨機模擬的方式得到，其更新方程如式(2)~式(6)所示。

其中，p()和p()分別代表粒子在第次迭代時的個體最優位置和種群的全局最優位置；是在[0,1]上服從均勻分布的隨機數；()為粒子第次迭代的局部吸引域，表示的是每個粒子介于個體最優位置和全局最優位置之間的隨機位置；表示粒子與種群平均最優位置的帶權距離；是在[0,1]上服從均勻分布的隨機數；稱為收縮-擴張系數，用來控制粒子的收斂速度，隨著迭代的進行，線性地從變化到[13]，通常=1，=0.5；max表示最大的迭代次數。

綜合式(2)~式(6)可得：

此外，以求函數最小值為例，個體最優位置和全局最優位置的更新公式如式(8)和式(9)所示，其中，=1,2,…,。

3 AQPSO的基本原理和算法流程

3.1 AQPSO的基本原理

3.1.1 自適應收縮-擴張系數

根據式(5)，標準QPSO中的收縮-擴張系數是隨著迭代次數的增加而線性遞減，而實際的搜索過程是非線性的，所以，不能適應復雜的非線性尋優過程。文獻[14]證明當<1.7時，粒子收斂于當前全局最優位置；當>1.8時，粒子發散，將逃離全局最優位置區域。本文對的改進算法[15]如下：

If fitness(xi)==0

then hi=1

else hi=fitness(pg)/fitness(xi)

Endif

hmax=max(hi)

hmin=min(hi)

If hmax==hmin

thenai=amin+(amax–amin)*hmax

elseai=(amax–amin)/(hmax–hmin)*hi+(amin*hmax–amax*hmin)/

(hmax– hmin)

Endif

說明：該算法的適用前提是求解函數的最小值，并且最小值均非負；x表示第個粒子的位置，=1,2,…,；=()表示適應度函數，即需要被優化的目標函數，因此，(x)表示x的適應度函數值；p表示全局最優位置；h表示當前全局最優位置的適應度函數值和當前第個粒子的適應度函數值的比值；max和min分別表示所有粒子中的最大值和最小值；max=1.7，min=0.5。

α和h的關系如圖1和圖2表示。

圖1 hmax==hmin時αi的值

圖2 hmax≠hmin時αi的值

由算法可知，h在0~1之間，h越大，表明該粒子越靠近全局最優位置，此時α越大，其跳出局部最優的能力越強；反之，α越小，加速收斂。由此可知，該算法能夠保證每個粒子更好地自適應調節各自的值，避免陷入局部最優，從而提高了搜索尋優能力。

3.1.2 雙重更新全局最優位置策略

由標準QPSO基本原理知，全局最優位置p是一個至關重要的位置[16]，它指引著整個種群向最優解靠近，影響著最優解的質量和整體的收斂速度。文獻[10]提出了雙中心粒子群優化算法，并用實驗驗證了該算法的優勢，但并未充分利用該雙中心粒子。本文受文獻[10]啟發，提出雙重更新全局最優位置的思想。第1種更新方式和QPSO一致。在第2種方式中，將雙中心思想從PSO移植到QPSO中，通過雙中心粒子和當前全局最優位置在相應維度上合作來更新全局最優位置。每次迭代先后分別應用這2種方式。下文主要介紹第2種更新方式。

雙中心粒子-廣義中心粒子(x)和狹義中心粒子(x)(分別為當前所有粒子個體最優位置中心和所有粒子當前位置中心)，在本質上和其他粒子相同，是群體的組成部分，參與粒子間的共存與合作、個體優劣的比較以及全局最優位置的競爭等行為。其更新方式如式(10)和式(11)所示。

圖3 粒子間合作示意圖

首先，在1、2、3中選擇適應度最優的位置，不妨設為1；其次，對于1的每一維度，分別用其他2個位置的相應維度值進行替換，若替換后的位置更加優秀，則用該位置更新1。例如，分別用21、31替換11可分別得到1’=(21,12,13,…,1D)、1’’=(31,12,13,…,1D)，將它們和1= (11,12,13,…,1D)進行比較，選擇三者中最優的位置，不妨設1’最優，則用1’更新1，其他維度同理合作。最后，利用最終得到最優位置更新p。

3.2 AQPSO算法流程

AQPSO算法具體步驟如下：

Step1置迭代次數=0；初始化種群規模；隨機初始化前–2個粒子的位置x，=1,2,…,–2，以及個體最優位置p=x(=1,2,…,–2)；由式(10)和式(11)計算得到雙中心粒子的初始位置x(=–1,)，并初始化雙中心粒子的個體最優位置p=x(=–1,)；根據式(9)求出初始全局最優位置。

Step2根據3.1.1節中的方法計算，并更新前–2個粒子的位置x(=1,2,…,–2)。

Step3計算前–2個粒子的適應度函數值。

Step4分別由式(8)、式(9)更新前–2個粒子的個體最優位置p(=1,2,…,–2)，以及全局最優位置p。

Step5由式(10)和式(11)更新雙中心粒子的位置x，=–1,。

Step6計算雙中心粒子的適應度函數值。

Step7類似Step4，更新雙中心粒子的個體最優位置p，i=–1,，以及全局最優位置p。

Step8利用3.1.2節的第2種方式更新p。

Step9判斷是否達到終止條件，若否，置=+1，返回Step2；否則算法結束。

4 性能測試與結果分析

4.1 測試函數

本文采用4個測試函數，具體特點如表1所示。

表1 測試函數

4.2 固定迭代次數的測試結果與分析

參數設置如下：粒子數=20；運行50次；維度用表示；最大迭代次數用max表示。

測試結果見表2和圖4~圖7。由表2可以看出，對于1，AQPSO優于QPSO和DQPSO。對于2，低維時，AQPSO的平均值稍優，最優值稍遜，但是最差值和標準差遠遠勝出；高維時AQPSO較優。對于3，當迭代次數稍大于1 000時，AQPSO的最優值急劇下降，并很快找到最優值0，這是因為3雖然具有很多的局部最優點，但其圖形整體輪廓簡單，不像2那樣最優值位于形狀復雜的谷底，該實驗結果同時也驗證了AQPSO算法在迭代后期克服局部最優的能力遠勝于QPSO和DQPSO。對于4，低維時，AQPSO優于另外2種算法；高維時，AQPSO稍遜。由圖4~圖7可以看出，AQPSO的收斂速度和尋優能力優于其他2種算法。因此，固定迭代次數時，AQPSO性能遠遠優于QPSO和DQPSO算法。

表2 固定迭代次數的仿真結果

圖4 Sphere函數測試結果(維度20，迭代1 500次)

圖5 Rosenbrock函數測試結果(維度20，迭代1 500次)

圖6 Rastrigrin函數測試結果(維度20，迭代2 000次)

圖7 Griewank函數測試結果(維度20，迭代1 500次)

4.3 固定精度的測試結果與分析

參數設置：粒子數=20，運行50次；1的終止精度為10–10，2終止精度為20，3的終止精度為0.1，4的終止精度為0.1。測試結果如表3所示，其中，平均迭代次數指在50次的運行中，達到指定精度時的平均迭代次數；平均時間指在50次的運行中，達到指定精度時所消耗的平均時間；成功次數指50次運行中，在最大迭代次數的限制下，能夠成功達到所需精度的次數；失敗次數=50–成功次數。

由表3可以看出，對于1、3、4，AQPSO的性能明顯優于其他2種算法；對于2，在平均迭代時間上三者算法相差不大，但AQPSO的成功次數遠大于另外2種算法。因此，固定精度時AQPSO算法的性能優于QPSO和DQPSO算法。

表3 固定精度的仿真結果

5 結束語

在本文提出的AQPSO算法中，自適應收縮-擴張系數有助于粒子跳出局部最優位置，提高全局搜索能力；雙中心協作思想有助于粒子更充分地利用群體信息，改進全局最優位置的更新方式，提高全局最優位置的指引作用。上述2個創新點的結合，可有效提高算法的尋優能力，加快收斂速度。實驗結果證明，AQPSO在尋優能力和尋優速度上均取得了較好的效果。下一步將設計性能更優的自適應收縮-擴張系數方法，以提高全局搜索能力，同時利用群體知識提高群體學習能力，從而進一步提高算法的尋優能力。

[1] Sun Jun, Feng Bin, Xu Wenbo. Particle Swarm Optimization with Particles Having Quantum Behavior[C]//Proc. of 2004 Congress on Evolutionary Computation. Piscataway, USA: [s. n.], 2004.

[2] Sun Jun, Xu Wenbo, Feng Bin. A Global Search Strategy of Quantum-behaved Particle Swarm Optimization[C]//Proc. of IEEE Conference on Cybernetics and Intelligent Systems. Singapore: IEEE Press, 2004.

[3] 李盼池, 王海英. 量子勢阱粒子群優化算法的改進研究[J]. 物理學報, 2012, 61(6): 19-27.

[4] 方 偉, 孫 俊, 謝振平, 等. 量子粒子群優化算法的收斂性分析及控制參數研究[J]. 物理學報, 2010, 59(6): 3686- 3694.

[5] 黃澤霞, 俞攸紅. 慣性權自適應調整的量子粒子群算法[J].上海交通大學學報, 2012, 46(2): 228-232.

[6] 程 偉, 陳森發. 權重自適應調整的混沌量子粒子群優 化[J]. 計算機工程與應用, 2010, 46(9): 46-48.

[7] Gong Shangfu, Gong Xingyu, Bi Xiaoru. Feature Selection Method for Network Intrusion Based on GQPSO Attribute Reduction[C]//Proc. of International Conference on Multimedia Technology. Hangzhou, China: [s. n.], 2011.

[8] Lu Kezhong, Fang Kangnian, Xie Guangqian. A Hybrid Quantum-behaved Particle Swarm Optimization Algorithm for Clustering Analysis[C]//Proc. of the 5th International Conference on Fuzzy Systems and Knowledge Discovery. Jinan, China: [s. n.], 2008.

[9] 胡苓苓, 郭業才. 基于QPSO的小波分數間隔盲均衡算 法[J]. 計算機工程, 2011, 37(24): 195-197.

[10] 湯可宗, 柳炳祥. 雙中心粒子優化算法[J]. 計算機研究與發展, 2012, 49(5): 1086-1094.

[11] Li Yangyang, Xiang Ronggong, Jiao Licheng. An Improved Cooperative Quantum-behaved Particle Swarm Optimization [J]. Soft Computing, 2012, 16(6): 1061-1069.

[12] Kennedy J, Eberhart R. Particle Swarm Optimization[C]//Proc. of IEEE International Conference on Neural Networks. Piscataway, USA: IEEE Press, 1995.

[13] Sun Jun, Fang Wei, Wu Xiaojun. Quantum-behaved Particle Swarm Optimization: Analysis of the Individual Particle’s Behavior and Parameter Selection[J]. Evolutionary Compu- tation, 2012, 20(3): 349-393.

[14] Zhu Haodong, Zhong Yong. Study of Optimized RBF Network in Feature Selection[J]. Journal of Microcomputer & Its Applications, 2009, 28(15): 76-79.

[15] Liu Junhui, Li Na. Parallel Adaptive Immune Quantum-Behaved Particle Swarm Optimization Algorithm(PAIQPSO)[C]//Proc. of International Conference on Intelligent Systems Design and Engineering Application. Sanya, China: [s. n.], 2012.

[16] 陳 偉, 周 頔, 孫俊陳, 等. 一種采用完全學習策略的量子行為粒子群優化算法[J]. 控制與決策, 2012, 27(5): 719- 730.

編輯 金胡考

Cooperative Double-center QPSO Algorithm with Self-adaptive Contraction-expansion Coefficient

DING Yinga, LI Feib

(a. College of Communication & Information Engineering; b. Institute of Signal Processing and Transmission, Nanjing University of Posts and Telecommunications, Nanjing 210003, China)

Against the problems of Quantum Particle Swarm Optimization(QPSO) algorithm in the late part of iterations, such as decline of population diversity, slow convergence rate and easy to fall into the local optima, a cooperative double-center QPSO algorithm with self-adaptive contraction-expansion coefficient is proposed in this paper. It has two characteristics: (1)The contraction-expansion coefficient is self-adaptively adjusted, which can help jump out of the local optima and improve the global search ability; (2)It renews the global best location of every iteration in two ways, and one way of them is the same as that in QPSO, the other is that double-center particles, together with the current global optimal location, which is used to improve the way of renewing the global best location by cooperating in the corresponding dimensions among them. The performance of this algorithm is analyzed from fixed iterations and fixedprecisions. Experimental results show that compared with QPSO, it has higher convergence rate and better search ability.

Quantum Particle Swarm Optimization(QPSO) algorithm; contraction-expansion coefficient; double-center particle; cooperative; global optimal location

1000-3428(2014)03-0232-06

A

TP301.6

丁 穎(1988－)，女，碩士研究生，主研方向：量子信息技術；李 飛，教授

2013-01-23

2013-03-05 E-mail：dingying_better@163.com

10.3969/j.issn.1000-3428.2014.03.049