基于種群熵的變步長布谷鳥搜索算法

劉洪達(dá)，李德全，王 棟

(1. 中國科學(xué)院長春光學(xué)精密機(jī)械與物理研究所，吉林 長春 130033； 2. 中國科學(xué)院大學(xué)，北京 100049)

1 引言

隨著科學(xué)技術(shù)的發(fā)展，最優(yōu)化問題成為了各個(gè)領(lǐng)域的重點(diǎn)研究對象。由于各行各業(yè)提出的最優(yōu)化問題變得越來越抽象復(fù)雜，存在著非線性約束、計(jì)算量大等問題，經(jīng)典的優(yōu)化計(jì)算方法已經(jīng)無法滿足實(shí)際的需求。為獲得復(fù)雜的優(yōu)化問題合理有效的近似解，研究者們基于沒有免費(fèi)午餐(No Free Lunch，NFL)定理，針對不同的優(yōu)化問題設(shè)計(jì)了大量的元啟發(fā)式算法，例如模仿動(dòng)物種群群集行為的粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)、模擬自然選擇與生物進(jìn)化過程的遺傳算法(Genetic Algorithm，GA)、模仿蜜蜂行為的人工蜂群算法(Artificial Bee Colony Algorithm，ABC)等。在這些元啟發(fā)式算法的基礎(chǔ)上，諸多研究者對算法進(jìn)行改進(jìn)，提出了諸多改進(jìn)策略，從而提高算法的效率。

許多優(yōu)化算法由于其算法簡單、易于實(shí)現(xiàn)等優(yōu)點(diǎn)受人青睞，比如劍橋大學(xué)的Yang 和Deb于2009年提出的布谷鳥搜索算法(Cuckoo Search，CS)。這是一種通過模擬布谷鳥尋窩產(chǎn)卵的行為所設(shè)計(jì)的優(yōu)化算法，基于萊維飛行機(jī)制進(jìn)行尋優(yōu)，能夠有效解決最優(yōu)化問題，并成功應(yīng)用于圖像處理、系統(tǒng)設(shè)計(jì)、醫(yī)學(xué)應(yīng)用、數(shù)據(jù)挖掘等各個(gè)領(lǐng)域的實(shí)際問題中，也可與其它算法相結(jié)合以提高混合算法的性能，如BP神經(jīng)網(wǎng)絡(luò)、PSO算法、極限學(xué)習(xí)機(jī)等。該算法簡單、參數(shù)少，易于實(shí)現(xiàn)、全局搜索能力強(qiáng)，采用的隨機(jī)搜索策略使得算法更為高效。此外CS算法的通用性強(qiáng)，可以與其它算法相結(jié)合。但是CS算法也和諸多元啟發(fā)式算法一樣，存在著后期的搜索效率低、尋優(yōu)精度不高等缺點(diǎn)。

為了克服這些缺點(diǎn)，研究者們紛紛對CS算法進(jìn)行改進(jìn)：Rodrigues、馮登科等學(xué)者將二進(jìn)制這一概念引入了CS算法中，獲得了更優(yōu)秀的全局搜索能力與魯棒性，但仍存在一些收斂速度較差的問題；Ouaarab、王超等學(xué)者提出了一類離散CS算法，但是面對一些條件時(shí)提高效果并不明顯；馬英輝、Wang等學(xué)者將混沌理論引入到CS算法中，提高了尋優(yōu)速度與精度，但是算法復(fù)雜度增大，影響了尋優(yōu)時(shí)間。

針對CS算法存在的問題，本文通過種群熵對布谷鳥步長控制因子進(jìn)行改進(jìn)：將尋優(yōu)搜索空間等分為多個(gè)子空間，計(jì)算種群熵以確定種群的分布特性，基于分布特性控制步長控制因子實(shí)時(shí)變化，從而提高了算法的尋優(yōu)效率。此外，這項(xiàng)改進(jìn)保持了CS算法的通用性，可配合其它改進(jìn)策略來進(jìn)一步提高算法的性能。

2 布谷鳥搜索算法

布谷鳥算法(Cuckoo Search，CS)通過模擬布谷鳥巢寄生繁殖的原理，利用萊維飛行機(jī)制(Levy Flight)來有效地求解最優(yōu)化問題。

