基于佳點集構造的改進量子粒子群優化算法

陳義雄，梁昔明，黃亞飛

(1. 中南大學 信息科學與工程學院，湖南 長沙，410083；2. 湘潭鋼鐵公司 培訓中心，湖南 湘潭，411104；3. 北京建筑工程學院 理學院，北京，100044)

基于佳點集構造的改進量子粒子群優化算法

陳義雄1,2，梁昔明1,3，黃亞飛1

(1. 中南大學 信息科學與工程學院，湖南 長沙，410083；2. 湘潭鋼鐵公司 培訓中心，湖南 湘潭，411104；3. 北京建筑工程學院 理學院，北京，100044)

針對粒子群優化算法易出現早熟收斂及局部搜索能力不足的特點，提出一種改進的量子粒子群優化算法(IQPSO)。該算法在量子粒子群優化算法(QPSO)的基礎上，引入佳點集初始化量子的初始角位置，提高初始種群的遍歷性；在粒子角速度位置更新中，采用混沌時間序列數，促使粒子跳出局部極值點；為避免粒子陷入早熟收斂，在算法中加入變異處理。仿真實驗結果表明：與標準粒子群優化(SPSO)算法和量子粒子群優化(QPSO)算法比較，提出的算法具有快速的收斂能力、良好的穩定性，其優化性能有較明顯的提高。

粒子群優化；混沌；早熟收斂；佳點集；量子粒子群優化

粒子群優化(PSO)算法[1]最初是由 Kenedy和Eberhart于1995年受人工生命研究結果的啟發，在模擬鳥類捕食行為時提出的一種全局優化算法。PSO不要求被優化函數具有可微、可導、有無梯度等性質，并且算法具有概念簡單、參數設置少、易于實現、收斂速度快等特點，自提出以來得到廣泛的應用。由于PSO容易陷入局部最優、算法收斂精度不高、收斂速度慢、容易遭受維數災的困擾[2]等缺點，很多學者對此提出相應的改進策略。李輝[3]將禁忌搜索算法與粒子群算法結合，提出禁忌粒子群算法；王波等[4]在粒子群優化算法中引入進化算法，提高了預測電網短期負荷的預測精度；林楠[5]提出了動態粒子群優化算法，改善了算法的全局尋優能力和收斂速度；吳軍和李為吉[6]將免疫算法中濃度的概念引入粒子群算法中，提出了一種基于濃度概念的競爭排擠粒子群算法；梁昔明等[7]將動態隨機搜索和佳點集引入到粒子群優化算法中，提高了收斂速度和粒子跳出局部最優能力；丁華福等[8]針對慣性權重線性遞減粒子群算法不能適應復雜的非線性優化搜索過程的問題，提出了一種基于Sigmoid函數和聚集距離變化率改變慣性權重的方法；王俊偉和王定偉[9]利用梯度信息來影響粒子速度的更新，提高了算法的搜索效率；李士勇和李盼池[10]將量子進化算法(QEA)融合到PSO中，提出一種新穎的量子粒子群優化算法(QPSO)。這些改進算法在很大程度上依賴于對初始參數的選擇，容易陷入局部最優，導致早熟收斂；部分算法雖然提高了局部搜索能力，避免了早熟收斂，但不同程度地降低了收斂速度[11]。針對上述問題，本文作者提出一種基于佳點集構造的改進量子粒子群優化(IQPSO) 算法。運用佳點集構造初始化量子位置的初始角度，提高量子初始位置的遍歷性；在算法中引入變異算子增加了種群的多樣性，避免早熟收斂。

1 標準粒子群優化算法

粒子群優化算法模擬鳥群飛行覓食的行為，通過鳥之間的集體協作與競爭使群體達到目的。為改善算法的收斂性能，Shi和 Eberhart[12]引入慣性權重的概念，對速度的更新方程做了修改，這種方法被稱為標準粒子群優化(SPSO)算法。標準粒子群優化 (SPSO)算法可描述為：第i個粒子在D維搜索空間中的位置為 xi=[xi,1，xi,2，…，xi,D]T，速度為 vi=[vi,1，vi,2，…，vi,D]T，M為粒子的種群規模，第i個粒子搜索到的歷史最優位置為Pi=[pi,1，pi,2，…，pi,D]T，整個種群搜索到的最優位置為Pg=[pg,1，pg,2，…，pg,D]T，將xi帶入目標函數計算其適應值，同時利用下列公式不斷地更新粒子的位置和速度，并比較適應值直至找到最優解。

