获取更多资讯，赶快关注上面的公众号吧！

第三十一章 引力搜索算法（Gravitational Search Algorithm，GSA）

2009，伊朗的Esmat Rashedi等人基于万有引力定律和粒子间相互作用提出了一种新型的优化算法——引力搜索算法（Gravitational Search Algorithm，GSA）。在该算法中，在提出的算法中，搜索代理是基于牛顿引力和运动定律相互作用的粒子集合。算法源代码可以关注公众号，后台回复"GSA或引力"获取。

万有引力定律

万有引力，全称为"万有引力定律"(law of universal gravitation)，为物体间相互作用的一条定律，1687年为牛顿所发现。任何物体之间都有相互吸引力，这个力的大小与各个物体的质量成正比例，而与它们之间的距离的平方成反比。如果用$M_1$M1​、$M_2$M2​表示两个物体的质量，$R$R表示它们间的距离，则物体间相互吸引力为
$F=（GM_1M_2）/R²\tag{1}$F=（GM1​M2​）/R²(1)
$G$G称为万有引力常数也可简称为引力常数。

牛顿第二定律说的是，当一个力$F$F作用于一个粒子时，其加速度$a$a仅取决于该力和其质量$M$M：
$a=F/M \tag{2}$a=F/M(2)

此外，由于引力递减的影响，引力常数的实际值取决于宇宙的实际年龄，下面给出了引力常数随着年龄的递减方程：
$G(t)=G\left(t_{0}\right) \times\left(\frac{t_{0}}{t}\right)^{\beta}, \quad \beta<1\tag{3}$G(t)=G(t0​)×(tt0​​)β,β<1(3)

在理论物理学中，存在三种质量：

• 主动引力质量$M_a$Ma​：决定物体产生的引力场的强弱;
• 被动引力质量$M-P$M−P：决定物体在处于其他引力场时受到的引力大小；
• 惯性质量$M_i$Mi​：用于度量施加外力时运动状态不易改变的程度。

根据以上描述，可以重写牛顿定律。质量$j$j作用于质量$i$i的引力$F_{ij}$Fij​与主动引力质量$j$j和被动引力质量$i$i的乘积成正比，与它们的距离平方成反比。$a_i$ai​与$F_{ij}$Fij​成正比，与$i$i的惯性质量成反比，即

$F_{i j} =G \frac{M_{a j} \times M_{p i}}{R^{2}} \tag{4}$Fij​=GR2Maj​×Mpi​​(4)

$a_{i} =\frac{F_{i j}}{M_{i i}} \tag{5}$ai​=Mii​Fij​​(5)
其中$M_{a j}$Maj​和$M_{pi}$Mpi​分别表示粒子$i$i的主动引力质量和粒子$j$j的被动引力质量。$M_{ii}$Mii​为粒子$i$i的惯性质量。

GSA

在GSA中，代理即为物体，其性能由它们的质量进行度量。所有这些物体都受到引力的吸引，这个引力导致所有物体都朝着质量更重的物体运动。较重的质量——对应于好的解——比较轻的解移动得更慢，这保证了对算法进行利用。

每个质量（代理)有4个属性：位置，惯性质量，主动引力质量和被动引力质量。随着时间的推移，质量期望被最大质量吸引，而这个最大质量就表达了搜索空间中的一个最优解。

GSA可以看成是一个孤立的质量系统，各个质量满足以下定律：

• 引力定律：每个粒子吸引其他粒子，两个粒子之间的引力成与质量的乘积成正比，而与它们之间的距离$R$R成反比。在这里使用$R$R代替$R^2$R2,因为根据实验结果,$R$R比$R^2$R2在所有实验情况下能提供更好的结果。
• 运动定律：任何质量的速度变化或加速度等于作用在系统上的力除以惯性质量。

下面，考虑一个具有$N$N个代理（质量）的系统，第$i$i个代理的位置定义为：
$X_{i}=\left(x_{i}^{1}, \ldots, x_{i}^{d}, \ldots, x_{i}^{n}\right) \quad \text { for } i=1,2, \ldots, N\tag{6}$Xi​=(xi1​,…,xid​,…,xin​) for i=1,2,…,N(6)
其中，$x_{i}^{d}$xid​表示第$i$i个代理在第$d$d个维度上的位置。

