基于復合權值自調整策略的量子粒子群優化算法

宋益春，毛 力

（江南大學 物聯網工程學院 輕工過程先進控制教育部重點實驗室，江蘇 無錫214122）

0 引 言

有研究結果表明，運用Solis 和Wets 對粒子群優化（PSO）算法進行關于隨機性算法的收斂性準則理論分析后，發現其無法保證算法全局收斂性和局部收斂性的結論。PSO 算法雖然具有設計簡單、易實現、參數少等諸多優點，但也存在著收斂速度慢、精度差等問題［1，2］。

在Clerc等關于粒子收斂性行為研究的基礎上，Sun等融合量子力學的思想，提出了一種粒子進化模型，即量子粒子群優化 （QPSO）算法［3，4］，該算法認為δ 勢阱中粒子向勢阱中心移動的過程符合粒子搜索尋優的機理，具備量子行為的粒子的搜索范圍擴大至整個可行解區域，移動時不再受速度和方向的束縛，因此它的全局搜索性遠好于一般的PSO 算法。近年來，QPSO 算法在函數優化、神經網絡、多目標優化、聚類分析等領域得到較多的應用［5－8］。

收縮－擴張系數β 是能夠調節QPSO 算法的收斂過程，平衡全局搜索和局部搜索能力，因而是算法控制收斂的一個重要參數。QPSO 算法采用收縮－擴張系數線性遞減的策略［4］，使得β的變化符合粒子群的總體運行方向，但在具體運行過程中沒有獨立于粒子群的實際狀況，影響了收斂速度和收斂精度。基于進化速度－聚集度的動態改變權值策略［9］的量子粒子群 （dynamically changing weight QPSO，DCWQPSO）提出動態改變權值策略中，β的變化依賴于粒子群的進化速度與聚集度的改變，本質上不能避開粒子低效或者失效的情形，陷入局部極小值點，加之采用這策略的QPSO 本身逃逸能力很弱，導致全局搜索能力減弱，收斂精度大打折扣。

對此，本文提出了一種基于復合權值自調整策略的量子粒子群優化算法 （quantum－behaved particle swarm optimization algorithm based on the adaptive strategy of composite weight，ACWQPSO）。此算法采用復合典型線性遞減策略與基于進化速度－聚集度的動態改變權值策略的方法調節收縮－擴張系數β，由此β的改變不但與迭代次數相關聯，而且受算法實際運行的種群集聚態勢的影響，從而可以根據運行的實際情況調整β，有效地平衡全局搜索和局部搜索，進而改善算法的性能。通過5個基準測試函數對收斂性和算法性能進行了分析。實驗結果表明，ACWQPSO 算法在尋優過程中提高了收斂精度，對大部分優化函數都能找到較好的解。

1 量子粒子群優化算法

假設在一個n 維的目標搜索空間中，粒子群中第個個體在第k次迭代中，位置為向量＝，…）∈Rn。第個粒子自身迄今搜索到的最優適應度值位置，記為個體最優極值位置＝（，，…，）；整個粒子群迄今搜索到的最優適應度值位置，記為全局最優極值位置＝（，，…，）。粒子在每一次迭代中追蹤這兩個最優極值位置來完成位置的更新。

Clerc等對PSO 算法中的粒子運動軌跡的研究［10］表明，每個粒子必須收斂于他們各自的局部吸引子qi

式中：L——δ勢阱的特征長度，決定著粒子搜索的范圍。

使用蒙特卡羅隨機模擬的方式可獲得粒子的位置更新方程

式中：u—— （0，1）之間符合均勻分布的隨機數。L 的控制方法對QPSO 的收斂速度和性能有關鍵性的影響，通常采用的是文獻 ［3］中提出的平均最好位置 （mbestk），即所有粒子群個體最好位置的平均

式中：M ——粒子群的種群規模。

最終式 （3）被定義為

