基于逐維判定的記憶減退布谷鳥(niǎo)搜索算法

劉紫陽(yáng) 龐志華 鄭韓飛 李叢萱 北華航天工業(yè)學(xué)院 計(jì)算機(jī)學(xué)院

引言

布谷鳥(niǎo)搜索算法（Cuckoo Search Algorithm，CSA）是一種模擬布谷鳥(niǎo)寄生育雛行為的仿生優(yōu)化算法，其尋優(yōu)能力來(lái)源于它的兩個(gè)重要組成部分，一是基于萊維飛行（Lévy Flights）的隨機(jī)游走過(guò)程，二是基于種群內(nèi)部交叉變異的偏好隨機(jī)游走過(guò)程。萊維飛行的隨機(jī)步長(zhǎng)來(lái)自于具有無(wú)限方差和無(wú)限均值的萊維分布，鳥(niǎo)巢位置采取強(qiáng)記憶性更新策略。強(qiáng)記憶性更新策略與盲目跳變的結(jié)合保證了最優(yōu)解在進(jìn)化中傳遞，避免了算法退化，但也會(huì)導(dǎo)致算法在當(dāng)前解附進(jìn)行多次無(wú)效開(kāi)發(fā)，導(dǎo)致收斂速度過(guò)緩。

一些改進(jìn)的CS 算法在一定程度上提升了CSA 的性能，但存在計(jì)算量大，引入更多外部參數(shù)等問(wèn)題，面對(duì)高維復(fù)雜函數(shù)優(yōu)化問(wèn)題時(shí)難以兼顧全局探索與局部尋優(yōu)性能。文獻(xiàn)[5]提出逐維改進(jìn)的布谷鳥(niǎo)搜索算法，通過(guò)降低隨機(jī)游走的盲目性來(lái)提升搜索效率，但其萊維更新階段仍使用強(qiáng)記憶更新策略，削弱了算法的全局探索能力，使算法容易陷入局部最優(yōu)。

本文提出了基于逐維判定和記憶減退的布谷鳥(niǎo)搜索算法（Dimension by Dimension Decision Based Memory Loss Cuckoo Search Algorithm, DML-CSA）。MDL-CSA 在萊維更新階段，采取無(wú)記憶策略，完全保留萊維飛行的更新結(jié)果。在偏好隨機(jī)游走階段采取逐維判定策略，逐個(gè)維度依次判斷當(dāng)前解在交叉變異后適應(yīng)度是否降低（最小值問(wèn)題），降低則接納更新，否則保留原值。實(shí)驗(yàn)結(jié)果表明，兩種策略的結(jié)合可以有效地提高CS 算法的收斂速度。

1 CS 算法

2 DML-CS 算法

2.1 逐維判定

結(jié)合式(4)和CS 算法的計(jì)算步驟可以看出，偏好隨機(jī)游走是一種整體判定方式。對(duì)于多維目標(biāo)函數(shù)，將解的各個(gè)維度進(jìn)行種群間隨機(jī)交叉變異后，再?gòu)恼w評(píng)價(jià)本次更新是否提升解質(zhì)量。然而，對(duì)于高維目標(biāo)函數(shù)，每個(gè)維度的變化都會(huì)影響函數(shù)適應(yīng)度，如果個(gè)別維度的退化覆蓋了其他維度的進(jìn)化，導(dǎo)致整個(gè)解的適應(yīng)度退化，那么本次更新記為無(wú)效，不僅產(chǎn)生計(jì)算浪費(fèi)。

DML-CS 算法采用逐維判定策略。在偏好隨機(jī)游走階段，從第一個(gè)維度開(kāi)始依次執(zhí)行如下操作：更新該維度值，評(píng)價(jià)更新對(duì)適應(yīng)度的影響。如果更新使目標(biāo)函數(shù)適應(yīng)度降低則接納該更新，否則保留原值。這是一種貪婪的更新方式，下一維度的更新在上一維度評(píng)價(jià)的基礎(chǔ)上展開(kāi)，每次更新都會(huì)提高解質(zhì)量，從而加速了算法的收斂。

2.2 記憶減退策略

標(biāo)準(zhǔn)布谷鳥(niǎo)算法通過(guò)萊維飛行產(chǎn)生隨機(jī)步長(zhǎng)，如果隨機(jī)步長(zhǎng)的加入使得函數(shù)適應(yīng)度降低則保留更新，否則保持原值。強(qiáng)記憶性的更新策略與跳變的盲目性的結(jié)合避免了算法退化，但同時(shí)削弱了萊維飛行的全局探索能力和局部掙脫能力，使算法容易在局部最優(yōu)點(diǎn)處震蕩。記憶減退策略則是直接將萊維飛行更新作為新解，不再對(duì)更新結(jié)果進(jìn)行評(píng)判。這不僅減少了該環(huán)節(jié)對(duì)目標(biāo)函數(shù)的評(píng)價(jià)次數(shù)，而且充分發(fā)揮萊維飛行的高隨機(jī)性特點(diǎn)，使算法有能力跳出局部最優(yōu)，找到全局最優(yōu)值。

2.3 DML-CS 算法流程

DML-CS 算法步驟如下：

3 數(shù)值仿真與分析

