国外新型智能优化算法

韩毅 徐梓斌 张亮

摘 要：工程优化和人工智能领域的研究中，存在着无免费午餐（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表示当前迭代。滑动常数Gc实现全局与局部搜索之间的平衡，经过大量分析论证，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.