求解無(wú)約束優(yōu)化問(wèn)題的改進(jìn)布谷鳥(niǎo)搜索算法

蘇芙華，劉云連，伍鐵斌

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

求解無(wú)約束優(yōu)化問(wèn)題的改進(jìn)布谷鳥(niǎo)搜索算法

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

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

布谷鳥(niǎo)搜索算法是一種基于種群迭代搜索的全局優(yōu)化算法。為求解無(wú)約束優(yōu)化問(wèn)題，提出一種改進(jìn)的布谷鳥(niǎo)搜索算法。利用混沌序列構(gòu)造初始種群以增加群體的多樣性，引入動(dòng)態(tài)隨機(jī)局部搜索技術(shù)對(duì)當(dāng)前最優(yōu)解進(jìn)行局部搜索，以加快算法的收斂速度。對(duì)4個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行仿真實(shí)驗(yàn)，并與其他6種算法進(jìn)行比較，結(jié)果表明，該算法具有較強(qiáng)的全局搜索能力和較快的收斂速度。

布谷鳥(niǎo)搜索算法；無(wú)約束優(yōu)化問(wèn)題；混沌；動(dòng)態(tài)隨機(jī)局部搜索；慣性權(quán)重；多樣性

1 概述

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

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

為了改善CS算法的性能，本文提出一種求解無(wú)約束優(yōu)化問(wèn)題的改進(jìn)CS算法。該算法首先利用混沌序列產(chǎn)生初始種群以維持群體的多樣性；在Lévy f light隨機(jī)搜索中引入慣性權(quán)重以增強(qiáng)其全局搜索能力；利用動(dòng)態(tài)隨機(jī)局部搜索技術(shù)對(duì)當(dāng)前最優(yōu)解進(jìn)行局部搜索，以加快算法的收斂速度。

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

CS算法模擬了布谷鳥(niǎo)為尋找適合產(chǎn)卵的鳥(niǎo)窩而隨機(jī)游走的尋窩過(guò)程。為了模擬布谷鳥(niǎo)尋窩的行為，需設(shè)定以下3個(gè)理想的狀態(tài)[1]：(1)布谷鳥(niǎo)一次只產(chǎn)一個(gè)卵，并隨機(jī)選擇鳥(niǎo)窩位置來(lái)孵化它。(2)在隨機(jī)選擇的一組鳥(niǎo)窩中，最好位置的鳥(niǎo)窩將會(huì)保留到下一代。(3)可利用的鳥(niǎo)窩數(shù)量N是固定的，一個(gè)鳥(niǎo)窩主人能發(fā)現(xiàn)一個(gè)外來(lái)鳥(niǎo)蛋的概率為Pa。

在CS算法中，一個(gè)鳥(niǎo)巢的卵表示一個(gè)候選解，一個(gè)布谷鳥(niǎo)的卵表示一個(gè)新的解。在上述3個(gè)理想狀態(tài)的基礎(chǔ)上，布谷鳥(niǎo)尋窩的路徑和位置更新公式如下：

通過(guò)位置更新后，用隨機(jī)數(shù)r∈[0,1]與鳥(niǎo)窩的主人發(fā)現(xiàn)外來(lái)鳥(niǎo)的概率Pa作對(duì)比，若r＞Pa，則對(duì)xti進(jìn)行隨機(jī)改變，否則不變。

CS算法的步驟如下：

Step1設(shè)置算法基本參數(shù)，在問(wèn)題的搜索空間中隨機(jī)產(chǎn)生N個(gè)初始鳥(niǎo)窩位置。

Step2計(jì)算各鳥(niǎo)窩位置的適應(yīng)度值，確定當(dāng)前最佳適應(yīng)度值及最佳鳥(niǎo)窩位置。

Step3利用式(1)和式(2)對(duì)鳥(niǎo)窩位置進(jìn)行更新，得到一組新的鳥(niǎo)窩位置。

Step4計(jì)算更新后的鳥(niǎo)窩位置的適應(yīng)度值，比較更新鳥(niǎo)窩的歷史最佳位置。

Step5產(chǎn)生一個(gè)隨機(jī)數(shù)r∈[0,1]與pa對(duì)比，保留被發(fā)現(xiàn)概率較小的鳥(niǎo)窩位置，同時(shí)隨機(jī)改變被發(fā)現(xiàn)概率較大的鳥(niǎo)窩位置，得到一組新的鳥(niǎo)窩位置。

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

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