式中：β——QPSO 算法的收縮－擴張系數，用于控制粒子的收斂速度，是除了迭代次數和種群規模之外的唯一參數。

2 權值β的選擇策略

文獻 ［4］仿真實驗結果表明，在QPSO 算法中，當β＜1.782時，單個粒子可以收斂到吸引子，算法的收斂性能得到保證。從式 （6）中可以看出，在算法迭代初期，較大的β，算法的收斂速度較快，可以取得較好的全局尋優效果；在算法迭代后期，較小的β，算法的收斂精度較高，可以取得較好的局部尋優效果。對參數β控制通常可以采用固定取值、線性遞減和非線性遞減等方式，但文獻 ［11］通過實驗得出，固定取值策略的魯棒性較差，而線性遞減和非線性遞減兩種慣性權值策略則體現了求解相對穩定的特點。因此，本文嘗試把這兩種策略相融合的方法來確定收縮－擴張系數β。

2.1 線性遞減權值策略

目前對β 的改進策略使用最為普遍的是文獻 ［3，4］中提出線性遞減的策略，表示為

如果在全局尋優能力較強的迭代初期沒有搜索到較優的點，由于搜索空間的縮小不是線性遞減而是高度復雜的，所以這種簡單的線性遞減β，容易使算法陷入局部最優，出現所謂的早熟收斂現象，在一定程度上會影響算法的收斂速度和尋優精度。

2.2 基于進化速度－聚集度的動態改變權值策略

算法運行過程中，QPSO 的收縮－擴張系數β的變化根據粒子群的進化速度和聚集度實時進行調整，從而更加有效地搜索最優解。

由式 （8）可知0＜h≤1。h 的值越小，進化速度就越快。h的值保持為1，則可判斷算法找到了問題的最優值。設Favg是當前所有粒子適應度值的平均值，則

引入聚集度因子s的定義如下

0＜s≤1，s反映了粒子的聚集程度和一定程度上的種群多樣性，s的值增大，表明粒子的聚集程度也提高，同時粒子的多樣性降低。當s的值為1時，全部粒子具有同樣的特征，此時算法陷入局部最優的狀態。

基于這樣的論述，可以把β表示成關于進化速度因子h和聚集度因子s的函數β ＝f（h，s），即

2.3 復合權值自調整策略

2.3.1 復合權值調整策略的參數

線性遞減權重的策略，β 的數值只與迭代次數k 有關，雖沒有很好地匹配算法運行過程中搜索空間非線性變化的特點，但是能夠符合粒子群整體運動的趨勢；動態改變權重的策略中，雖契合粒子群當前的變化態勢，但也存在一旦種群粒子出現低效或失效的情形，就難以避開陷入局部極小的困境，因而此時的β不能準確地反映粒子群的實際狀態變化。綜合考慮，本文引入權重參數λ，提出了用典型的線性遞減策略和動態改變策略相復合的方法來確定收縮－擴張因子β的量子粒子群優化算法

通過對λ值的調整來控制線性遞減策略和進化速度－聚集度的動態改變策略對每一代收縮－擴張因子β的影響程度λ 作為平衡線性權重和動態權重改變的核心參數，它的取值將直接影響到算法的收斂效率。過大的取值將使得混合權重調整策略退化成權值線性遞減策略，算法尋優性能欠佳；過小的取值又將混合權重調整策略改變成動態調整策略，喪失了一般性。

本文使用黃金分割的比例來確定λ，即λ ＝0.618。本文算法以線性遞減策略為主、動態改變權值策略為輔的復合權值，既保證了算法能夠以線性遞減策略跟隨粒子群整體運行趨勢，又避免了過度使用動態改變策略帶來的粒子低效或失效導致收斂精度低的問題。

2.3.2 ACWQPSO 算法執行流程

步驟1 設置種群規模為M，尋優維數為n，最大進化代數MAXITER，h＝0，s＝0，隨機初始化粒子群個體位置；

步驟2 根據目標函數計算出每個粒子的適度值；

