基于萊維飛行的鳥群優(yōu)化算法

劉曉龍，寧 芊，趙成萍， 涂 榫

(四川大學(xué) 電子信息學(xué)院，成都 610065)

基于萊維飛行的鳥群優(yōu)化算法

劉曉龍，寧 芊，趙成萍， 涂 榫

(四川大學(xué) 電子信息學(xué)院，成都 610065)

針對(duì)鳥群優(yōu)化算法(BSA)在求解高維多極值優(yōu)化問題時(shí)容易陷入局部最優(yōu)解和出現(xiàn)早熟收斂的情況，在原始鳥群算法的基礎(chǔ)上，在模擬鳥群飛行行為的過程中引入萊維飛行，提出了一種基于萊維飛行的改進(jìn)算法——萊維-鳥群算法(LBSA);這種算法替換了原算法中隨機(jī)的飛行位置跳變，而采用萊維飛行更新鳥群飛行后的位置，大幅提高了鳥群的位置變化活力，提高了算法的有效性;仿真結(jié)果表明，在求解高維多極值優(yōu)化問題時(shí)，該算法性能優(yōu)于原始鳥群算法。

鳥群算法；萊維飛行；高維；多極值

0 引言

最優(yōu)化問題是當(dāng)今社會(huì)各領(lǐng)域應(yīng)用十分廣泛的一類問題，如空間最優(yōu)化、時(shí)間最優(yōu)化、分類最優(yōu)化等。有些最優(yōu)化問題非常復(fù)雜，難以在可接受的時(shí)間內(nèi)獲取有效解，如非凸的或不可微的問題。為了解決這些復(fù)雜問題，近年來人們模仿自然進(jìn)化和生物系統(tǒng)，提出了大量群體智能優(yōu)化算法[1]，如遺傳算法(GA)[2]、微分進(jìn)化算法(DE)[3]、粒子群算法(PSO)[4]、人工魚群算法(AFSA)[5]、布谷鳥搜索算法(CS)[6]、蝙蝠算法(BA)[7]、雞群算法(CSO)[8]等。這些算法為求解大量存在于計(jì)算科學(xué)、工程科學(xué)、管理科學(xué)等領(lǐng)域的全局最優(yōu)化問題提供了有效的途徑。

鳥群算法(bird swarm algorithm，BSA)是由Xian-Bing Meng等[9]于2015年提出的一種基于鳥群智慧和鳥群行為的群體智能優(yōu)化算法。通過文中的測試表明，鳥群算法在解決多領(lǐng)域的最優(yōu)化問題時(shí)的性能明顯優(yōu)于粒子群算法和微分進(jìn)化算法，但也發(fā)現(xiàn)在解決部分高維多極值問題時(shí)仍存在容易陷入局部最優(yōu)解和早熟收斂的問題。對(duì)此，根據(jù)作者Xian-Bing Meng等提出的幾種算法改進(jìn)意見對(duì)原始鳥群算法進(jìn)行改進(jìn)，通過動(dòng)態(tài)調(diào)整鳥群飛行頻率FQ以提高收斂性能，以及在鳥群的飛行行為中引入萊維飛行以改善種群尋優(yōu)的靈活性，大幅提升算法跳出局部最優(yōu)解的能力。這種改進(jìn)的鳥群算法，稱之為萊維-鳥群算法(levy bird swarm algorithm，LBSA)。

1 鳥群算法

鳥群算法是對(duì)鳥群群體行為和群體互動(dòng)的簡化，它模仿的是鳥群的覓食行為、警戒行為和飛行行為，并用這種群體智慧解決最優(yōu)化問題。鳥群算法可以被如下規(guī)則簡化描述：

1)鳥群中的每只鳥可以在警戒行為和覓食行為之間切換，鳥類是否覓食或是保持警戒是一個(gè)隨機(jī)決策模型。

2)覓食的時(shí)候，每只鳥可以迅速記錄和更新個(gè)體和群體之前最好的覓食經(jīng)驗(yàn)，這個(gè)經(jīng)驗(yàn)也將用于覓食，群體信息將即刻共享于整個(gè)鳥群。

3)保持警戒的時(shí)候，每只鳥都將試圖向群體中心靠近。這種行為會(huì)被群體競爭誘發(fā)的沖突所影響。而具有較高食物儲(chǔ)量的鳥類更傾向于躲起來向群體中心靠近。

4)鳥類可以周期性地向其他位置移動(dòng)。當(dāng)移動(dòng)到另一個(gè)位置時(shí)，鳥類一般要在生產(chǎn)者和乞討者之間做出選擇。具有最高食物儲(chǔ)量的鳥將成為生產(chǎn)者，而具有最低食物儲(chǔ)量的鳥將成為乞討者。其他食物儲(chǔ)量在最高和最低之間的鳥將隨機(jī)選擇成為生產(chǎn)者或者是乞討者。

