國外新型智能優化算法

韓毅 徐梓斌 張亮

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

關鍵詞：智能優化; 飛行松鼠; 無免費午餐理論; 滑翔

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

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

松鼠覓食算法（SSA）

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

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

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

隨機初始化

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

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

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

適應值評價

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

排序、聲明和隨機選擇

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

生成新位置

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

①第一種情況，在橡樹上的松鼠會向山核桃樹移動。

其中dg是隨機滑行距離，R1是[0，1]范圍內的隨機數，[FStht]是山核桃樹的位置，t表示當前迭代?；瑒映礕c實現全局與局部搜索之間的平衡，經過大量分析論證，Gc的值設為1.9。

②第二種情況，在普通樹上的松鼠會向橡樹移動。

其中R2是[0，1]范圍內的隨機數。

③第三種情況，一些在普通樹上的松鼠已經吃了橡果，它們可能會向山核桃樹移動以便儲存山核桃來應對食物短缺。

其中R3是[0，1]范圍內的隨機數。

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

滑翔的空氣動力學

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

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

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

CD是摩擦阻力系數，低速移動時松鼠增加阻力，高速移動時松鼠減小阻力。

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

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

季節變化條件

季節變化會顯著影響飛行松鼠的覓食活動，松鼠在低溫條件下會損失大量熱量。因為它們的體溫高、體型小，導致覓食過程的代價很大，并且由于天敵的存在而具有風險。與秋天相比，氣候條件迫使它們在冬天不太活躍。在SSA算法中通過檢查季節變化條件，防止算法陷入局部最優。

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

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

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

其中ra和rb是[0，1]區間上的兩個正態分布隨機數，[β]=1.5，[σ]計算如下：

其中[Γ（x）=（x-1）！]。算法停止準則為最大迭代次數tm。

算法步驟

1）定義輸入參數

2）為n只松鼠生成隨機位置

3）評估每只松鼠位置的適應值

4）根據飛行松鼠的適應值，按升序排列它們的位置

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

6）While（不滿足停止準則）

8）for z=1 to n1（橡樹上向山核桃樹移動的松鼠數量）

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

10） for u=1 to n2（普通樹上向橡樹移動的松鼠數量）

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

12）for e=1 to n3（普通樹上向山核桃樹移動的松鼠數量）

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

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

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

16）根據公式（13）更新Smin的值

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

18）程序While循環結束，輸出山核桃樹上松鼠的位置和適應值

結語：

本文還原了國外學者最新提出的新穎智能優化算法——松鼠覓食算法，再現了算法背景，算法的基本模型和算法的具體執行步驟。本文旨在為其他工程優化和人工智能領域的學者提供參考和借鑒，為算法的進一步完善和混合算法的研究起到一定的啟發作用。

參考文獻：

[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.