【智能算法】引力搜索算法（GSA)原理及实现

在这里插入图片描述

1.背景

2009年，Esmat Rashedi等人受到万有引力定律启发，提出了引力搜索算法(Gravitational Search Algorithm，GSA)。

2.算法原理

2.1算法思想

GSA基于万有引力定律：任何物体之间都有相互吸引力，这个力的大小与各个物体的质量成正比例，而与它们之间的距离的平方成反比。

2.2算法过程

万有引力定律：
万有引力定律可以表述为：
$F=G\frac{M_{1}M_{2}}{R^{2}}$
其中， $G$ 是引力常数。由于重力减弱的影响，引力常数的实际值取决于宇宙的实际年龄：
$G(t)=G(t_{0})\times\left(\frac{t_{0}}{t}\right)^{\beta},\quad\beta<1$
在理论物理中，存在三种质量：

主动引力质量 $M_a$ ：决定物体产生的引力场的强弱
被动引力质量 $M_p$ ：决定物体在处于其他引力场时受到的引力大小
惯性质量 $M_i$ ：用于度量施加外力时运动状态不易改变的程度

因此，质量 $i$ 受到质量 $j$ 作用的引力 $F_{ij}$ ，与质量 $j$ 的主动引力质量和质量 $i$ 的被动引力质量的乘积成正比，与它们之间的距离的平方成反比，牛顿定律可以重新表述为：
$\begin{aligned}F_{ij}&=G\frac{M_{aj}\times M_{pi}}{R^2}\\a_i&=\frac{F_{ij}}{M_{ii}}\end{aligned}$
加速度，速度和位置更新:
在 $t$ 时刻，质量 $i$ 受到质量 $j$ 的力为：
$F_{ij}^{d}(t)=G(t)\frac{M_{pi}(t)\times M_{aj}(t)}{R_{ij}(t)+\varepsilon}(x_{j}^{d}(t)-x_{i}^{d}(t))$
其中，距离 $R_{ij}$ 为欧式距离。
GSA中考虑随机特征，这里将质量 $i$ 在维度 $d$ 上受到的力随机加权：
$F_{i}^{d}(t)=\sum_{j=1,j\neq i}^{N}rand_{j}F_{ij}^{d}(t)$
由牛顿第二定律，加速度有：
$a_{i}^{d}(t)=\frac{F_{i}^{d}(t)}{M_{ii}(t)}$
因此，速度和位置更新为：
$\begin{aligned}\nu_i^d(t+1)&=rand_i\times\nu_i^d(t)+a_i^d(t)\\x_i^d(t+1)&=x_i^d(t)+\nu_i^d(t+1)\end{aligned}$
流程图：
在这里插入图片描述