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

引言

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

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

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

1 CS 算法

2 DML-CS 算法

2.1 逐維判定

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

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

2.2 記憶減退策略

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

2.3 DML-CS 算法流程

DML-CS 算法步驟如下：

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

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

3.1 實驗參數(shù)

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

3.2 實驗結(jié)果與分析

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

圖1 Sphere 函數(shù)

圖2 Rosenbrock 函數(shù)

圖3 Griewank 函數(shù)

圖4 Alpine 函數(shù)

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

圖5 Schaffer 函數(shù)

4 結(jié)語

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

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

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

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