3.1 種群初始化

在求解優(yōu)化問(wèn)題前無(wú)法預(yù)知全局最優(yōu)解所在區(qū)域的情況下，初始種群個(gè)體必須充分代表解空間的個(gè)體，在有限數(shù)量?jī)?nèi)最大限度地表征所有個(gè)體的信息，這樣才能使算法以較快的方式快速逼近最優(yōu)解。

文獻(xiàn)[9]認(rèn)為，在基于種群迭代搜索的全局優(yōu)化算法中，多樣性較好的初始種群對(duì)尋找全局最優(yōu)解很有幫助。然而，在CS算法中，通常在搜索空間中隨機(jī)初始化種群，從而導(dǎo)致多樣性較差。

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

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

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

i

i化變量取值區(qū)間，通過(guò)計(jì)算適應(yīng)度值，從M個(gè)初始群體中選擇適應(yīng)度值較優(yōu)的N個(gè)作為初始解。

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

3.2 慣性權(quán)重的引入

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

慣性權(quán)重的引入，可使CS算法有擴(kuò)展搜索空間的趨勢(shì)，有能力搜索新的區(qū)域。一般來(lái)說(shuō)，在全局優(yōu)化算法中，總希望前期有較強(qiáng)的全局搜索能力，而在后期有較高的開(kāi)發(fā)能力，以加快收斂速度。

實(shí)驗(yàn)結(jié)果表明，較大的慣性權(quán)重w有利于跳出局部最優(yōu)，進(jìn)行全局尋優(yōu)；較小的w值有利于局部尋優(yōu)，加速算法收斂。所以在迭代過(guò)程中，慣性權(quán)重w的值應(yīng)隨著迭代次數(shù)的增加而遞減。本文采取一種慣性權(quán)重w線性遞減策略：

其中，wmax和wmin分別是w的最大值和最小值；t和tmax分別為當(dāng)前迭代次數(shù)和最大迭代次數(shù)。

3.3 動(dòng)態(tài)隨機(jī)局部搜索

文獻(xiàn)[6]指出，CS算法具有較強(qiáng)的全局搜索能力，但局部搜索能力差，收斂速度慢。為了加快CS算法的收斂速度，增強(qiáng)其局部搜索能力，本文引入一種具有很強(qiáng)搜索能力的動(dòng)態(tài)隨機(jī)局部搜索技術(shù)，其具體步驟如下[11]：

Step1設(shè)定局部搜索代數(shù)E，搜索步長(zhǎng)上限0α，對(duì)于每一個(gè)搜索步長(zhǎng)αt的最大迭代次數(shù)為M，Xcurrent=Xbest，epoch = 0，k=0。

Step7如果m＜M，則轉(zhuǎn)Step3；否則轉(zhuǎn)Step8。

Step8k=k+1。 f(·)為計(jì)算適應(yīng)值的函數(shù)。

3.4 改進(jìn)CS算法

改進(jìn)CS算法步驟如下：

Step1參數(shù)設(shè)置：最大迭代次數(shù)，種群規(guī)模N,α,Pa,E, M，慣性權(quán)重wmax,wmin。

Step2在搜索空間中利用混沌序列產(chǎn)生N個(gè)鳥(niǎo)窩的位置，令t=1。

Step3找出當(dāng)前最優(yōu)鳥(niǎo)窩位置和對(duì)應(yīng)的最優(yōu)適應(yīng)度值。

Step4判斷算法是否滿足終止條件，若滿足，則算法結(jié)束；否則，轉(zhuǎn)Step5。

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

Step6隨機(jī)產(chǎn)生一個(gè)均勻分布的數(shù)r∈[0,1]，如果r＞Pa，則隨機(jī)改變發(fā)現(xiàn)概率較大的鳥(niǎo)窩位置，找出并保留最優(yōu)鳥(niǎo)窩位置及對(duì)應(yīng)值。

Step7利用算法對(duì)當(dāng)前最優(yōu)鳥(niǎo)窩位置進(jìn)行局部尋優(yōu)，令t=t+1，返回Step3。Step10如果epoch = E，則算法結(jié)束；否則返回Step2。epoch為局部搜索迭代計(jì)數(shù)器；Xbest為當(dāng)前最優(yōu)解；

4 數(shù)值實(shí)驗(yàn)