5)生產(chǎn)者積極尋覓食物，乞討者隨機(jī)跟隨一個(gè)生產(chǎn)者尋找食物。

假設(shè)有N只鳥在D維空間中飛行覓食，第i只鳥在t時(shí)刻的位置描述為：

規(guī)則1可以被表述為一個(gè)隨機(jī)的決策。每一只鳥的決策依賴于一個(gè)[0，1]之間的均勻隨機(jī)數(shù)，同時(shí)設(shè)定一個(gè)[0，1]之間的常量P，當(dāng)隨機(jī)數(shù)小于P時(shí)，該鳥將進(jìn)行覓食，否則，繼續(xù)保持警戒。

基于規(guī)則2，鳥群的覓食行為遵從每只鳥自身的經(jīng)驗(yàn)以及種群經(jīng)驗(yàn)，覓食行為的位置更新公式為：

(1)

式中，j∈[1,…,D]，rand(0,1)表示在[0，1]范圍內(nèi)獨(dú)立均勻分布的隨機(jī)數(shù)。C和S是兩個(gè)正數(shù)，分別稱為感知系數(shù)和社會(huì)加速系數(shù)。Pi,j表示第i只鳥早先的最佳位置，gj表示群體共享的早先最佳位置。

基于規(guī)則3，鳥群保持警戒的時(shí)候?qū)L試向種群的中心移動(dòng)，并伴隨著與同類的競爭，因而不能直接向種群中心移動(dòng)，警戒行為的位置更新公式為：

(2)

(3)

(4)

式中，k(k≠i)是一個(gè)[1，N]之間的隨機(jī)正整數(shù)。a1和a2是兩個(gè)[0，2]之間的常量，pFiti表示第i只鳥的最佳適應(yīng)度值，sumFit表示整個(gè)種群的最佳適應(yīng)度值之和。ε是為了避免零因子錯(cuò)誤而使用的由計(jì)算機(jī)產(chǎn)生的最小正常量。meanj表示整個(gè)種群平均位置的第j個(gè)元素。A1描述的是一只鳥向鳥群中心移動(dòng)過程中由環(huán)境引發(fā)的間接作用，而A2描述的則是由某個(gè)具體沖突而引發(fā)的直接作用。

基于規(guī)則4和規(guī)則5，鳥類會(huì)因逃避捕食等原因變動(dòng)飛行中的位置，每當(dāng)其飛行到一個(gè)新的位置，將在生產(chǎn)者和乞討者之間做出選擇，自行覓食或者跟隨生產(chǎn)者獲取食物，飛行行為中生產(chǎn)者和乞討者的位置更新公式分別為：

(5)

(6)

式中，randn(0,1)表示均值為0，標(biāo)準(zhǔn)差為1的高斯隨機(jī)分布，F(xiàn)L∈[0,2]代表乞討者跟隨生產(chǎn)者尋找食物。鳥群的飛行移動(dòng)間隔為FQ，F(xiàn)Q是一個(gè)正整數(shù)。

2 萊維飛行

萊維分布是法國數(shù)學(xué)家萊維(Lévy)于20世紀(jì)30年代提出的一種概率分布，而萊維飛行是服從萊維分布的隨機(jī)搜索路徑，這是一種短距離搜索與偶爾長距離搜索相間的隨機(jī)行走模式[10]。經(jīng)過大量的研究，萊維飛行符合蜜蜂、信天翁等多種自然界生物的行為軌跡[11]，并可以解釋許多自然界的隨機(jī)現(xiàn)象，如布朗運(yùn)動(dòng)等。

近年來，萊維飛行被大量引入優(yōu)化領(lǐng)域，如Yan Xinshe等利用萊維飛行改進(jìn)布谷鳥算法[12]，Wang Qingxi等利用萊維飛行改進(jìn)粒子群算法[13]。萊維飛行的引入，增強(qiáng)了種群的多樣性，擴(kuò)大了搜索的范圍，更容易跳出局部最優(yōu)點(diǎn)[14]，有效增強(qiáng)了算法的尋優(yōu)能力。

萊維飛行的實(shí)質(zhì)是一種隨機(jī)步長，其位置更新公式為：

⊕Levy(λ)

(7)

式中，i∈[1,…,N]，代表步長控制量，Levy(λ)為隨機(jī)搜索路徑，⊕為點(diǎn)對(duì)點(diǎn)乘法。并滿足萊維分布：

Levy～u=t-λ,1<λ≤3

(8)

由于萊維飛行十分復(fù)雜，目前大多使用Mantegna算法模擬，數(shù)學(xué)表達(dá)式表示如下。

步長s計(jì)算公式：

(9)

其中:μ,υ滿足正態(tài)分布：

(10)

(11)

(12)

各式中的β通常取常量1.5。

為了證明萊維飛行的優(yōu)越性，在Matlab中分別對(duì)萊維飛行和隨機(jī)行走進(jìn)行了模擬仿真，步長均為200步，結(jié)果如圖1所示。

圖1 萊維飛行和隨機(jī)行走對(duì)比圖

從圖1可以看出，萊維飛行具有更大的搜索范圍和更強(qiáng)的搜索能力，而隨機(jī)行走則搜索范圍相對(duì)集中。因而，將萊維飛行引入鳥群算法的飛行規(guī)則中，將使鳥群算法具有更強(qiáng)的跳躍能力，特別是提高算法跳出局部最優(yōu)點(diǎn)的能力，從而有效提高算法的全局尋優(yōu)能力。

3 基于萊維飛行的鳥群優(yōu)化算法

3.1 算法改進(jìn)

萊維-鳥群優(yōu)化算法在原有的鳥群算法基礎(chǔ)上做出了3個(gè)方面的改進(jìn)：

3.1.1 在鳥群的飛行行為中引入萊維飛行進(jìn)行位置更新，公式5由以下公式替換：

⊕Levy(β)

(13)

Levy(β)由式(9)計(jì)算得出。由于式(12)中含有Γ積分運(yùn)算，因而萊維飛行的引入將大大增加整個(gè)算法的運(yùn)算開銷。為節(jié)約開銷，β常常取定值1.5，則σμ運(yùn)算的結(jié)果也為常量0.696 6。式(13)可以簡化為：

(14)

s(μ,υ)由式(9)計(jì)算得出，其中:

μ～N(0,0.69662)

(15)

υ～N(0,1)

(16)

3.1.2 鳥群的飛行頻率FQ動(dòng)態(tài)改變

圖2 LBSA算法基本流程圖

參數(shù)FQ是決定算法能否有效跳出局部最優(yōu)點(diǎn)，獲得全局最優(yōu)的關(guān)鍵參數(shù)。FQ取固定值時(shí)，算法在計(jì)算開銷和準(zhǔn)確性兩者之間難以取得好的平衡。FQ過小，則計(jì)算開銷直線上升，F(xiàn)Q太大，則準(zhǔn)確性難以得到保障，算法容易陷入局部最優(yōu)。因此，改進(jìn)的鳥群算法使FQ成為一個(gè)動(dòng)態(tài)改變的量，F(xiàn)Q的取值范圍為[3,15]，初始化的時(shí)候選取默認(rèn)值5。在迭代的過程中，每完成H次飛行位置跳躍，即進(jìn)行H次萊維飛行運(yùn)算，就對(duì)整個(gè)周期內(nèi)全局最優(yōu)值改變情況進(jìn)行判斷：如果完全沒有發(fā)生變化，說明算法長期處于某一極值點(diǎn)中無法跳出，則增加飛行頻率，F(xiàn)Q默認(rèn)自減1。若變化h～H(h

3.1.3 生產(chǎn)者和乞討者的分類更加隨機(jī)化。

在鳥群算法的原始設(shè)計(jì)中，生產(chǎn)者和乞討者的劃分是更加細(xì)致和隨機(jī)的。具有最高食物儲(chǔ)量的鳥將成為生產(chǎn)者，具有最低食物儲(chǔ)量的鳥將成為乞討者。在兩者之間的鳥類也并非完全隨機(jī)選擇成為生產(chǎn)者和乞討者，而是擁有食物越多的鳥將有更大的概率成為生產(chǎn)者，反之則有更大的概率成為乞討者。因此，改進(jìn)的鳥群算法在劃分生產(chǎn)者和乞討者時(shí)，將產(chǎn)生一組隨機(jī)數(shù)Pi(Pi為范圍在[0,1]之間的隨機(jī)數(shù)，i∈ [1, …,N])。當(dāng)鳥i的適應(yīng)度值pFiti小于Pi時(shí)，鳥i成為生產(chǎn)者，否則成為乞討者。這種改進(jìn)，增加了算法的靈活性。

3.2 算法步驟

LBSA的基本流程見圖2。

3.3 計(jì)算量與耗時(shí)

LBSA算法因引入了萊維飛行，計(jì)算復(fù)雜度呈幾何倍率增長。從50次對(duì)比仿真實(shí)驗(yàn)中可以得出平均運(yùn)行時(shí)間，每100次萊維飛行的計(jì)算耗時(shí)約為2.181秒，而100次隨機(jī)行走的計(jì)算耗時(shí)僅為0.002秒。當(dāng)選用sphere為測試函數(shù)，迭代次數(shù)1 000次，維數(shù)為20維，飛行頻率FQ為常量10，即固定飛行100次時(shí)，LBSA平均耗時(shí)36.892秒，BSA平均耗時(shí)0.682秒。這種計(jì)算量的大幅增加，主要是因?yàn)槭?2)～(6)中的兩次Γ積分運(yùn)算，為減小計(jì)算復(fù)雜度，將參數(shù)β取定值1.5，則計(jì)算復(fù)雜度直接下降至接近原始算法水平。依舊采用上述測試標(biāo)準(zhǔn)，50次仿真實(shí)驗(yàn)的平均耗時(shí)0.832秒。因?yàn)槿R維飛行的引入大大增加了算法的活力和性能，因而這種程度的計(jì)算開銷增加是可以接受的。

