楊榮瑩，何 慶，王 茜 ，林 杰

1(貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴陽 550025) 2(貴州省公共大數(shù)據(jù)重點(diǎn)實(shí)驗(yàn)室，貴陽 550025)

1 引 言

隨著科學(xué)技術(shù)的發(fā)展，傳統(tǒng)優(yōu)化機(jī)制不能滿足實(shí)際優(yōu)化問題中精度高、速度快、穩(wěn)定性強(qiáng)等需求.由此，長期以來，眾學(xué)者致力于發(fā)掘適合各種應(yīng)用場(chǎng)景的優(yōu)化策略，開發(fā)了多種群體仿生智能優(yōu)化算法.如螢火蟲算法(Firefly Algorithm，F(xiàn)A)[1]、人工蜂群算法(Artificial Bee Colony，ABC)[2]、粒子群算法(Particle Swarm Optimization，PSO)[3]、蝙蝠算法(Bat Algorithm，BA)[4]；灰狼優(yōu)化算法(Grey Wolf Optimization，GWO)[5]等等.

布谷鳥搜索算法(Cuckoo Search，CS)于2009年提出，是模擬布谷鳥育雛行為和萊維飛行機(jī)制的仿生優(yōu)化算法[6]，現(xiàn)已被廣泛應(yīng)用于實(shí)際優(yōu)化問題中.劉等人[7]在優(yōu)化配送路徑時(shí)，提出了基于定向變異的布谷鳥算法；孫等人[8]提出多種群并行CS算法對(duì)防空火力分配進(jìn)行優(yōu)化；張等人[9]將改進(jìn)的多目標(biāo)CS算法應(yīng)用于氣動(dòng)優(yōu)化問題中；文獻(xiàn)[10]在K均值聚類中利用CS進(jìn)行優(yōu)化，旨在Twitter的情感內(nèi)容中尋找最優(yōu)簇頭.

然而，當(dāng)面對(duì)NP難、適應(yīng)度函數(shù)復(fù)雜且高維度的實(shí)際優(yōu)化環(huán)境時(shí)，因CS易早熟、收斂速度慢、勘測(cè)開發(fā)不平衡、種群多樣性低等缺陷遭遇瓶頸.于此，許多學(xué)者對(duì)CS算法進(jìn)行改進(jìn).Lian等[11]將PSO的位置更新方式嵌入萊維機(jī)制中，提出了新布谷鳥算法(New Cuckoo Search，NCS)，結(jié)果表明，通過NCS得到的解均優(yōu)于PSO和CS，但該算法魯棒性弱、求解精度低；張等人[12]在CS中運(yùn)用交互學(xué)習(xí)方式融合蟻群算法構(gòu)造學(xué)習(xí)模型，動(dòng)態(tài)更新步長和發(fā)現(xiàn)概率，然而該算法無法有效提升CS的種群多樣性(1)http://kns.cnki.net/kcms/detail/11.2127.TP.20190409.1706.028.html. 2 https://doi.org/10.19734/j.issn.10013695.2018.10.0725.；黃等人[13]在CS中引進(jìn)逐維處理和反向?qū)W習(xí)策略，以降低維間干擾，但該機(jī)制增加了算法的時(shí)間復(fù)雜度2；文獻(xiàn)[14]在CS中構(gòu)建3組更新策略，采用Snap-drift機(jī)制改進(jìn)發(fā)現(xiàn)概率，但此算法隨機(jī)性較強(qiáng)；為增強(qiáng)CS的局部開發(fā)能力，文獻(xiàn)[15]融合Powell方法提出Powell Cuckoo Search(PCS)，從結(jié)果看，該混合算法的求解精度和收斂速度已不能滿足現(xiàn)在尋優(yōu)需求；張燕[16]利用Cubic混沌算子改進(jìn)位置更新機(jī)制并引入自適應(yīng)策略，既提高算法的求解質(zhì)量，也擴(kuò)大種群多樣性.

統(tǒng)計(jì)發(fā)現(xiàn)，大部分改進(jìn)CS算法中，位置更新策略固定，尋優(yōu)搜索采用的鳥巢信息片面，缺乏多類別的種群個(gè)體信息；僅鎖定迭代次數(shù)與發(fā)現(xiàn)概率的關(guān)系，忽略了適應(yīng)度變化對(duì)發(fā)現(xiàn)概率的影響.而采用具有單一信息的個(gè)體搜索種群，會(huì)降低種群多樣性、限制算法搜索活力[17].因此，本文提出一種信息交互的動(dòng)態(tài)選擇布谷鳥算法(dynamic selection cuckoo search algorithm of information interaction，II-DSCS).首先，改進(jìn)更新策略，在偽隨機(jī)因子擾動(dòng)下，從樣本整體(既種群整體N1)、當(dāng)代最優(yōu)(N2)、自身個(gè)體(N3)中采集鳥巢信息，構(gòu)建N1、N2、N3彼此間的交互信息，建立3組位置更新模式.交互信息反映了種群的尋優(yōu)情況，依據(jù)交互信息可調(diào)整算法的搜索方向使算法向最優(yōu)解靠近，增加算法尋優(yōu)速度，在搜索時(shí)，采用交互信息可增強(qiáng)搜索空間多樣性.其次，對(duì)隨機(jī)游走策略進(jìn)行雙向擾動(dòng)，利用擾動(dòng)因子構(gòu)建兩組游走機(jī)制.此外，為提升尋優(yōu)收斂效率，利用鳥巢解的差異度自適應(yīng)地更新發(fā)現(xiàn)概率.最終結(jié)果表明II-DSCS可以提高算法的求解精度，增強(qiáng)算法的搜索活力，加快算法的收斂速度.

2 標(biāo)準(zhǔn)布谷鳥搜索算法

布谷鳥算法起源于布谷鳥寄生育雛的繁衍模式，布谷鳥將自己的蛋放入其他鳥巢，由該巢主進(jìn)行孵化，為保證幼雛存活率，布谷鳥必須找到最優(yōu)鳥巢.基于此原理，將優(yōu)化問題的解映射為巢穴，巢的優(yōu)劣代表優(yōu)化問題中解質(zhì)量的高低，尋優(yōu)既找尋優(yōu)質(zhì)鳥巢的過程，其遵照萊維機(jī)制和偏好隨機(jī)游走策略來更新種群中鳥巢的位置.CS有3項(xiàng)理想準(zhǔn)則：

a)一鳥一蛋，把蛋隨機(jī)放入宿主鳥的鳥巢中；

b)每進(jìn)化一次，都將最優(yōu)質(zhì)的鳥巢保存至下一次進(jìn)化；

c)種群中鳥巢數(shù)量固定，巢主以概率Pa發(fā)現(xiàn)布谷鳥放入的蛋并丟棄該蛋.

在CS中，以萊維飛行機(jī)制更新鳥巢的位置，其表達(dá)式如下：

(1)

(2)

巢穴更新后，計(jì)算巢的優(yōu)劣度，用一個(gè)均勻分布的隨機(jī)數(shù)與發(fā)現(xiàn)概率比較，發(fā)現(xiàn)概率小于隨機(jī)數(shù)則丟棄劣質(zhì)的巢，重新構(gòu)造鳥巢位置，更新公式如下所示：

(3)

3 II-DSCS

3.1 萊維機(jī)制改進(jìn)

在標(biāo)準(zhǔn)CS中，萊維飛行雖然能有效探索全局空間，但只利用當(dāng)前解與最優(yōu)解更新鳥巢位置，種群信息受限，更新方式單調(diào).這使算法在迭代前期無法獵獲更多樣的種群信息，限制算法的搜索范圍，群間多樣性差，算法搜索活力低；在迭代中后期，個(gè)體間相似度較高，算法陷入局部極值的概率增大；此外，更新方式單一，采集的個(gè)體信息片面，綜合性、實(shí)時(shí)性的種群尋優(yōu)數(shù)據(jù)在搜索過程中被忽略.因此，在保留萊維特性的基礎(chǔ)下，引進(jìn)新的個(gè)體信息，將多類別交互信息融入位置更新策略中，利用該信息擴(kuò)展搜索空間多樣性，開辟新的搜索領(lǐng)域.交互信息反映種群內(nèi)個(gè)體之間適應(yīng)度的差異，根據(jù)差異可及時(shí)調(diào)整算法進(jìn)化方向，加快搜索速度，即使在高維復(fù)雜環(huán)境下，算法也能快速向最優(yōu)解靠近.基于上述，改進(jìn)的萊維機(jī)制表達(dá)式如式(4)所示：

(4)

(5)

cauchy的數(shù)學(xué)表示為：

(6)

上式中，g=1為尺度參數(shù).

式(4)中，構(gòu)建3組位置更新策略.通過“減法”構(gòu)建信息的交互機(jī)制，分別從種群整體(N1)、當(dāng)代最優(yōu)(N2)、當(dāng)前個(gè)體(N3)獲取鳥巢交互信息，將此信息實(shí)時(shí)嵌入位置更新中，及時(shí)掌握鳥巢內(nèi)適應(yīng)度的優(yōu)劣狀況，再利用隨機(jī)策略選擇位置更新方式.為確保交互信息的全面性和總體性，采用Cauchy算子對(duì)隨機(jī)鳥巢進(jìn)行擾動(dòng)，柯西算子可以無重復(fù)地遍歷種群中每個(gè)個(gè)體，使算法更大限度地收集種群個(gè)體信息，延展交互信息領(lǐng)域[18].

采用更新策略1時(shí)，在柯西算子擾動(dòng)下，利用種群內(nèi)兩個(gè)隨機(jī)鳥巢的差值來衡量所有個(gè)體的差異度(構(gòu)建N1與N1的交互信息)，在N1&N1(種群整體)領(lǐng)域進(jìn)行全局尋優(yōu)；在更新策略2中，依據(jù)柯西算子選擇一個(gè)隨機(jī)鳥巢，并評(píng)價(jià)N1與N2的適應(yīng)度差異(構(gòu)建N1與N2的交互信息)，在N1&N2維度上來更新鳥巢位置(進(jìn)行以N2為核心的局部搜索)；更新策略3中，構(gòu)建N1與N3的交互信息，考量N1與N3的差異，在N1&N3內(nèi)尋優(yōu)搜索(進(jìn)行以N3為主干的局部搜索).該改進(jìn)策略，依據(jù)N1、N2、N3的交互信息進(jìn)行多方位的位置更新，全面評(píng)估種群差異與尋優(yōu)情況，充分拓展算法的搜索范圍；隨機(jī)選擇位置更新策略，使算法在全局與局部之間動(dòng)態(tài)尋優(yōu)，克服勘測(cè)開發(fā)不均衡問題；基于柯西算子引入實(shí)時(shí)個(gè)體信息，最大化地增加種群多樣性.

3.2 偏好隨機(jī)游走策略改進(jìn)

標(biāo)準(zhǔn)CS算法經(jīng)發(fā)現(xiàn)概率丟棄劣解后對(duì)鳥巢位置進(jìn)行更新，并采用精英策略保留最優(yōu)值至下一代，隨著算法迭代加深，鳥巢信息相似度升高，搜索空間多樣降低，陷入局部極值概率增大，尋優(yōu)能力受到干擾.因此，依據(jù)3.1節(jié)理論，將動(dòng)態(tài)選擇、信息交互思想與偏好隨機(jī)游走策略融合，以提高算法種群多樣性和搜索性能，消除局部極值的約束.對(duì)式(3)做改進(jìn)，表達(dá)式如式(7)所示：

(7)

式(7)中，M=0.5，A=rand(1，ps)，P∈(-1，1)為隨機(jī)數(shù).

