樽海鞘群算法原理详解

首先请大家跟我读,樽(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 f(x,y)=100(x3)2(y4)2,当然这个函数是我随便写的,但是我们不用很关心这个函数的表达式是什么样子的,我们只需要知道,我们现在的任务是找到一对数字 ( x 0 , y 0 ) (x_0,y_0) (x0,y0) 使得这一对数字作为自变量带到函数式里面可以让函数值 f ( x , y ) f(x,y) f(x,y) 的值尽量的大。现在我们就一步一步来使用更高端的方法。

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

  1. 后来我们学会了使用计算机,我只需要在一定范围内枚举所有的自变量的值,找到最大的函数值,就是我们希望找到的了。这个的优势就是,如果 f ( x ) f(x) f(x) 变成这个样子 f ( x ) = c o s ( ( x 2 + y 2 ) 1 6 ) + s i n ( ( x 2 + y 2 ) 1 6 ) f(x) = cos((x^2+y^2)^{\frac16}) + sin((x^2+y^2)^{\frac16}) 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;   
    }
    
  2. 再后来我们发现,如果我们不一定非要找到能使得这个函数取得最大值的自变量,而是只需要使得这个函数的函数值尽量大就可以了,那么这样我们就可以通过放弃最优解而减轻很大的计算量,使得计算较优解变得可行。下面偷鸡开始了,最简单的,我就根据我的计算能力随机的在定义域内取若干个点,然后计算它们的函数值,取其中最大的一个作为我们函数的这个优化结果。这样的好处就是,我根据我的计算机计算能力,限定时间内,我能计算多少个点,我就随机取多少个点进行计算。代码如下:

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

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

樽海鞘算法原理

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

现在假设我们要在一个 n + 1 n+1 n+1 维空间的山中找一个最高峰,我们就让每一个樽海鞘个体的位置表示成一个 n n n 维向量,或者叫一个位置矢量 ( x 1 , x 2 , . . . , x n ) (x_1,x_2,...,x_n) (x1,x2,...,xn) d d d 个樽海鞘连成的樽海鞘链就可以看成是一个种群,用一个 d × N d\times N d×N 的矩阵表示:
X = [ <mstyle displaystyle="false" scriptlevel="0"> x 1 1 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> x 2 1 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> . . . </mstyle> <mstyle displaystyle="false" scriptlevel="0"> x N 1 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> x 1 2 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> x 2 2 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> . . . </mstyle> <mstyle displaystyle="false" scriptlevel="0"> x N 2 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> . . . </mstyle> <mstyle displaystyle="false" scriptlevel="0"> . . . </mstyle> <mstyle displaystyle="false" scriptlevel="0"> . . . </mstyle> <mstyle displaystyle="false" scriptlevel="0"> . . . </mstyle> <mstyle displaystyle="false" scriptlevel="0"> x 1 d </mstyle> <mstyle displaystyle="false" scriptlevel="0"> x 2 d </mstyle> <mstyle displaystyle="false" scriptlevel="0"> . . . </mstyle> <mstyle displaystyle="false" scriptlevel="0"> x N d </mstyle> ] X =\begin{bmatrix}x_1^1 & x_2^1 & ... & x_N^1\\ x_1^2& x_2^2 & ... &x_N^2 \\ ...& ... & ... & ... \\ x_1^d & x_2^d & ... & x_N^d\\\end {bmatrix}\quad X=x11x12...x1dx21x22...x2d............xN1xN2...xNd
其中第 i i i 个樽海鞘个体的表示为: X i = [ <mstyle displaystyle="false" scriptlevel="0"> x 1 i </mstyle> <mstyle displaystyle="false" scriptlevel="0"> x 2 i </mstyle> <mstyle displaystyle="false" scriptlevel="0"> . . . </mstyle> <mstyle displaystyle="false" scriptlevel="0"> x N i </mstyle> ] X_i =\begin{bmatrix}x_1^i & x_2^i & ...& x_N^i \\\end {bmatrix} Xi=[x1ix2i...xNi] 。这时我们把要求最大值的函数叫做目标函数或者适应度函数,一个个体就可以作为自变量带入这个公式中计算出它对应的函数值,这个数值也可以看做是他们对环境的适应程度,或者说叫优秀程度,这个值越高说明这个个体越优秀。然后我们就把这个个体的当前位置当做食物的位置,然后通过公式进一步的模拟樽海鞘的行为。

  • 领导者樽海鞘:领导者也就是 X X X 矩阵中的第一个向量,它作为领导者,它的下一步位置就是会一定程度的朝着食物前进。因此领导者的位置更新公式为:
    x j 1 = { <mstyle displaystyle="false" scriptlevel="0"> F j + c 1 ( ( m a x j m i n j ) c 2 + m i n j ) , c 3 0.5 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> F j c 1 ( ( m a x j m i n j ) c 2 + m i n j ) , c 3 < 0.5 </mstyle> x_j^1=\begin{cases} F_j+c_1((max_j-min_j)c_2+min_j),\quad c_3\ge 0.5\\ F_j-c_1((max_j-min_j)c_2+min_j),\quad c_3< 0.5 \end{cases} xj1={Fj+c1((maxjminj)c2+minj),c30.5Fjc1((maxjminj)c2+minj),c3<0.5
    x j 1 x_j^1 xj1 为领导者在第 j j j 维空间的位置; F j F_j Fj 为食物在第 j j j 维空间的位置; m a x j max_j maxj 是第 j j j 维空间的取值上边界, m i n j min_j minj 是第 j j j 维空间的取值下边界; c 2 c_2 c2 c 3 c_3 c3 是区间 [ 0 , 1 ] [0,1] [0,1] 内产生的随机数, c 2 c_2 c2 决定的是移动的长度, c 3 c_3 c3 决定的是移动的方向的正反; c 1 c_1 c1 主要用于控制整个群体的探索能力开发能力,它和当前种群的迭代次数有关。 c 1 = 2 e ( 4 t T m a x ) 2 c_1 = 2e^{- (\frac{4t}{T_{max}})^2} c1=2e(Tmax4t)2 t t t 为当前的迭代次数, T m a x T_{max} Tmax 为最大的迭代次数。

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

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


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

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

代码实现

C++版: