薛益鴿

(溫州商學(xué)院信息工程學(xué)院，浙江 溫州 325035)

基于動(dòng)態(tài)分組與混沌擾動(dòng)的改進(jìn)布谷鳥算法

薛益鴿

(溫州商學(xué)院信息工程學(xué)院，浙江 溫州 325035)

針對(duì)布谷鳥算法(CS)求解速度不夠快、精度不夠高的問題，給出一種基于動(dòng)態(tài)分組與混沌擾動(dòng)的改進(jìn)布谷鳥算法(ICS)，并通過5種經(jīng)典的測試函數(shù)對(duì)其性能進(jìn)行測試.仿真實(shí)驗(yàn)結(jié)果表明，ICS比CS有更快的求解速度和更高的求解精度.

布谷鳥搜索算法;混沌擾動(dòng);動(dòng)態(tài)分組

0 引言

20世紀(jì)以來，各種啟發(fā)式算法出現(xiàn)，包括粒子群算法(PSO)[1]、遺傳算法(GA)[2]、蝙蝠算法(BA)[3]、布谷鳥算法(CS)[4]等.

CS算法是一種新型的啟發(fā)式算法，自提出開始便受到學(xué)術(shù)界的廣泛關(guān)注，并不斷得以改進(jìn).如王李進(jìn)等[5]給出了基于逐維改進(jìn)的布谷鳥算法，將對(duì)解的尋優(yōu)從全局轉(zhuǎn)移到了每一個(gè)維度，并通過仿真實(shí)驗(yàn)驗(yàn)證了改進(jìn)的有效性；Wang等[6]給出了基于可變縮放因子的布谷鳥算法，通過改變縮放因子的方式影響解的尋優(yōu)步長與尋優(yōu)方向，一定程度上提高了CS算法的求解速度；Xue等[7]利用動(dòng)態(tài)分組策略改進(jìn)CS算法，給出了基于動(dòng)態(tài)分組的改進(jìn)布谷鳥算法(DGCS)，即對(duì)每次尋優(yōu)的解根據(jù)適應(yīng)值進(jìn)行分組，對(duì)于不同的分組采取不同的調(diào)整步長控制量，從而在較大程度上提高了CS算法的求解精度和求解速度.Wang等[8]利用混沌擾動(dòng)策略改進(jìn)CS算法，進(jìn)一步提高了CS算法的性能.本文將使用動(dòng)態(tài)分組策略與混沌擾動(dòng)策略對(duì)CS算法進(jìn)行改進(jìn).

1 布谷鳥算法

CS算法由Yang等[4]根據(jù)布谷鳥寄生育雛的特殊繁殖方式給出：寄生育雛即布谷鳥會(huì)將自己的鳥蛋產(chǎn)入其他鳥類的鳥巢中讓鳥巢主人為自己孵化幼鳥，鳥巢主人能有一定的概率發(fā)現(xiàn)布谷鳥蛋，這時(shí)它會(huì)毀壞布谷鳥蛋或者放棄自己的鳥巢.

CS算法步驟[4,9-10]總結(jié)如下：

1) (初始化)隨機(jī)生成n個(gè)解，記錄其中適應(yīng)值最優(yōu)的解；

2) (循環(huán)體)使用Lévy-flights隨機(jī)游動(dòng)公式(1)生成新的解集并與舊解集比較，保留較優(yōu)的解，記為lk=[xk,1,xk,2,…,xk,n]；

(1)

3) 對(duì)lk中的每個(gè)解都隨機(jī)生成隨機(jī)數(shù)r～U(0,1)，如r>0.25，對(duì)解使用式(2)進(jìn)行改變；保留適應(yīng)值較優(yōu)的解到下一代，記為jk=[xk,1,xk,2,…,xk,n];

xk+1,i=xk,i+r(xk,j-xk,e).

(2)

其中,r～U(0,1)是縮放因子；xk,j、xk,e是第k代的兩個(gè)隨機(jī)解.

4) 判斷此時(shí)是否滿足算法結(jié)束條件.滿足則輸出最優(yōu)解與最優(yōu)適應(yīng)值；否則，執(zhí)行步驟2.

2 基于動(dòng)態(tài)分組與混沌擾動(dòng)的改進(jìn)布谷鳥算法

2.1 混沌擾動(dòng)策略

啟發(fā)式算法，包括CS算法的求解過程會(huì)依賴種群中其他解的信息，一旦陷入局部收斂就會(huì)降低種群的多樣性從而影響算法的求解速度和精度.CS算法中引入混沌擾動(dòng)可以有效地提高種群多樣性，從而避免種群陷入局部收斂.

