松鼠算法

没有免费的午餐

对它的简单易懂的解释就是:
1、一种算法(算法A)在特定数据集上的表现优于另一种算法(算法B)的同时,一定伴随着算法A在另外某一个特定的数据集上有着不如算法B的表现;
2、具体问题(机器学习领域内问题)具体分析(具体的机器学习算法选择)。

松鼠觅食算法

一种新颖的全局优化算法——松鼠觅食算法(Squirrel Search Algorithm, SSA)

松鼠习性

在温暖的秋天,它们一找到橡树籽就立即吃掉。
在满足了他们每天的能量需求后,他们开始寻找可以储存能量的山核桃,来减少充满风险的觅食,从而增加生存的可能性。
在寒冷的冬季,森林中树叶掉落增加了觅食活动的风险,因此松鼠变得不太活跃,但并未冬眠。冬季结束时,飞行松鼠再次活跃起来。
松鼠在一生中不断重复上述过程,直到松鼠的生命终结为止。

抽象出的数学模型

以下假设为简化的数学模型。
落叶森林中有n 只松鼠,每只松鼠停留在一棵树上。
每只松鼠都单独寻找食物,并通过动态觅食行为来优化利用食物资源。
在森林中,只有三种类型的树——普通树、橡树和山核桃树。
假设森林中包含50棵树,50只松鼠。
1棵山核桃树,3棵橡树,46棵普通树(没有食物资源)。
92%的松鼠生活在普通树上,其余的8%生活在有食物资源的树上。
食物资源的数量(Number of Food,NFS)可以根据约束1 < NFS < n而变化。
飞行松鼠的位置在SSA算法中由向量表示,每个向量有多个维度。
因此,飞行松鼠可以在一维、二维、三维或超维搜索空间中滑行来改变它们自身的位置。

算法大体流程

  1. 随机初始化

    有n只飞鼠,第i只松鼠的位置可以通过一个矢量来确定,所有松鼠的位置可以用FS矩阵表示。

upload successful
其中,FSi,j是第i只松鼠第j维上的值,该值根据下面的公式来随机确定。
FSi,j = FSi,L + U(0,1)×( FSi,U - FSi,L )
FSi,U和FSi,L是第j维的上界和下界,U(0,1)是在0和1之间的均匀分布值。

  1. 适应值评价

    每只松鼠位置的适应值描述了食物源的等级,即最佳食物源(山核桃树)、正常食物源(橡树)和无食物来源(普通树)。

upload successful

  1. 排序、声明和随机选择

    • 排序

      在存储了每只松鼠的位置的适应值后,数组按升序排序。
    • 声明

      最小适应值的松鼠停留在山核桃树上,接下来的三只松鼠停留在橡树上,它们可以向山核桃树飞行,其余的松鼠停留在普通树上。
    • 随机选择

      通过随机选择方式,选择已经满足每日所需能量的松鼠朝着山核桃树移动,剩余的松鼠将朝着橡树移动以获取每日所需能量。
      松鼠的觅食行为会受到天敌的影响,松鼠具体采用哪种移动策略也要根据天敌的出现概率(Pdp)而定。
  2. 生成新位置

    在飞行松鼠的觅食过程中,可能会出现三种情况。
    在每种情况下,假设在没有天敌的情况下,松鼠在整个森林中滑行并高效地搜寻它最喜欢的食物,而天敌的存在使它变得谨慎,松鼠被迫在小范围内随机行走,来搜寻附近的躲藏地点。
    第一种情况,在橡树上的松鼠会向山核桃树移动。
    upload successful
    其中 dg 是随机滑行距离,R1是[0,1]范围内的随机数,FShtt是山核桃树的位置,t表示当前迭代。滑动常数Gc实现全局与局部搜索之间的平衡,经过大量分析论证,G的值设为1.9。
    第二种情况,在普通树上的松鼠会向橡树移动。
    upload successful
    其中R2是[0,1]范围内的随机数。
    第三种情况,一些在普通树上的松鼠已经吃了橡果,它们可能会向山核桃树移动以便储存山核桃来应对食物短缺。
    upload successful
    其中R3是[0,1]范围内的随机数。
    所有情况下,天敌出现的概率都为0.1。通过调整升力和阻力,松鼠可以到达不同的树上。

  3. 滑翔的空气动力学

    松鼠的滑行机制是通过平衡滑行来描述的。
    升力(L)和阻力(D)之和产生一个合力(R),该合力与飞鼠的重力大小相等且方向相反。因此,R以恒定速度(V)保证松鼠能够在直线上与水平面成一定角度 φ 下降滑行。升阻比或滑行比定义如下:

    L/D = 1/tanφ