其中：i=1，2，…，M；j=1，2，…，D；t為迭代次數；w為慣性權重；c1和c2為學習因子；r1和r2為區間[0,1]內的隨機數。另外，粒子在每一維飛行的最大速度為Vmax，即式(1)中|vi,j|＞Vmax時，取|vi,j|=Vmax。粒子在解空間內不斷的進行個體尋優與全局尋優，直到達到規定的迭代次數或滿足給定的誤差標準為止。

2 改進的量子粒子群優化算法

2.1 改進的量子粒子群優化算法的基本思想

為提高標準PSO算法的局部搜索能力，避免陷入早熟收斂。本文作者在QPSO算法的基礎上，結合佳點集構造理論，提出一種改進的量子粒子群優化算法。其基本思想是在量子粒子群算法中，采用佳點集構造理論取點分布均勻的特點，使種群初始化更為均勻，提高初始種群的遍歷性；將慣性因子設置為混沌時間序列數，使粒子能跳出局部極值點；從而達到全局尋優的目的。

2.2 量子粒子群優化算法

量子粒子群[10](QPSO)算法是受量子力學的啟發，最近幾年發展起來的一種優化方法。在QPSO算法中，為提高解空間的遍歷能力，該算法采用概率幅的編碼機制；采用量子旋轉門實現粒子的移動，用量子非門對粒子進行變異；量子位幅角增量用下式進行更新。

其中：c1，c2，r1和r2的含義與其在SPSO算法中的含義相同，取值也基本相似；w為混沌時間序列數映射到[0.1，0.9]區間上的數值；θ為量子比特的相位；Δθl為當前個體和個體之間的角度差；Δθg為當前個體與全局最優之間的角度差，計算公式如下：

在QPSO中，用量子非門實現變異操作。其操作過程如下：

令變異概率為pm，每個粒子在(0,1)之間設定一個隨機數，則用量子非門兌換2個概率幅，該粒子記憶的自身最優位置和轉向角仍保持不變。

在QPSO中由于采用量子位概率幅的編碼機制擴展解空間的遍歷性，在群體規模不變的情況下，有利于提高算法的優化效率。

2.3 佳點集

