本文采取0/1覆盖模型,具体描述请参考这里。
SOS算法模仿生物行为,最终形成“互利共生”、“偏利共生”和“寄生”3个进化阶段,引导个体逐渐进化。SOS算法的关键操作具体如下:
假设种群数目为 N N N,个体的搜索范围上限和下限分别为 U U U和 L L L,按下式随机生成 N N N个初始个体 X i X_i Xi: X i = L + rand ( 1 , D ) × ( U − L ) (1) X_i=L+\text{rand}(1,D)×(U-L)\tag{1} Xi=L+rand(1,D)×(U−L)(1)其中, X i X_i Xi表示种群中第 i i i( i = 1 , 2 , ⋯ , N i=1,2,\cdots,N i=1,2,⋯,N)个生物个体, rand \text{rand} rand表示 [ 0 , 1 ] [0,1] [0,1]之间的随机数, D D D表示所优化问题的维数。
对于种群中的每个个体
X
i
X_i
Xi,随机选择一个其他个体
X
j
(
i
,
j
∈
{
1
,
2
,
⋯
,
N
}
,
j
≠
i
)
X_j(i, j\in\{1,2,\cdots,N\},j≠i)
Xj(i,j∈{1,2,⋯,N},j=i)与其自身按照下式进行互利共生,生成2个新的个体:
{
X
i
new
=
X
i
+
rand
(
0
,
1
)
×
(
X
best
−
MV
×
BF
1
)
X
j
new
=
X
j
+
rand
(
0
,
1
)
×
(
X
best
−
MV
×
BF
2
)
(2)
\begin{dcases}X_{i\text{new}}=X_i+\text{rand}(0,1)×(X_{\text{best}}-\text{MV}×\text{BF}_1)\\X_{j\text{new}}=X_j+\text{rand}(0,1)×(X_{\text{best}}-\text{MV}×\text{BF}_2)\end{dcases}\tag{2}
{Xinew=Xi+rand(0,1)×(Xbest−MV×BF1)Xjnew=Xj+rand(0,1)×(Xbest−MV×BF2)(2)其中,
rand
(
0
,
1
)
\text{rand}(0,1)
rand(0,1)为
[
0
,
1
]
[0,1]
[0,1]之间的随机数;
X
best
X_{\text{best}}
Xbest为当前迭代次数下的最优个体;
MV
=
(
X
i
+
X
j
)
/
2
\text{MV}=(X_i+X_j)/2
MV=(Xi+Xj)/2为“互利向量”,代表生物体之间的关系特征;
BF
1
\text{BF}_1
BF1、
BF
2
\text{BF}_2
BF2为获益因子,随机选择1或2。
经式(2)产生新的个体
X
i
new
X_{i_\text{new}}
Xinew和
X
j
new
X_{j_\text{new}}
Xjnew,通过与
X
i
X_i
Xi和
X
j
X_j
Xj进行适应度值的比较,最终保留
X
i
new
X_{i_\text{new}}
Xinew与
X
i
X_i
Xi、
X
j
new
X_{j_\text{new}}
Xjnew与
X
j
X_j
Xj中的较优个体,替换
X
i
X_i
Xi和
X
j
X_j
Xj。
种群中的个体
X
i
X_i
Xi按照下式进行“偏利共生”策略:
X
i
new
=
X
i
+
rand
(
−
1
,
1
)
×
(
X
best
−
X
j
)
(3)
X_{i\text{new}}=X_i+\text{rand}(-1,1)×(X_{\text{best}}-X_j)\tag{3}
Xinew=Xi+rand(−1,1)×(Xbest−Xj)(3)其中,
X
j
X_j
Xj为种群中与
X
i
X_i
Xi不同的个体,即
i
,
j
∈
{
1
,
2
,
⋯
,
N
}
,
j
≠
i
i,j\in\{1,2,\cdots,N\},j≠i
i,j∈{1,2,⋯,N},j=i;
X
best
X_{\text{best}}
Xbest为当前种群中的最优个体;
rand
(
−
1
,
1
)
\text{rand}(-1,1)
rand(−1,1)为
[
−
1
,
1
]
[-1,1]
[−1,1]之间的随机数。通过式(3)新产生的个体
X
i
new
X_{i\text{new}}
Xinew经适应度值比较之后决定是否要替换
X
i
X_i
Xi。
由偏利共生的策略可见:与“互利共生”阶段类似,每个个体都从种群中随机选择一个其他个体与其自身相互作用;与之不同的是,二者相互作用仅使
X
i
X_i
Xi受益,对于
X
j
X_j
Xj自身的发展既无利益也无损害。
在定义域内产生一个或者多个随机数(不多于基因位位数),修改个体 X i X_i Xi相应的基因位,形成新个体 Parasite_Vector \text{Parasite\_Vector} Parasite_Vector(简称P_V),与随机选择的个体 X j ( i , j ∈ 1 , 2 , ⋅ ⋅ ⋅ , N , j ≠ i ) X_j(i, j∈ {1,2,· · ·, N}, j≠i) Xj(i,j∈1,2,⋅⋅⋅,N,j=i)(称为“宿主”)进行适应度值比较。若P_V的适应度值更优,则“宿主” X j X_j Xj将被P_V取代,否则 X j X_j Xj将被视为免疫个体被保留。
将SOS与FPA、WOA、MFO、SCA、GWO进行对比,以文献[1]中的F1、F2、F16、F17、F25、F26为例,种群规模设置为30,最大迭代次数设置为500,每个算法独立运算30次。结果显示如下:
函数:F1 FPA:最差值: 9.5109e-12,最优值:1.1937e-18,平均值:1.2781e-12,标准差:2.4481e-12 WOA:最差值: 0.76207,最优值:2.3163e-13,平均值:0.076207,标准差:0.23253 MFO:最差值: 1.6904e-08,最优值:0,平均值:5.6347e-10,标准差:3.0863e-09 SCA:最差值: 0.0029332,最优值:1.1219e-05,平均值:0.00034985,标准差:0.0005416 GWO:最差值: 0.76207,最优值:3.8961e-09,平均值:0.025402,标准差:0.13913 SOS:最差值: 0,最优值:0,平均值:0,标准差:0 函数:F2 FPA:最差值: -1,最优值:-1,平均值:-1,标准差:4.0834e-09 WOA:最差值: -1,最优值:-1,平均值:-1,标准差:6.8516e-07 MFO:最差值: -1,最优值:-1,平均值:-1,标准差:0 SCA:最差值: -0.99207,最优值:-0.99989,平均值:-0.9979,标准差:0.0020357 GWO:最差值: -1,最优值:-1,平均值:-1,标准差:8.2047e-07 SOS:最差值: -1,最优值:-1,平均值:-1,标准差:0 函数:F16 FPA:最差值: 0.4289,最优值:0.087323,平均值:0.20346,标准差:0.075546 WOA:最差值: 0.15936,最优值:0.024134,平均值:0.061615,标准差:0.037101 MFO:最差值: 42.6906,最优值:0.001229,平均值:7.4352,标准差:13.1045 SCA:最差值: 6.976,最优值:3.7828,平均值:4.8192,标准差:0.61568 GWO:最差值: 1.2637,最优值:6.5089e-05,平均值:0.62033,标准差:0.30985 SOS:最差值: 5.5871e-23,最优值:1.1133e-26,平均值:6.7267e-24,标准差:1.3362e-23 函数:F17 FPA:最差值: 130.5562,最优值:37.1901,平均值:68.9236,标准差:24.3054 WOA:最差值: 5.9377e-70,最优值:2.1857e-89,平均值:1.9822e-71,标准差:1.084e-70 MFO:最差值: 10001.9982,最优值:0.66141,平均值:2006.8331,标准差:4065.0722 SCA:最差值: 68.3455,最优值:0.0017531,平均值:10.2897,标准差:17.2873 GWO:最差值: 1.278e-26,最优值:3.4061e-29,平均值:2.0882e-27,标准差:3.1648e-27 SOS:最差值: 1.0245e-133,最优值:5.2837e-139,平均值:4.0699e-135,标准差:1.8616e-134 函数:F25 FPA:最差值: 2.3744,最优值:1.3128,平均值:1.6881,标准差:0.24307 WOA:最差值: 0,最优值:0,平均值:0,标准差:0 MFO:最差值: 90.8951,最优值:0.3891,平均值:16.0292,标准差:33.9355 SCA:最差值: 1.473,最优值:0.17989,平均值:0.91643,标准差:0.34017 GWO:最差值: 0.042361,最优值:0,平均值:0.0051044,标准差:0.009838 SOS:最差值: 0,最优值:0,平均值:0,标准差:0 函数:F26 FPA:最差值: 16.5721,最优值:6.0727,平均值:10.7366,标准差:3.0996 WOA:最差值: 7.9936e-15,最优值:8.8818e-16,平均值:4.5593e-15,标准差:1.9755e-15 MFO:最差值: 19.9631,最优值:1.9986,平均值:15.8598,标准差:5.9102 SCA:最差值: 20.3871,最优值:0.022724,平均值:12.4272,标准差:9.5256 GWO:最差值: 1.4655e-13,最优值:7.5495e-14,平均值:1.0617e-13,标准差:2.2479e-14 SOS:最差值: 4.4409e-15,最优值:8.8818e-16,平均值:3.8488e-15,标准差:1.3467e-15
实验结果表明,SOS算法精度更佳,收敛速度优势明显。
设监测区域为
50
m
×
50
m
50 m×50 m
50m×50m的二维平面,传感器节点个数
N
=
35
N=35
N=35,其感知半径是
R
s
=
5
m
R_s=5m
Rs=5m,通信半径
R
c
=
10
m
R_c=10m
Rc=10m,迭代500次。初始部署、SOS优化覆盖、SOS算法覆盖率进化曲线如下图所示。
初始部署和最终部署的节点位置及对应的覆盖率分别为:
初始位置: 32.6545 32.446 41.2426 45.945 13.0846 49.5728 29.2021 43.8733 48.0295 3.955 47.3663 37.7734 1.3201 16.5851 19.2888 18.9047 12.7334 26.0067 22.0335 31.4901 23.0718 7.1101 47.1069 20.9824 37.1141 18.8479 9.1479 36.7856 14.2348 8.1498 13.6283 15.9827 41.5419 35.7073 40.6812 44.231 26.2897 40.0419 4.9575 40.1513 34.5246 27.7789 29.3381 33.8751 32.179 6.9931 9.0222 42.9654 17.4824 23.1989 4.3904 33.918 14.0562 35.1384 49.8881 42.8776 22.4286 23.2057 18.4397 44.4531 39.7413 45.4298 19 34.206 44.524 32.9813 6.6118 27.7741 43.4236 16.3376 初始覆盖率:0.69512 最优位置: 15.7466 29.0815 10.9187 41.3071 47.0841 19.2871 35.9243 39.494 36.3785 25.5118 46.3233 4.6537 28.624 12.7572 35.1543 9.1547 20.18 19.4115 4.5097 2.912 4.2651 46.435 46.7193 27.6348 26.4977 4.1642 18.8016 45.9033 38.8681 32.5106 9.3462 31.4209 3.2417 36.6712 25.3966 48.3782 34.4429 47.0442 43.9273 13.483 45.667 45.6503 18.5576 36.9728 21.9133 28.5272 3.554 23.739 23.2557 13.3457 17.6117 1.143 37.6181 3.3859 29.5581 22.2684 10.7122 20.5166 16.3281 13.6298 37.6176 17.8293 6.3979 11.3552 46.7737 36.7952 29.6526 32.3906 26.8222 40.7059 最优覆盖率:0.89773
实验结果表明,SOS能够有效提升传感器节点的覆盖率,使得节点分布更加均匀。
[1] Min-Yuan Cheng, Doddy Prayogo. Symbiotic Organisms Search: A new metaheuristic optimization algorithm[J]. Computers and Structures, 2014, 139(jul.): 98-112.
[2] 王艳娇, 马壮. 基于子种群拉伸操作的精英共生生物搜索算法. 控制与决策, 2019, 34(7): 1355-1364.