求解無約束優化問題的改進布谷鳥搜索算法

蘇芙華，劉云連，伍鐵斌

(1. 湖南人文科技學院 a. 物理與電子信息系；b. 機電工程系，湖南 婁底 41 7000；2. 湖南科技大學信息與電氣工程學院，湖南 湘潭 41 1201)

求解無約束優化問題的改進布谷鳥搜索算法

蘇芙華1a，劉云連1b,2，伍鐵斌1b

(1. 湖南人文科技學院 a. 物理與電子信息系；b. 機電工程系，湖南 婁底 41 7000；2. 湖南科技大學信息與電氣工程學院，湖南 湘潭 41 1201)

布谷鳥搜索算法是一種基于種群迭代搜索的全局優化算法。為求解無約束優化問題，提出一種改進的布谷鳥搜索算法。利用混沌序列構造初始種群以增加群體的多樣性，引入動態隨機局部搜索技術對當前最優解進行局部搜索，以加快算法的收斂速度。對4個標準測試函數進行仿真實驗，并與其他6種算法進行比較，結果表明，該算法具有較強的全局搜索能力和較快的收斂速度。

布谷鳥搜索算法；無約束優化問題；混沌；動態隨機局部搜索；慣性權重；多樣性

1 概述

布谷鳥搜索(Cuckoo Search, CS)算法是一種模擬布谷鳥尋窩產卵行為的全局搜索算法[1]。CS算法具有概念簡單、參數設置少、容易實現的特點，已被證明在收斂速度和穩定性方面均超過了遺傳算法(Genetic Algorithm, GA)和粒子群優化(Particle Swarm Optimization, PSO)算法。因此，CS算法在函數優化、組合優化、神經網絡訓練、結構優化和多目標優化等領域有著廣泛的應用。文獻[2]將CS算法應用到13個結構設計優化問題中取得了較好的結果。文獻[3]提出一種多目標布谷鳥搜索算法應用于設計優化。文獻[4]將CS算法應用到柔性制造系統的調度中。文獻[5]將布谷鳥搜索算法應用于圖形分割中。

然而，與其他基于種群迭代搜索的全局優化算法一樣，CS算法同樣存在后期收斂速度慢、局部搜索能力弱和易早熟收斂等缺點。產生早熟收斂等缺陷的根本原因是隨著迭代次數的增加種群多樣性快速下降。針對以上缺點，文獻[6]提出一種基于正交學習方法的改進CS算法，用于求解混沌系統參數優化問題。文獻[7]提出一種基于高斯分布的改進CS算法，用于求解無約束優化問題。文獻[8]提出一種基于共軛梯度的改進布谷鳥搜索算法，用于求解高維無約束優化問題。文獻[9]指出，多樣性高的初始種群對尋找全局最優解很有幫助。

為了改善CS算法的性能，本文提出一種求解無約束優化問題的改進CS算法。該算法首先利用混沌序列產生初始種群以維持群體的多樣性；在Lévy f light隨機搜索中引入慣性權重以增強其全局搜索能力；利用動態隨機局部搜索技術對當前最優解進行局部搜索，以加快算法的收斂速度。

2 布谷鳥搜索算法

CS算法模擬了布谷鳥為尋找適合產卵的鳥窩而隨機游走的尋窩過程。為了模擬布谷鳥尋窩的行為，需設定以下3個理想的狀態[1]：(1)布谷鳥一次只產一個卵，并隨機選擇鳥窩位置來孵化它。(2)在隨機選擇的一組鳥窩中，最好位置的鳥窩將會保留到下一代。(3)可利用的鳥窩數量N是固定的，一個鳥窩主人能發現一個外來鳥蛋的概率為Pa。

在CS算法中，一個鳥巢的卵表示一個候選解，一個布谷鳥的卵表示一個新的解。在上述3個理想狀態的基礎上，布谷鳥尋窩的路徑和位置更新公式如下：