步驟3 比較每個粒子的適度值和個體極值，若較優則更新當前個體極值；

步驟4 比較每個粒子的適度值和全局極值，若較優則更新當前全局極值；

步驟5 使用式 （4）計算得到粒子群的平均最優位置；

步驟6 對于粒子的每一維，使用式（1）計算得到一個隨機點的位置，使用式（6）計算得到下一代粒子的位置；

步驟7 根據式 （7）計算出βlin；根據式 （8）、式 （9）、式 （10）、式 （11）計算出βdcw；再根據式 （12）計算出β；

步驟8 重復步驟2～步驟7，直到當前迭代的次數達到預先設定的最大次數，輸出粒子最佳位置，算法結束。

3 仿真實驗及效果評價

本實驗采用表1中5個常用的基準測試函數，這些函數包括了單峰非獨立 （Schwefel）、多峰獨立 （Rastrigin）、多峰非獨立 （Rosenbrock、Griewank、Ackley）3種類型。

表1 全局優化的測試函數

現使用3種不同權值策略的QPSO 算法分別對表1中所列的函數分別進行20次實驗，測試函數的維數為30。算法中參數設置：采用線性遞減策略的標準QPSO［4］中，βstart＝1.0，βend ＝0.5；基于進化速度－聚集度的動態改變權值策略的DCWQPSO［9］中，βini ＝1，ηh ＝0.5，ηs ＝0.2。最大進化次數均取MAXITER ＝1000，種群規模均取M ＝120。經過用Rosenbrock、Rastrigrin和Griewank等典型測試函數測試發現：λ∈（0.6，0.8）時，算法的整體性能較優。

實驗中每種算法對每個測試函數優化所得的平均值、標準差、最優值，見表2。

表2 3種不同權值策略的QPSO 優化結果比較

表2中對Griewank的尋優結果為0，理論上結果不為0；產生這種結果的原因是在MATLAB2009 的仿真環境下，當某個數小于1.0e－324時，輸出結果就為0。

對于表1 中的所有測試函數，表2 的實驗結果表明ACWQPSO 算法尋優的平均值和最好值比其它權值策略的算法跟接近最優值，在算法收斂精度上有一定的提高，標準差反映算法在尋優過程中表現出較強的穩定性。

為了比較這幾種算法的收斂速度，繪制以橫坐標為進化代數，縱坐標為20次實驗的每代的平均最優值的對數的收斂曲線圖，如圖1～圖5所示。

由圖1～圖5的進化曲線中很直觀地看出，算法初期，對比標準QPSO，ACWQPSO 和DCWQPSO 粒子均表現出更快的收斂速度，其中ACWQPSO 的收斂速度稍遜于DCWQPSO，這是因為DCWQPSO 算法初期能夠很好地契合了粒子群運動的方向。但也正是因為收斂速度過快，粒子在局部尋優性能上表現不足，陷入早熟的困境，所以在算法運行的迭代后期，ACWQPSO 的收斂精度上超過DCWQPSO。

圖1 f1 Rosenbrock函數尋優曲線對比

圖2 f2 Rastrigin函數尋優曲線對比

圖3 f3 Griewank函數尋優曲線對比

特別在圖2中，Rastrigin函數具有大量按正弦拐點排列的局部極小點，對優化算法來說是一個極難優化的函數。優化過程中，標準QPSO 和DCWQPSO 都出現了失效狀態，即二者都無法找到全局最優值。DCWQPSO 優化效果次于標準QPSO，表明僅僅使用動態改變權值策略QPSO跳出局部最優值的能力次于標準線性遞減策略QPSO。但兩種策略復合后的ACWQPSO，尋優精度有了一定的提高，比單純的DCWQPSO 好。

圖4 f4Schwefel函數尋優曲線對比

圖5 f5 Ackley函數尋優曲線對比

