文章目录

一、理论基础1、流向算法2、FDA算法流程图二、WSN覆盖优化仿真1、二维覆盖优化2、三维覆盖优化三、参考文献

一、理论基础

1、流向算法

流向算法(Flow Direction Algorithm, FDA)模拟了流向排水池中具有最低高度的出口点的水流方向，是一种基于物理的优化算法。

FDA算法在将降雨转化为径流后，确定流域中的流向。该算法首先在搜索空间中创建初始种群。然后，气流流向海拔较低的位置，以达到最佳答案或最低海拔出口点。

该算法基于以下假设执行：

每个流都有一个位置和一个高度。每个流周围都有β\betaβ位置，每个位置都有一个高度或目标函数。水流运动速度与坡度直接相关。水流速度为VVV，流向海拔最低的方向。流域出口点是具有最优目标函数的水流位置。

该算法的初始参数包括种群数量α\alphaα、邻域数量β\betaβ和邻域半径Δ\DeltaΔ。关于FDA算法，流的初始位置通过以下关系计算：Flow_X(i)=lb+rand∗(ub−lb)(1)Flow\_X(i)=lb+rand^*(ub-lb)\tag{1}Flow_X(i)=lb+rand∗(ub−lb)(1)其中，Flow_X(i)Flow\_X(i)Flow_X(i)表示第iii个流的位置，lblblb和ububub分别表示决策变量的下限和上限，randrandrand表示0和1之间均匀分布的随机值。还假设每个流周围都存在βββ邻域，其位置由以下式子产生：Neighbor_X(j)=Flow_X(i)+randn∗Δ(2)Neighbor\_X(j) = Flow\_X(i)+randn^*\Delta\tag{2}Neighbor_X(j)=Flow_X(i)+randn∗Δ(2)其中，Neighbor_X(j)Neighbor\_X(j)Neighbor_X(j)表示第jjj个邻居的位置；randnrandnrandn表示标准正态分布随机数；小数值Δ\DeltaΔ在小范围内搜索，大数值Δ\DeltaΔ允许在大范围内搜索该参数。事实上，在大范围内搜索会产生更多种类的解，并增加找到接近最优解的概率(全局搜索)。当算法的解接近全局最优解时，在小范围内搜索可获得更高精度的全局最优解(局部搜索)，突出了在这两种能力之间建立平衡。其原因是，仅实现全局搜索算子会导致算法无法以所需的精度找到全局最优解。 另一方面，只进行局部搜索会导致算法陷入局部最优。因此，为了在全局搜索和局部搜索之间建立平衡，本研究使用以下公式，将Δ\DeltaΔ从较大值线性减少到较小值。因此，Δ\DeltaΔ方向朝向随机位置，以获得更多的多样性。Δ=(rand∗Xrand−rand∗Flow_X(i))∗∣∣Best_X−Flow_X(i)∣∣∗W(3)\Delta=(rand^*Xrand-rand^*Flow\_X(i))^*||Best\_X-Flow\_X(i)||^*W\tag{3}Δ=(rand∗Xrand−rand∗Flow_X(i))∗∣∣Best_X−Flow_X(i)∣∣∗W(3)其中，randrandrand是均匀分布的随机数，XrandXrandXrand是由式(1)生成的随机位置，WWW是随机数在0和inf之间的非线性权重。在上式中，第一项表示Flow_X(i)Flow\_X(i)Flow_X(i)移动到随机位置(XrandXrandXrand)，对于第二项，通过增加迭代，Flow_X(i)Flow\_X(i)Flow_X(i)接近Best_XBest\_XBest_X，并且Best_XBest\_XBest_X和Flow_X(i)Flow\_X(i)Flow_X(i)之间的欧几里得距离减小为零。因此，局部搜索已停止。第三项中的WWW计算如下：W=((1−iterMax_Iter)(2∗randn))∗(rand‾∗iterMax_Iter)(4)W=\left(\left(1-\frac{iter}{Max\_Iter}\right)^{(2^*randn)}\right)*\left(\overline{rand}^*\frac{iter}{Max\_Iter}\right)\tag{4}W=((1−Max_Iteriter​)(2∗randn))∗(rand∗Max_Iteriter​)(4)其中，randrandrand是均匀分布的随机向量。图1显示了通过增加迭代得到的WWW的变化图。很明显，WWW在迭代过程中有很大的变化，能够使得FDA算法跳出局部最优。

