樽海鞘群算法原理详解

首先请大家跟我读，樽（zūn）海（hǎi）鞘（qiào）！
网上看了不少论文用了这个算法，但是还没有很详细清楚的原理介绍。所以我就来开一篇啦。

起源背景

首先这个算法是 Mirjalili 等人2017年在文章《Salp Swarm Algorithm:A bio-inspired optimizer for engineering design problems》中介绍的一个模拟樽海鞘生物的智能优化算法。它对于一些优化问题具有很强的优越性，当然它也会包含一些类似于粒子群等算法相关的内容。

群体智能算法介绍

首先我们先要知道这个算法是做什么的，我们先举一个最简单的例子，假如说，有一个函数 $f(x,y)=100-(x-3{)}^2-(y-4{)}^2$f(x,y)=100−(x−3)2−(y−4)2，当然这个函数是我随便写的，但是我们不用很关心这个函数的表达式是什么样子的，我们只需要知道，我们现在的任务是找到一对数字 $(x_0,y_0)$(x0​,y0​) 使得这一对数字作为自变量带到函数式里面可以让函数值 $f(x,y)$f(x,y) 的值尽量的大。现在我们就一步一步来使用更高端的方法。

1. 如果我们高中的做法，肯定是使用一些数学的知识，比如根据感觉我们知道这个函数在 $(3,4)$(3,4) 这个点可以取得最大值。其实这个函数就是下面这个样子的，可以想象一下，最高点在 $(3,4,100)$(3,4,100)。这种方法需要一定的数学基础。

2. 后来我们学会了使用计算机，我只需要在一定范围内枚举所有的自变量的值，找到最大的函数值，就是我们希望找到的了。这个的优势就是，如果 $f\left(x\right)$f(x) 变成这个样子 $f\left(x\right)=cos\left(\right(x^2+y^2{)}^{\frac{1}{6}})+sin((x^2+y^2{)}^{\frac{1}{6}})$f(x)=cos((x2+y2)61​)+sin((x2+y2)61​) 甚至更复杂的样子，那么数学能力总有捉鸡的时候，所以这时第二种方法的优越性就体现出来了。这种方法很暴力无脑，但是需要确定一个适当的枚举范围，因为自变量的范围可能会很大很大。更需要很强的计算机运算能力。

   double f(int x, int y) {
       return 100 - (x-3)*(x-3) - (y-4)*(y-4);
   }
   double getMax(){
   	double ans = -inf;
       for (int i=-100; i<=100; i++) {
           for (int j=-100; j<=100; j++) {
               ans = max(ans, f(i,j));
           }
       }
    return ans;   
   }
   

3. 再后来我们发现，如果我们不一定非要找到能使得这个函数取得最大值的自变量，而是只需要使得这个函数的函数值尽量大就可以了，那么这样我们就可以通过放弃最优解而减轻很大的计算量，使得计算较优解变得可行。下面偷鸡开始了，最简单的，我就根据我的计算能力随机的在定义域内取若干个点，然后计算它们的函数值，取其中最大的一个作为我们函数的这个优化结果。这样的好处就是，我根据我的计算机计算能力，限定时间内，我能计算多少个点，我就随机取多少个点进行计算。代码如下：

   double f(int x, int y) {
       return 100 - (x-3)*(x-3) - (y-4)*(y-4);
   }
   double getMax(){
   	double ans = -inf;
       int T = 100000;
       while(T--){
           ans = max( ans , f(rand(), rand()) );
       }
    return ans;
   }
   

4. 偷鸡继续中，上面方法3虽然是随机的，但是我们希望可以更多地利用到之前随机得到的信息，也就是之前随机到的每个点的函数值，来让我们下一次随机的位置更有意义。那么如何利用呢，我们重新看这个问题，我们这个函数的图像想象成是一个凹凸不平的山脉。如果是上面的函数，那么我们可以看到它只有一个山顶，但是如果是分段函数呢，或者有的函数不好用表达式表示出来，而是一段代码描述。那么这个函数的图像就会是一个凹凸不平的山脉，我们的目标就是找到他的最高峰，或者说，找到一个尽量高的位置。那么这个时候如果是我们人类，我们就会充分的利用我们掌握的信息，比如我们站在一个点上，我们肯定就会尽量向周围高的方向前进，那么动物也是，而且因为获取的信息有限（只能知道当前所在点的位置的高度），所以有时候往往动物的一些行为对于这种找最高点的目标更有优势。这样就衍生了各种各样的群体智能算法，其实都是在模拟各种各样的小动物的行为。从众多的群体智能算法中，我们这一篇博客讲的就是模拟樽海鞘行动的算法。

