一種改進的布谷鳥搜索算法

田野，方明

（長春理工大學(xué)計算機科學(xué)技術(shù)學(xué)院，長春 130022）

一種改進的布谷鳥搜索算法

田野，方明

（長春理工大學(xué)計算機科學(xué)技術(shù)學(xué)院，長春 130022）

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

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

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

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

1 布谷鳥搜索算法

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

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

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

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

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

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

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

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

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

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

2 改進的布谷鳥搜索算法

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

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

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

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

第一種情況：ri＜Pa

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

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

第二種情況：ri≥Pa

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

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

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

表1 測試函數(shù)

3 實驗

本節(jié)中，將文中提出的ICS算法和標準的CS算法［1］在一些標準測試函數(shù)上進行對比分析，驗證ICS算法的有效性。

3.1 測試問題

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

3.2 實驗結(jié)果

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

3.2.1 實驗一

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

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

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

3.2.2 實驗二

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

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

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

4 結(jié)論

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

文中采用了具有不同難度的基準優(yōu)化問題，通過兩組對比實驗分別來驗證算法在求解質(zhì)量和收斂速度上的性能，并且和標準的CS算法進行了比較。結(jié)果表明改進的ICS在求解質(zhì)量及收斂速度上較標準的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ā)展計劃、吉林省公共計算平臺資助（20130101179JC-11）；吉林省自然科學(xué)基金（20130101054JC）

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