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

田野，方明

（長春理工大學計算機科學技術學院，長春 130022）

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

田野，方明

（長春理工大學計算機科學技術學院，長春 130022）

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

人工智能；全局優化；布谷鳥搜索算法；適應度

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

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

1 布谷鳥搜索算法

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

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

假設1：每只布谷鳥每次只產一個鳥蛋隨機放進某個鳥巢；

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

假設3：鳥巢數量固定，并且布谷鳥蛋被鳥巢的主人以一定的概率發現。

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

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

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

Step 3.根據發現概率Pa，丟棄部分解，并用偏好隨機游動產生新的解替代丟棄的解；

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

2 改進的布谷鳥搜索算法

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

首先，根據解的適應度，計算解的選擇概率，公式如下：

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

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

第一種情況：ri＜Pa

如果第i個解適應度較好，則Pi值相對較小，因此該解仍然以較小的概率被發現并放棄；

如果第i個解適應度較差，則Pi值相對較大，因此可能增加該解被發現并放棄的概率；

第二種情況：ri≥Pa

如果第i個解適應度較好，則Pi值相對較小，因此可能降低該解被發現并放棄的概率；

如果第i個解適應度較差，則Pi值相對較大，因此該解可能以較大的概率被發現并放棄；

由于r是隨機數，所以在放棄解的時候無法辨識其適應度情況，而Pi值的作用就是用來幫助調節新的隨機數r'i的，即調節解的發現放棄概率。總的來說，解的適應度越好，Pi值越小，則會降低該解被放棄的概率；解的適應度越差，Pi值越大，則會增加被放棄的概率。整個改進算法流程可以描述為如下算法：

表1 測試函數

3 實驗

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

3.1 測試問題

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

3.2 實驗結果

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

3.2.1 實驗一

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

表2 CS和ICS關于最優解均值對比

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

3.2.2 實驗二

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

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

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

4 結論

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

文中采用了具有不同難度的基準優化問題，通過兩組對比實驗分別來驗證算法在求解質量和收斂速度上的性能，并且和標準的CS算法進行了比較。結果表明改進的ICS在求解質量及收斂速度上較標準的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，FANG 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

吉林省科技發展計劃、吉林省公共計算平臺資助（20130101179JC-11）；吉林省自然科學基金（20130101054JC）

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