鞏世兵， 沈海斌

(浙江大學(xué) 超大規(guī)模集成電路設(shè)計(jì)研究所，浙江 杭州 310027)

仿生策略優(yōu)化的鯨魚(yú)算法研究*

鞏世兵， 沈海斌

(浙江大學(xué)超大規(guī)模集成電路設(shè)計(jì)研究所，浙江杭州310027)

通過(guò)對(duì)混沌映射初始化種群和自適應(yīng)調(diào)整搜索策略對(duì)鯨魚(yú)優(yōu)化算法(WOA)改進(jìn)，提出了仿生策略優(yōu)化的鯨魚(yú)算法(BWOA)，實(shí)現(xiàn)了對(duì)算法的全局優(yōu)化能力和收斂速度的改進(jìn)。通過(guò)基準(zhǔn)測(cè)試函數(shù)的仿真，BWOA與標(biāo)準(zhǔn)WOA及高效的WOA(EWOA)對(duì)比分析，證明了BWOA的有效性。

鯨魚(yú)算法； 仿生策略； 群智優(yōu)化算法； 切比雪夫序列； 混沌映射初始化種群

0 引 言

啟發(fā)式優(yōu)化算法具有簡(jiǎn)單易實(shí)現(xiàn)、能有效避免局部最優(yōu)、可擴(kuò)展性好等優(yōu)點(diǎn)，廣泛應(yīng)用于各種工程設(shè)計(jì)中[1]。啟發(fā)式算法的思想來(lái)源于各種生物機(jī)制、物理規(guī)律，一般可以分為兩類：基于個(gè)體的方法[2]和基于群體的方法[3]。其中基于群體的方法有：遺傳算法(genetic algorithm,GA)、粒子群優(yōu)化(particle swarm optimization,PSO)算法[3]、蟻群優(yōu)化(ant colony optimization,ACO)算法[4]、蜂群算法(bee colony algorithm,ABC)[5]、細(xì)菌覓食優(yōu)化算法(bacterial foraging optimization algorithm,BFOA)[6]、螢火蟲(chóng)算法(firefly algorithm,FA)[7]、布谷鳥(niǎo)算法(cuckoo algorithm,CS)[8]、果蠅優(yōu)化算法(fruitflies optimization algorithm,FOA)[9]、鯨魚(yú)優(yōu)化算法(whale optimization algorithm,WOA)[1]等。事實(shí)上，這些算法均沒(méi)有對(duì)參數(shù)空間的數(shù)據(jù)完全利用，得到的結(jié)果也具有一定隨機(jī)性[2]。為了實(shí)現(xiàn)對(duì)數(shù)據(jù)的充分利用和快速收斂的目標(biāo)，新的算法在研究中不斷被提出。

本文提出了仿生策略優(yōu)化的鯨魚(yú)優(yōu)化算法(biomimetic whale optimization algorithm,BWOA)以混沌映射初始化種群和自適應(yīng)調(diào)整搜索策略的方式實(shí)現(xiàn)對(duì)基本鯨魚(yú)算法的仿生策略優(yōu)化，避免局部收斂，提高收斂速度。

1 標(biāo)準(zhǔn)鯨魚(yú)算法

WOA算法[1]模仿座頭鯨的捕食機(jī)制，在優(yōu)化過(guò)程中以50 %的概率隨機(jī)選擇收縮圈方式和螺旋氣泡網(wǎng)方式更新個(gè)體的位置。

1.1 收縮圈方式

鯨魚(yú)算法假設(shè)當(dāng)前的最佳候選方案是目標(biāo)位置或是接近目標(biāo)的位置。在最佳搜索代理被定義后，其他搜索代理將試著朝向最佳搜索代理更新其位置。該行為表示為

(1)

(2)

(3)

(4)

1.2 螺旋氣泡網(wǎng)方式

在鯨魚(yú)位置和獵物位置之間使用螺旋方程模擬座頭鯨的螺旋狀移動(dòng)

(5)

(6)

式中b為定義對(duì)數(shù)螺線形狀的常數(shù)；l為[-1,1]的隨機(jī)數(shù)。