5. 我们继续进行扩展，上面我们的方法都是对于某一个形如 $f(x,y)$f(x,y) 的自变量是二维向量的，那么如果是自变量是 $n$n 维向量的呢，当然是看成是在一个 $n+1$n+1 维空间的山上找最高峰啦，那么我们的生物就是在 $n$n 维空间上移动，所在的每一个位置都有一个对应的山峰的高度，这样让生物按照一定的规则移动去寻找最高峰就好啦。

樽海鞘算法原理

好了下面就是进入正题的阶段了，樽海鞘群算法就是在模拟樽海鞘的聚集行为，它们组成樽海鞘链，然后进行捕食和移动。樽海鞘链由两种类型的樽海鞘组成：领导者和追随者，领导者是链的头部的樽海鞘，链上后边的都是追随者角色。

现在假设我们要在一个 $n+1$n+1 维空间的山中找一个最高峰，我们就让每一个樽海鞘个体的位置表示成一个 $n$n 维向量，或者叫一个位置矢量 $(x_1,x_2,...,x_n)$(x1​,x2​,...,xn​)， $d$d 个樽海鞘连成的樽海鞘链就可以看成是一个种群，用一个 $d\times N$d×N 的矩阵表示：
X=⎣⎢⎢⎡​x11​x12​...x1d​​x21​x22​...x2d​​............​xN1​xN2​...xNd​​⎦⎥⎥⎤​
其中第 $i$i 个樽海鞘个体的表示为： Xi​=[x1i​​x2i​​...​xNi​​] 。这时我们把要求最大值的函数叫做目标函数或者适应度函数，一个个体就可以作为自变量带入这个公式中计算出它对应的函数值，这个数值也可以看做是他们对环境的适应程度，或者说叫优秀程度，这个值越高说明这个个体越优秀。然后我们就把这个个体的当前位置当做食物的位置，然后通过公式进一步的模拟樽海鞘的行为。

• 领导者樽海鞘：领导者也就是 $X$X 矩阵中的第一个向量，它作为领导者，它的下一步位置就是会一定程度的朝着食物前进。因此领导者的位置更新公式为：
  xj1​={Fj​+c1​((maxj​−minj​)c2​+minj​),c3​≥0.5Fj​−c1​((maxj​−minj​)c2​+minj​),c3​<0.5​
  $x_j^1$xj1​ 为领导者在第 $j$j 维空间的位置； $F_j$Fj​ 为食物在第 $j$j 维空间的位置； $ma{x}_j$maxj​ 是第 $j$j 维空间的取值上边界， $mi{n}_j$minj​ 是第 $j$j 维空间的取值下边界； $c_2$c2​ 和 $c_3$c3​ 是区间 $[0,1]$[0,1] 内产生的随机数， $c_2$c2​ 决定的是移动的长度， $c_3$c3​ 决定的是移动的方向的正反； $c_1$c1​ 主要用于控制整个群体的探索能力和开发能力，它和当前种群的迭代次数有关。 $c_1=2e^{-(\frac{4t}{T_{max}}{)}^2}$c1​=2e−(Tmax​4t​)2， $t$t 为当前的迭代次数， $T_{max}$Tmax​ 为最大的迭代次数。

• 追随者樽海鞘：顾名思义，追随者樽海鞘就是跟着领导者来运动的，第 $i$i 只追随者下一次迭代的位置是由，“当前迭代中它自己的位置” 和 ”第 $i-1$i−1 只樽海鞘的位置“ 共同决定的。根据牛顿运动定理公式的一定化简我们得到追随者的位置更新公式：
  $x_j^i\left(t\right)=\frac{1}{2}\left[x_j^i\right(t-1)+x_j^{i-1}(t-1\left)\right]$xji​(t)=21​[xji​(t−1)+xji−1​(t−1)]
  其中： $x_j^i\left(t\right)$xji​(t) 表示在第 $t$t 次迭代的时候，第 $i$i 只樽海鞘在第 $j$j 维空间的坐标。

至此我们就描述完成了樽海鞘群算法的两种个体的行为模式，接下来只要选定合适的参数进行模拟就可以了。

后面待更新。。。。。。
欢迎交流QQ：1040865060

樽海鞘群算法解决路径规划时的编码设计

代码实现

C++版：