upload successful

松鼠可以通过减小下滑角来增加滑行路径长度,从而提高升阻比。升力是空气撞击膜产生了向下的偏转而产生的反推力的结果,定义为

L=1/2ρCLV2S

其中(ρ= 1.204 kg/m3)为空气密度,CL称为升力系数,V = 5.25 m/s为速度,S =0.0154 m2)为松鼠膜表面积。

D=1/2ρCDV2S

CD是摩擦阻力系数,低速移动时松鼠增加阻力,高速移动时松鼠减小阻力。

φ=arctan(L/D)
dg=hg/tanφ

其中 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 有助于实现全局搜索和局部寻优之间的均衡状态。

  1. 季节变化条件

    季节变化会显著影响飞行松鼠的觅食活动,松鼠在低温条件下会损失大量热量。因为它们的体温高、体型小,导致觅食过程的代价很大,并且由于天敌的存在而具有风险。与秋天相比,气候条件迫使它们在冬天不太活跃。在SSA算法中,通过检查季节变化条件,防止算法陷入局部最优。
    • 计算季节常量 Sc
      upload successful
    • 计算季节变化条件 (Sct小于Smin
      upload successful
      其中t和tm分别是当前和最大迭代值,Smin值影响算法的全局和局部搜索能力。Smin的值较大会有利于全局搜索,而Smin的值较小会有利于局部搜索。对于任何启发式算法,全局和局部搜索过程需要进行有效的平衡。这种平衡可以通过滑动常数 Gc 来维持的,也可以通过在迭代过程中自适应地改变Smin的值来实现。
    • 如果季节变化条件得到满足(冬天结束),则随机改变普通树上松鼠的位置。
      upload successful
      列维分布(Levy distribution)能够帮助算法以更好和更有 效的方式进行全局搜索,列维飞行(Levy flight)帮助算法寻找 远离当前最佳位置的新位置。列维飞行是一种随机改变步长 的方法,其中步长是从列维分布中得出的。
      upload successful
      其中 ra 和 rb 是[0,1]区间上的两个正态分布随机数,β=1.5,σ计算如下:
      upload successful
      且有
      upload successful
      算法停止准则为最大迭代次数tm

算法步骤(论文里有伪代码)

1)定义输入参数
2)为n只松鼠生成随机位置
3)评估每只松鼠位置的适应值
4)根据飞行松鼠的适应值,按升序排列它们的位置
5)将飞行松鼠分配到山核桃树、橡子树和普通树
6)While(不满足停止准则)
7)for z=1 to n1(橡树上向山核桃树移动的松鼠数量)
8)利用“生成新位置”中的“公式1”更新松鼠位置
9)for u=1 to n2(普通树上向橡树移动的松鼠数量)
10)利用“生成新位置”中的“公式2”更新松鼠位置
11)for e=1 to n3(普通树上向山核桃树移动的松鼠数量)
1 3 )利用“生成新位置”中的“公式3”更新松鼠位置
14)计算松鼠适应值,升序排列位置,将飞行松鼠分配到山核桃树、橡子树和普通树 15)判断季节变化条件是否满足,满足则根据“季节变化条件”中的“冬天结束”四个公式更新普通树上松鼠位置
16)根据公式(13)更新Smin的值
17)计算松鼠适应值,升序排列位置,将飞行松鼠分配到山核桃树、橡子树和普通树
18)程序 While 循环结束,输出山核桃树上松鼠的位置和适应值

请我吃包辣条吧💕