國外新型智能優(yōu)化算法

韓毅 徐梓斌 張亮

摘 要：工程優(yōu)化和人工智能領(lǐng)域的研究中，存在著無免費(fèi)午餐（No-Free-Lunch）理論。這就意味著，沒有一種算法可以在所有的優(yōu)化領(lǐng)域中都具有顯著優(yōu)勢。有鑒于此，文獻(xiàn)提出了一種受自然界的一種飛行松鼠的啟發(fā)，提出了一種新穎的全局優(yōu)化算法——松鼠覓食算法。松鼠覓食算法（Squirrel Search Algorithm， SSA）模仿東南亞南部的飛行松鼠的覓食行為和它們被稱為滑翔（Gliding）的運(yùn)動(dòng)方式，這種方式是小型哺乳動(dòng)物進(jìn)行長距離移動(dòng)的最有效方式。

關(guān)鍵詞：智能優(yōu)化; 飛行松鼠; 無免費(fèi)午餐理論; 滑翔

飛行松鼠是一類棲息在樹上并在夜間進(jìn)行活動(dòng)的嚙齒動(dòng)物，它們特別適合滑翔運(yùn)動(dòng)。目前，飛行松鼠共有15屬44種，其中大部分分布在歐洲和亞洲的落葉林區(qū)（特別是東南亞）。在歐亞大陸以外發(fā)現(xiàn)的、研究最多的是南部飛行松鼠。飛行松鼠被認(rèn)為是空氣動(dòng)力學(xué)上最復(fù)雜的物種，它有一個(gè)類似降落傘的膜，可以幫助松鼠改變升力和阻力，在高空中從一棵樹滑翔到另一棵樹。飛行松鼠不會(huì)飛行，而是采用滑翔方式快速和有效地跨越很長的距離。松鼠之所以要滑翔，是為了躲避捕食者、尋找捕食的最佳地點(diǎn)和以較小的代價(jià)進(jìn)行捕食。圖1a給出了飛行松鼠滑行時(shí)的真實(shí)圖像，圖1b展示了飛行松鼠著陸于樹之前的慢動(dòng)作。

飛行松鼠的覓食策略靈活多變，這可以幫助飛行松鼠以最佳的方式應(yīng)對食物資源。比如，松鼠為了滿足秋季的營養(yǎng)需求，它們選擇吃掉可以大量獲取的橡樹籽，將山核桃存儲(chǔ)在巢穴里、其他洞穴中或者地底下。由于冬季溫度低且營養(yǎng)需求較高，飛行松鼠在覓食時(shí)如發(fā)現(xiàn)山核桃就立刻慈鯛，如果沒有山核桃，飛行松鼠會(huì)從儲(chǔ)存的備用食物中吃山核桃。因此，飛行松鼠根據(jù)營養(yǎng)需求，有選擇地吃一些堅(jiān)果和儲(chǔ)存其他堅(jiān)果。

松鼠覓食算法（SSA）

當(dāng)飛行松鼠開始覓食時(shí)，搜尋過程就開始了。在溫暖的天氣（秋天），飛行松鼠通過從一棵樹滑行到另一棵樹來尋找食物資源。飛行松鼠通過改變位置，探索不同的森林區(qū)域。由于氣候條件足夠溫暖，它們可以通過食用隨處可見的橡樹籽來快速滿足日常能量需求，因此它們一找到橡樹籽就立即吃掉。在滿足了他們每天的能量需求后，他們開始尋找山核桃。山核桃的儲(chǔ)存將有助于它們在極端惡劣的天氣中保持能量需求，減少充滿風(fēng)險(xiǎn)的覓食旅行，從而增加生存的可能性。在冬季，森林中樹葉掉落增加了覓食活動(dòng)的風(fēng)險(xiǎn)，因此松鼠變得不太活躍，但并未冬眠。冬季結(jié)束時(shí)，飛行松鼠再次活躍起來。松鼠在一生中不斷重復(fù)上述過程，直到松鼠的生命終結(jié)為止。

為了簡化數(shù)學(xué)模型，考慮以下假設(shè)。落葉森林中有n只松鼠，每只松鼠停留在一棵樹上。每只松鼠都單獨(dú)尋找食物，并通過動(dòng)態(tài)覓食行為來優(yōu)化利用食物資源。在森林中，只有三種類型的樹——普通樹、橡樹和山核桃樹。假設(shè)森林中包含三棵橡樹和一棵山核桃樹，松鼠的數(shù)為50只。1棵山核桃樹和3棵橡樹是4個(gè)食物資源，其他46棵普通樹沒有食物資源。也就是說，松鼠總數(shù)的92%生活在普通樹上，其余的8%生活在有食物資源的樹上。然而，食物資源的數(shù)量（Number of Food，NFS）可以根據(jù)約束1 < NFS < n而變化。