部分布谷鳥不會自己孵卵育雛，而是偷偷地在其它鳥類的巢穴中產(chǎn)卵，并移除相同數(shù)量的寄主卵，從而保持巢穴內(nèi)的卵總數(shù)不變，最終由該寄主代為孵化育雛。若寄生卵被發(fā)現(xiàn)，此寄生卵將會被寄主移除，導(dǎo)致布谷鳥的寄生繁殖失敗。

萊維飛行是一種混合了短距離與長距離的隨機(jī)游走機(jī)制。其步長服從于重尾分布，隨機(jī)游走過程中有相對較高的幾率出現(xiàn)大的步長。而對于搜索算法而言，前期的大步長便于增強(qiáng)種群多樣性，提高前期的全局搜索能力，易于搜索到全局最優(yōu)值所在鄰域；后期的小步長提高了局部搜索能力，縮小了搜索范圍，從而獲得全局最優(yōu)解。

CS算法通過假設(shè)三個(gè)理想條件來模擬布谷鳥的巢寄生繁殖機(jī)制：

1)布谷鳥一次僅產(chǎn)一個(gè)蛋，并隨機(jī)選擇宿主巢穴來孵化自己的蛋；

2)在隨機(jī)選擇的一組巢穴中，孵化條件最好的巢穴將會被保留到下一代；

3)可寄生的宿主巢穴數(shù)量是固定的，一個(gè)宿主巢穴的主人能發(fā)現(xiàn)一個(gè)寄生鳥蛋的概率∈[0，1]。

在以上3個(gè)理想條件的基礎(chǔ)上，基于萊維飛行機(jī)制的位置更新公式如下

+1=+(-)⊕′()

(1)

其中萊維飛行可以利用Mantegna方法進(jìn)行模擬

(2)

式(1)中，+1與為第+1代與第代的宿主巢穴位置，為當(dāng)前最優(yōu)解，為步長控制因子，⊕為點(diǎn)對點(diǎn)乘法，()為萊維飛行公式。

(3)

宿主鳥發(fā)現(xiàn)寄生鳥蛋的概率稱為發(fā)現(xiàn)概率，在算法中常取=025。算法通過萊維飛行更新位置后，生成一個(gè)隨機(jī)數(shù)∈[0，1]，當(dāng)>時(shí)，則對進(jìn)行隨機(jī)改變，采用偏好游走的方式生成等量的新解以替換舊解，象征著宿主發(fā)現(xiàn)并處理掉寄生鳥蛋的行為，使得布谷鳥隨機(jī)選擇一個(gè)新的巢穴進(jìn)行寄生繁殖。偏好游走公式如式(4)所示

(4)

在處理實(shí)際的優(yōu)化問題時(shí)，巢穴的位置代表待辨識變量的解值，巢穴的適應(yīng)度代表待辨識變量取不同解的時(shí)候?qū)?yīng)的目標(biāo)函數(shù)值。算法的實(shí)現(xiàn)過程如下：

1) 參數(shù)初始化。設(shè)置最大迭代次數(shù)、種群規(guī)模、搜索空間維度、搜索上下界，生成鳥巢初始位置=(，，…，)，并定義目標(biāo)函數(shù)為()，=1，2，…，；

2) 計(jì)算每個(gè)巢穴的對應(yīng)適應(yīng)度，選出最優(yōu)函數(shù)值作為當(dāng)前最優(yōu)適應(yīng)度；

3) 基于萊維飛行機(jī)制，利用式(1)對巢穴的位置進(jìn)行更新，獲得一組新的巢穴位置并計(jì)算對應(yīng)的適應(yīng)度，此時(shí)式(1)中的步長控制因子=001。選擇新巢穴的最優(yōu)適應(yīng)度與更新前的巢穴最優(yōu)適應(yīng)度進(jìn)行對比，獲得當(dāng)前最優(yōu)適應(yīng)度與當(dāng)前最優(yōu)巢穴位置；

4) 隨機(jī)產(chǎn)生一個(gè)隨機(jī)數(shù)，令與進(jìn)行比較。若大于則利用式(4)對巢穴位置進(jìn)行隨機(jī)更新，否則巢穴位置不發(fā)生變化；