4 驗(yàn)證與比較

表1所列的8個(gè)基本測試函數(shù)涵蓋了單極值、多極值、高維和低維等各種情況，其中的大多數(shù)最優(yōu)化問題用傳統(tǒng)經(jīng)典算法是無法解決的。通過對(duì)這8個(gè)基本測試函數(shù)的仿真實(shí)驗(yàn)，以及和粒子群算法(PSO)、微分進(jìn)化算法(DE)、原始鳥群算法(BSA)的對(duì)比測試，驗(yàn)證改進(jìn)的萊維-鳥群算法(LBSA)的有效性、高效性和穩(wěn)定性。

為使測試結(jié)果更加公平，所有的測試均采用Intel i5-5200U 2.2G雙核處理器，4G內(nèi)存，Win10操作系統(tǒng)，Matlab R2014a仿真環(huán)境。各種算法的種群規(guī)模為、維數(shù)、最大迭代次數(shù)等關(guān)鍵參數(shù)都設(shè)置相同，并分別獨(dú)立運(yùn)行100次。

相關(guān)參數(shù)見表2；測試結(jié)果見表3。

表1 測試函數(shù)

表2 算法參數(shù)設(shè)置

從表3的所有8個(gè)測試結(jié)果來看，BSA和LBSA算法在整體性能上是明顯超越了PSO和DE算法的，特別是F3、F4、F6及F8四個(gè)測試函數(shù)的結(jié)果顯示，在同樣的條件下，PSO和DE算法在多極值函數(shù)的最優(yōu)化求解方面存在較大的困難，容易陷入局部最優(yōu)。

表3 四類算法在D=20(F1-F4)、D=2(F6-F7)及D=1(F8)時(shí)求解結(jié)果比較

在BSA和LBSA的橫向比較中，可以看出，兩種算法的性能整體是比較接近的。在F1、F3、F5～F8的最優(yōu)值結(jié)論都是一致的，其中在標(biāo)準(zhǔn)差方面的差異主要是因?yàn)榈?種算法改進(jìn)導(dǎo)致的隨機(jī)性區(qū)別。而在F2和F4函數(shù)的求解中，LBSA體現(xiàn)出了其改進(jìn)的優(yōu)勢?？梢钥闯?，在這兩個(gè)問題上BSA算法是陷入了局部極值點(diǎn)的，F(xiàn)2問題可以通過增加迭代次數(shù)來解決這個(gè)問題，但F4問題則無法通過增加迭代數(shù)的方法來解決，這說明通過引入萊維飛行增加算法的跳躍靈活性、提高算法性能是有效的。

同時(shí)，從實(shí)驗(yàn)的函數(shù)收斂曲線也可以發(fā)現(xiàn)，BSA和LBSA的收斂性能比PSO和DE算法有優(yōu)勢，而LBSA因?qū)Q系數(shù)進(jìn)行了自適應(yīng)改進(jìn)，因而也比BSA收斂速度更快。

5 結(jié)論