通過位置更新后，用隨機數r∈[0,1]與鳥窩的主人發現外來鳥的概率Pa作對比，若r＞Pa，則對xti進行隨機改變，否則不變。

CS算法的步驟如下：

Step1設置算法基本參數，在問題的搜索空間中隨機產生N個初始鳥窩位置。

Step2計算各鳥窩位置的適應度值，確定當前最佳適應度值及最佳鳥窩位置。

Step3利用式(1)和式(2)對鳥窩位置進行更新，得到一組新的鳥窩位置。

Step4計算更新后的鳥窩位置的適應度值，比較更新鳥窩的歷史最佳位置。

Step5產生一個隨機數r∈[0,1]與pa對比，保留被發現概率較小的鳥窩位置，同時隨機改變被發現概率較大的鳥窩位置，得到一組新的鳥窩位置。

Step6判斷算法是否滿足結束條件，若滿足，則輸出結果，算法結束；否則，返回Step3。

3 布谷鳥搜索改進算法

3.1 種群初始化

在求解優化問題前無法預知全局最優解所在區域的情況下，初始種群個體必須充分代表解空間的個體，在有限數量內最大限度地表征所有個體的信息，這樣才能使算法以較快的方式快速逼近最優解。

文獻[9]認為，在基于種群迭代搜索的全局優化算法中，多樣性較好的初始種群對尋找全局最優解很有幫助。然而，在CS算法中，通常在搜索空間中隨機初始化種群，從而導致多樣性較差。

混沌是一種非線性現象，具有隨機性、遍歷性等特點。本文利用混沌的遍歷性產生初始群體。Tent混沌映射是一種能產生均勻序列且迭代速度快的混沌模型，其序列的迭代公式如下[10]：

其中，Xn∈[0,1]，n=1,2,…。

隨機產生一個Q維的變量X=(x1, x2,…,xQ)，通過Zi=(xi-aj)/(bj-aj),i=1,2,…,Q 將變量X變換到混沌變量的取值區間[0,1]，然后根據式(3)進行M次迭代產生Zm(m=1,2,…,M)，將Z用式(4)將混沌序列還原到原優

i

i化變量取值區間，通過計算適應度值，從M個初始群體中選擇適應度值較優的N個作為初始解。

其中，i=1,2,…,M ；j=1,2,…,Q；aj和bj分別為xij的取值范圍。

3.2 慣性權重的引入

在基本CS算法中，布谷鳥尋窩的路徑和位置是隨機的，以父代位置信息為參考進行更新。為提高CS算法的性能，在布谷鳥尋窩的路徑和位置更新公式中引入慣性權重：

慣性權重的引入，可使CS算法有擴展搜索空間的趨勢，有能力搜索新的區域。一般來說，在全局優化算法中，總希望前期有較強的全局搜索能力，而在后期有較高的開發能力，以加快收斂速度。

實驗結果表明，較大的慣性權重w有利于跳出局部最優，進行全局尋優；較小的w值有利于局部尋優，加速算法收斂。所以在迭代過程中，慣性權重w的值應隨著迭代次數的增加而遞減。本文采取一種慣性權重w線性遞減策略：

其中，wmax和wmin分別是w的最大值和最小值；t和tmax分別為當前迭代次數和最大迭代次數。

3.3 動態隨機局部搜索

文獻[6]指出，CS算法具有較強的全局搜索能力，但局部搜索能力差，收斂速度慢。為了加快CS算法的收斂速度，增強其局部搜索能力，本文引入一種具有很強搜索能力的動態隨機局部搜索技術，其具體步驟如下[11]：

Step1設定局部搜索代數E，搜索步長上限0α，對于每一個搜索步長αt的最大迭代次數為M，Xcurrent=Xbest，epoch = 0，k=0。

Step7如果m＜M，則轉Step3；否則轉Step8。

Step8k=k+1。 f(·)為計算適應值的函數。

3.4 改進CS算法

改進CS算法步驟如下：

Step1參數設置：最大迭代次數，種群規模N,α,Pa,E, M，慣性權重wmax,wmin。