1.3 搜索階段

(7)

(8)

2 BWOA

BWOA在鯨魚(yú)算法的基礎(chǔ)上，利用混沌映射初始化種群和自適應(yīng)調(diào)整搜索策略實(shí)現(xiàn)鯨魚(yú)算法的仿生策略優(yōu)化。

2.1 混沌映射初始化種群

傳統(tǒng)的群智算法采用隨機(jī)方式初始化種群，不同的隨機(jī)映射使種群有不同的空間分布，其結(jié)果直接影響算法的性能。而混沌運(yùn)動(dòng)具有遍歷性和偽隨機(jī)性[10]，混沌映射初始化種群應(yīng)較常規(guī)的方法具有遍歷空間的優(yōu)勢(shì)。

如圖1所示，Logistic序列和Chebyshev序列為混沌序列，rand函數(shù)為Matlab默認(rèn)隨機(jī)序列函數(shù)。從散點(diǎn)圖可以看出：混沌序列與rand函數(shù)相比在邊界取值上更容易實(shí)現(xiàn)，遍歷性更好。而Chebyshev混沌序列[11]的自相關(guān)函數(shù)更好，其迭代公式

X(t+1)=cos(warccos(x(t)))

(9)

式中w為Chebyshev的分形參數(shù)。改進(jìn)算法采用Chebyshev混沌映射初始化種群。

圖1 混沌映射散點(diǎn)圖及自相關(guān)函數(shù)

2.2 自適應(yīng)調(diào)整搜索策略

搜索階段，個(gè)體根據(jù)概率閾值p改變隨機(jī)選擇的變量值[12]，如式(10)

p=0.5(1-t/tmax)

(10)

式中t為當(dāng)前迭代次數(shù)；tmax為最大迭代次數(shù)。對(duì)每個(gè)搜索代理，以一個(gè)[0,1]隨機(jī)數(shù)q與概率閾值p進(jìn)行比較。當(dāng)q

Xj=Xjmin+r·(Xjmax-xjmin)

(11)

式中r為[0,1]隨機(jī)數(shù);xjmin,xjmax為變量xj取值的最小值和最大值。

3 基準(zhǔn)函數(shù)測(cè)試與分析

為了測(cè)試算法的收斂速度和全局優(yōu)化能力，選擇單峰和多峰的無(wú)約束測(cè)試函數(shù)[1,4]進(jìn)行仿真，如表1所示，其中，F(xiàn)1，F(xiàn)2為單峰值函數(shù)，其余為多峰值函數(shù)。實(shí)驗(yàn)采用Matlab 2014a進(jìn)行仿真，選擇相同參數(shù)：種群個(gè)體數(shù)50，迭代次數(shù)500。

表1 基準(zhǔn)測(cè)試函數(shù)

BWOA、WOA、高效WOA(EWOA)[2]的平均收斂曲線如圖2所示，其中F4和F5函數(shù)經(jīng)過(guò)了局部放大。

圖2 基準(zhǔn)測(cè)試函數(shù)收斂曲線

從圖中各函數(shù)的收斂曲線可以看出:BWOA相較于標(biāo)準(zhǔn)WOA和EWOA，在單峰函數(shù)和多峰函數(shù)尋優(yōu)過(guò)程中，均具有較快的收斂速度，能有效節(jié)約尋優(yōu)的時(shí)間。從多峰函數(shù)的尋優(yōu)過(guò)程可以看出，典型的如F5和F6函數(shù)，BWOA相較于標(biāo)準(zhǔn)WOA和EWOA，能夠有效地避免局部收斂，更易獲得全局最優(yōu)解。

4 結(jié) 論