混沌擾動(dòng)是在原解上加一個(gè)服從混沌分布的隨機(jī)量[11]，如式(3)所示：

(3)

式中N(0,1)服從標(biāo)準(zhǔn)正態(tài)分布.

設(shè)立記錄板，記錄算法每代的最優(yōu)解的適應(yīng)值，如果連續(xù)3代適應(yīng)值變化極小，則判定為陷入局部收斂，此時(shí)用當(dāng)前最優(yōu)解替代當(dāng)前最差解，用式(3)更新剩下的解，比較更新前后解集的適應(yīng)值，保留較優(yōu)的解到下一代，并選出最優(yōu)解至記錄板.

2.2 動(dòng)態(tài)分組策略

(4)

2) 適應(yīng)值劣于fa的解為第二組，用式(5)更新步長控制向量的對(duì)應(yīng)分量.

(5)

2.3 改進(jìn)算法的流程

1) (初始化) CS算法的解空間維數(shù)為m，算法最大迭代次數(shù)為K，發(fā)現(xiàn)概率為Pa∈[0,1]，最低閾值q，適應(yīng)值連續(xù)不明顯改變代數(shù)a，隨機(jī)生成n個(gè)解，記錄其中適應(yīng)值最優(yōu)的解為x0,b,其最優(yōu)適應(yīng)值fmin,b∈{1,2,…,n]；記錄板記錄fmin.

2) (循環(huán)體)保留上一代的最優(yōu)解，記為xk-1,b.式(4)和(5)改變步長控制向量，使用式(1)生成新的解集并與舊解集lk-1= [xk-1,1,xk-1,2,…,xk-1,n]比較.保留較優(yōu)的解，記為lk=[xk,1,xk,2,…,xk,n]；

3) 對(duì)lk中的每個(gè)解都隨機(jī)生成隨機(jī)數(shù)r～U(0,1)作為鳥巢主人發(fā)現(xiàn)布谷鳥蛋的概率，即發(fā)現(xiàn)概率，如r>Pa，對(duì)解使用式(2)進(jìn)行改變；否則保留此解不變.比較更新前后的解，并保留適應(yīng)值較優(yōu)的解到下一代，記為jk=[xk,1,xk,2,…,xk,n];

4) 計(jì)算jk中最優(yōu)解xk,b與最優(yōu)適應(yīng)值fmin，判斷此時(shí)是否滿足算法結(jié)束條件.滿足則輸出xk,b與fmin；否則，執(zhí)行步驟5.

3 實(shí)驗(yàn)與結(jié)果

3.1 實(shí)驗(yàn)設(shè)計(jì)

為了驗(yàn)證ICS改進(jìn)策略的有效性，對(duì)ICS，CS，DGCS和CCS[8]設(shè)計(jì)仿真實(shí)驗(yàn)進(jìn)行性能比較.仿真環(huán)境為Windows 8，內(nèi)存8.00 GB，機(jī)器主頻2.90 GHz，MATLAB R2016a.各算法參數(shù)的設(shè)計(jì)見表1.

表1 參數(shù)設(shè)計(jì)表Tab. 1 Table of parameter design

表2 測試函數(shù)參數(shù)

本文使用如下5個(gè)基準(zhǔn)測試函數(shù)進(jìn)行測試，各函數(shù)的參數(shù)列于表2.

3.2 實(shí)驗(yàn)結(jié)果分析

3.2.1 4種算法的平均收斂曲線對(duì)比

在種群規(guī)模為20，最大迭代次數(shù)相同，CS，DGCS，CCS和ICS分別獨(dú)立運(yùn)行30次的前提下，4種算法對(duì)5個(gè)測試函數(shù)的收斂曲線見圖1所示.其中當(dāng)前最優(yōu)適應(yīng)值的對(duì)數(shù)平均值(MBFL)計(jì)算公式為：

式中，G為算法的運(yùn)行次數(shù)，gbesti(t)為第i次運(yùn)行第t次迭代的當(dāng)前最優(yōu)值.

由圖1各曲線的變化可見，在算法迭代次數(shù)相同的情況下，ICS相比CS,DGCS和CCS有更快的收斂速度與更高的求解精度.

圖1 4種算法求解測試函數(shù)的平均收斂曲線對(duì)比Fig. 1 Comparison of average convergence curves of test functions by four algorithms

3.2.2 4種算法的全局最優(yōu)值對(duì)比

