扇区搜索机制的果蝇优化算法

摘要：针对传统果蝇算法 （FOA）搜索方向不均匀导致算法求解高维问题时收敛稳定性差和收敛精度低的问题，对果蝇算法的搜索机制进行研究，用扇区搜索机制替代传统搜索机制产生新型果蝇算法 (SS-FOA)。分析果蝇群搜索机制对果蝇飞行方向的影响，提出扇区搜索机制；提出再优化概念，将扇区搜索机制用于参考文献中优化算法再优化。

1.果蝇优化法

基础果蝇优化算法的具体原理参考，我的博客：https://blog.csdn.net/u011835903/article/details/108344654

2. 扇区搜索机制

2.1 扇区搜索机制分析及设计

为了避免因果蝇群搜索不均匀所导致果蝇飞行方向单一的问题，提出一种均匀的果蝇群搜索机制。首先将以种群坐标为中心，搜索步长为半径的虚拟圆划分成多个扇区。再使每个果蝇都沿着属于自己的扇区飞行，每个果蝇的飞行步长都为 ［ 0，L］的随机值，这样使果蝇飞向各个方向的概率相同。果蝇群只会向着味道浓度最大的方向前进，不会受到果蝇群分布不均匀的影响，从而提高算法的稳定性与收敛精度。给出果蝇群基于扇区搜索机制生成果蝇个体的具体步骤如下：

步骤1 根据种群规模Sizepop确定扇区角度，其中 t为扇区的角度间隔
$$t=0:\frac{2\pi }{\mathrm{Sizepop}-4}:2\pi \text{\hspace{1em}(2)}$$
步骤２以种群坐标为中心，在每个扇区随机生成果蝇个体，扇区的划分使用了正弦函数和余弦函数
$$\{\begin{array}{l}{X}_i=X\text{ axis }+L\sin (t)\times \text{ rand }()\\ Y_i=Y\text{ a axis }+L\cos (t)\times \mathrm{rand}()\end{array}\text{\hspace{1em}(3)}$$
改进后果蝇群分布如图所示，可以看出改进后的果蝇群分布在二维平面呈现出以种群坐标为原点的近圆状，圆的半径为搜索步长L ，每个果蝇与种群坐标间的距离为［0,L］的随机值，方向都各自独立且沿着各自的扇区方向飞行，保证了果蝇群选择每个飞行方向的概率相同，有效减少迭代步长的不稳定性。

同时，为了减少算法的无效迭代，设置在$\pi /4,3\pi /4,5\pi /4,7\pi /4$这 ４ 个特殊扇区方向上不再使用传统的随机步长，而使用定值步长。即在４个扇区方向上放置４只果蝇个体，其搜索步长固定为L ，这样设置可以使果蝇群在搜索气味源位置固定且较远的目标时，会以最快速度接近明显的目标。

2.2 再优化概念

扇区搜索机制改进了传统果蝇算法的搜索机制，但是对传统算法的步长及寻优方式不会产生影响。因此扇区搜索机制最重要的特征是可与已改进的果蝇优化方法结合，用于果蝇优化算法的再优化。使用扇区搜索机制替换传统搜索机制能在已改进果蝇算法的基础上达到更高的收敛精度和稳定性。

2.3 SS-FOA算法

将扇区搜索机制与传统果蝇算法结合，提出新型算法SS-FOA 算法，其具体实现步骤如下：
步骤1　 初始化算法参数：最大迭代次数 Maxgen，种群规模Sizepop，扇区角度 t ，初始化种群坐标[X_axis,Y_axis];

步骤2　 根据扇区搜索机制产生果蝇个体，其中R 为[0,L]的随机值，扇区角度间隔 t由式（2）推出
$$\{\begin{array}{l}{X}_i=X_{\_axis}+R\sin (t)\\ Y_i=Y_{\_axis}+R\cos (t)\end{array},i<\text{ Sizepop-4 }.\text{\hspace{1em}(4)}$$
产生固定方向的果蝇个体，其中 L为搜索半径
$$\{\begin{array}{l}{X}_i=X\text{ axis }+L\sin (T)\\ Y_i=Y\text{ axis }+L\cos (T)\end{array},T=\frac{n\pi }{4},n=1,3,5,7\text{\hspace{1em}(5)}$$
步骤３ 定位果蝇个体坐标$[X_i,Y_i]$ ，并根据式（6）求得个体味道浓度值 S
$$\{\begin{array}{l}{D}_i=\sqrt{X_i^2+Y_i^2}\\ S_i=1/D_i\end{array}\text{\hspace{1em}(6)}$$
步骤4　 将味道浓度值 $S_i$带入判定函数求出每个果蝇的适应度 $Smel{l}_i$
$${\text{ Smell }}_i=\text{ function }\left(S_i\right)\text{\hspace{1em}(7)}$$
步骤5　 如果种群最优优于当前最优，则将种群最优个体的坐标作为下一次迭代的种群坐标，并记录其适应度
$$\{\begin{array}{l}\text{ Smellbest }=\text{ best Smell }\\ X_{\text{axis }}=X(\text{ bestindex })\\ Y_{\text{axis }}=Y(\text{ bestindex })\end{array}\text{\hspace{1em}(8)}$$
步骤6　 重复执行步骤 2～ 步骤 2 ，直到达到终结条件。

3.实验结果

4.参考文献

[1]曹珍贯,李智威,余俊峰.扇区搜索机制的果蝇优化算法[J].计算机工程与设计,2019,40(06):1590-1594.

5.Matlab代码

6.python代码