丁 穎，李 飛

?

自適應(yīng)收擴系數(shù)的雙中心協(xié)作QPSO算法

丁 穎a，李 飛b

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

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

量子粒子群優(yōu)化算法；收縮-擴張系數(shù)；雙中心粒子；協(xié)作；全局最優(yōu)位置

1 概述

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

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

2 QPSO的基本原理

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

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

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

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

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

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

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

3.1 AQPSO的基本原理

3.1.1 自適應(yīng)收縮-擴張系數(shù)

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

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

α和h的關(guān)系如圖1和圖2表示。

圖1 hmax==hmin時αi的值

圖2 hmax≠hmin時αi的值

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

3.1.2 雙重更新全局最優(yōu)位置策略

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

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

圖3 粒子間合作示意圖

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

3.2 AQPSO算法流程

AQPSO算法具體步驟如下：

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

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

Step3計算前–2個粒子的適應(yīng)度函數(shù)值。

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

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

Step6計算雙中心粒子的適應(yīng)度函數(shù)值。

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

Step8利用3.1.2節(jié)的第2種方式更新p。

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

4 性能測試與結(jié)果分析

4.1 測試函數(shù)

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

表1 測試函數(shù)

4.2 固定迭代次數(shù)的測試結(jié)果與分析

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

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

表2 固定迭代次數(shù)的仿真結(jié)果

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

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

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

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

4.3 固定精度的測試結(jié)果與分析

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

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

表3 固定精度的仿真結(jié)果

5 結(jié)束語

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

[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] 李盼池, 王海英. 量子勢阱粒子群優(yōu)化算法的改進研究[J]. 物理學報, 2012, 61(6): 19-27.

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

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

[6] 程 偉, 陳森發(fā). 權(quán)重自適應(yīng)調(diào)整的混沌量子粒子群優(yōu) 化[J]. 計算機工程與應(yīng)用, 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] 胡苓苓, 郭業(yè)才. 基于QPSO的小波分數(shù)間隔盲均衡算 法[J]. 計算機工程, 2011, 37(24): 195-197.

[10] 湯可宗, 柳炳祥. 雙中心粒子優(yōu)化算法[J]. 計算機研究與發(fā)展, 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] 陳 偉, 周 頔, 孫俊陳, 等. 一種采用完全學習策略的量子行為粒子群優(yōu)化算法[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－)，女，碩士研究生，主研方向：量子信息技術(shù)；李 飛，教授

2013-01-23

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

10.3969/j.issn.1000-3428.2014.03.049