智能优化算法：引力搜索算法

智能优化算法：引力搜索算法-附代码

@[toc]
摘要：万有引力搜索算法 (gravitational searchalgorithm，GSA) 由伊朗的 Esmat Rashedi 教授等人提出，该算法是基于牛顿万有引力定律的一种元启发式智能优化算法，能够用于解决优化问题。

1.算法原理

引力搜索算法利用物体间的万有引力定律搜索最优解，全局优化能力突出。设 $n$ 维空间引力系统中有 $N$ 个粒子，定义第 $i$ 个粒子位置为 $X_i={x_i^1,...,x_i^d,...,x_i^n},(i=1,2,...,N)$ 。其中: $x^d_i$ 为第 $i$ 个粒子在第 $d$ 维中位置。GSA 算法流程见图 1。

图1 算法流程图

粒子 $i$ 在 $t$ 时刻质量 $M_i (t)$ 为:
$m_i(t)=\frac{fit_i(t)-worst(t)}{best(t)-worst(t)}\tag{1}$

$M_i(t)=\frac{m_i(t)}{\sum_{j=1}^Nm_j(t)}\tag{2}$

式中: $fit_i(t)$ 为在 $t$ 时刻粒子 $i$ 的适应度函数值。

如求解适应度函数极小值，则
$best(t) = min\,fit_j(t)\tag{3}$

$worst(t) = max\,fit_j(t)\tag{4}$

在第 $d$ 维空间上，第 $i$ 个粒子受第 $j$ 个粒子作用力为:
$F_{ij}^d(t) = G(t)\frac{M_i(t)M_j(t)}{||X_i(t),X_j(t)||_2+\varepsilon}[x_j^d(t)-x_i^d(t)]\tag{7}$
式中: $\varepsilon$ 为接近 0 的常量; $G(t)$ 为 $t$ 时刻引力常数。
$G(t) = G_0e^{-at/T}\tag{8}$
式中: $G_0 =100;a =20$ ; $T$ 为迭代次数。

在第 $d$ 维空间上，第 $i$ 个粒子受其它粒子引力合力作用，用各粒子引力的随机加权和表示，即:
$F_i^d(t)=\sum_{j=1,j\neq i}^N randF_{ij}^d(t)\tag{9}$
式中: $rand$ 为范围在［0，1］间任意数。

基于牛顿第二定理，在第 $d$ 维空间上粒子 $i$ 在引力合力作用下加速度为:
$a_i^d(t) = F_i^d(t)/M_i(t)\tag{10}$
在 $GSA$ 中，粒子 $i$ 更新在第 $d$ 维空间位置 $x^d_i (t)$ 及速度 $v^d_i (t)$ 以实现迭代过程，速度及位置更新式为:
$v_i^d(t+1)=randv_i^d(t)+a_i^d(t)\tag{11}$