田野，方明

（長(zhǎng)春理工大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長(zhǎng)春 130022）

一種改進(jìn)的布谷鳥(niǎo)搜索算法

田野，方明

（長(zhǎng)春理工大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長(zhǎng)春 130022）

布谷鳥(niǎo)搜索算法是近年來(lái)提出的一種新的仿生智能算法，算法主要通過(guò)模擬布谷鳥(niǎo)的繁殖習(xí)性對(duì)問(wèn)題進(jìn)行最優(yōu)求解。針對(duì)布谷鳥(niǎo)搜索算法中解的發(fā)現(xiàn)及放棄策略的隨機(jī)性問(wèn)題，將解的適應(yīng)度情況同時(shí)考慮進(jìn)來(lái)，并在此基礎(chǔ)上提出一種基于解的優(yōu)劣度的改進(jìn)布谷鳥(niǎo)搜索算法。算法充分考慮解的適應(yīng)度，并將適應(yīng)度作為評(píng)估是否被放棄的一個(gè)標(biāo)準(zhǔn)，從而使得適應(yīng)度較好的解更有可能被保留下來(lái)，提高算法的求解質(zhì)量。實(shí)驗(yàn)結(jié)果表明新算法在求解質(zhì)量以及收斂速度方面，都比標(biāo)準(zhǔn)的布谷鳥(niǎo)搜索算法有了一定的提高。

人工智能；全局優(yōu)化；布谷鳥(niǎo)搜索算法；適應(yīng)度

智能優(yōu)化算法是通過(guò)模擬自然界的生物運(yùn)動(dòng)或者自然現(xiàn)象來(lái)設(shè)計(jì)求解實(shí)際復(fù)雜優(yōu)化問(wèn)題的新型算法，如遺傳算法［1］、粒子群優(yōu)化算法［2］、人工蜂群算法［3］等都屬于智能優(yōu)化算法。布谷鳥(niǎo)搜索（Cuckoo Search，CS）算法是2009年由Yang和Deb提出的一種新的智能優(yōu)化算法［4-5］，其原理是對(duì)布谷鳥(niǎo)的繁殖習(xí)性進(jìn)行模擬，根據(jù)布谷鳥(niǎo)寄生育雛的特點(diǎn)，對(duì)問(wèn)題的最優(yōu)解進(jìn)行有效搜索。由于CS算法具有參數(shù)少、簡(jiǎn)單易實(shí)現(xiàn)等優(yōu)點(diǎn)，很快吸引了眾多學(xué)者的關(guān)注和研究熱情［6-8］。

CS算法的高效性主要源于它的萊維飛行（Lévy flights）隨機(jī)游動(dòng)和偏好隨機(jī)游動(dòng)。而在偏好隨機(jī)游動(dòng)過(guò)程中，算法以一定的概率隨機(jī)發(fā)現(xiàn)需要被放棄，并且重新生成的解，這種隨機(jī)方式使得質(zhì)量較好的解可能被放棄。針對(duì)這一問(wèn)題，文中考慮將解的適應(yīng)度情況作為是否放棄解的評(píng)價(jià)標(biāo)準(zhǔn)，提出一種基于解的優(yōu)劣度的改進(jìn)布谷鳥(niǎo)搜索（Improved Cuckoo Search，ICS）算法，來(lái)提高算法的性能。

1 布谷鳥(niǎo)搜索算法

CS算法通過(guò)模擬某些種屬布谷鳥(niǎo)的寄生育雛習(xí)性有效的求解最優(yōu)化問(wèn)題。布谷鳥(niǎo)最為特殊的習(xí)性是寄生育雛［4］。某些種屬的布谷鳥(niǎo)將自己的卵偷偷產(chǎn)入宿主巢穴，由于布谷鳥(niǎo)后代的孵化時(shí)間比宿主的幼雛早，孵化的幼雛會(huì)本能的破壞同一巢穴中其他的卵（推出巢穴）并發(fā)出比宿主幼雛更響亮的叫聲。很多宿主通過(guò)后代的叫聲大小判斷其健康程度，而健康后代獲得的食物較多，進(jìn)而擁有更高的存活率。在某些情況下，宿主也會(huì)發(fā)現(xiàn)巢穴中的陌生卵，這時(shí)，宿主將遺棄該巢穴，并選擇其他地方重新筑巢。在與宿主不斷的生存競(jìng)爭(zhēng)中，布谷鳥(niǎo)的卵以及幼雛叫聲均朝著模擬宿主的方向發(fā)展，以對(duì)抗宿主不斷進(jìn)化的分辨能力。

