目录
- 1.背景
- 2.算法原理
- 2.1算法思想
- 2.2算法过程
- 3.结果展示
- 4.参考文献
1.背景
2019年,Zhao等人受到原子运动规律启发,提出了原子搜索算法(Atom Search Algorithm,ASO)。
2.算法原理
2.1算法思想
ASO根据分子动力学中原子的物理运动规律建立,通过种群中各个原子之间的相互作用力来指导群体进行智能优化搜索。
2.2算法过程
根据牛顿第二定律,如果Fi是作用在第i个原子上的相互作用力,而Gi是作用
在第i个原子上的约束力,该原子的质量为mi,那么第i个原子的加速度为:
a
i
=
F
i
+
G
i
m
i
(1)
a_i=\frac{F_i+G_i}{m_i}\tag{1}
ai=miFi+Gi(1)
相互作用力Fi:
相互作用力 Fi表示周围原子对当前原子 i 的作用力之和:
F
i
d
(
t
)
=
∑
j
∈
K
b
e
s
t
r
a
n
d
j
F
i
j
d
(
t
)
(2)
F_{i}^{d}\left(t\right)=\sum_{j\in K_{\mathrm{best}}}rand_{j}F_{ij}^{d}\left(t\right)\tag{2}
Fid(t)=j∈Kbest∑randjFijd(t)(2)
其中,d为原子所在的维数。Kbest为对原子i产生作用力的原子的集合;Fijd(t)为第t次迭代中第j个原子对原子i的伦纳德·琼斯(L-J)势作用力:
K
b
e
s
t
(
t
)
=
N
−
(
N
−
2
)
⋅
t
T
(3)
K_{\mathrm{best}}(t)=N-(N-2)\cdot\sqrt{\frac{t}{T}}\tag{3}
Kbest(t)=N−(N−2)⋅Tt(3)
Fijd(t)定义为:
F
i
j
d
(
t
)
=
−
η
(
t
)
[
2
(
h
i
j
(
t
)
)
13
−
(
h
i
j
(
t
)
)
7
]
(4)
F_{ij}^d(t)=-\eta\left(t\right)\left[2\bigl(h_{ij}(t)\bigr)^{13}-\bigl(h_{ij}(t)\bigr)^{7}\right]\tag{4}
Fijd(t)=−η(t)[2(hij(t))13−(hij(t))7](4)
η(t)为用于调整排斥区域或吸引区域的深度函数:
η
(
t
)
=
−
α
(
1
−
t
−
1
T
)
3
e
−
20
t
T
(5)
\eta\left(t\right)=-\alpha\left(1-\frac{t-1}{T}\right)^3\mathrm{e}^{-\frac{20t}{T}}\tag{5}
η(t)=−α(1−Tt−1)3e−T20t(5)
hij标准定义为:
h
i
j
=
r
i
j
(
t
)
σ
(
t
)
(6)
h_{ij}=\frac{r_{ij}(t)}{\sigma(t)}\tag{6}
hij=σ(t)rij(t)(6)
σ为长度尺度,表示碰撞直径;rij为2个原子之间的欧几里得距离:
r
i
j
(
t
)
=
∥
x
i
(
t
)
,
x
j
(
t
)
∥
2
σ
(
t
)
=
∥
x
i
(
t
)
,
∑
j
∈
K
b
e
s
t
(
t
)
x
j
(
t
)
K
b
e
s
t
(
t
)
∥
2
(7)
\begin{aligned}&r_{ij}(t)=\left\|x_{i}(t),x_{j}(t)\right\|_{2}\\&\sigma(t)=\left\|x_{i}(t),\frac{\sum_{j\in K_{\mathrm{best}}(t)}x_{j}(t)}{K_{\mathrm{best}}(t)}\right\|_{2}\end{aligned}\tag{7}
rij(t)=∥xi(t),xj(t)∥2σ(t)=
xi(t),Kbest(t)∑j∈Kbest(t)xj(t)
2(7)
为了改善勘探范围,论文中将表现为斥力的 h 的下限设置为 hmin=1.1,上限设置为 hmax=2.4,并且在hmin的基础上增加了一个正弦扰动函数g(t):
h
i
j
(
t
)
=
{
h
min
+
g
(
t
)
r
i
j
(
t
)
σ
(
t
)
<
h
min
r
i
j
(
t
)
σ
(
t
)
h
min
⩽
r
i
j
(
t
)
σ
(
t
)
⩽
h
max
h
max
r
i
j
(
t
)
σ
(
t
)
>
h
max
(8)
h_{ij}\left(t\right)=\begin{cases}h_{\min}+g(t)&\frac{r_{ij(t)}}{\sigma(t)}<h_{\min}\\\\\frac{r_{ij(t)}}{\sigma(t)}&h_{\min}\leqslant\frac{r_{ij(t)}}{\sigma(t)}\leqslant h_{\max}\\\\h_{\max}&\frac{r_{ij(t)}}{\sigma(t)}>h_{\max}\end{cases}\tag{8}
hij(t)=⎩
⎨
⎧hmin+g(t)σ(t)rij(t)hmaxσ(t)rij(t)<hminhmin⩽σ(t)rij(t)⩽hmaxσ(t)rij(t)>hmax(8)
g(t)定义为:
g
(
t
)
=
0.1
sin
(
π
2
⋅
t
T
)
(9)
g(t)=0.1\sin\left(\frac{\pi}{2} \cdot \frac{t}{T}\right)\tag{9}
g(t)=0.1sin(2π⋅Tt)(9)
共价键约束力Gi:
为了突出种群最佳原子的引导作用,假设每个原子与种群最佳原子具有一个共价键,因此每个原子都要受到最佳原子的约束力作用:
G i d = β e − 20 t T ( x b e s t d ( t ) − x i d ( t ) ) (10) G_i^d=\beta\mathrm{e}^{\frac{-20t}{T}}\Big( x_{\mathrm{best}}^d( t ) -x_i^d( t ) \Big)\tag{10} Gid=βeT−20t(xbestd(t)−xid(t))(10)
原子加速度ai:
结合相互作用力和几何约束力,在时间t的第i个原子在第d维上的加速度:
a
i
d
=
F
i
d
+
G
i
d
m
i
(
t
)
=
−
α
(
1
−
t
−
1
T
)
3
e
−
20
t
T
∑
j
∈
K
b
e
s
t
r
a
n
d
j
[
2
(
h
i
j
(
t
)
)
13
−
(
h
i
j
(
t
)
)
7
]
m
i
(
t
)
+
β
e
−
20
t
T
(
x
b
e
s
t
d
(
t
)
–
x
i
d
(
t
)
)
m
i
(11)
\begin{aligned} a_i^d= \frac{F_i^d+G_i^d}{m_i(t)}= -\alpha\left(1-\frac{t-1}T\right)^3\mathrm{e}^{-\frac{20t}T}\sum_{j\in K_{\mathrm{best}}}\frac{rand_j\left[2\left(h_{ij}\left(t\right)\right)^{13}-\left(h_{ij}\left(t\right)\right)^7\right]}{m_i\left(t\right)}+ \beta\mathrm{e}^{-\frac{20t}T}\frac{\left(x_{\mathrm{best}}^d(t)–x_i^d(t)\right)}{m_i} \end{aligned}\tag{11}
aid=mi(t)Fid+Gid=−α(1−Tt−1)3e−T20tj∈Kbest∑mi(t)randj[2(hij(t))13−(hij(t))7]+βe−T20tmi(xbestd(t)–xid(t))(11)
第t次迭代中第i个原子的质量mi(t)由当前种群个体的适应度值大小决定:
M
i
(
t
)
=
e
−
f
i
(
t
)
−
f
min
(
t
)
f
max
(
t
)
−
f
min
(
t
)
m
i
(
t
)
=
M
i
(
t
)
∑
j
=
1
N
M
i
(
t
)
(12)
M_{i}(t)=\mathrm{e}^{-\frac{f_{i}(t)-f_{\min}(t)}{f_{\max}(t)-f_{\min}(t)}}\\m_{i}(t)=\frac{M_{i}(t)}{\sum_{j=1}^{N}M_{i}(t)}\tag{12}
Mi(t)=e−fmax(t)−fmin(t)fi(t)−fmin(t)mi(t)=∑j=1NMi(t)Mi(t)(12)
其中,fmax(t)和fmin(t)分别表示原子种群中最大适应度值和最小适应度值。
位置更新:
更新公式:
ν
i
d
(
t
+
1
)
=
r
a
n
d
i
d
ν
i
d
(
t
)
+
a
i
d
(
t
)
x
i
d
(
t
+
1
)
=
x
i
d
(
t
)
+
ν
i
d
(
t
+
1
)
(13)
\begin{aligned}&\nu_{i}^{d}\left(t+1\right)=rand_{i}^{d}\nu_{i}^{d}\left(t\right)+a_{i}^{d}\left(t\right)\\&x_{i}^{d}\left(t+1\right)=x_{i}^{d}\left(t\right)+\nu_{i}^{d}\left(t+1\right)\end{aligned}\tag{13}
νid(t+1)=randidνid(t)+aid(t)xid(t+1)=xid(t)+νid(t+1)(13)
伪代码:
3.结果展示
4.参考文献
[1] Zhao W, Wang L, Zhang Z. A novel atom search optimization for dispersion coefficient estimation in groundwater[J]. Future Generation Computer Systems, 2019, 91: 601-610.