飛行松鼠的位置在SSA算法中由向量表示，每個(gè)向量有多個(gè)維度。因此，飛行松鼠可以在一維、二維、三維或超維搜索空間中滑行來改變它們自身的位置。

隨機(jī)初始化

森林中有n只飛鼠，第i只松鼠的位置可以通過一個(gè)矢量來確定。所有松鼠的位置可以用下面的矩陣表示：

FSi，j是第i只松鼠第j維上的值，該值根據(jù)公式（2）來隨機(jī)確定。

FSi，U和FSi，L是第j維的上界和下界，U（0，1）是在0和1之間的均勻分布值。

適應(yīng)值評價(jià)

每只松鼠位置的適應(yīng)值描述了食物源的等級，即最佳食物源（山核桃樹）、正常食物源（橡樹）和無食物來源（普通樹）。

排序、聲明和隨機(jī)選擇

在存儲(chǔ)了每只松鼠的位置的適應(yīng)值后，數(shù)組按升序排序。最小適應(yīng)值的松鼠停留在山核桃樹上，接下來的三只松鼠停留在橡樹上，它們可以向山核桃樹飛行，其余的松鼠停留在普通樹上。通過隨機(jī)選擇方式，選擇已經(jīng)滿足每日所需能量的松鼠朝著山核桃樹移動(dòng)，剩余的松鼠將朝著橡樹移動(dòng)以獲取每日所需能量。松鼠的覓食行為會(huì)受到天敵的影響，松鼠具體采用哪種移動(dòng)策略也要根據(jù)天敵的出現(xiàn)概率（Pdp）而定。

生成新位置

在飛行松鼠的覓食過程中，可能會(huì)出現(xiàn)三種情況。在每種情況下，假設(shè)在沒有天敵的情況下，松鼠在整個(gè)森林中滑行并高效地搜尋它最喜歡的食物，而天敵的存在使它變得謹(jǐn)慎，松鼠被迫在小范圍內(nèi)隨機(jī)行走，來搜尋附近的躲藏地點(diǎn)。

①第一種情況，在橡樹上的松鼠會(huì)向山核桃樹移動(dòng)。

其中dg是隨機(jī)滑行距離，R1是[0，1]范圍內(nèi)的隨機(jī)數(shù)，[FStht]是山核桃樹的位置，t表示當(dāng)前迭代?；瑒?dòng)常數(shù)Gc實(shí)現(xiàn)全局與局部搜索之間的平衡，經(jīng)過大量分析論證，Gc的值設(shè)為1.9。

②第二種情況，在普通樹上的松鼠會(huì)向橡樹移動(dòng)。

其中R2是[0，1]范圍內(nèi)的隨機(jī)數(shù)。

③第三種情況，一些在普通樹上的松鼠已經(jīng)吃了橡果，它們可能會(huì)向山核桃樹移動(dòng)以便儲(chǔ)存山核桃來應(yīng)對食物短缺。

其中R3是[0，1]范圍內(nèi)的隨機(jī)數(shù)。

所有情況下，天敵出現(xiàn)的概率都為0.1。圖2顯示了飛行松鼠的滑行動(dòng)作，通過調(diào)整升力和阻力，松鼠可以到達(dá)不同的樹上。

滑翔的空氣動(dòng)力學(xué)

松鼠的滑行機(jī)制是通過平衡滑行來描述的，升力（L）和阻力（D）之和產(chǎn)生一個(gè)合力（R），該合力與飛鼠的重力大小相等且方向相反。因此，R以恒定速度（V）保證松鼠能夠在直線上與水平面成一定角度[φ]下降滑行。升阻比或滑行比定義如下：

松鼠可以通過減小下滑角來增加滑行路徑長度，從而提高升阻比。升力是空氣撞擊膜產(chǎn)生了向下的偏轉(zhuǎn)而產(chǎn)生的反推力的結(jié)果，定義為

其中（[ρ]= 1.204 kg/m3）為空氣密度，CL稱為升力系數(shù)，V = 5.25 m/s為速度，S =0.0154 m2）為松鼠膜表面積。

CD是摩擦阻力系數(shù)，低速移動(dòng)時(shí)松鼠增加阻力，高速移動(dòng)時(shí)松鼠減小阻力。

其中hg =8m是滑行后發(fā)生的高度減少量，計(jì)算dg所需的所有參數(shù)值，包括CL和CD，都是來自于自然界的真實(shí)測量值。因此，松鼠可以根據(jù)著陸位置，簡單地改變升阻比來改變其滑行路徑長度或dg。CL的取值為[0.675，1.5]之間的某個(gè)值，CD的值為0.6。