5) 若達(dá)到最大迭代次數(shù)或滿足指定搜索精度時(shí)，輸出全局最優(yōu)巢穴位置，即全局最優(yōu)解，否則循環(huán)步驟2-4。

3 改進(jìn)布谷鳥搜索算法

由式(2)與式(3)可知，Levy(λ)的值取決于正態(tài)分布隨機(jī)數(shù)μ和v這導(dǎo)致萊維飛行搜索步長和方向都是高度隨機(jī)變化的。對于步長控制因子而言，較大的控制因子可以增強(qiáng)全局搜索能力，但是局部搜索能力較差，容易造成搜索至在真值附近擺動(dòng)；較小的控制因子會導(dǎo)致算法的效率低下，需要更多的迭代次數(shù)。為改善該問題，本文提出了PE-VSCS算法(Variable Step-size Cuckoo Search based on Population Entropy)，將種群的分布熵引入到CS算法中，對步長控制因子進(jìn)行改進(jìn)。

熵為某一系統(tǒng)體系混亂程度的度量，種群熵為算法尋優(yōu)過程中種群分布混亂程度的度量。假設(shè)布谷鳥種群總數(shù)為、搜索維度為，將尋優(yōu)搜索空間分為個(gè)搜索子空間，每個(gè)子空間含有個(gè)體數(shù)為(=1，2，…，)，則第維度(=1，2，…，)的分布熵為

(5)

式(5)為布谷鳥種群在尋優(yōu)搜索空間中的分布熵的表達(dá)式。為使分布熵更能體現(xiàn)出尋優(yōu)解的分布信息，一般搜索子空間取較大值。越大，則種群越分散，表明算法未收斂，需要較大的更新步長進(jìn)行全局搜索；越小，則種群越集中，表明算法開始收斂，需要較小的更新步長進(jìn)行局部搜索。

為滿足上述關(guān)系，對改進(jìn)步長控制因子進(jìn)行構(gòu)造，其表達(dá)式如下

(6)

式中，為第維的步長控制因子，=0為分布熵理論最小值，=為分布熵的理論最大值，為調(diào)整參數(shù)。由于一般>，由式(5)可知，分布熵實(shí)際最小值為0，實(shí)際最大值為

(7)

PE-VSCS算法的實(shí)現(xiàn)過程如下：

1) 參數(shù)初始化。設(shè)置最大迭代次數(shù)、種群規(guī)模、搜索空間維度、搜索上下界、搜索子空間數(shù)量，生成鳥巢初始位置=(，，…，)，并定義目標(biāo)函數(shù)為()，=1，2，…，；

2) 計(jì)算每個(gè)巢穴的對應(yīng)適應(yīng)度，選出最優(yōu)函數(shù)值作為當(dāng)前最優(yōu)適應(yīng)度；

3) 基于萊維飛行機(jī)制，利用式(1)對巢穴的位置進(jìn)行更新，獲得一組新的巢穴位置并計(jì)算對應(yīng)的適應(yīng)度，此時(shí)步長控制因子由式(6)決定。選擇新巢穴的最優(yōu)適應(yīng)度與更新前的巢穴最優(yōu)適應(yīng)度進(jìn)行對比，獲得當(dāng)前最優(yōu)適應(yīng)度與當(dāng)前最優(yōu)巢穴位置；

4) 隨機(jī)產(chǎn)生一個(gè)隨機(jī)數(shù)，令與進(jìn)行比較。若大于則利用式(4)對巢穴位置進(jìn)行隨機(jī)更新，否則巢穴位置不發(fā)生變化；

5) 若達(dá)到最大迭代次數(shù)或滿足指定搜索精度時(shí)，輸出全局最優(yōu)巢穴位置，即全局最優(yōu)解，否則循環(huán)步驟2-4。

4 仿真研究

為驗(yàn)證PE-VSCS算法的尋優(yōu)性能，本文選用了如表1所示的不同特點(diǎn)的測試函數(shù)。針對不同的測試函數(shù)，利用PE-VSCS算法與CS算法各進(jìn)行50次仿真，并記錄結(jié)果進(jìn)行分析。其中()-()為多維函數(shù)，()-()為二維函數(shù)，()、()、()、()為多峰函數(shù)，其余為單峰函數(shù)。