Step2在搜索空間中利用混沌序列產生N個鳥窩的位置，令t=1。

Step3找出當前最優鳥窩位置和對應的最優適應度值。

Step4判斷算法是否滿足終止條件，若滿足，則算法結束；否則，轉Step5。

Step5按式(5)、式(6)和式(1)更新鳥窩的位置，得到新的鳥窩位置。

Step6隨機產生一個均勻分布的數r∈[0,1]，如果r＞Pa，則隨機改變發現概率較大的鳥窩位置，找出并保留最優鳥窩位置及對應值。

Step7利用算法對當前最優鳥窩位置進行局部尋優，令t=t+1，返回Step3。Step10如果epoch = E，則算法結束；否則返回Step2。epoch為局部搜索迭代計數器；Xbest為當前最優解；

4 數值實驗

為評估本文提出的改進布谷鳥搜索(MCS)算法的性能，選取4個標準測試函數進行仿真實驗，并與標準布谷鳥搜索(CS)算法進行比較，各測試函數的主要特征如表1所示。

表1 4個標準測試函數

測試函數的數學表達式如下：

利用CS算法和MCS算法對上述4個標準測試函數進行實驗。參數設置如下：在CS算法中，種群規模為25，α=1，Pa=0.25，最大迭代次數為1 000。在MCS算法中，種群規模為N=25，α=1，Pa=0.25，最大迭代次數為1 000，E=100，M=10，wmax=0.9，wmin=0.4。對每個測試函數，2種算法在上述參數設置下分別單獨運行30次，記錄最優值、平均值、最差值和標準差，比較結果如表2所示。

表2 CS算法和MCS算法的尋優結果比較

從表2可知，對于4個測試函數，MCS算法在30次實驗中獲得的最優值、平均值、最差值和標準差值均要優于CS算法，這充分說明無論是算法的收斂精度，還是算法的穩定性，MCS算法都比CS算法有了較大的提高。

圖1～圖4分別給出了CS算法和MCS算法對4個測試函數的收斂曲線，從圖中可以看出，對于函數f1、f3和f4，MCS算法能很快收斂到最優解或接近最優解。

圖1 f1函數的收斂性能比較

圖2 f2函數的收斂性能比較

圖3 f3函數的收斂性能比較

圖4 f4函數的收斂性能比較

為了進一步說明MCS算法的有效性，將其與6種有代表性的智能優化算法的性能進行比較，它們分別是：遺傳算法(Genetic Algorithm, GA)，進化策略(Evolution Strategy, ES)，粒子群優化(Particle Swarm Optimization, PSO)，蟻群優化(Ant Colony Optimization, ACO)，差分進化(Differential Evolution, DE)和生物地理優化(Biogeography-based Optimization, BBO)，6種算法的實驗結果來源于文獻[12]。表3給出了7種算法對測試函數f1～f4的尋優結果比較。

表3 MCS與其他6種算法的尋優結果比較

從表3可以看出，與GA、ES、PSO、ACO和DE算法相比，無論是獲得最優解的精度，還是算法的穩定性，MCS算法在6個測試函數中得到的結果要優。與BBO算法相比，MCS算法在函數f2和f4上得到的結果要優，而在函數f1和f3上，BBO算法得到了較好的結果。從上述比較可知，MCS算法顯示出較強的尋優性能。

5 結束語

針對布谷鳥搜索算法全局搜索能力強而局部搜索能力弱、易出現早熟收斂的缺點，本文提出一種有效的改進布谷鳥搜索算法。該算法利用混沌序列產生初始種群，為提高算法全局搜索能力奠定基礎；引入慣性權重以平衡算法的勘探和開采能力；利用動態隨機局部搜索技術進行局部搜索，以加快算法的收斂速度。針對4個標準測試函數的實驗結果表明，該混合算法能有效地平衡其局部搜索和全局搜索性能。