為評(píng)估本文提出的改進(jìn)布谷鳥(niǎo)搜索(MCS)算法的性能，選取4個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行仿真實(shí)驗(yàn)，并與標(biāo)準(zhǔn)布谷鳥(niǎo)搜索(CS)算法進(jìn)行比較，各測(cè)試函數(shù)的主要特征如表1所示。

表1 4個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)

測(cè)試函數(shù)的數(shù)學(xué)表達(dá)式如下：

利用CS算法和MCS算法對(duì)上述4個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行實(shí)驗(yàn)。參數(shù)設(shè)置如下：在CS算法中，種群規(guī)模為25，α=1，Pa=0.25，最大迭代次數(shù)為1 000。在MCS算法中，種群規(guī)模為N=25，α=1，Pa=0.25，最大迭代次數(shù)為1 000，E=100，M=10，wmax=0.9，wmin=0.4。對(duì)每個(gè)測(cè)試函數(shù)，2種算法在上述參數(shù)設(shè)置下分別單獨(dú)運(yùn)行30次，記錄最優(yōu)值、平均值、最差值和標(biāo)準(zhǔn)差，比較結(jié)果如表2所示。

表2 CS算法和MCS算法的尋優(yōu)結(jié)果比較

從表2可知，對(duì)于4個(gè)測(cè)試函數(shù)，MCS算法在30次實(shí)驗(yàn)中獲得的最優(yōu)值、平均值、最差值和標(biāo)準(zhǔn)差值均要優(yōu)于CS算法，這充分說(shuō)明無(wú)論是算法的收斂精度，還是算法的穩(wěn)定性，MCS算法都比CS算法有了較大的提高。

圖1～圖4分別給出了CS算法和MCS算法對(duì)4個(gè)測(cè)試函數(shù)的收斂曲線，從圖中可以看出，對(duì)于函數(shù)f1、f3和f4，MCS算法能很快收斂到最優(yōu)解或接近最優(yōu)解。

圖1 f1函數(shù)的收斂性能比較

圖2 f2函數(shù)的收斂性能比較

圖3 f3函數(shù)的收斂性能比較

圖4 f4函數(shù)的收斂性能比較

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

表3 MCS與其他6種算法的尋優(yōu)結(jié)果比較

從表3可以看出，與GA、ES、PSO、ACO和DE算法相比，無(wú)論是獲得最優(yōu)解的精度，還是算法的穩(wěn)定性，MCS算法在6個(gè)測(cè)試函數(shù)中得到的結(jié)果要優(yōu)。與BBO算法相比，MCS算法在函數(shù)f2和f4上得到的結(jié)果要優(yōu)，而在函數(shù)f1和f3上，BBO算法得到了較好的結(jié)果。從上述比較可知，MCS算法顯示出較強(qiáng)的尋優(yōu)性能。

5 結(jié)束語(yǔ)

針對(duì)布谷鳥(niǎo)搜索算法全局搜索能力強(qiáng)而局部搜索能力弱、易出現(xiàn)早熟收斂的缺點(diǎn)，本文提出一種有效的改進(jìn)布谷鳥(niǎo)搜索算法。該算法利用混沌序列產(chǎn)生初始種群，為提高算法全局搜索能力奠定基礎(chǔ)；引入慣性權(quán)重以平衡算法的勘探和開(kāi)采能力；利用動(dòng)態(tài)隨機(jī)局部搜索技術(shù)進(jìn)行局部搜索，以加快算法的收斂速度。針對(duì)4個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的實(shí)驗(yàn)結(jié)果表明，該混合算法能有效地平衡其局部搜索和全局搜索性能。

[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] 柳新妮, 馬 苗. 布谷鳥(niǎo)搜索算法在多閾值圖像分割中的應(yīng)用[J]. 計(jì)算機(jī)工程, 2013, 39(7): 274-278.

[6] 李向濤, 殷明浩. Parameter Estimation for Chaotic Systems Using the Cuckoo Search Algo rithm with an Orthogonal Learning Method[J]. 中國(guó)物理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] 杜利敏, 阮 奇, 馮登科. 基于共軛梯度的布谷鳥(niǎo)搜索算法[J]. 計(jì)算機(jī)與應(yīng)用化學(xué), 2013, 30(4): 406-410.

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

[10] 劉悅婷. 基于混沌和動(dòng)態(tài)變異的蛙跳算法[J]. 計(jì)算機(jī)應(yīng)用與軟件, 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

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

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

2013-09-22

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

1000-3428(2014)05-0224-04

A

TP301.6