基于復(fù)合權(quán)值自調(diào)整策略的量子粒子群優(yōu)化算法

宋益春，毛 力

（江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院 輕工過程先進(jìn)控制教育部重點實驗室，江蘇 無錫214122）

0 引 言

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

在Clerc等關(guān)于粒子收斂性行為研究的基礎(chǔ)上，Sun等融合量子力學(xué)的思想，提出了一種粒子進(jìn)化模型，即量子粒子群優(yōu)化 （QPSO）算法［3，4］，該算法認(rèn)為δ 勢阱中粒子向勢阱中心移動的過程符合粒子搜索尋優(yōu)的機(jī)理，具備量子行為的粒子的搜索范圍擴(kuò)大至整個可行解區(qū)域，移動時不再受速度和方向的束縛，因此它的全局搜索性遠(yuǎn)好于一般的PSO 算法。近年來，QPSO 算法在函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)、多目標(biāo)優(yōu)化、聚類分析等領(lǐng)域得到較多的應(yīng)用［5－8］。

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

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

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

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

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

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

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

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

式中：M ——粒子群的種群規(guī)模。

最終式 （3）被定義為

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

2 權(quán)值β的選擇策略

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

2.1 線性遞減權(quán)值策略

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

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

2.2 基于進(jìn)化速度－聚集度的動態(tài)改變權(quán)值策略

算法運(yùn)行過程中，QPSO 的收縮－擴(kuò)張系數(shù)β的變化根據(jù)粒子群的進(jìn)化速度和聚集度實時進(jìn)行調(diào)整，從而更加有效地搜索最優(yōu)解。

由式 （8）可知0＜h≤1。h 的值越小，進(jìn)化速度就越快。h的值保持為1，則可判斷算法找到了問題的最優(yōu)值。設(shè)Favg是當(dāng)前所有粒子適應(yīng)度值的平均值，則

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

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

基于這樣的論述，可以把β表示成關(guān)于進(jìn)化速度因子h和聚集度因子s的函數(shù)β ＝f（h，s），即

2.3 復(fù)合權(quán)值自調(diào)整策略

2.3.1 復(fù)合權(quán)值調(diào)整策略的參數(shù)

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

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

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

2.3.2 ACWQPSO 算法執(zhí)行流程

步驟1 設(shè)置種群規(guī)模為M，尋優(yōu)維數(shù)為n，最大進(jìn)化代數(shù)MAXITER，h＝0，s＝0，隨機(jī)初始化粒子群個體位置；

步驟2 根據(jù)目標(biāo)函數(shù)計算出每個粒子的適度值；

步驟3 比較每個粒子的適度值和個體極值，若較優(yōu)則更新當(dāng)前個體極值；

步驟4 比較每個粒子的適度值和全局極值，若較優(yōu)則更新當(dāng)前全局極值；

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

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

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

步驟8 重復(fù)步驟2～步驟7，直到當(dāng)前迭代的次數(shù)達(dá)到預(yù)先設(shè)定的最大次數(shù)，輸出粒子最佳位置，算法結(jié)束。

3 仿真實驗及效果評價

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

表1 全局優(yōu)化的測試函數(shù)

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

實驗中每種算法對每個測試函數(shù)優(yōu)化所得的平均值、標(biāo)準(zhǔn)差、最優(yōu)值，見表2。

表2 3種不同權(quán)值策略的QPSO 優(yōu)化結(jié)果比較

表2中對Griewank的尋優(yōu)結(jié)果為0，理論上結(jié)果不為0；產(chǎn)生這種結(jié)果的原因是在MATLAB2009 的仿真環(huán)境下，當(dāng)某個數(shù)小于1.0e－324時，輸出結(jié)果就為0。

對于表1 中的所有測試函數(shù)，表2 的實驗結(jié)果表明ACWQPSO 算法尋優(yōu)的平均值和最好值比其它權(quán)值策略的算法跟接近最優(yōu)值，在算法收斂精度上有一定的提高，標(biāo)準(zhǔn)差反映算法在尋優(yōu)過程中表現(xiàn)出較強(qiáng)的穩(wěn)定性。

為了比較這幾種算法的收斂速度，繪制以橫坐標(biāo)為進(jìn)化代數(shù)，縱坐標(biāo)為20次實驗的每代的平均最優(yōu)值的對數(shù)的收斂曲線圖，如圖1～圖5所示。

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

圖1 f1 Rosenbrock函數(shù)尋優(yōu)曲線對比

圖2 f2 Rastrigin函數(shù)尋優(yōu)曲線對比

圖3 f3 Griewank函數(shù)尋優(yōu)曲線對比

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

圖4 f4Schwefel函數(shù)尋優(yōu)曲線對比

圖5 f5 Ackley函數(shù)尋優(yōu)曲線對比

本文構(gòu)造的復(fù)合權(quán)值，整合線性遞減策略和動態(tài)改變權(quán)值策略，改善了種群的多樣性，能夠有效地均衡全局搜索和局部搜索能力，增進(jìn)了算法的尋優(yōu)性能，同時算法的收斂速度也有一定程度地提高。

4 結(jié)束語

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

［1］HUANG Shaorong.Survey of particle swarm optimization al－gorithm ［J］.Computer Engineer and Design，2009，30 （8）：1977－1980 （in Chinese）.［黃少榮.粒子群優(yōu)化算法綜述 ［J］.計算機(jī)工程與設(shè)計，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，F(xiàn)ang 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）.［孫俊.量子行為粒子群優(yōu)化算法研究 ［D］.無錫：江南大學(xué)，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）.［徐敏，須文波.基于量子粒子群算法的復(fù)雜函數(shù)參數(shù)估計 ［J］.計算機(jī)工程與設(shè)計，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）.［黃澤霞，俞攸紅，黃德才.慣性權(quán)自適應(yīng)調(diào)整的量子粒子群優(yōu)化算法 ［J］.上海交通大學(xué)學(xué)報，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）.［湯繼濤，戴月明.內(nèi)嵌區(qū)域震蕩搜索的粒子群優(yōu)化算法 ［J］.計算機(jī)工程與應(yīng)用，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）. ［方偉，孫俊，謝振平，等.量子粒子群優(yōu)化算法的收斂性分析及控制參數(shù)研究 ［J］.物理學(xué)報，2010，59 （6）：3686－3694.］