將DML-CS 與標(biāo)準(zhǔn)布谷鳥(niǎo)算法CSA 和逐DDICS 算法[5]在多個(gè)具有典型特性的基準(zhǔn)函數(shù)上進(jìn)行測(cè)試，測(cè)試函數(shù)包含了2 個(gè)單峰函數(shù)（Sphere、Rosenbrock）和3 個(gè)多峰函數(shù)（Griewank、Alpine、Schaffer）。

3.1 實(shí)驗(yàn)參數(shù)

為使比較過(guò)程更公平，將3 種算法的共同參數(shù)設(shè)為一致（參見(jiàn)文獻(xiàn)[5]），步長(zhǎng)因子 ，發(fā)現(xiàn)概率 ，種群大 設(shè)為小為30，多維函數(shù)維數(shù)設(shè)為30，所有函數(shù)自變量變化范圍設(shè)為[-100.00~,100.00]。

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

為直觀展示DCS 算法尋優(yōu)過(guò)程，圖1~圖5 展示了測(cè)試函數(shù)在3種算法下的適應(yīng)度進(jìn)化曲線，進(jìn)化曲線采用半對(duì)數(shù)坐標(biāo)，橫坐標(biāo)是目標(biāo)函數(shù)的評(píng)價(jià)次數(shù)。目標(biāo)函數(shù)評(píng)價(jià)是法迭代過(guò)程中占據(jù)計(jì)算資源對(duì)多的環(huán)節(jié)，橫坐標(biāo)采用評(píng)價(jià)次數(shù)可以直觀比較3 種算法在消耗相同的計(jì)算資源情況下的尋優(yōu)效果。

圖1 Sphere 函數(shù)

圖2 Rosenbrock 函數(shù)

圖3 Griewank 函數(shù)

圖4 Alpine 函數(shù)

可以看出，相較于標(biāo)準(zhǔn)布谷鳥(niǎo)算法，逐維改進(jìn)的CS 算法的收斂速度在前期有了明顯提升，但在迭代后期其收斂趨于緩慢，可能陷入局部極小值。而DML-CS 算法在整個(gè)尋優(yōu)過(guò)程中都具有較快的收斂速度，隨著迭代次數(shù)增長(zhǎng)，DML-CS 算法適應(yīng)度仍能保持較高的下降率。因此，在達(dá)到相同尋優(yōu)精度條件下，DML-CS 算法所需時(shí)間更少。為了驗(yàn)證算法對(duì)低維函數(shù)的尋優(yōu)能力，實(shí)驗(yàn)中引入了二維函數(shù)Schaffer 和Alpine。其中，Alpine 函數(shù)是一種經(jīng)典的多模態(tài)最小化測(cè)試函數(shù)。當(dāng)在定義域內(nèi)趨于無(wú)窮大時(shí)，該函數(shù)沿著自變量方向會(huì)產(chǎn)生大量可微的局部極值，具有較高的尋優(yōu)難度。圖4 展示了Alpine函數(shù)在3 種算法下的適應(yīng)度進(jìn)化過(guò)程，CS 算法陷入局部最小值，尋優(yōu)失敗，DDICS 算法收斂較慢，DML-CS 算法經(jīng)過(guò)3.0E+4 次評(píng)價(jià)就使誤差達(dá)到了 10-20 級(jí)別，而為達(dá)到此精度，DDICS 算法所需的評(píng)價(jià)次數(shù)是DML-CS 的3 倍。由此表明，DML-CS 算法雖然針對(duì)的是高維函數(shù)的尋優(yōu)問(wèn)題，但它對(duì)低維函數(shù)同樣有效。

圖5 Schaffer 函數(shù)

4 結(jié)語(yǔ)

解決高維函數(shù)優(yōu)化問(wèn)題時(shí)，CS 算法未能考慮不同維度間的相互干擾，強(qiáng)記憶更新策略又限制了萊維飛行隨機(jī)步長(zhǎng)的全局探索能力，導(dǎo)致算法收斂緩慢，容易陷入局部最優(yōu)。本文提出了基于逐維判定和記憶減退的布谷鳥(niǎo)搜索算法，創(chuàng)新點(diǎn)有：

(1）萊維更新階段，采取無(wú)記憶策略，充分發(fā)揮了萊維飛行步長(zhǎng)的隨機(jī)性，使算法有較強(qiáng)的全局探索能力和局部最優(yōu)掙脫能力。

(2）偏好隨機(jī)游走階段采取逐維判定策略，逐維度判斷當(dāng)前解在交叉變異后適應(yīng)度是否降低，減少了解的各個(gè)維度間的相互干擾，降低隨機(jī)游走的盲目性，提升算法收斂速度。

DML-CS 算法與CS 算法和DDICS 算法的對(duì)比試驗(yàn)結(jié)果表明，DML-CS 算法不僅能在多維函數(shù)上取得較好的尋優(yōu)效果，在低維函數(shù)上的表現(xiàn)同樣優(yōu)異，并且DML-CS 算法對(duì)多峰函數(shù)和單峰函數(shù)的優(yōu)化效果同樣優(yōu)于對(duì)比算法。因此，DML-CS 算法是一種更有競(jìng)爭(zhēng)力的算法。