對(duì)于鳥群算法在求解高維多極值優(yōu)化問題時(shí)容易陷入局部最優(yōu)解和出現(xiàn)早熟收斂的情況，對(duì)鳥群算法進(jìn)行了性能改進(jìn)。在算法的飛行公式中引入了萊維飛行，并對(duì)飛行頻率進(jìn)行了自適應(yīng)改進(jìn)，調(diào)整了飛行行為中兩類鳥群的分類模型。這些改進(jìn)的優(yōu)點(diǎn)是增加了算法的跳躍活力，在高迭代次數(shù)的情況下，通過FQ的自適應(yīng)調(diào)整能有效調(diào)節(jié)整體運(yùn)算量，增加算法的收斂性能。缺點(diǎn)是一定程度上增加了計(jì)算量，且因加入了更加隨機(jī)的分類機(jī)制，使算法的穩(wěn)定性有輕微的下降。通過8個(gè)基本測試函數(shù)的仿真測試表明，萊維-鳥群算法在增加了可控的時(shí)間開銷情況下，比原始的鳥群算法更易于跳出局部最優(yōu)值，算法的收斂性能有明顯的提高，同時(shí)保持了良好的穩(wěn)定性。所以文中綜合前人研究，試驗(yàn)改進(jìn)的算法具有可行性和先進(jìn)性。

[1] Beheshti Z, Shamsudding S M H. (2013).A review of population- based meta- heuristic algorithms[J]. Int. J. Adv. Soft Comput. Appl.，5(1):1-35.

[2] Kuo H C, Lin C H. (2013).A directed Genetic Algorithm for global optimization[J]. Applied Mathematics and Computation, 2013:7348-7364.

[3] Das S, Suganthan P N. Differential evolution: A survey of the state-of-the-art[J]. IEEE Transactions on Evolutionary Computation,2011.

[4] Rezaee J A R, Jasni J. Parameter selection in particle swarm optimization : A survey[J]. Journal of Experimental & Theoretical Artificial Intelligence, 2013,25:527-542.

[5] Gao X Z, Wu Y, Zenger K, et al. A knowledge-based artificial fish-swarm algorithm[A].13th IEEE International Conference on Computational Science and Engineering[C]. Hong Kong: IEEE Computer Society,2010:327-332.

[6] Yang X S, Deb S.Cuckoo search: Recent advances and applications[J]. Neural Computing &Applications,2014,24: 169-174.

[7] Yang X S. A new metaheuristic bat-inspired algorithm[A]. Nature Inspired Cooperative Strategies for Optimization (NICSO 2010)[C]. Studies in Computational Intelligence, 2010,284: 65-74.

[8] Meng X B, Liu Y, Gao X Z, et al. A new bio- inspired algorithm: chicken swarm optimization[A].5th International Conference on Swarm Intelligence[C]. Hefei: Springer International Publishing, 2014:86-94.

[9] Meng X B, Gao X Z, Lu L H,et al. A new bio-inspired optimization algorithm: bird swarm algorithm[J]. Journal of Experimental & Theoretical Artificial Intelligence, 2015.

[10] 楊 嬌，葉春明，應(yīng)用新型螢火蟲算法求解Job-shop調(diào)度問題[J]. 計(jì)算機(jī)工程與應(yīng)用，2013，49(11):213-215.

[11] 劉長平，葉春明，一種新穎的仿生群智能優(yōu)化算法：螢火蟲算法[J]. 計(jì)算機(jī)應(yīng)用與研究，2011，28(9):3295-3297.

[12] Yang X S, Deb S. Engineering optimization by cuckoo search[J]. International Journal of Mathematical Modeling and Numerical Optimization,2010 (4):330-343.

[13] 王慶喜，郭曉波， 基于萊維飛行的粒子群算法[J]. 計(jì)算機(jī)應(yīng)用與研究，2016，33(9).

[14] Yang X S. Nature-inspired metaheuristic algorithm[M]. 2nd ed. Frome: Luniver Press, 2010:16-29.

Bird Swarm Algorithm Based on Levy Flight

Liu Xiaolong, Ning Qian, Zhao Chengping, Tu Sun

(College of Electronics and Information Engineering, Sichuan University, Chengdu 610065,China)

Considering the fact that the original Bird Swarm Algorithm(BSA) in optimizing high-dimensional multi-extreme value easily gets locally optimal solution and premature convergence, an improved algorithm, Levy-Bird Swarm Algorithm(LBSA) is proposed, which is based on Levy flight, a simulation of the birds flying. LBSA replaces the random location changes in the original algorithm by using Levy flight to update the flight locations, which substantially increases the vitality of the location changes, and makes the algorithm more effective. The results of simulation show that the LBSA outperforms the original BSA in optimizing high-dimensional multi-extreme value.

bird swarm algorithm; Levy flight; high-dimensional; multiple extreme value

2016-07-06；

2016-08-09。

973計(jì)劃科研項(xiàng)目(2013CB328903-2)。

劉曉龍(1983-)，男，四川成都人，碩士研究生，主要從事衛(wèi)星通信方向的研究。

1671-4598(2016)12-0194-04

10.16526/j.cnki.11-4762/tp.2016.12.055

TP301.6

A