式(7)中，利用“減法”交互機(jī)制，構(gòu)建擾動(dòng)鳥巢(受縮放因子P擾動(dòng))與隨機(jī)鳥巢的交互信息，組成一個(gè)新的位置更新策略；保留原始的偏好隨機(jī)游走策略(既P擾動(dòng)兩個(gè)隨機(jī)鳥巢的交互信息)作為另一組位置更新方式；此外，將標(biāo)準(zhǔn)CS中R∈(0，1)變成P∈(-1，1)，將單向(正向)擾動(dòng)擴(kuò)展成正反雙向擾動(dòng).該位置更新模型由兩組攜帶不同交互信息的更新機(jī)制組成，克服了單一的更新方式，動(dòng)態(tài)選擇機(jī)制將利用更多樣的鳥巢信息解鎖新的搜索空間，既提高算法種群多樣性，又改善算法尋優(yōu)效率.

3.3 發(fā)現(xiàn)概率改進(jìn)

在CS算法中，發(fā)現(xiàn)概率Pa是平衡全局探索和局部開發(fā)的重要指標(biāo)，其大小影響著算法的收斂速度和尋優(yōu)精度.而傳統(tǒng)CS的Pa是固定值，無法自適應(yīng)變化，在迭代過程中可能會(huì)丟棄過多的鳥巢導(dǎo)致多樣性降低，算法求解能力受限.針對(duì)以上問題，對(duì)發(fā)現(xiàn)概率做自適應(yīng)動(dòng)態(tài)改進(jìn)，在Pa中融合迭代、種群適應(yīng)度信息，依據(jù)迭代程度動(dòng)態(tài)選擇丟棄概率，改進(jìn)的發(fā)現(xiàn)概率為：

(8)

m=fmax-fmin

(9)

(10)

式(8)中，iter為當(dāng)前迭代次數(shù)，Maxiter為最大迭代次數(shù)，式(9)中，fmax、fmin、avgen(iter)分別為每一輪迭代時(shí)適應(yīng)度的最大值、最小值、平均值.

以上3個(gè)式子中，以攜帶迭代信息的Pa1作為控制參數(shù)操縱Pa，將每輪迭代時(shí)適應(yīng)度的平均值和最大差異值作為發(fā)現(xiàn)概率的選擇指標(biāo).若差異值大于平均適應(yīng)度，種群內(nèi)個(gè)體之間的差距過大，算法表現(xiàn)較弱，此時(shí)應(yīng)增大丟棄的可能性，降低發(fā)現(xiàn)概率；若差異小于或等于平均適應(yīng)度，表明個(gè)體向最優(yōu)解聚攏，應(yīng)保留更多優(yōu)質(zhì)解，減小丟棄可能性，增加發(fā)現(xiàn)概率.此策略組合適應(yīng)度與迭代次數(shù)的信息，更精準(zhǔn)地估量進(jìn)化程度并調(diào)整發(fā)現(xiàn)概率，提高進(jìn)化與收斂速度，平衡局部開發(fā)與全局探索.

3.4 II-DSCS算法實(shí)現(xiàn)流程

交互信息的動(dòng)態(tài)選擇布谷鳥算法的主要步驟為：

a)設(shè)置種群規(guī)模、迭代次數(shù)、初始位置等初始參數(shù)；

b)計(jì)算種群中所有個(gè)體的適應(yīng)度，并保留最優(yōu)解；

c)根據(jù)式(4)進(jìn)行位置更新，并計(jì)算所有個(gè)體的適應(yīng)度，保留最優(yōu)解至下一代.

d)利用式(10)計(jì)算發(fā)現(xiàn)概率，比較Pa與隨機(jī)數(shù)K，若K>Pa，丟棄劣質(zhì)巢穴，利用式(7)進(jìn)行位置的更新；反之，保持當(dāng)前鳥巢位置不變；

e)計(jì)算經(jīng)過步驟d)變化后每個(gè)鳥巢適應(yīng)度，并保留最優(yōu)鳥巢進(jìn)行下一輪的進(jìn)化；

f)判斷算法終止條件，若滿足，則輸出最后結(jié)果；反之，返回步驟c)繼續(xù)進(jìn)化，直到滿足結(jié)束條件為止.

該改進(jìn)算法的流程圖如圖1所示.

圖1 II-DSCS算法流程圖Fig.1 Schematic diagram of II-DSCS algorithm

4 實(shí)驗(yàn)與分析