記錄每一次的仿真結(jié)果，將50次仿真結(jié)果中的最優(yōu)值、最差值、平均值、標(biāo)準(zhǔn)差作為算法性能的評價(jià)指標(biāo)。最優(yōu)值代表了算法尋優(yōu)可達(dá)到的精度上限，平均值代表了算法尋優(yōu)的平均精度，標(biāo)準(zhǔn)差代表了算法的穩(wěn)定性。

測試結(jié)果如表3至表10所示。圖1至圖8為PE-VSCS與CS算法的最優(yōu)收斂曲線圖，圖1至圖4所示曲線圖的維度取值為10，圖5至圖8所示曲線圖的維度取值為2。

4.1 測試函數(shù)

表1 測試函數(shù)

4.2 測試環(huán)境與算法參數(shù)

仿真環(huán)境操作系統(tǒng)為7，為5-6400 27，運(yùn)行內(nèi)存為8，編程環(huán)境為2014。

算法的最大迭代次數(shù)根據(jù)測試函數(shù)的搜索難度適當(dāng)調(diào)整。其余的參數(shù)設(shè)置見表2。

表2 算法參數(shù)設(shè)置

4.3 算法性能比較

表3 Ackley函數(shù)f1(x)仿真結(jié)果

表4 Sphere函數(shù)f2(x)仿真結(jié)果

表5 Schwefel’s P2.22函數(shù)f3(x)仿真結(jié)果

表6 Sum Square函數(shù)f4(x)仿真結(jié)果

表7 Drop-Wave函數(shù)f5(x)仿真結(jié)果

表8 Easom函數(shù)f6(x)仿真結(jié)果

表9 Shubert函數(shù)f7(x)仿真結(jié)果

表10 Schaffer函數(shù)f8(x)仿真結(jié)果

由上述測試結(jié)果可以看出，與CS算法進(jìn)行對比，PE-VSCS算法的性能大幅度提高。

面對低維度尋優(yōu)問題時(shí)，PE-VSCS算法的收斂速度更快。從表7與表8可以看出，在面對一些較簡單的測試函數(shù)時(shí)，PE-VSCS算法能在最大迭代次數(shù)較少的情況下，獲得最優(yōu)值并使得標(biāo)準(zhǔn)差為0，表明面對該類問題時(shí)，PE-VSCS算法能得到最優(yōu)解且穩(wěn)定性高。而CS算法在同樣的最大迭代次數(shù)內(nèi)，無法穩(wěn)定尋出最優(yōu)值甚至無法尋出最優(yōu)值。從表9與表10可以看出，面對一些難度較高的測試函數(shù)時(shí)，PE-VSCS算法的四個(gè)評價(jià)指標(biāo)的數(shù)量級均小于CS算法的評價(jià)指標(biāo)數(shù)量級，表明PE-VSCS算法的穩(wěn)定性與尋優(yōu)精度優(yōu)于CS算法。

面對多維問題時(shí)，PE-VSCS算法能達(dá)到一個(gè)很高的精度，優(yōu)于CS算法。從表4與表6可以看出，PE-VSCS算法可以使得評價(jià)函數(shù)的數(shù)量級達(dá)到-30甚至-40，在一些實(shí)際問題中該數(shù)量級的誤差可近似視為0。而CS算法所達(dá)到的數(shù)量級與PE-VSCS算法相比，數(shù)量級相差了10甚至20，表明了PE-VSCS算法的尋優(yōu)精度要強(qiáng)于CS算法。

隨著尋優(yōu)維度的增加，PE-VSCS算法的尋優(yōu)能力有所下降，如表3至表6所示，當(dāng)尋優(yōu)維度為50時(shí)，需要的迭代次數(shù)相比于10維度而言變大，且四個(gè)評價(jià)指標(biāo)相比于低維度的尋優(yōu)精度而言變差。但是與CS算法相比，仍有顯著的提高，PE-VSCS算法與CS算法的四個(gè)指標(biāo)相差至少5個(gè)數(shù)量級。