飛行松鼠通常在一次滑行中行進(jìn)5到25米的水平距離，在SSA算法模型中，滑行距離在9～20米的范圍內(nèi)。dg的值過大會(huì)引起大的擾動(dòng)，可能導(dǎo)致算法的性能不能令人滿意。因此將dg除以一個(gè)稱為比例因子（sf）的非零值，sf = 18使得dg在[0.5，1.11]區(qū)間內(nèi)浮動(dòng)。因此，sf有助于實(shí)現(xiàn)全局搜索和局部尋優(yōu)之間的均衡狀態(tài)。

季節(jié)變化條件

季節(jié)變化會(huì)顯著影響飛行松鼠的覓食活動(dòng)，松鼠在低溫條件下會(huì)損失大量熱量。因?yàn)樗鼈兊捏w溫高、體型小，導(dǎo)致覓食過程的代價(jià)很大，并且由于天敵的存在而具有風(fēng)險(xiǎn)。與秋天相比，氣候條件迫使它們在冬天不太活躍。在SSA算法中通過檢查季節(jié)變化條件，防止算法陷入局部最優(yōu)。

其中t和tm分別是當(dāng)前和最大迭代值，Smin值影響算法的全局和局部搜索能力。Smin的值較大會(huì)有利于全局搜索，而Smin的較小值有利于算法的局部搜索。對于任何啟發(fā)式算法，全局和局部搜索過程需要進(jìn)行有效的平衡。這種平衡可以通過滑動(dòng)常數(shù)Gc來維持的，也可以通過在迭代過程中自適應(yīng)地改變Smin的值來實(shí)現(xiàn)。

③如果季節(jié)變化條件得到滿足（冬天結(jié)束），則隨機(jī)改變普通樹上松鼠的位置。

列維分布（Levy distribution）能夠幫助算法以更好和更有效的方式進(jìn)行全局搜索，列維飛行（Levy flight）幫助算法尋找遠(yuǎn)離當(dāng)前最佳位置的新位置。列維飛行是一種隨機(jī)改變步長的方法，其中步長是從列維分布中得出的。

其中ra和rb是[0，1]區(qū)間上的兩個(gè)正態(tài)分布隨機(jī)數(shù)，[β]=1.5，[σ]計(jì)算如下：

其中[Γ（x）=（x-1）！]。算法停止準(zhǔn)則為最大迭代次數(shù)tm。

算法步驟

1）定義輸入?yún)?shù)

2）為n只松鼠生成隨機(jī)位置

3）評估每只松鼠位置的適應(yīng)值

4）根據(jù)飛行松鼠的適應(yīng)值，按升序排列它們的位置

5）將飛行松鼠分配到山核桃樹、橡子樹和普通樹

6）While（不滿足停止準(zhǔn)則）

8）for z=1 to n1（橡樹上向山核桃樹移動(dòng)的松鼠數(shù)量）

9）利用公式（4）更新松鼠位置

10） for u=1 to n2（普通樹上向橡樹移動(dòng)的松鼠數(shù)量）

11）利用公式（5）更新松鼠位置

12）for e=1 to n3（普通樹上向山核桃樹移動(dòng)的松鼠數(shù)量）

13）利用公式（6）更新松鼠位置

14）計(jì)算松鼠適應(yīng)值，升序排列位置，將飛行松鼠分配到山核桃樹、橡子樹和普通樹

15）判斷季節(jié)變化條件是否滿足，滿足則根據(jù)公式（14-16）更新普通樹上松鼠位置

16）根據(jù)公式（13）更新Smin的值

17）計(jì)算松鼠適應(yīng)值，升序排列位置，將飛行松鼠分配到山核桃樹、橡子樹和普通樹

18）程序While循環(huán)結(jié)束，輸出山核桃樹上松鼠的位置和適應(yīng)值

結(jié)語：

本文還原了國外學(xué)者最新提出的新穎智能優(yōu)化算法——松鼠覓食算法，再現(xiàn)了算法背景，算法的基本模型和算法的具體執(zhí)行步驟。本文旨在為其他工程優(yōu)化和人工智能領(lǐng)域的學(xué)者提供參考和借鑒，為算法的進(jìn)一步完善和混合算法的研究起到一定的啟發(fā)作用。

參考文獻(xiàn)：

[1] Jain M， Singh V， Rani A. A novel nature-inspired algorithm for optimization： Squirrel search algorithm [J]. 2019， 44（2）： 148-175.

[2] Arbogast B S. A brief history of the new world flying squirrels： Phylogeny， biogeography， and conservation genetics [J]. Journal of Mammalogy， 2007， 88（4）： 840-849.