為檢驗(yàn)II-DSCS算法的有效性，選取12個(gè)具有不同特征的經(jīng)典基準(zhǔn)函數(shù)進(jìn)行仿真實(shí)驗(yàn)，將該算法與PSO[3]、CS[6]以及CS的3個(gè)變體NCS[11]、DA-DOCS[13]、SDCS(Snap-drift cuckoo search)[14]進(jìn)行比較.該仿真實(shí)驗(yàn)在MATLAB R2015b、corei5、32位windows7操作系統(tǒng)下進(jìn)行.

4.1 函數(shù)與參數(shù)設(shè)置

12種基準(zhǔn)函數(shù)如表1所示，包括6個(gè)單模態(tài)函數(shù)(F1-F6)和6個(gè)多模態(tài)函數(shù)(F7-F12)，F(xiàn)1在搜索空間下，極值唯一，用于檢驗(yàn)算法的尋優(yōu)能力；F7的全局最優(yōu)點(diǎn)位于一個(gè)平滑、狹長的拋物線形峰谷內(nèi)，算法提供的有限信息使其在尋優(yōu)時(shí)很難辨別搜索方向，搜索難度大；F5與F9用來檢測(cè)算法的收斂性能，與F5不同的是，F(xiàn)9在多維空間下，其順著梯度的尋優(yōu)方向是多向散射的；F11震蕩性較強(qiáng)，具有無數(shù)個(gè)極小值點(diǎn)，很難找到全局最優(yōu)值；F12是典型的非線性多模態(tài)函數(shù)，尋優(yōu)空間廣泛，局部極小值數(shù)量與求解維度相關(guān)，很難處理高維環(huán)境的優(yōu)化問題.這些函數(shù)在高維下，求解難度較高，將其運(yùn)用于仿真實(shí)驗(yàn)中，以測(cè)試在高維、適應(yīng)度函數(shù)復(fù)雜、搜尋方向多變等環(huán)境下算法的尋優(yōu)效率、求解精度、收斂速度等性能.

表1 測(cè)試函數(shù)Table 1 Test functions

4.2 尋優(yōu)結(jié)果分析

為保證比較的公正性、可比性，選取的3個(gè)CS變體都對(duì)CS位置更新進(jìn)行改進(jìn).

將平均值、最小值作為求解精度的評(píng)價(jià)參數(shù).表2-表4中，PSO、CS、NCS均不能在12個(gè)函數(shù)下同時(shí)得到min和avg的最優(yōu)值，只能在F6中得到min的最優(yōu)解.其中， DA-DOCS只能在F6下滿足求解精度最優(yōu)要求.SDCS在5個(gè)函數(shù)中尋到精度評(píng)價(jià)參數(shù)的理論最優(yōu)值.而II-DSCS獲得8個(gè)函數(shù)的精度評(píng)價(jià)指標(biāo)的理論最優(yōu)，尋優(yōu)成功率100%；且在F3、F10中，avg的尋優(yōu)效果已達(dá)百個(gè)數(shù)量級(jí)，min已得理論最優(yōu)解，若增加迭代次數(shù)，II-DSCS將會(huì)搜索到F3、F10的avg的全局最優(yōu)解.由于多模態(tài)函數(shù)F7的極值點(diǎn)位置偏僻，求解難度較大，PSO、CS、NCS、DA-DOCS、SDCS在該函數(shù)中均無法收斂，而II-DSCS在該函數(shù)下已能收斂，精度指標(biāo)高于前5種算法.結(jié)果表明，II-DSCS獲得極具壓倒性的尋優(yōu)能力，引入的信息交互機(jī)制多角度采集種群個(gè)體并及時(shí)用于更新策略中，增強(qiáng)了局部尋優(yōu)和全局搜索性能，提升了搜索精準(zhǔn)性.

