IBGSA 改进的二进制引力搜索算法

作者: 天生诗言 | 来源:发表于2019-03-27 11:57 被阅读0次

IBGSA 改进的二进制引力搜索算法
具体算法7 - A*启发式搜索
2019-05-30（让搜索过程具有一定的爬山能力）
谷歌更新March 2019 Core Update算法
算法-二分搜索算法
数据结构与算法--BFS&DFS
DFS（深度优先搜索）和BFS(广度优先搜索)
广度优先搜索算法(BFS)
深度优先搜索算法(DFS)
003——继续

IBGSA：improved binary gravitational search algorithm

改进的引力搜索算法

GSA

原始算法GSA^[1]（引力搜索算法）在2009年被首次提出，是一种基于万有引力定律和牛顿第二定律的种群优化算法。

该算法通过种群的粒子位置移动来寻找最优解，即随着算法的循环，粒子靠它们之间的万有引力（两个粒子之间的引力与两个粒子的质量成正比，与两粒子之间的距离成反比）在搜索空间内不断运动，当粒子移动到最优位置（形成最大质量）时，最优解便找到了。

初始化各个参数和种群位置
计算适应度值
计算粒子的惯性质量、每个粒子的在每个方向的引力、加速度
更新每个粒子的位置及适应度值和全局最优值
达到终止条件就结束，输出最优解，否则就返回步骤3进入下一轮迭代

BGSA

提出了BGSA^[2]算法来解决二值问题。在BGSA算法中，每个agent (particle)都有四个参数:位置、被动引力质量、主动引力质量和惯性质量。惯性质量和引力质量由适应度函数计算，而质量位置表示问题的解。在算法的连续迭代过程中，对引力和惯性质量进行了概率调整。BGSA算法的数学解释如下:假设存在一个含有N个agent(粒子)的系统，其中第i个agent的位置为:

$X_i=(x_i^1,x_i^2,...,x_i^d,...,x_i^n),\quad \forall i = 1,2,3,...,n \tag1$

其中n为空间维数， $x_i^d$ 为第i个agent在第d维数中的位置。每个位置 $x_i^d$ 只取二进制值(1或0)，第i个agent在t时刻的质量更新如下:

$M_i(t)=\frac{m_i(t)}{\sum_{k=1}^Nm_k(t)},\quad\forall i=1,2,…,N \tag2$

其中

$m_k(t)=\frac{fit_k(t)-worst(t)}{best(t)-worst(t)} \tag3$

其中 $fit_k(t)$ 是 agent k 在 t 时刻的适应度值，对于最大化问题，分别给出了 $best(t)$ 和 $worst(t)$ 。

$bset(t)=\max \limits_{k\in\{1,2,..,N\}}fit_k(t) \tag4$

$worst(t)=\min \limits_{k\in\{1,2,..,N\}}fit_k(t) \tag5$

第 d 维第 i 个 agent 在第 t 时刻作用的总力 F 计算方法为:

$F_i^d(t)=\sum\limits_{j \in kbset,j \neq i} \gamma_j\ G(t) \frac{M_i(t)×M_j(t)}{R_{ij}(t)+\epsilon} (x_j^d(t)-x_i^d(t)) \tag6$

$R_{ij} (t)$ 为第i个agent到第j个agent在t时刻的汉明距离：

$R_{ij}(t)=\sum\limits_{d=1}^n\ |\ x_j^d(t)-x_i^d(t)\ | \tag7$

$G(t)$ 的值是重力常数G0的初值与时间t的函数:

$G(t)=G_0(1-\frac t T)\tag8$

$a$ 的值是加速度:

$a_i^d(t)=\frac{F_i^d(t)}{M_{ii}(t)}\tag9$

为了利用 BGSA 算法求解优化问题，在每次迭代t中更新每个agent的位置和速度。agent的速度限制为 $| v(t) |< 6$ 。
则下一刻的速度是：

$v_i^d(t+1)=\gamma_i^d×v_i^d(t)+a_i^d(t)\tag{10}$

第i个agent的新位置 $x(t +1)$ 如式(11)所示。 $γ$ 是一个在0和1之间选取的随机值：

$x_i^d(t+1)= \begin{cases} \overline{x_i^d(t)} & \gamma < f(v_i^d(t+1)) \\ x_i^d(t) & otherwise \end{cases} \tag{11}$

其中，
$f(v_i^d(t+1))=|\tan h(v_i^d(t+1))|\tag{12}$

BGSA 的停滞现象

停滞是一种agent降到局部最小值的情况。当某一刻的速度为零时就会发生这种情况。IBGSA的目标便是为了减轻停滞效应。

IBGSA 中的改进

改变公式(12)中的函数，
把公式(7)中的汉明距离 $R_{ij}(t)$ 除以空间维n来将其归一化，
采用精英主义策略，当新agent的适应度值高于前一个agent时，更新agent的位置，否则agent将停留在原来的位置。式(12)中的函数修改如下：

$f(_i^d(t+1))=A+(1-A)×|\tanh(v_i^d(t+1))|\tag{13}$

这里面的 $A$ 由公式(14)得出：

$A=k_1(1-e^\frac{F_C}{K_2})\tag{14}$

agent 的新位置就成了：

$X_i(t+1)= \begin{cases} X_i(t+1) & fit(X_i(t+1))\geq fit(X_i(t))\\ X^i(t) & otherwise \end{cases} \tag{15}$

E. Rashedi, H. Nezamabadi-pour, and S. Saryazdi, “GSA: A Gravita-tional Search Algorithm,” Information Sciences, vol. 179, no. 13, pp. 2232–2248, 2009. ↩
E. Rashedi, H. Nezamabadi-pour, and S. Saryazdi, “BGSA: binary gravitational search algorithm,” Natural Computing, vol. 9, no. 3, pp. 727–745, 2009. ↩

IBGSA 改进的二进制引力搜索算法
IBGSA：improved binary gravitational search algorithm 改进的引...
具体算法7 - A*启发式搜索
A* 启发式搜索算法是对 Dijkstra 算法的改进版本，它和后者的主要差别在于，加入了到终点的距离量化，使得 ...
2019-05-30（让搜索过程具有一定的爬山能力）
前言为了解决模型局部最小问题，只能通过改进搜索算法解决，一种方法是让搜索过程具有爬山的能力，同时不会爬出全局最小...
谷歌更新March 2019 Core Update算法
谷歌在2019年3月12日发布了最新核心搜索算法更新通知，这次应该是多年来最大的一次更新，将会对整体算法改进。这...
算法-二分搜索算法
算法：二分搜索算法（折半查找算法）时间复杂度：二分搜索算法概述二分搜索算法伪代码二分搜索算法实现二分搜索算...
数据结构与算法--BFS&DFS
“搜索”算法深度优先搜索算法和广度优先搜索算法都是基于“图”这种数据结构。图上的搜索算法就是，在图中找出从一个...
DFS（深度优先搜索）和BFS(广度优先搜索)
深度优先搜索算法（Depth-First-Search）深度优先搜索算法（Depth-First-Search），...
广度优先搜索算法(BFS)
广度优先搜索算法(BFS) 标签（空格分隔）： algorithm 1.广度优先搜索算法(Breadth Firs...
深度优先搜索算法(DFS)
深度优先搜索算法(BFS) 标签（空格分隔）： algorithm 1.深度优先搜索算法(Breath Fisrt...
003——继续
输出几个$_SERVER的信息计算器改进进制进制转换 dec:十进制，bin:二进制，oct:八进制，hex...