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

文章目录

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

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

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

万有引力定律

万有引力，全称为"万有引力定律"(law of universal gravitation)，为物体间相互作用的一条定律，1687年为牛顿所发现。任何物体之间都有相互吸引力，这个力的大小与各个物体的质量成正比例，而与它们之间的距离的平方成反比。如果用M1M_1M1​、M2M_2M2​表示两个物体的质量，RRR表示它们间的距离，则物体间相互吸引力为

F=（GM1M2）/R²(1)F=（GM_1M_2）/R²\tag{1}F=（GM1​M2​）/R²(1)

GGG称为万有引力常数也可简称为引力常数。

牛顿第二定律说的是，当一个力FFF作用于一个粒子时，其加速度aaa仅取决于该力和其质量MMM：

a=F/M(2)a=F/M \tag{2}a=F/M(2)

此外，由于引力递减的影响，引力常数的实际值取决于宇宙的实际年龄，下面给出了引力常数随着年龄的递减方程：

G(t)=G(t0)×(t0t)β,β<1(3)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)

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

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

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

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

ai=FijMii(5)a_{i} =\frac{F_{i j}}{M_{i i}} \tag{5}ai​=Mii​Fij​​(5)

其中MajM_{a j}Maj​和MpiM_{pi}Mpi​分别表示粒子iii的主动引力质量和粒子jjj的被动引力质量。MiiM_{ii}Mii​为粒子iii的惯性质量。

GSA

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

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

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

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

下面，考虑一个具有NNN个代理（质量）的系统，第iii个代理的位置定义为：

Xi=(xi1,…,xid,…,xin)fori=1,2,…,N(6)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​)fori=1,2,…,N(6)

其中，xidx_{i}^{d}xid​表示第iii个代理在第ddd个维度上的位置。

在某一时刻ttt，将质量jjj作用于质量iii的力定义为：

Fijd(t)=G(t)Mpi(t)×Maj(t)Rij(t)+ε(xjd(t)−xid(t))(7)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)

其中，MajM_{a j}Maj​为代理jjj的主动引力质量，MpiM_{pi}Mpi​为代理iii的被动引力质量。G(t)G(t)G(t)为ttt时刻的引力常量。ε\varepsilonε为一很小的常量，Rij(t)R_{ij}(t)Rij​(t)为代理iii和jjj之间的欧式距离：

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

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

Fid(t)=∑j=1,j≠iNrand⁡jFijd(t)(9)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)

其中rand⁡j\operatorname{rand}_{j}randj​为[0,1][0,1][0,1]之间的随机数。

因此，根据运动定律，代理iii在时刻ttt，第ddd维上的加速度aid(t)a^d_i(t)aid​(t)为：

aid(t)=Fid(t)Mii(t)(10)a_{i}^{d}(t)=\frac{F_{i}^{d}(t)}{M_{i i}(t)} \tag{10}aid​(t)=Mii​(t)Fid​(t)​(10)

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

vid(t+1)=rand⁡i×vid(t)+aid(t)(11)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)

xid(t+1)=xid(t)+vid(t+1)(12)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)

其中rand⁡i\operatorname{rand}_{i}randi​为[0,1][0,1][0,1]内的均匀随机变量。

算法开始时先对引力常数GGG进行初始化，然后随着时间递减以控制搜索精度：

G(t)=G(G0,t)(13)G(t)=G(G_0,t)\tag{13}G(t)=G(G0​,t)(13)

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

Mai=Mpi=Mii=Mi,i=1,2,…,N(14)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)

mi(t)=fiti(t)−worst(t)best(t)−worst(t)(15)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)

Mi(t)=mi(t)∑j=1Nmj(t)(16)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的性能，只有KbestKbestKbest个最优代理才能吸引其他代理。KbestKbestKbest是时间的函数，初始值为K0K0K0，随时间减小。以这种方式，开始时，所有的代理都施加力，随着时间的推移，KbestKbestKbest线性地减少，最后只有一个代理施加于其他代理。因此，等式(9)可以修改为：

Fid(t)=∑j∈Kbest,j≠irand⁡jFijd(t)(17)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)

其中KbestKbestKbest为前KKK个最优代理。

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