求解規(guī)模為20，迭代次數(shù)為500，4種算法分別獨(dú)立運(yùn)行30次，比較各自的全局最優(yōu)值.依據(jù)表3中4種算法求解測試函數(shù)的最小值、最大值和平均值可知，ICS算法較CS，DGCS和CCS算法有更高的收斂速度、求解精度.從4種算法的標(biāo)準(zhǔn)差比較則可看出ICS算法相比CS，DGCS和CCS算法有更高的穩(wěn)定性.

表3 4種算法求解函數(shù)的最小值、最大值、平均值對(duì)比Tab. 3 The minimum, maximum, average value comparison of the four algorithms for solving test functions

表4 4種算法的平均迭代次數(shù)對(duì)比

3.2.3 4種算法的平均迭代次數(shù)對(duì)比

求解精度為e-10，4種算法獨(dú)立運(yùn)行30次，每次算法所得最優(yōu)適應(yīng)值精度達(dá)到e-10記錄當(dāng)前迭代次數(shù)，比較30個(gè)迭代次數(shù)的平均值，結(jié)果如表4所示.

可見，在求解精度相同的情況下，ICS算法相對(duì)CS，DGCS和CCS算法能更快地得到目標(biāo)精度，即ICS算法具有更快的求解速度.

4 結(jié)論

本文給出基于動(dòng)態(tài)分組與混沌擾動(dòng)的改進(jìn)布谷鳥算法,用于提高CS算法的收斂速度與求解精度.仿真實(shí)驗(yàn)證明，ICS算法相對(duì)CS，DGCS與CCS算法有更高的收斂速度、求解精度及穩(wěn)定性.

[1] EBERCHART R C, KENNEDY J. Particle swarm optimization[C]//Proceedings of the IEEE International Conference on Neural Networks. Perth： IEEE，1995:1942-1948.

[2] GOLDBERG D E. Genetic algorithms in search, optimization, and machine learning[M]. San Francisco： Addison-Wesley Pub. Co.，1989:2104-2116.

[3] YANG X S. A new metaheuristic bat-inspired algorithm[J]. Nature Inspired Cooperative Strategies for Optimization，2010,284:65-74.

[4] YANG X S, DEB S. Cuckoo search via Lévy flights[C]. Proceedings of World Congress on Nature & Biologically Inspired Computing. Coimbatore: IEEE,2009:210-214.

[5] 王李進(jìn),尹義龍,鐘一文.逐維改進(jìn)的布谷鳥搜索算法[J].軟件學(xué)報(bào),2013(11):2687-2698.

[6] WANG L J, YIN Y L, ZHONG Y W. Cuckoo search with varied scaling factor[J]. Frontiers of Computer Science,2015,9(4):623-635.

[7] XUE Y G, DENG H W. The cuckoo search algorithm based on dynamic grouping to adjust flight scale[J]. Applied Mechanics and Materials,2014,543:1822-1826.

[8] WANG G G, DEB S, GANDOMI A H, et al. Chaotic cuckoo search[J]. Soft Computing,2016,20(9):3349-3362.

[9] VALIAN E, MOHANNA S, TAVAKOLI S. Improved cuckoo search algorithm for global optimization[J]. International Journal of Communications and Information Technology，2011，1(1)：31-44.

[10] 薛益鴿.改進(jìn)的布谷鳥搜索算法及其應(yīng)用研究[D].重慶：西南大學(xué)，2015.

[11] YANG M, HUANG H X, XIAO G Z. A novel dynamic particle swarm optimization algorithm based on chaotic mutation[C]//Second International Workshop on Knowledge Discovery and Data Mining. Moscow: IEEE,2009:656-659.

ImprovedCuckooAlgorithmBasedonDynamicGroupingandChaoticDisturbing

XUE Yige

(College of Information Engineering, Wenzhou Business College, Wenzhou 325035, China)

The cuckoo algorithm (CS) is a new heuristic intelligent algorithm, which has the problem that the solving speed is not fast enough and the solving accuracy is not high enough. An improved cuckoo algorithm(ICS) based on dynamic grouping and chaotic disturbing is given, and the performance of which is tested by 5 classical test functions. The simulation results show that the ICS has faster speed and higher precision than the CS.

cuckoo search algorithm; chaotic disturbing; dynamic grouping

2017-02-10

浙江省教育廳科研項(xiàng)目(Y201636359).

薛益鴿(1990-)，男，助教，碩士，主要從事計(jì)算智能研究.E-mail:15968723096@163.com

10.3969/j.issn.1674-232X.2017.06.020

TP301.6

A

1674-232X(2017)06-0676-05