图1 WWW的变化

如前所述，流以VVV的速度向目标函数最小的邻居移动。另一方面，流向邻近地区的流速与坡度直接相关。因此，以下关系式用于确定流速矢量：V=randn∗S0(5)V=randn^*S_0\tag{5}V=randn∗S0​(5)其中，S0S_0S0​表示相邻位置和流的当前位置之间的斜率向量，随机数randnrandnrandn生成各种解决方案并增加全局搜索。第iii个流相对于其第jjj个邻居流的斜率向量由以下关系式确定：S0(i,j,d)=Flow_fitness(i)−Neighbor_fitness(j)∣∣Flow_x(i,d)−Neighbor_x(j,d)∣∣(6)S_0(i,j,d)=\frac{Flow\_fitness(i)-Neighbor\_fitness(j)}{||Flow\_x(i,d)-Neighbor\_x(j,d)||}\tag{6}S0​(i,j,d)=∣∣Flow_x(i,d)−Neighbor_x(j,d)∣∣Flow_fitness(i)−Neighbor_fitness(j)​(6)其中，Flow_fitness(i)Flow\_fitness(i)Flow_fitness(i)和Neighbor_fitness(j)Neighbor\_fitness(j)Neighbor_fitness(j)分别表示流iii和邻居jjj的目标值，ddd参数表示问题的维度。以下式子用于确定流的新位置：Flow_newX(i)=flow_X(i)+V∗Flow_X(i)−Neighbor_X(j)∣∣Flow_x(i)−Neighbor_x(j)∣∣(7)Flow\_newX(i)=flow\_X(i)+V^*\frac{Flow\_X(i)-Neighbor\_X(j)}{||Flow\_x(i)-Neighbor\_x(j)||}\tag{7}Flow_newX(i)=flow_X(i)+V∗∣∣Flow_x(i)−Neighbor_x(j)∣∣Flow_X(i)−Neighbor_X(j)​(7)其中Flow_newX(i)Flow\_newX(i)Flow_newX(i)表示流iii的新位置。

