基于共生搜索的生物地理学优化算法
作者： 朱晓雯 范成礼 卢盈齐 齐铖 李威
摘 要：为平衡生物地理优化（Biogeography-Based Optimization， BBO）算法在搜索过程中多样性和集约性能力，引入共生生物搜索（Symbiotic Organisms Search，SOS）思想，提出基于共生搜索的生物地理学优化（Symbiotic Biogeography Based Optimization，SBBO）算法。首先，通过共生操作优化初始种群，减小初始种群的随机性。在此基础上，为提高迁移过程对解的多样性的探索能力，避免陷入早熟收敛，提出动态选择迁移算子以及互利迁移算子，并通过余弦自适应因子来平衡两种迁移算子在不同迭代阶段的作用。进一步，提出共栖突变算子，提升算法的种群多样性保持能力。仿真实例表明，该算法可较好地协调局部搜索和全局搜索的能力，能够有效提高求解精度和效率。
关键词：BBO算法；SOS算法；动态迁移算子；互利迁移算子；共栖变异算子; 启发式算法; 导弹突防; 武器目标分配
中图分类号：TJ760
文献标识码：A
文章编号：1673-5048（2022）06-0040-10
DOI：10.12132/ISSN.1673-5048.2022.0042
0 引 言
由于精确算法在寻找复杂问题全局最优解中的表现不佳，近几十年来，各种模拟自然界现象的元启发式算法被不断提出，如粒子群算法、遗传算法、人工蜂群算法、蚁群算法等。
生物地理学优化［1］（Biogeography-Based Optimization，BBO）算法是美国学者Simon于2008年首次提出的一种启发式算法。Simon证明，相较于常见的GA，PSO，ACO等算法而言，其对候选解具有良好的挖掘能力和全局搜索能力，因而受到了众多国内外学者的关注。不同算法在求解全局最优问题中都体现出不同的优势，但是由于“没有免费的午餐”，没有哪一种算法在任何方面都表现良好，因而当前算法的改进点都集中在提升求解精度和效率，并使其尽可能优于其他相关算法。
和其他算法相比，原始BBO算法也存在一些较明显的问题：迁移过程中对较优解的直接复制，种群的多样性不高；候选解受适应度值高的个别解强烈吸引，迭代后期出现多个解相近或是超级个体现象；算法早熟收敛等。因而学者专家也不断对BBO算法进行不同程度的改进。在BBO算法的优化方面，通常可分为以下几类：基于迁移和突变操作的优化［2-3］；与其他智能算法或精确算法杂交［4-6］；建立多种群或局部拓扑的BBO［7-8］。
与其他智能算法或精确算法杂交是优化算法的有效手段。本文引入共生生物搜索算法对原始BBO算法进行优化。共生生物搜索 （Symbiotic Organisms Search，SOS） 算法是Cheng等［9］于2014年提出的一种新型启发式算法。该算法模拟了生物体在生态系统中生存和繁殖所采取的共生互动策略，具有较强的鲁棒性和寻优能力。
为解决原始BBO算法存在的问题，更好地平衡算法的集约化和多样化搜索能力，本文汲取BBO算法和SOS算法的共性特点和互补优势，对BBO算法中的迁移和变异操作进行改进，提出基于共生搜索的生物地理学优化算法。SOS算法与BBO算法都受进化理论的启发而产生，理论上具有同源性，两种算法都不需要特定参数；BBO算法的优势在于不同栖息地之间的信息共享，SOS算法中生物共享优势协同进化的功能可以较好地促进BBO算法发挥特点。
反导WTA问题是经典的复杂全局优化问题，多种启发式算法被应用于求解该类问题。罗锐涵等［10］对BBO算法增加了三维变异操作，对火力分配方案进行优化，增加了对于方案的全局搜索能力。本文以导弹突防过程中的武器目标分配为背景，进行仿真实例应用。实例中进一步表明，该优化算法相较于原始算法和其他相关算法，较好地平衡了全局搜索和局部搜索的能力，并且一定程度上有利于提升求解精度和效率。
1 原始的生物地理学优化算法
BBO算法模拟了自然界中物种在不同岛屿之间的迁移，岛屿在BBO算法中被称为“栖息地（Habitat）”，那些被认为适合物种居住的栖息地有着较高的栖息地适宜指数（Habitat Suitability Index，HSI），与这个指数有关的因素有降雨、植被多样性等，这些因素被称为适宜性指数变量（Suitability Index Variables，SIVs）。SIV可以看作是栖息地的自变量，HSI可以看作为因变量。
BBO算法线性模型如图1所示。HSI高的栖息地物种数量多，迁入率低、迁出率高；HSI低的栖息地物种数量少，迁入率高，迁出率低。因而迁移率可以作为物种迁移的标准。
BBO算法的迁移过程可以描述为
式中：μk为第k个栖息地的迁出率；λk为第k个栖息地的迁入率；E为最大迁出率；I为最大迁入率；k为第k个栖息地当前的物种数量；n为最大物种数量。迁入率和迁出率都取决于栖息地的物种数量。
此外，BBO算法中，为了实现种群的多样性，种群的内部会进行变异操作，概率为
式中：m（k）为第k个栖息地的变异率；mmax为用户定义的最大变异修改概率；Pk为当前物种数量概率；Pmax=max（Pi）。
2 共生生物搜索算法
SOS算法体现了生态系统中的不同生物体互利共生、协同进化的特点，主要由三个阶段构成：
（1） 互利阶段
式中：Xi与Xj为两个候选解；rand为（0，1）之间的随机数；由于两个生物之间相互作用时总存在一方获取收益大，另一方获取收益小的情况，因而获利因子BF1和BF2∈{1，2}；MV为生物之间的互利向量，体现了Xi与Xj之间的关系特征。
（2） 共栖阶段
式中：随机选择的候选解Xj与Xi进行互动，生物Xi从与Xj的互动中获益，而Xj未受到影响；（Xbest－Xj）体现了Xj帮助Xi提升至最优解的最大程度。
（3） 寄生阶段
在此阶段中，Xi为寄生变量，Xj为生态系统中随机选择的寄生变量的宿主，Xi试图取代生态系统中的Xj。通过对Xi和Xj两种生物体的适应度进行评估，如果Xi比Xj有更好的适应性，则会替代Xj，否则Xj将保留。
3 改进的生物地理学优化算法
3.1 改进思路
BBO算法存在一些固有的问题：（1）初始种群的生成具有随机性；（2）迁移机制中在栖息地的选择中使用轮盘赌的方式，存在很大的随机性，且耗时长、计算复杂度高；（3）迁移操作中通过对已选择的SIV特征进行直接复制，导致在整个优化迭代的过程中对新解的勘探能力有限，容易被个别HSI很高的精英解强烈吸引，从而出现超级个体或过早收敛的情况；（4）突变操作对种群后半部分较差解进行变异，这个变异方向是随机的，无法保证向优质解方向变异，且对于新解的探索贡献不足。
针对以上问题，本文以BBO算法为主，引入SOS算法中的思想，对BBO算法的核心步骤：迁移操作和突变操作进行改进，提出SBBO算法。首先，对初始种群进行优化；其次，在迁移机制中，对栖息地选择进行动态调整，引入余弦自适应框架，并与SOS算法中互利操作进行融合；突变操作中，引入SOS算法中的共栖操作对原始突变进行优化。仿真实例表明，SBBO算法有利于扩大种群多样性，同时可提高算法的求解精度和效率。
3.2 初始种群优化
由于初始种群的生成是随机且无向的，首先根据共生生物搜索算法中的互利操作，使初始种群进行初步优化，便于对优质解的探索：
式中：Hi_new和Hj_new为经过互利操作协同进化生成的新的栖息地；Hi与Hj为随机选取的栖息地；MV为两个栖息地之间的互利向量；BF1和BF2∈{1， 2}为获利因子。初始种群优化过程如图2所示。原始种群在可行域内生成的位置是无向且随机的，因而存在如图中Hj远离最优解的解。而互利操作可以使Hi与Hj以不同的程度向最优解靠近，从而使初始种群向最优解范围进化，进化程度由rand×（Hbest－MV×BF1或2）决定，这个程度是随机的，并不会降低初始种群的随机性。该优化操作有利于减小初始解生成的随机无向性，并加速对最优解的寻找过程。
3.3 迁移算子改进
3.3.1 基于动态选择的迁移算子
在BBO算法对迁出的栖息地选择中，主要采取轮盘赌的方式，这种选择概率都是随机的，无法根据不同迭代阶段进行相应的变化，容易造成种群的多样性不高、算法过早局部收敛的问题。
因而本文设置了栖息地动态选择策略，即在不同的阶段中，进行迁入迁出操作时，规定不同的选择压力。在早期， 缩小选择压力，使HSI值较低但可能含有优秀SIV因素的栖息地能够更多地参与到迁移过程中，保持种群的多样性；在后期， 适当增加选择压力，使种群能够较快收敛，从而更加趋近最优解。本文提出以下选择概率：
式中：Pk为第k个解被选择进行迁出的概率；μk为当前栖息地的迁出率；n为种群数量；μi为任意第i个栖息地的迁出率；G为当前迭代次数；Gmax为最大迭代次数；a为选择压力因子；pdmax为选择压力因子的变化初始值；pdmin为选择压力因子的变化终值。
pdmax和pdmin为定常参数，为测试pdmax和pdmin对算法性能的影响，选择具有代表性的多峰不可分Ackley测试函数进行实验。表1和图3显示了不同取值的pdmax和pdmin对整体优化效果的影响。可以看出，pdmax和pdmin取值对算法整体寻优趋势有较大的影响，当pdmax=0.9，pdmin=0.1时， 优化效果最佳。其原因是在迭代前期收敛速度慢，后期收敛速度快，同时求解精度增加，符合压力选择的原则。
改进后， 动态栖息地选择公式前期收敛速度慢，有利于进行全局搜索；后期收敛速度快，有利于加强局部搜索，取得的结果也较优，并且较原始BBO算法的栖息地选择上有较大改善。
3.3.2 互利迁移算子
其他算法中针对迁移算子的改进如表2所示。
表2中，α，F为文中确定的随机参数；t为当前迭代次数；T为最大迭代次数；k为最大种群数；k1， k2， k3为原文中选取的栖息地。
综合以上迁移操作的修改来看，主要是通过将选择的迁入地进行修改或者是多个栖息地按照一定的比例进行迁入，然而迁入和迁出的栖息地在进化中并不是完全孤立的。在自然界中，两个不同的栖息地也可能因为迁入的物种而发生适应性的变化，从而使两者的适应性程度得到提升。受这一思想启发，本文引入SOS算法中的互利操作。如图4所示，针对第j维的栖息地，左侧是原始BBO算法的迁移过程，右侧是对选择的迁入地和迁出地进行互利进化，二者都吸收相互间的有利因素，通过互相学习和反馈，进行协同进化：