標(biāo)準(zhǔn)差大小反映了算法魯棒性的強(qiáng)弱，魯棒性越強(qiáng)，標(biāo)準(zhǔn)差越?。环粗?，魯棒性越差.由表2、表3、表4的std可知，PSO、CS、NCS幾乎無法得到12個(gè)函數(shù)下std的最優(yōu)解，穩(wěn)定性極差；DA-DOCS只在個(gè)別函數(shù)下具有一定的穩(wěn)定性；SDCS在8個(gè)函數(shù)的std中尋到最優(yōu)(在F1/F5中，SDCS的avg、min劣于II-DSCS)；除F7外，II-DSCS在11個(gè)函數(shù)的中，std均為理論最優(yōu)值，且F7的std小于其他5種算法.其表明，改進(jìn)的II-DSCS以全局為視角，綜合性勘測(cè)種群尋優(yōu)情況，使得算法魯棒性顯著提升.

統(tǒng)計(jì)數(shù)據(jù)可知，3種維度下，II-DSCS搜索能力不受影響，維度之間尋優(yōu)精度差異均控制在1-4個(gè)數(shù)量級(jí)內(nèi).差異較明顯的是DA-DOCS，其在F1-F3、F5、F9、F12六個(gè)函數(shù)中，搜索性能隨著維度的升高而降低；PSO在處理F4時(shí)，求解能力隨著維度增加呈指數(shù)下降，當(dāng)維度升到100，解的質(zhì)量比30維的增長了100多個(gè)數(shù)量級(jí)；觀察II-DSCS，3個(gè)維度下，尋優(yōu)性能幾乎保持不變，其余算法的求解性能隨著維度的增加幾乎均有所衰弱.由此可得，改進(jìn)的II-DSCS的維度敏感性強(qiáng)于其余算法，求解性能對(duì)維度不敏感，能有效處理高維問題，具有較強(qiáng)的維度敏感性.

表2 30維的尋優(yōu)精度結(jié)果Table 2 Optimization accuracy values of 30 dimensions

表3 50維的尋優(yōu)精度結(jié)果Table 3 Optimization accuracy values of 50 dimensions

表4 100維的尋優(yōu)精度結(jié)果Table 4 Optimization accuracy values of 100 dimensions

4.3 收斂性分析

為了更直觀地觀察算法的尋優(yōu)進(jìn)程與求解性能，圖2給出了6種算法在1000次迭代下的進(jìn)化曲線.為保證進(jìn)化曲線的清晰度與可視度，降低重合度與模糊度，將縱軸設(shè)置為適應(yīng)度值取對(duì)數(shù)(log10)，橫軸為迭代次數(shù)，每個(gè)函數(shù)的縱軸取值不同，且縱坐標(biāo)為對(duì)數(shù)值，當(dāng)算法收斂到0時(shí)，此時(shí)的尋優(yōu)曲線在圖上無法顯示.

單模態(tài)函數(shù)中，CS、PSO、NCS、DA-DOCS的求解能力顯著低與SDSC與II-DSCS；特別地，F(xiàn)3、F4函數(shù)下，CS、PSO、NCS、DA-DOCS的收斂曲線幾乎與橫軸平行； NCS跳出局部極值能力高于PSO、CS，但其陷入局部極值的時(shí)間與迭代次數(shù)成正比；SDCS的尋優(yōu)性能強(qiáng)于前4種算法，進(jìn)化曲線波動(dòng)小； F6中，II-DSCS 的收斂曲線幾乎垂直于縱軸，能在30代內(nèi)收斂到最優(yōu)值.

多模態(tài)函數(shù)下，所對(duì)比的5種算法收斂能力均有所降低，尋優(yōu)結(jié)果與理論最優(yōu)值差距變大.F7中6個(gè)算法都沒有收斂到理論最優(yōu)值，SDCS從約40次迭代開始陷入極值區(qū)域無法跳出，而 II-DSCS迭代初期收斂能力更強(qiáng)，進(jìn)化過程中跳出局部極值的概率更高；F8、F10、F11中，PSO、CS、DA-DOCS的進(jìn)化曲線幾乎垂直于縱軸，說明算法陷入局部極值的時(shí)間較長，搜索空間的多樣性較弱；F11/F12中，II-DSCS比SDCS提前100余次收斂到理論最優(yōu)值.