在某一时刻$t$t，将质量$j$j作用于质量$i$i的力定义为：
$F_{i j}^{d}(t)=G(t) \frac{M_{p i}(t) \times M_{a j}(t)}{R_{i j}(t)+\varepsilon}\left(x_{j}^{d}(t)-x_{i}^{d}(t)\right)\tag{7}$Fijd​(t)=G(t)Rij​(t)+εMpi​(t)×Maj​(t)​(xjd​(t)−xid​(t))(7)
其中，$M_{a j}$Maj​为代理$j$j的主动引力质量，$M_{pi}$Mpi​为代理$i$i的被动引力质量。$G(t)$G(t)为$t$t时刻的引力常量。$\varepsilon$ε为一很小的常量，$R_{ij}(t)$Rij​(t)为代理$i$i和$j$j之间的欧式距离：

$R_{i j}(t)=\left\|X_{i}(t), X_{j}(t)\right\|_{2}\tag{8}$Rij​(t)=∥Xi​(t),Xj​(t)∥2​(8)

为了在算法中引入随机特征，假设作用于代理$i$i维度$d$d上的总力为其他代理施加的力在第$d$d维度上的随机加权和：

$F_{i}^{d}(t)=\sum_{j=1, j \neq i}^{N} \operatorname{rand}_{j} F_{i j}^{d}(t) \tag{9}$Fid​(t)=j=1,j​=i∑N​randj​Fijd​(t)(9)
其中$\operatorname{rand}_{j}$randj​为$[0,1]$[0,1]之间的随机数。

因此，根据运动定律，代理$i$i在时刻$t$t，第$d$d维上的加速度$a^d_i(t)$aid​(t)为：
$a_{i}^{d}(t)=\frac{F_{i}^{d}(t)}{M_{i i}(t)} \tag{10}$aid​(t)=Mii​(t)Fid​(t)​(10)

那么，代理$i$i的下一速度被认为是部分当前速度加上其加速度，从而可以得到其速度和位置计算公式：

$v_{i}^{d}(t+1)=\operatorname{rand}_{i} \times v_{i}^{d}(t)+a_{i}^{d}(t)\tag{11}$vid​(t+1)=randi​×vid​(t)+aid​(t)(11)
$x_{i}^{d}(t+1)=x_{i}^{d}(t)+v_{i}^{d}(t+1)\tag{12}$xid​(t+1)=xid​(t)+vid​(t+1)(12)
其中$\operatorname{rand}_{i}$randi​为$[0,1]$[0,1]内的均匀随机变量。

算法开始时先对引力常数$G$G进行初始化，然后随着时间递减以控制搜索精度：
$G(t)=G(G_0,t)\tag{13}$G(t)=G(G0​,t)(13)

引力质量和惯性质量均通过适应度评估计算得到，质量越大代理越优，代理吸引力越强，行走的也越慢。假设引力质量和惯性质量是等效的，则质量按下式进行更新：

$M_{a i}=M_{p i}=M_{i i}=M_{i}, \quad i=1,2, \ldots, N\tag{14}$Mai​=Mpi​=Mii​=Mi​,i=1,2,…,N(14)

$m_{i}(t)=\frac{f i t_{i}(t)-w o r s t(t)}{b e s t(t)-w o r s t(t)}\tag{15}$mi​(t)=best(t)−worst(t)fiti​(t)−worst(t)​(15)

$M_{i}(t)=\frac{m_{i}(t)}{\sum_{j=1}^{N} m_{j}(t)}\tag{16}$Mi​(t)=∑j=1N​mj​(t)mi​(t)​(16)

在探索和利用之间实现良好折衷的一种方法是在(9)中，随着时间的推移减少agent的数量。因此，建议只有一组质量较大的agent对其他代理施加其力。

为了避免陷入局部最优，算法必须在开始时使用探索。随着迭代的推移，探索逐渐减弱而利用逐渐增强。为了通过控制探索和利用来提高GSA的性能，只有$Kbest$Kbest个最优代理才能吸引其他代理。$Kbest$Kbest是时间的函数，初始值为$K0$K0，随时间减小。以这种方式，开始时，所有的代理都施加力，随着时间的推移，$Kbest$Kbest线性地减少，最后只有一个代理施加于其他代理。因此，等式(9)可以修改为：
$F_{i}^{d}(t)=\sum_{j \in Kbest, j \neq i} \operatorname{rand}_{j} F_{i j}^{d}(t)\tag{17}$Fid​(t)=j∈Kbest,j​=i∑​randj​Fijd​(t)(17)

其中$Kbest$Kbest为前$K$K个最优代理。

算法中的各个参数可以参考源代码中的设置，赶快关注公众号，后台回复"GSA或引力"吧。