在此生物學(xué)基礎(chǔ)上，YANG和Deb對(duì)其寄生育雛行為提出了三個(gè)假設(shè)，并依據(jù)該假設(shè)給出了布谷鳥(niǎo)算法［5］。

假設(shè)1：每只布谷鳥(niǎo)每次只產(chǎn)一個(gè)鳥(niǎo)蛋隨機(jī)放進(jìn)某個(gè)鳥(niǎo)巢；

假設(shè)2：存有布谷鳥(niǎo)蛋的最好的鳥(niǎo)巢會(huì)被保留到下一代；

假設(shè)3：鳥(niǎo)巢數(shù)量固定，并且布谷鳥(niǎo)蛋被鳥(niǎo)巢的主人以一定的概率發(fā)現(xiàn)。

由此得到CS算法的步驟描述如下：

Step 1.初始化。隨機(jī)產(chǎn)生N個(gè)鳥(niǎo)窩（即問(wèn)題的解），其位置表示為，記錄最優(yōu)的解；

Step 2.利用萊維飛行進(jìn)行解的位置更新，獲取新的候選解的位置，利用貪心選擇策略保留更好的解；

Step 3.根據(jù)發(fā)現(xiàn)概率Pa，丟棄部分解，并用偏好隨機(jī)游動(dòng)產(chǎn)生新的解替代丟棄的解；

Step 4.選擇當(dāng)前最好的解，如果滿足終止條件，則輸出最好的解；否則，返回Step 2繼續(xù)迭代。

2 改進(jìn)的布谷鳥(niǎo)搜索算法

在CS算法中，為了提高種群的多樣性，算法以Pa概率放棄一部分解，并通過(guò)偏好隨機(jī)游走的方式生成新的解，這種策略有效地加強(qiáng)了算法的全局搜索能力。但是，在以Pa概率發(fā)現(xiàn)并放棄解的時(shí)候，算法采用了隨機(jī)的方式，即對(duì)于每個(gè)解生成一個(gè)0到1之間的隨機(jī)數(shù)，如果該隨機(jī)數(shù)大于發(fā)現(xiàn)概率Pa，則該解被放棄，這種隨機(jī)方式可能導(dǎo)致適應(yīng)度較好的解被放棄掉，而適應(yīng)度較差的解得以保留的問(wèn)題，影響算法收斂速度和解的質(zhì)量。因此文中ICS算法的主要思想是：在發(fā)現(xiàn)并放棄解的時(shí)候，將解的適應(yīng)度同時(shí)考慮進(jìn)來(lái)，將解的適應(yīng)度作為評(píng)判是否放棄解的一個(gè)度量。

首先，根據(jù)解的適應(yīng)度，計(jì)算解的選擇概率，公式如下：

其中，Pi表示第i個(gè)解的選擇概率，F(xiàn)iti是第i個(gè)解的適應(yīng)度，gBest和gWorst分別表示目前為止最好的解和最差的解的適應(yīng)度值。從公式（1）中可以看出，解的質(zhì)量越好，適應(yīng)度越好（適應(yīng)度值越?。?，則解的選擇概率也就越小，反之亦然?，F(xiàn)在將適應(yīng)度考慮到以Pa概率發(fā)現(xiàn)并放棄解的策略中，如公式（2）所示：

其中，ri表示第i個(gè)解對(duì)應(yīng)的隨機(jī)數(shù)，取自［0，1］之間，r'i是經(jīng)過(guò)計(jì)算后的新隨機(jī)數(shù)，如果r'i＞Pa，則該解被發(fā)現(xiàn)并放棄，通過(guò)偏好隨機(jī)游走的方式生成新的解，否則，保留該解。根據(jù)公式（2），按以下兩種情況來(lái)分析：

第一種情況：ri＜Pa

如果第i個(gè)解適應(yīng)度較好，則Pi值相對(duì)較小，因此該解仍然以較小的概率被發(fā)現(xiàn)并放棄；

如果第i個(gè)解適應(yīng)度較差，則Pi值相對(duì)較大，因此可能增加該解被發(fā)現(xiàn)并放棄的概率；

第二種情況：ri≥Pa

如果第i個(gè)解適應(yīng)度較好，則Pi值相對(duì)較小，因此可能降低該解被發(fā)現(xiàn)并放棄的概率；

如果第i個(gè)解適應(yīng)度較差，則Pi值相對(duì)較大，因此該解可能以較大的概率被發(fā)現(xiàn)并放棄；