收斂曲線表明，加入信息交互機(jī)制的II-DSCS既能提高收斂速度，也能增強(qiáng)收斂精度，改進(jìn)策略多角度更新鳥巢位置，動(dòng)態(tài)評(píng)估搜索情況，使算法在高維環(huán)境下保持活躍的搜索力、快速的收斂速度以及較強(qiáng)的穩(wěn)定性.

4.4 收斂性分析

時(shí)間復(fù)雜度是評(píng)價(jià)算法性能的重要因素，其高低反映算法運(yùn)行效率.由文獻(xiàn)[19]和文獻(xiàn)[20]可知，CS每一代總的時(shí)間復(fù)雜度為O(n+f(n))[19]，依據(jù)文獻(xiàn)[19]、文獻(xiàn)[20]的分析方法，對(duì)II-DSCS算法的時(shí)間復(fù)雜度進(jìn)行分析.

在II-DSCS算法中，初始化階段的時(shí)間復(fù)雜度與CS算法一致，為O(n+f(n)).在第一個(gè)新解生成階段，設(shè)變量生成時(shí)間為x1，公式(4)評(píng)價(jià)一次的時(shí)間為x2，新舊解比較時(shí)間為x3，新解替換舊解的時(shí)間為x4，計(jì)算目標(biāo)函數(shù)的時(shí)間為f(n)，時(shí)間復(fù)雜度為：

O(N(n(x1+x2)+x3+x4n+f(n)))=O(n+f(n))

(11)

在第二個(gè)新解生成階段，設(shè)求解發(fā)現(xiàn)概率的時(shí)間為x5，此階段的變量初始化時(shí)間為x6，公式(7)每操作一次的時(shí)間為x7，新解與舊解比較以及替換的運(yùn)行時(shí)間與第一個(gè)新解生成階段一致，該階段的時(shí)間復(fù)雜度為：

O(N(x6n+x7n+x3+x4n+f(n)))=O(n+f(n))

(12)

可知，II-DSCS記錄最優(yōu)解的時(shí)間復(fù)雜度與CS算法一樣，為O(N(x3+x4n))=O(n).由此，本文所提算法最終的時(shí)間復(fù)雜度為O(n+f(n)).改進(jìn)的II-DSCS算法增加了選擇比較操作時(shí)間，但時(shí)間復(fù)雜度與原始CS保持在同一量級(jí)上.

5 結(jié)束語

基于傳統(tǒng)CS算法，綜合考慮其收斂速率低、勘探開發(fā)不平衡、搜索空間多樣性低等缺點(diǎn)后提出一種利用鳥巢信息交互的動(dòng)態(tài)選擇布谷鳥算法.在保證CS算法自身特性的基礎(chǔ)下，采集多類別種群數(shù)據(jù)，將單一更新機(jī)制變成多組搜索策略，利用個(gè)體交互信息擴(kuò)展搜索區(qū)域的多樣性，并動(dòng)態(tài)選擇位置更新方式以確保局部開發(fā)與全局探索之間達(dá)到平衡；融合擾動(dòng)因子，保證交互信息的全面性；運(yùn)用適應(yīng)度差值來評(píng)價(jià)種群的進(jìn)化程度，基于控制參數(shù)自適應(yīng)更新發(fā)現(xiàn)概率.對(duì)該算法進(jìn)行測(cè)試驗(yàn)證，結(jié)果表明，在6種算法中，II-DSCS算法的收斂精度和速度均優(yōu)于PSO、CS、NCS、DA-DOCS、SDCS算法，該算法的穩(wěn)定性更高、魯棒性更強(qiáng)、搜索更靈活，擁有極具競(jìng)爭(zhēng)價(jià)值的尋優(yōu)求解能力，具有較高的實(shí)際應(yīng)用價(jià)值.近一步的計(jì)劃是將該改進(jìn)機(jī)制應(yīng)用于實(shí)際優(yōu)化問題中.

圖2 PSO/CS/NCS/DA-DOCS/SDCS/II-DSCS尋優(yōu)收斂曲線圖Fig.2 Optimization convergence curves of PSO/CS/NCS/DA-DOCS/SDCS and II-DSCS