本文構造的復合權值，整合線性遞減策略和動態改變權值策略，改善了種群的多樣性，能夠有效地均衡全局搜索和局部搜索能力，增進了算法的尋優性能，同時算法的收斂速度也有一定程度地提高。

4 結束語

本文針對QPSO 算法收斂速度緩慢及收斂精度低的問題，對算法收縮－擴張系數β進行了復合權值策略的改進，提出了基于復合權值自調整策略的量子粒子群優化算法。同時將該改進算法與其它兩種權值策略的QPSO 對5個標準測試函數進行了數值實驗。實驗結果表明，復合權值策略能夠適應QPSO 算法早期收斂速度快，盡快讓算法進入局部搜索的要求，也能夠有效地避免陷入局部最優值，提高了算法的收斂精度和穩定性，也說明了算法改進的可行性和有效性。利用本文提出的算法求解其它基準測試函數和解決工程實際問題是筆者下一步的研究方向。

［1］HUANG Shaorong.Survey of particle swarm optimization al－gorithm ［J］.Computer Engineer and Design，2009，30 （8）：1977－1980 （in Chinese）.［黃少榮.粒子群優化算法綜述 ［J］.計算機工程與設計，2009，30 （8）：1977－1980.］

［2］van den Bergh F.A new locally convergent particle swarm optimizer［C］／／IEEE International Conference on Systems，Man and Cybernetics，2002.

［3］Sun J，Fang W，Palade V，et al.Quantum－behaved particle swarm optimization with Gaussian distributed local attractor point［J］.Applied Mathematics and Computation，2011，218（7）：3763－3775.

［4］SUN Jun.Research of quantum－behaved particle swarm optimization algorithm ［D］.Wuxi：Jiangnan University，2009 （in Chinese）.［孫俊.量子行為粒子群優化算法研究 ［D］.無錫：江南大學，2009.］

［5］Ahmad Bagheri，Hamed Mohammadi Peyhani，Mohsen Akbari.Financial forecasting using ANFIS networks with quantum－behaved particle swarm optimization ［J］.Expert Systems with Applications，2014，41 （14）：6235－6250.

［6］Omkar SN，Khandelwal R，Ananth TVS，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.

［7］XU Min，XU Wenbo.Parameter estimation of complex function based on quantum－behaved particle swarm optimization algorithm ［J］.Computer Engineering and Design，2007，28（15）：3665－3667 （in Chinese）.［徐敏，須文波.基于量子粒子群算法的復雜函數參數估計 ［J］.計算機工程與設計，2007，28 （15）：3665－3667.］

［8］Sun Jun.Gene expression data analysis with the clustering method based on an improved quantum－behaved particle swarm optimization ［J］.Engineering Applications of Artificial Intelligence，2012，25 （2），376－391.

［9］HUANG Zexia，YU Youhong，HUANG Decai.Quantum－behaved particle swarm algorithm with self－adapting adjustment of inertia weight ［J］.Journal of Shanghai Jiaotong University，2012，46 （2）：228－232 （in Chinese）.［黃澤霞，俞攸紅，黃德才.慣性權自適應調整的量子粒子群優化算法 ［J］.上海交通大學學報，2012，46 （2）：228－232.］

［10］TANG Jitao，DAI Yueming.Regional shock search embedded particle swarm optimization algorithm ［J］.Computer Engineering and Applications，2013，49 （21）：33－36 （in Chinese）.［湯繼濤，戴月明.內嵌區域震蕩搜索的粒子群優化算法 ［J］.計算機工程與應用，2013，49 （21）：33－36.］

［11］FANG Wei，SUN Jun，XIE Zhenping，et al.Convergence analysis of quantum－behaved particle swarm optimization algorithm and study on its control parameter ［J］.Acta Physica Sinica，2010，59 （6）：3686－3694 （in Chinese）. ［方偉，孫俊，謝振平，等.量子粒子群優化算法的收斂性分析及控制參數研究 ［J］.物理學報，2010，59 （6）：3686－3694.］