BWOA算法利用混沌特有的遍歷性和偽隨機(jī)性對(duì)鯨魚(yú)算法初始化種群的優(yōu)化，使種群個(gè)體在搜索階段能夠均勻分布并遍歷整個(gè)搜索空間；自適應(yīng)調(diào)整搜索策略，能更好地完成搜索空間的搜索。BWOA既保留了鯨魚(yú)算法簡(jiǎn)單高效的優(yōu)點(diǎn)，同時(shí)引入混沌機(jī)制和自適應(yīng)機(jī)制實(shí)現(xiàn)仿生策略優(yōu)化，實(shí)現(xiàn)對(duì)優(yōu)化算法全局尋優(yōu)能力和收斂速度的提升。

[1] Mirjalili S,Lewis A.The whale optimization algorithm[J].Advances in Engineering Software,2016,95:51-67.

[2] Ebrahimi A,Khamehchi E.Sperm whale algorithm:An effective metaheuristic algorithm for production optimization problems[J].Journal of Natural Gas Science and Engineering,2016,29:211-222.

[3] Kaveh A.Advances in metaheuristic algorithms for optimal design of structures[M].New York:Springer Verlag,2015.

[4] 倪 壯,肖 剛,敬忠良,等.改進(jìn)蟻群算法的飛機(jī)沖突解脫路徑規(guī)劃方法[J].傳感器與微系統(tǒng)，2016，35(4)：130-133.

[5] Yu Ting,Wang Limin,Han Xuming,et al.Swarm intelligence optimization algorithms and their application[C]∥Proceedings of Fourteenth Wuhan International Conference on E-Business,WHICEB 2015,Wuhan,China,2015:1-9.

[6] Das S,Biswas A,Dasgupta S,et al.Foundations of computational intelligence[M].Berlin Heidelberg:Springer,2009:23-55.

[7] Yang X S.Firefly algorithms for multimodal optimization[C]∥International Symposium on Stochastic Algorithms,2009:169-178.

[8] 鄭洪清,周永權(quán).一種自適應(yīng)步長(zhǎng)布谷鳥(niǎo)搜索算法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(10):68-71.

[9] 霍慧慧,李國(guó)勇.改進(jìn)的離散果蠅優(yōu)化算法在WSNs覆蓋中的應(yīng)用[J].傳感器與微系統(tǒng)，2016,35(2)：157-160.

[10] 許 棟,崔小欣,王 田,等.基于Logistic映射的混沌隨機(jī)數(shù)發(fā)生器研究[J].微電子學(xué)與計(jì)算機(jī),2016,33(2):1-6.

[11] Zhou Y,Zhou J,Wang F,et al.An efficient chaotic map-based authentication scheme with mutual anonymity[J].Applied Computational Intelligence and Soft Computing,2016,10:1-8.

[12] Kaveh A,Ghazaan M I.Enhanced whale optimization algorithm for sizing optimization of skeletal structures[J].Mechanics-based Design of Structures and Machines,2017,45:345-362.

Studyofwhalealgorithmforbiomimeticstrategyoptimization*

GONG Shi-bing, SHEN Hai-bin

(InstituteofVLSIDesign,ZhejiangUniversity,Hangzhou310027，China)

The whale optimization algorithm(WOA)is inspired by the hunting behavior of humpback whales and it’s presented as a new swarm-based optimization algorithm recently.This study proposes an improved whale optimization algorithm with optimization strategy of bionics(BWOA)by Chaos mapping initialization population and adaptive adjusting search strategy,in order to improve the accuracy of global optimization and the rate of convergence.By simulation on reference test function,BWOA is compared with standard WOA and effective WOA(EWOA),efficiency of BWOA,is demonstrated.

whale optimization algorithm(WOA); biomimetic strategy; swarm-based optimization algorithm; Chebyshev sequences; initial population based on Chaos mapping

10.13873/J.1000—9787(2017)12—0010—03

TP 301

A

1000—9787(2017)12—0010—03

2017—01—04

國(guó)家“863”計(jì)劃資助項(xiàng)目(2012AA041701)

鞏世兵(1985-)，男，碩士研究生，主要研究方向?yàn)橹悄馨踩c芯片設(shè)計(jì)。沈海斌，男，教授，博士生導(dǎo)師，主要從事智能算法、安全處理器架構(gòu)及其實(shí)現(xiàn)等方面的研究工作。