佳點集最初由華羅庚等[13]提出，其基本定義與構造為：設Gs是s維歐氏空間中的單位立方體，如果r中：C(r，ε)是只與r和ε(ε是任意的正數)有關的常數，則稱Pn(k)為佳點集，r為佳點。取r={2cos(2πk/p)，1≤k≤s}(p是滿足(p?3)/2≥s的最小素數，則r為佳點。

采用佳點集法和隨機法生成二維初始種群進行對比，如圖1所示。從圖1可見：在相同的取點個數下，佳點集法取點比隨機法取點更為均勻。因此，將Gs上佳點映射到目標求解空間，使初始種群更具有遍歷性，從而更好的達到全局尋優的目的。利用佳點集法產生的二維圖形，無論經過多少次計算，只要種群數量一定，其產生的圖形都是確定不變的，即具有相當的穩定性。

圖1 二維初始種群分布圖Fig. 1 2-D initial population distribution

2.4 改進量子粒子群優化算法步驟

算法的具體步驟如下：

Step 1：設置IQPSO初始化的有關參數，如種群規模、變量個數、迭代次數、解空間范圍等。

Step 2：應用佳點集理論對種群幅角進行初始化。

Step 3：利用適應度函數對每個粒子的初始位置進行評價，計算出每個粒子位置的適應值。若粒子目前的位置優于自身記憶的最優位置，則用目前位置替換；若目前全局最優位置優于到目前為止搜索到的最優位置，則用全局最優位置替換。

Step 4：根據式(3)和(4)更新粒子的位置。

Step 5：對每個粒子依變異概率，根據式(7)實現變異操作。

Step 6：返回Step 3循環計算，直到滿足收斂條件或迭代次數達到最大限制為止。收斂條件由具體問題決定。

3 數值仿真

為測試本文提出的IQPSO算法的優化效果，進行大量的計算機數值實驗，并且與SPSO和QPSO[10]進行實驗比較。選取其中的某些測試函數[14](如表 1所示)，分別采用SPSO，QPSO和IQPSO算法各優化20次，3種算法種群規模均取20，最大迭代次數取300。算法的參數設置：慣性權重w取值范圍為[0.1，0.9]的混沌時間序列數，自身因子和全局因子取c1=c2=2.0，變異概率取pm=0.05，收斂精度設為 1×10?2。優化結果對比如表2所示，其中BEST，MEAN和SD分別表示算法獨立運算300次的最好適應值、平均適應值和適應值方差；表2中的收斂步數表示達到收斂精度計算的平均步數(沒有達到收斂精度的不進行計算)。

由表 2的數據對比可知：對 6個函數的測試，IQPSO算法產生適應值的最好結果、平均結果都優于SPSO和QPSO算法產生的結果，更接近于目標函數值；6個函數的標準差比較，IQPSO算法產生的標準差更小，說明IQPSO算法在函數的每次優化過程中穩定性更高；從收斂次數看，在優化過程中IQPSO達到精度要求的次數明顯高于SPSO和QPSO算法。

為更直觀地反映算法的尋優效果，將IQPSO算法與SPSO算法、QPSO算法的相關測試函數的收斂曲線的結果進行對比，如圖2所示。從圖2可以看出：對6個函數的測試，在迭代后期，IQPSO算法比SPSO、QPSO算法更易跳出局部極值點，避免早熟收斂。從圖2(f)可以看出：SPSO算法在迭代后期已陷入局部極值點。

表1 基準測試函數Table 1 Benchmark test function

表2 3種算法對函數極值問題的優化結果對比Table 2 Comparison of optimization results between proposed algorithm and other algorithms

圖2 測試函數收斂曲線Fig. 2 Convergence curve of test function

綜合以上可見，無論是算法的收斂精度還是收斂能力，IQPSO算法都比SPSO和QPSO算法有較大的提高。引進佳點集法后，提高了初始種群的遍歷性，初始種群分布更為均勻，從而提高了種群的全局尋優能力；慣性因子中引入混沌時間序列數，可以使粒子跳出局部極值點，避免早熟收斂。對于單峰函數和多峰函數，IQPSO算法都取得了相對滿意的優化效果。本文提出的基于佳點集構造的改進量子粒子群算法提高了算法的全局搜索能力，算法的尋優性能得到改善。

4 結論

(1) 將引入佳點集構造初始化種群，使初始種群具有遍歷性，提高了解空間的搜索能力；角速度中的慣性因子采用混沌時間序列數，可以使粒子遍歷解空間，避免粒子陷入局部最優；同時，為避免粒子陷入早熟收斂，在算法中加入了變異處理。

(2) 仿真結果表明：基于佳點集構造的改進量子粒子群優化算法(IQPSO)，與標準粒子群優化(SPSO)算法和量子粒子群優化(QPSO)算法相比較，在尋優能力上，提出的算法具有快速的收斂能力，優化性能有較明顯的提高。

[1] Kennedy J, Eberhart R C. Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ: IEEE Press, 1995: 1942?1948.

[2] 曾建潮, 介婧, 崔志華. 微粒群算法[M]. 北京: 科學出版社,2004: 1?23, 116?139.

CENG Jianchao, JIE Jing, CUI Zhihua. Particle swarm optimization[M]. Beijing: Science Press, 2004: 1?23, 116?139.

[3] 李輝. 禁忌粒子群算法[J]. 陜西理工學院學報: 自然科學版,2011, 27(1): 85?90.

LI Hui. The taboo particle swarm optimization[J]. Journal of Shananxi University of Technology: Natural Science Edition,2011, 27(1): 85?90.

[4] 王波, 邰能靈, 翟海青, 等. 基于混合粒子群算法的短期負荷預測模型[J]. 電力系統及其自動化學報, 2008, 20(3): 50?55.

WANG Bo, TAI Nengling, ZHAI Haiqing, et al. Hybrid optimization method based on evolutionary algorithm and particle swarm optimization for short-term load forecasting[J].Journal of Electric Power System and its Automation, 2008,20(3): 50?55.

[5] 林楠. 一種新型的動態粒子群優化算法[J]. 計算機應用研究,2011, 28(3): 935?937.

LIN Nan. Newel dynamic particle swarm optimization algorithm[J]. Application Research of Computers, 2011, 28(3):935?937.

[6] 吳軍, 李為吉. 改進的粒子群算法及在結構優化中的應用[J].陜西理工學院學報, 2006, 22(4): 36?39.

WU Jun, LI Weiji. Improved particle swarm optimization and its application to structural optimum design[J]. Journal of Shaanxi University of Technology, 2006, 22(4): 36?39.

[7] 梁昔明, 陳富, 龍文. 基于動態隨機搜索和佳點集構造的改進粒子群優化算法[J]. 計算機應用, 2011, 31(10): 2796?2799.

LIANG Ximing, CHEN Fu, LONG Wen. Improved particle swarm optimization based on dynamic random search technique and good-point set[J]. Journal of Computer Applications, 2011,31(10): 2796?2799.

[8] 丁華福, 姜曉偉, 王麗雪. 基于禁忌搜索的自適應粒子群算法[J]. 計算機技術與發展, 2010, 20(4): 140?143.

DING Huafu, JIANG Xiaowei, WANG Lixue. Adaptive particle swarm optimization algorithm based on tabu search[J].Computer Technology and Development, 2010, 20(4): 140?143.

[9] 王俊偉, 王定偉. 一種帶有梯度加速的粒子群算法[J]. 控制與決策, 2004, 19(11): 1298?1300.

WANG Junwei, WANG Dingwei. Particle swarm optimization algorithm with gradient acceleration[J]. Control and Decision,2004, 19(11): 1298?1300.

[10] 李士勇, 李盼池. 求解連續空間優化問題的量子粒子群算法[J]. 量子電子學報, 2007, 24(5): 569?574.

LI Shiyong, LI Panchi. Quantum particle swarms algorithm for continuous space optimization[J]. Chinese Journal of Quantum Electronics, 2007, 24(5): 569?574.

[11] Chen B R, Feng X T. Particle swarm optimization with contracted ranges of both search space and velocity[J]. Journal of Northeastern University: Natural Science, 2005, 26(5): 488?491.

[12] Shi Y, Eberhart R. A modified particle swarm optimizer[C]//IEEE International Conference on Evolutionary Computation Proceedings, Anchorage, AK: IEEE, 1998: 69?73.

[13] 華羅庚, 王元. 數論在近代分析中的應用[M]. 北京: 科學出版社, 1978: 1?99.HUA Luogeng, WANG Yuan. The application of number theory in the modern analysis[M]. Beijing: Science Press, 1978: 1?99.

[14] Yao X, Liu Y, Lin G M. Evolutionary programming made faster[J]. IEEE Transactions on Evolutionary Computation, 1999,3(2): 82?102.

(編輯 鄧履翔)

Improved quantum particle swarm optimization based on good-point set

CHEN Yixiong1,2, LIANG Ximing1,3, HUANG Yafei1

(1. School of Information Science and Engineering, Central South University, Changsha 410083, China;2. Training Center, Xiangtan Iron & Steel Co. Ltd., Xiangtan 411104, China;3. School of Science, Beijing University of Civil Engineering and Architecture, Beijing 100044, China)

In order to solve the problems of premature convergence and poor local search on particle swarm optimization(PSO) algorithm, an improved quantum particle swarm optimization(IQPSO) approach was proposed. Based on quantum particle swarm optimization algorithm (QPSO), good-point set was introduced to the approach to initialize initial angle of quantum position, to improve ergodicity of initial population. To make particle jump out of local extreme value point, the chaotic time series numbers were used to update particle velocity. To prevent particle from premature convergence,mutation process was added in the approach. The simulation experiment results show that the improved algorithm has rapid convergence, good stability and it gives better performance than standard particle swarm optimization (SPSO) and quantum particle swarm optimization (QPSO).

particle swarm optimization; chaos; premature convergence; good-point set; quantum particle swarm optimization

TP301.6

A

1672?7207(2013)04?1409?06

2012?07?28；

2012?10?23

北京市自然科學基金資助項目(4122022)；湖南省教育廳項目(10C0373)

陳義雄(1974?)，男，湖南東安人，工程師，博士研究生，從事智能優化算法研究；電話：13786203764；E-mail：chenyixiong_neu@163.com