圖1 基于f1(x)的PE-VSCS與CS算法的最優(yōu)收斂曲線圖

圖2 基于f2(x)的PE-VSCS與CS算法的最優(yōu)收斂曲線圖

圖3 基于f3(x)的PE-VSCS與CS算法的最優(yōu)收斂曲線圖

圖4 基于f4(x)的PE-VSCS與CS算法的最優(yōu)收斂曲線圖

圖5 基于f5(x)的PE-VSCS與CS算法的最優(yōu)收斂曲線圖 圖6 基于f6(x)的PE-VSCS與CS算法的最優(yōu)收斂曲線圖

圖7 基于f7(x)的PE-VSCS與CS算法的最優(yōu)收斂曲線圖 圖8 基于f8(x)的PE-VSCS與CS算法的最優(yōu)收斂曲線圖

4.4 算法收斂曲線分析

圖1至圖4為10維度測試函數(shù)的收斂曲線與對應(yīng)的半對數(shù)線圖，圖5至圖8為二維度測試函數(shù)的收斂曲線圖。

多峰函數(shù)f(x)、f(x)、f(x)、f(x)擁有多個(gè)局部極值點(diǎn)，可以測試算法跳出局部最優(yōu)的能力。單峰函數(shù)f(x)、f(x)、f(x)、f(x)可以測試算法的收斂速度。由曲線圖可以看出PE-VSCS算法的收斂速度要優(yōu)于CS算法。由半對數(shù)線圖可以看出PE-VSCS在指定最大迭代次數(shù)內(nèi)，評價(jià)函數(shù)的量級要優(yōu)于CS算法所能達(dá)到的量級。

綜上所述，通過八個(gè)測試函數(shù)的收斂曲線圖進(jìn)行對比分析，無論是低維度尋優(yōu)還是高維度尋優(yōu)，無論是單峰函數(shù)還是多峰函數(shù)，PE-VSCS算法都具有優(yōu)秀的尋優(yōu)能力與收斂速度，證明了引入種群熵的步長控制因子的有效性

4.5 改進(jìn)步長控制因子的分析

以Easom測試函數(shù)的測試結(jié)果的步長控制因子的變化為例，給出各維步長控制因子隨迭代次數(shù)變化的曲線如圖9所示。

圖9 各維步長控制因子隨迭代次數(shù)變化的曲線

由圖9可以看出，各維步長控制因子隨種群熵不斷變化，整體呈現(xiàn)下降趨勢。在迭代初期時(shí)，步長控制因子取較大值以提高前期的全局搜索能力；迭代后期時(shí)，步長控制因子處于一個(gè)較小值，提高了局部搜索能力。在迭代過程中，步長控制因子會偶爾出現(xiàn)變大的情況，以對應(yīng)由于隨機(jī)更新導(dǎo)致的種群分散情況。算法隨迭代次數(shù)的增加逐漸由全局搜索轉(zhuǎn)為局部搜索。

5 總結(jié)

熵可以度量某一系統(tǒng)體系混亂程度，CS算法尋優(yōu)模擬了布谷鳥種群從眾多分散的巢穴中尋找出最優(yōu)巢穴進(jìn)行寄生繁殖的過程，種群從發(fā)散最終收斂于某一點(diǎn)，種群熵也隨之變化從大變小。種群熵的變化代表了種群在尋優(yōu)過程中的變化。本文通過將種群熵引入到萊維飛行機(jī)制中，構(gòu)建了新的步長控制因子。通過8個(gè)測試函數(shù)的性能測試，可以表明PE-VSCS 算法的尋優(yōu)能力、求解精度、收斂速度等方面相比于CS算法均有提高。仿真結(jié)果表明，無論是單峰函數(shù)還是多峰函數(shù)，無論是低維函數(shù)還是多維函數(shù)，PE-VSCS算法的尋優(yōu)性能均超過CS算法，證明了基于種群熵的改進(jìn)步長控制因子是有效的。且這項(xiàng)改進(jìn)保持了CS算法的通用性，可配合其它改進(jìn)策略來進(jìn)一步提高算法的性能。本課題組將在后續(xù)工作中開展相關(guān)工作。