这里值得注意的是，任何邻居的目标函数都可能不小于流的目标函数，这类似于确定流向的水槽填充过程。为了模拟这种状态，FDA方法随机选择另一个流，如果该水流的目标函数小于当前水流的目标函数，则该水流将沿同一方向移动，否则，该水流将沿主导坡度方向移动。下式说明了如何在这些条件下模拟流向：Flow_newX(i)={Flow_X(i)+randn‾∗(Flow_X(r)−Flow_X(i))Flow_fitness(r)<Flow_fitness(i)Flow_X(i)+2randn∗(Best_X(r)−Flow_X(i))Flow_fitness(r)<Flow_fitness(i)(8)Flow\_newX(i)=\begin{dcases}Flow\_X(i)+\overline{randn}^*(Flow\_X(r)-Flow\_X(i))\quad\,\, Flow\_fitness(r)<Flow\_fitness(i)\\[2ex]Flow\_X(i)+2randn^*(Best\_X(r)-Flow\_X(i))\quad Flow\_fitness(r)<Flow\_fitness(i)\end{dcases}\tag{8}Flow_newX(i)=⎩⎨⎧​Flow_X(i)+randn∗(Flow_X(r)−Flow_X(i))Flow_fitness(r)<Flow_fitness(i)Flow_X(i)+2randn∗(Best_X(r)−Flow_X(i))Flow_fitness(r)<Flow_fitness(i)​(8)其中randn‾\overline{randn}randn为一个随机整数。

2、FDA算法流程图

FDA算法流程图如图2所示。

图2 FDA算法流程图

二、WSN覆盖优化仿真

1、二维覆盖优化

本文采用0/1模型，节点覆盖模型请参考这里。设监测区域为50m×50m50m×50m50m×50m的二维平面，传感器节点个数N=35N=35N=35，其感知半径是Rs​​=5mR_s​​=5mRs​​​=5m，通信半径Rc​​=10mR_c​​=10mRc​​​=10m，迭代500次。初始部署、FDA优化覆盖、FDA算法覆盖率进化曲线如下图所示：

初始部署和最终部署的节点位置及对应的覆盖率分别为：

初始位置：45.13544.65870.6362124.14940.471344.585115.571129.25415.192942.022943.340514.34180.5779332.034421.87463.060931.839912.975745.97755.90479.186217.614118.553144.766925.190441.810445.850723.68637.689516.539413.77737.433126.077433.537825.509316.07774.22063.54014.130234.71628.811513.007540.776623.953632.732236.854542.241348.011935.48235.86876.57667.137146.888939.24733.984625.312344.709431.839741.10270.4544715.988833.35475.556325.661441.753337.745230.382215.926710.47041.4335初始覆盖率：0.70396最优位置：45.419243.28252.397815.744236.102245.235316.296627.4646.46945.958445.81214.43830.729731.066120.13243.646920.335914.68746.61555.611311.627319.811716.838946.817426.499745.822948.02623.048338.091612.471214.614534.260424.365532.575724.683322.56624.25464.66445.670237.402526.31229.531941.3323.294331.899837.381843.746548.9533.31534.333611.617212.716547.537437.399933.426624.76446.941230.638840.70321.217916.086339.28237.879527.539640.24334.404231.728717.44110.63043.3714最优覆盖率：0.8812

实验结果表明，FDA算法能够提升二维无线传感器网络中节点的覆盖率。

2、三维覆盖优化

节点覆盖模型请参考这里。设监测区域为50m×50m×50m50m×50m×50m50m×50m×50m的三维空间，传感器节点个数N=30N=30N=30，其感知半径是Rs=10mR_s=10mRs​=10m，通信半径Rc=20mR_c=20mRc​=20m，迭代500次。初始部署、FDA优化覆盖、FDA算法覆盖率进化曲线如下图所示：

初始部署和最终部署的节点位置及对应的覆盖率分别为：

初始位置：38.915831.091849.61154.28695.861525.40721.285312.380521.904622.92544.046629.693640.687930.816617.08579.190233.047424.17681.005539.755836.951830.079545.633513.008935.293720.264242.05778.432618.138348.439643.199328.10734.907416.489142.711734.515547.173840.973619.39980.1554244.119914.65952.027634.88964.640432.795314.577713.835736.154537.175445.058344.89930.8667611.73056.049512.238136.940417.19127.44083.443942.143626.568816.210428.150833.609141.018124.327613.473525.02835.26938.241125.669747.346416.92630.90079.79980.106826.40417.92269.03175.328732.973446.080812.887330.801536.076120.63511.766821.984410.022初始覆盖率：0.58725最优位置：38.415220.049343.45119.629411.004522.594925.665.643321.745521.03636.494840.611943.253334.62613.14549.28827.697225.42436.277834.542541.970624.36241.82886.618938.35275.796741.472610.289818.227842.578146.632231.42.026219.100343.486835.341644.522642.759827.89169.279442.75920.35545.336638.32357.670431.414819.660616.724737.747143.112142.686641.666.87368.48173.44346.490235.881421.302327.80657.640239.93122.62514.430923.439830.30741.915325.438519.15832.048242.56238.112625.811943.640724.196527.67295.75295.68398.499322.87849.48416.124330.481345.78920.795327.643233.187424.11866.998720.55358.2148最优覆盖率：0.78214

实验结果表明，FDA算法能够提升三维无线传感器网络中节点的覆盖率。

代码下载链接：/download/weixin_43821559/85424729

三、参考文献

[1] Hojat Karami, Mahdi Valikhan Anaraki, Saeed Farzin, et al. Flow Direction Algorithm (FDA): A Novel Optimization Approach for Solving Optimization Problems[J]. Computers & Industrial Engineering, , 156: 107224.