[1] Yang Xinsh e, Deb S. Cucko o Search via L évy Flights[C]// Proc. of World Congress on Nature and Biologically Inspired Computing. [S. l.]: IEEE Press, 2009: 210-214.

[2] Gandomt A H, Y ang Xinsh e, Alavi A H. Cuckoo Search Algorithm: A M eta-heuristic A pproach to Solve Structural Optimization Problem[J]. Engineering with Computers, 2013, 29(1): 17-35.

[3] Y ang Xinshe, Deb S. Multi-obj ective Cuc koo Se arch fo r Design Optimization[J]. C omputers & O perations R esearch, 2013, 40(6): 1616-1624.

[4] B urnwal S, D eb S. Scheduling Optimizati on of Flexible Manu- facturing System Using Cuc koo S earch-based Approach[J]. International Journal of Advanced Manufacturing Technology, 2013, 64(5): 951-959.

[5] 柳新妮, 馬 苗. 布谷鳥搜索算法在多閾值圖像分割中的應用[J]. 計算機工程, 2013, 39(7): 274-278.

[6] 李向濤, 殷明浩. Parameter Estimation for Chaotic Systems Using the Cuckoo Search Algo rithm with an Orthogonal Learning Method[J]. 中國物理B: 英文版, 2012, 21(5).

[7] Zheng Hongqing, Zhou Yongquan. A Novel Cuckoo Search Optimization Algorithm Based on Gauss D istribution[J]. Journal of Computational Information Systems, 20 12, 8(10): 4193-4200.

[8] 杜利敏, 阮 奇, 馮登科. 基于共軛梯度的布谷鳥搜索算法[J]. 計算機與應用化學, 2013, 30(4): 406-410.

[9] Huapt R, Haupt S. Practical Genetic Algorithm[M]. [S. l.]: John Wiley & Sons, 2004.

[10] 劉悅婷. 基于混沌和動態變異的蛙跳算法[J]. 計算機應用與軟件, 2012, 29(12): 137-140.

[11] Hamzacebi C. Improving Genetic Algorithms’ Performance by Local S earch f or Co ntinuous Function Optimization[J]. Applied Mathem atics and Compu tation, 2008, 1 96(1): 309-317.

[12] Ma Haiping. An Analysis of the Equilibrium of Migration Models for Biog eography-based Optimization[J]. Information Sciences, 2010, 180(18): 3444-3464.

編輯 顧逸斐

Modified Cuckoo Search Algorithm for Solving Unconstrained Optimization Problem

SU Fu-hua1a, LIU Yun-lian1b,2, WU Tie-bin1b

(1a. Department of Physics and Electronic Information; 1b. Department of Electrical and Mechanical Engineering, Hunan University of Humanities, Science and Technology, Loudi 417000, China; 2. College of Information and Electrical Engineering, Hunan University of Science and Technology, Xiangtan 411201, China)

Cuckoo Search(CS) algorithm is proposed as a population-based optimization algorithm and it is so far successfully applied in a variety of field s. A modified CS algorithm is proposed for solving unconstrained optimization problems. Chaos sequence and dynamic random local search technique are introduced to enhance the optimization ability and to improve the convergence speed of CS algorithm. Through testing the performance of the proposed algorithm on a set of 4 benchmark functions and comparing with other six algorithms, simulation result shows that the proposed algorithm has great ability of global search and better convergence rate.

Cuckoo Search(CS) algorithm; unconstrained optimization problem; chaotic; dynamic random local search; inertia weight; diversity

10.3969/j.issn.1000-3428.2014.05.046

國家自然科學基金資助項目(61174113)；湖南省教育廳基金資助一般項目(13C433)；湖南省科技廳基金資助項目(2014GK3 033, 2 013FJ6073)。

蘇芙華(1976－)，女，講師、碩士，主研方向：智能控制，安全監測；劉云連，助教；伍鐵斌(通訊作者)，講師、博士研究生。

2013-09-22

2013-11-13E-mail：wutiebin81@163.com

1000-3428(2014)05-0224-04

A

TP301.6