由于r是隨機(jī)數(shù)，所以在放棄解的時(shí)候無(wú)法辨識(shí)其適應(yīng)度情況，而Pi值的作用就是用來(lái)幫助調(diào)節(jié)新的隨機(jī)數(shù)r'i的，即調(diào)節(jié)解的發(fā)現(xiàn)放棄概率?？偟膩?lái)說(shuō)，解的適應(yīng)度越好，Pi值越小，則會(huì)降低該解被放棄的概率；解的適應(yīng)度越差，Pi值越大，則會(huì)增加被放棄的概率。整個(gè)改進(jìn)算法流程可以描述為如下算法：

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

3 實(shí)驗(yàn)

本節(jié)中，將文中提出的ICS算法和標(biāo)準(zhǔn)的CS算法［1］在一些標(biāo)準(zhǔn)測(cè)試函數(shù)上進(jìn)行對(duì)比分析，驗(yàn)證ICS算法的有效性。

3.1 測(cè)試問(wèn)題

為了測(cè)試ICS算法的性能，文中列舉了一些具有不同復(fù)雜程度的基準(zhǔn)函數(shù)作為測(cè)試問(wèn)題，這些測(cè)試問(wèn)題包含單模和多模，最優(yōu)值均為0。表1中列出了函數(shù)的表達(dá)形式、搜索空間及誤差閾值。

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

本文中的ICS算法和標(biāo)準(zhǔn)的CS算法均采用Matlab編程。為了更好地觀察改進(jìn)算法和標(biāo)準(zhǔn)CS算法在收斂速度和解的質(zhì)量的對(duì)比情況，文中采取了兩組實(shí)驗(yàn)，第一組實(shí)驗(yàn)主要驗(yàn)證改進(jìn)算法的求解質(zhì)量；第二組實(shí)驗(yàn)側(cè)重于算法的收斂速度分析。

3.2.1 實(shí)驗(yàn)一

在本小節(jié)實(shí)驗(yàn)中，將本文提出的ICS算法與標(biāo)準(zhǔn)的CS算法進(jìn)行比較。其中測(cè)試問(wèn)題的維度D均為30，群體規(guī)模N=D，發(fā)現(xiàn)概率為Pa=0.25，最大函數(shù)評(píng)價(jià)次數(shù)FES=10000×D，每個(gè)算法獨(dú)立運(yùn)行30次，表2列出了兩種算法針對(duì)五個(gè)測(cè)試函數(shù)獲得的最優(yōu)解平均值及標(biāo)準(zhǔn)差。

表2 CS和ICS關(guān)于最優(yōu)解均值對(duì)比

從上表中可以看出，對(duì)于所有的測(cè)試問(wèn)題，改進(jìn)的ICS算法在最優(yōu)解的均值和方差都獲得了比標(biāo)準(zhǔn)的CS算法更好的結(jié)果，這說(shuō)明無(wú)論是在求解質(zhì)量、求解精度及穩(wěn)定性方面，ICS算法都有了一定的提高。主要原因是因?yàn)樵贗CS算法中，對(duì)于發(fā)現(xiàn)及放棄解的過(guò)程中，充分考慮到了解的適應(yīng)度情況，降低了適應(yīng)度更好的解被放棄的可能，使得算法的整體求解質(zhì)量有了提高。

3.2.2 實(shí)驗(yàn)二

本節(jié)實(shí)驗(yàn)主要是針對(duì)兩種算法的收斂速度進(jìn)行了對(duì)比分析。算法參數(shù)設(shè)置、終止條件及實(shí)驗(yàn)環(huán)境和3.2.1節(jié)相同。表3給出了兩種算法收斂于指定誤差閾值所需的平均函數(shù)評(píng)價(jià)次數(shù)和標(biāo)準(zhǔn)差及成功率（success rate，SR）?！?”表示算法在終止時(shí)未能收斂于指定誤差閾值，平均函數(shù)評(píng)價(jià)次數(shù)和標(biāo)準(zhǔn)差只考慮算法執(zhí)行成功的情況。ICS算法和標(biāo)準(zhǔn)的CS算法在成功次數(shù)上相差不大，幾乎一樣。此外，當(dāng)收斂失敗時(shí)，兩種算法的平均函數(shù)評(píng)價(jià)次數(shù)都是一樣的，因此不對(duì)問(wèn)題f2和f5的結(jié)果作對(duì)比分析。對(duì)于Ackley測(cè)試問(wèn)題，CS算法的成功率為83.33%，而ICS算法獲得了100%的成功，并且ICS算法在平均函數(shù)評(píng)價(jià)次數(shù)及標(biāo)準(zhǔn)差上，都遠(yuǎn)遠(yuǎn)優(yōu)于CS算法。對(duì)于其他測(cè)試問(wèn)題，兩種算法都以相同的成功次數(shù)收斂于指定誤差閾值，但從平均函數(shù)評(píng)價(jià)次數(shù)上來(lái)看，ICS算法以較快的速度收斂。而從方差可以看出，ICS算法收斂時(shí)的函數(shù)評(píng)價(jià)次數(shù)相對(duì)更穩(wěn)定。

表3 CS和ICS收斂于指定誤差閾值的平均函數(shù)評(píng)價(jià)次數(shù)

從以上兩組實(shí)驗(yàn)可以看出，由于改進(jìn)的ICS算法在解的發(fā)現(xiàn)放棄過(guò)程中，充分利用了解本身的優(yōu)劣情況，使得質(zhì)量較好的解更有機(jī)會(huì)得以保留下來(lái)，因此在整體上提升了最優(yōu)解的質(zhì)量，并且提高了算法的收斂速度。

4 結(jié)論

本文針對(duì)標(biāo)準(zhǔn)布谷鳥(niǎo)搜索算法在解的發(fā)現(xiàn)放棄過(guò)程中存在的問(wèn)題，將解本身的質(zhì)量考慮進(jìn)來(lái)，提出了基于解優(yōu)劣特征的改進(jìn)布谷鳥(niǎo)搜索算法ICS，算法將解的優(yōu)劣特征作為被發(fā)現(xiàn)并放棄的度量標(biāo)準(zhǔn)，有效地保障了適應(yīng)度較好的解能夠被保留下來(lái)的可能性，從而提高算法的求解質(zhì)量及收斂速度。

文中采用了具有不同難度的基準(zhǔn)優(yōu)化問(wèn)題，通過(guò)兩組對(duì)比實(shí)驗(yàn)分別來(lái)驗(yàn)證算法在求解質(zhì)量和收斂速度上的性能，并且和標(biāo)準(zhǔn)的CS算法進(jìn)行了比較。結(jié)果表明改進(jìn)的ICS在求解質(zhì)量及收斂速度上較標(biāo)準(zhǔn)的CS算法都得到了提高。

［1］Holland J H.Adaptation in natural and artificial systems［M］.AnnArbor：UniversityofMichigan Press，1975.

［2］KennedyJames，EberhartRussell.Particleswarm optimization［C］.Proceedings of the IEEE international conference on neural networks，Perth，Australia，1995（4）：1942-1948.

［3］Karaboga Dervis，Basturk Bahriye.A powerful and efficient algorithm for numerical function optimization：artificial bee colony（ABC）algorithm［J］.Journal of Global Optimization，2007，39（3）：459-471.

［4］Yang Xin She，Deb Suash.Cuckoo search via Lévy flights［C］.Proceedings of the World Congress on Nature and Biologically Inspired Computing（NaBIC 2009）.IEEE Publications，USA，2009：210-214.

［5］Yang Xin She，Deb Suash.Engineering optimisation by cuckoo search［J］.International Journal of Mathematical Modeling and Numerical Optimisation，2010，1（4）：330-343.

［6］Burnwal Shashikant，Deb Suash.Scheduling optimization of flexible manufacturing system using cuckoo search-based approach［J］.International Journal ofAdvancedManufacturingTechnology，2013，64（64）：951-959.

［7］Zhou Yongquan，Ouyang Xinxin，Xie Jian.A discrete cuckoo search algorithm for travelling salesman problem［J］.International Journal of Collaborative Intelligence，2014，1（1）：68-84.

［8］Civicioglu Pinar，Besdok Erkan.A conceptual comparison of the Cuckoo-search，particle swarm optimization，differential evolution and artificial bee colony algorithms swarm optimization，differential evolution and artificial bee colony algorithms［J］.Artificial Intelligence Review，2013，39（4）：315-346.

An Improved Cuckoo Search Algorithm

TIAN Ye，F(xiàn)ANG Ming
（School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022）

Cuckoo search（CS）algorithm is a new nature-inspired intelligent algorithm which simulates the breed behavior of the cuckoo species to solve the global optimization problems.In this paper，an improved cuckoo search（ICS）algorithm based on the fitness of the solution is presented to overcome the randomness on finding and abandoning one solution.In the presented algorithm，the fitness of the solution is considered and as the abandon metric，which makes the better solution be likely to survive，and improve the performance of the algorithm.The experiment results show that ICS is better than CS in not only the solution quality，but also the convergence speed.

artificial intelligence；global optimization；cuckoo search algorithm；fitness

TP18

A

1672-9870（2017）01-0115-04

2016-07-09

吉林省科技發(fā)展計(jì)劃、吉林省公共計(jì)算平臺(tái)資助（20130101179JC-11）；吉林省自然科學(xué)基金（20130101054JC）

田野（1979-），男，博士，講師，E-mail：tianye@cust.edu.cn