1. 引言

生物地理学优化算法(Biogeography-Based Optimization, BBO) [1] 是由Dan Simon于2008年提出的一种基于生物地理学理论发展起来的算法。BBO算法是在物种迁移的数学模型的基础上形成的，与其他智能算法(例如GA，ACO，PSO，DE等)相比，BBO也是一种基于种群优化的算法，但是它不需要繁殖或者产生下一代种群，因此可以大大降低算法的复杂度。BBO算法利用迁入率决定需要引入的特征变量的比例，而且迁入的特征变量来自不同的个体。相比之下遗传算法(GA)中交叉操作无法根据适应值的不同来控制交叉基因的比例，而且交叉的基因片段来自同一个体。这是遗传算法与BBO算法的显著不同之处。BBO算法也有别于ACO算法，ACO算法在每一代产生一系列方法，BBO则保持方法不变。在这点上BBO算法与和PSO和DE算法较为相似，都将产生的方法保存到下一代，每一方案都能与其邻居进行信息交互。但是BBO算法采用了根据不同栖息地种群数量选择不同操作强度的生物激励机制，是一种独特的智能优化算法。

BBO算法的自适应机制也适用于经济学理论中的市场调节机制下的均衡价格形成机制。这种自适应机制在其它领域中也有很多重要的应用。例如生物迁徙规律和人类社会中的人口流动机制有许多类似的地方。

生物地理学研究物种的地理分布，BBO算法思想来源于生物种群在栖息地的分布迁徙规律，算法的核心是迁移和变异过程。迁移过程是指在栖息地之间进行信息交换。变异过程指由于突发事件引起栖息地的变化。通过迁移和变异过程，不同栖息地有不同的适宜度，经过一段时间后得到动态的平衡。BBO算法是一种用于求解优化问题的自然启发技术。自从BBO算法提出以来，在理论研究，算子改进策略及应用领域诸方面都有迅速的发展，本文从BBO算法思想开始，对BBO算法的理论研究，改进策略及应用领域三个方面详细论述BBO的研究进展，以及对其下一步研究方向进行了系统的论述。

2. BBO算法

受自然现象的启发，Simon在2008年提出的生物地理学优化算法是基于生物地理学的数学模型，用于发现问题的最优解的计算技术[1] 。BBO算法在栖息地或岛屿的种群上操作，解的过程类似于自然界中物种的迁移。每个栖息地代表预处理问题的一个可能解。每个栖息地的适应度由它的栖息地适应性指数HSI所决定。HSI是决定候选解好坏的度量，每个栖息地的特征称为适宜度指数变量SIV。高HSI的岛屿类似于高质量的解，低HSI的岛屿类似于较差质量的解。高HSI解更可能与别的解分享他们的特征，低HSI解更可能接受来自其它解的共享特征。候选解之间特征的共享表示为岛屿间的迁入和迁出[2] 。每个栖息地的迁入率λ和迁出率µ被用于概率的在栖息地间共享信息。迁入与迁出率受栖息地种群数S影响，当栖息地没有物种时会出现最大迁入率I，并且随着越来越多的物种迁入，迁入率逐渐下降，当栖息地所有可能的物种都出现即达到Smax时，此时最大迁出率E出现。当栖息地种群数为S时，迁入率和迁出率的计算如公式(1)所示。

(1)

公式(1)中的Smax表示每个栖息地可容纳的最多物种数。

BBO算法描述如表1所示。BBO算法流程图如图1所示。BBO算法的核心包括迁移和变异两个基本算子。BBO算法使用每个解的迁移率在解之间概率的分享特征，迁入曲线用于概率的决定每个解中每个特征是否迁入，如果给定的解的某个特征被选择用于迁入，那么迁出岛屿也是概率的进行选择。在表2中给出迁移操作的描述。

灾难性事件可能会引起栖息地适应度指数HSI发生剧烈的变化，由于出现的随机事件也使得一个岛屿栖息地的HSI突然变化。在BBO算法中，变异算子即源于这种思想。如果一个栖息地被选择用于变异，那么在这个栖息地一个随机选择的SIV用它取值范围内随机生成的新的变量来代替。种群数概率Ps用于决定变异率，每个栖息地的变异率由栖息地的种群数概率决定，如公式(2)所示。变异操作在表3中给出

描述。

(2)

其中m_max是用户自定义的最大变异概率，并且P_Smax是指栖息地的种群概率的最大值。

3. BBO算法的研究进展

目前，生物地理学优化算法在理论分析、算法改进及应用方面都有很大的进展。下面主要从理论分析，算法改进及应用三个方面讨论生物地理学优化算法的发展情况。

3.1. 理论研究领域

Simon等人[2] 对BBO算法做了理论上的分析并推导出BBO算法的马尔科夫模型，理论分析表明当迭代次数趋于无穷大时马尔科夫模型给出每个可能种群出现的理论几率，通过仿真结果也证实了此理论。接着利用马尔科夫模型分析BBO算法[3] -[4] ，并在不同问题上对BBO算法，全局联合重组的遗传算法(GAGUR)和单点交叉的遗传算法(GASP)的马尔科夫模型进行比较，结果表明对于高变异率三者性能是相似的，低变异率情况下BBO算法优于GASP和GAGUR。BBO算法是全局联合重组的遗传算法(GAGUR)的推广，通过分析BBO和GAGUR两者的马尔科夫的模型并用于连续最优化基准问题[5] ，在标准基准问题及组合优化问题(如TSP，图着色问题，0-1背包问题)均表明BBO算法性能优于或匹配GAGUR算法。Simon等人[6] 首先提出了一个简化的BBO模型，并分析了该算法的性能，其次利用概率知识对BBO种群进行近似分析，分析提供了当种群达到最好解时需要经历的迭代次数以及改善程度的近似值。即随着种群规模的增大，迭代次数也随着增加，且随机产生种群中的最好解也随着增加，改善程度却随着种群规模的增加而降低。

由于在BBO中不同的迁移模型将导致性能明显变化，并且动态迁移率优于恒定迁移率。因此马海平等人[7] 提出一个一般性的余弦曲线迁移模型，用BBO马尔科夫模型分析了该迁移模型，并从理论分析和仿真结果证实了该模型的优越性。

Simon等人利用马尔科夫理论对局部的基于迁入的BBO算法得出动态系统模型(dynamic system model)[8] 。动态系统的状态等于种群中每个个体的比例，动态系统的维度等于优化问题的搜索空间的基。动态系统模型允许我们对给定的优化问题用理论而不是用仿真可得出种群中每个个体的比例，特别是对种群中不可能出现的个体来说，动态系统模型比仿真结果更准确，并用仿真结果验证了动态系统模型。也在一些简单问题上使用该模型比较了BBO，GAGUR和GASP三种算法的性能。结果表明，低变异率情况下BBO算法优于GA。

3.2. 算子改进策略

对BBO算法的改进思路主要是修改BBO算法的迁移算子和变异算子，或利用其他进化算法的优势来修改相应的算子。

马海平等人[9] 为改进BBO算法的迁移算子提出一个混杂的迁移算法，基准测试程序表明混杂的BBO算法优于标准BBO算法，并利用混杂的BBO算法解决有约束的优化问题。约束条件仅通过修改BBO的迁入和迁出过程来处理，与无约束的优化问题一样不需要调整更多的参数。最后将有约束的BBO算法与标准遗传算法(SGA)和标准的粒子群算法(SPSO07)比较，结果表明对有约束的单目标优化问题有约束的BBO算法优于SGA，与SPSO07性能类似。

Li等人[10] 同时改进了BBO算法的迁移算子和变异算子。算法中基于余弦曲线的迁移模型提出一种新的迁移算子称为扰动迁移(perturb migration)，它是标准BBO算法迁移算子的推广，然后用高斯变异算子集成到扰动的BBO算法(Perturb BBO, PBBO)中同时增加BBO算法的局部开发能力及增强种群的多样性。在23个基准问题上进行实验结果表明基于余弦曲线模型的PBBO算法的优越性。

Ergezer等人[11] 提出一种新的基于对立学习机制的BBO算法，即将基于对立的学习集成到BBO中(Opposition-Based Learning BBO, OBBO)作为一种变异机制改进BBO的收敛速度。在OBBO算法中，将基于对立的学习，动态域缩放及带权的反射合并到BBO中以提高BBO的性能，OBBO算法明显胜过BBO算法。准反射(quasi-reflection)和准对立(quasi-opposite)机制用于OBBO算法以改善性能，在高维情况下通过计算仿真表明了随着问题维数增加准反射和准对立的OBBO的性能随之改善。最后，使用准反射的BBO算法与其它基于对立的方法进行比较，准反射的BBO算法在产生更接近解方面有更高的概率及更少的计算量，因此准反射是建立OBBO优选的对立算法。

Tan等人[12] 根据进化多个量子概率模型的思路提出量子BBO (Quantum and Biogeography Based Optimization, QBBO)算法。在QBBO算法中，在决策空间中构建的一个区域的量子概率模型表示一个栖息地，整个种群的量子概率模型成为有多个栖息地交互的生态系统，应用于组合优化问题取得了较好效果。

还有将其它一些启发式算法的特性集成到BBO的改进思路，如Du等[13] 将进化策略(Evolutionary Strategy, ES)的特性加入BBO算法(BBO/ES)，且将一种新的迁入拒绝(Immigration Refusal)方法加入到BBO算法提出的BBO/ES/RE算法。在基准问题上用F测试和T测试均表明改进算法的优越性，并且加入ES特性对BBO算法有特别明显的影响。

Gong等[14] 提出BBO算法与差分算法的结合的BBO/DE算法。算法的主要思路是改进BBO的迁移算子，用差分算子代替BBO的迁移算子增加种群的多样性克服陷入局部最优。通过23个基准函数的测试，结果表明混合算法性能优于DE算法和BBO算法。Gong等[15] 又把进化算法中的邻域搜索算子融入BBO算法提出一种实数编码BBO算法，算法中通过变异策略提高了算法性能。此外，还有将BBO算法与带外推技术的粒子群结合提出ePSO/BBO算法，并用于求解连续域中无约束的全局数值优化问题也取得良好效果。

除了上述的一些改进思路，还有将BBO算法扩展到多目标的情况[16] [17] 。

马海平等人[16] 提出多目标的BBO优化算法(BBMO)，在BBMO算法中，使用非支配排序方法有效改善了算法的收敛能力，使用拥挤距离确保帕累托最优解的多样性，并根据三种度量与NSGA-II和AMGA算法进行比较。仿真结果表明，在大多数情况下BBMO算法比其它两种算法能发现解的更好分布并且更快的收敛到真正的帕累托最优前端。

Mo等人[17] 提出一种多目标的BBO进化算法(BBMOEA)，使用SPEA2的适应度分配和外部种群精英确保解集的均匀分布，并将BBO的种群进化操作应用到外部种群的进化以保证解集的收敛。在基准测试问题上的仿真结果表明提出的算法的有效性。

3.3. 应用领域

近几年BBO算法已经在许多领域有了广泛的应用，如电力系统、图像处理、旅行推销员问题、排列流水车间调度问题、在无线传感网中最优潮流布局问题、机器人的轨迹规划问题、离散变量函数优化问题、参数估计、模糊逻辑系统、快速运动估计算法等方面。电力系统中经典的问题如电力系统的经济负荷分配(Economic Load Dispatch, ELD)问题和电力系统最优潮流(Optimal Power Flow, OPF)问题。BBO算法的应用领域如表4所示。

ELD问题在电力系统中的经济调度中占有重要作用。ELD是一个非线性多目标有约束的全局优化问题。Bhattacharya等人[18] [19] 利用BBO算法求解凸和非凸的经济负荷分配问题。BBO算法很容易解决非凸的带约束的ELD问题。约束条件包括输电损耗，阀门点负荷，斜坡速率限制，多燃料选项及禁止操作区5个。Bhattacharya等人[20] 用DE/BBO算法解决凸的和非凸的热力发电单元的ELD问题，用DE/BBO算法改善了解的质量和收敛速度。

由于准反射对立的BBO算法能改善解的质量加速BBO的收敛，Bhattacharya等人[21] 用准反射对立的BBO算法解决热电厂复杂的ELD问题。准反射数被用于种群的初始化和代数跳变。算法的有效性在4个不同的测试系统中得到验证。Bhattacharya等人[22] 又用OBBO算法解决多目标的ELD问题。P. K. ROY等人[23] 考虑到发电机的非线性特性如阀门点负荷、斜坡率限制、禁止操作区及多燃料耗费等，将BBO算法在不同系统不同仿真条件下进行性能测试。此外，捕食者–食饵(Predator-Prey)BBO算法[24] 也应用到ELD问题，在2个测试系统上进行验证并与其它方法进行了比较。

考虑到不同的目标函数，不同的约束条件及不同类型的耗费函数，BBO算法是解决全局最优的OPF问题的一种较好的进化优化算法[25] -[27] 。Rarick等人[25] 将BBO算法应用到电力潮流问题中的一个IEEE 30-bus的测试案例系统。Roy等人[26] -[27] 将BBO算法用于解决带两个约束条件的OPF问题和多目标的OPF问题。在解决带有约束条件的OPF问题中，算法的可靠性使用9-bus系统和IEEE 30-bus系统进行测试，BBO优于PSO算法。在多目标的带有约束条件的OPF问题中，算法性能在带有三个目标函数的9-bus、26-bus和IEEE 118-bus系统中测试，与进化规划、遗传算法及混合整数的PSO算法相比，提出的算法对多目标带约束的OPF问题的全局优化有更好的解质量及更高的计算效率。

Panchal等人将BBO算法用于卫星图像的分类取得了较好的效果[28] 。原始的BBO算法没有内置的聚类特性，因此，修改BBO算法用于给定区域的卫星图像的分类。Johal等人[29] 将蜂群技术用于图像分类，提出一种新的基于人工蜂的花授粉技术的群数据聚类方法，用此方法聚类卫星图像像素。聚类的目的是把数据点分成自相似的组，这些聚类进一步通过BBO进行分类。用该算法可获得卫星图像的高精确的分类。Gupta等人[30] -[31] 将BBO算法用于文档图像的色彩量化及彩色图像的分段等。

Wang等人[32] 用BBO算法结合差分进化算法及单一的搜索思路设计了一个有效的杂合算法解决参数估计问题。参数估计问题可形式化为一个多维的最优化问题，通过适当融合一些不同搜索机制特性的优化方法，杂合算法的探测能力及开发能力得到增加和很好的平衡。

BBO可用于心脏疾病诊断的神经模糊系统参数的优化。心肌症可通过研究P波特性来诊断，Ovreiu等人[33] 设计一个用BBO算法训练的神经模糊网络，这个神经模糊网络识别和分类P波特性，此外，用基于对立的学习的BBO(OBBO)来改进训练。首先开发一个神经模糊模型结构来诊断使用P波特性的心肌症，随后使用BBO及心电图信号的临床数据库来训练网络。初步结果表明，使用这种方法心肌症能被可靠的诊断。

排列流水车间问题(Permutation Flow Shop Schedule Problem, PFSSP)是个有广泛工程和理论背景的NP问题，Yin等人[34] 提出基于文化基因算法(Memetic Algorithm, MA)的BBO算法用于解决PFSSP问题。BBO算法用于检测地下水可能性也取得了良好效果[35] -[36] ，即用BBO算法和基于案例的推理检索实现地下水可能性检索系统用以检测地下水的可能性。案例库中的地质情况、地形地貌、土壤、土地利用、斜坡和轮廓因素在测定地下水可能性方面扮演一个决定性的角色。专家分析和综合这些属性用于预测地下水的可能性。案例中存储的案例是有解集的这些属性的预先选择的组合，这些案例有高地下水可能性、中可能性和低可能性三个解，用高、中、低栖息地分别对应地下水高、中、低可能性的相应物种组成。

BBO算法用于组合优化问题如旅行商问题[37] -[38] ，在4个经典的TSP问题上进行测试，并与别的一些自然启发优化算法比较，结果表明了提出算法的有效性。

ABBO用于离散变量函数优化提出了加速的BBO算法[39] (Accelerate BBO, ABBO)增加局部开发能力，通过修改变异算子和去重复操作增加BBO的全局探测能力，明显改善BBO算法的收敛特性。BBO算法用于无线传感器网络功能耗费分析[40] ，目的是在一个预期的性能标准下使整个传感网总的功能耗费最小，使用约束的BBO/DE算法求解最优功率分配方式的解。BBO算法用于天线阵综合问题[41] ，即BBO算法用于决定天线元件的最优值。BBO还用于调控移动机器人的模糊跟踪控制问题[42] ，仿真和真实世界的实验结果表明BBO可调控模糊控制器隶属函数的形状。

4. 结论

BBO算法由于进化机理的新颖性，已受到计算智能领域众多学者的关注。尽管已经取得很多重要的成果，但相对其他进化算法(如PSO、GA)来说，其更深入的理论研究包括BBO算法中的参数选取、复杂性分析问题、适应度函数设计以及算法在工程实际中的应用还有待扩展。

总的来说，还有以下几方面工作值得进一步研究：

1) 理论研究

尽管BBO理论上已经取得许多重要的成果，如Simon对BBO算法做了理论上的分析，利用概率知识建立BBO的马尔科夫模型，分析了BBO算法的收敛性，并利用马尔科夫理论得到BBO的动态系统模型；马海平提出的余弦曲线迁移模型等，但对于该算法的理论分析还远远不够。目前，有关BBO算法的理论研究主要集中在Dan Simon的团队且大多是通过概率分析加实验仿真说明算法的计算性能，也从理论上给出算法中一些参数的参考取值。但BBO算法的理论研究还需要更多人从更广的角度进行分析。

2) 算法改进

生物地理学优化算法是生物地理学与计算智能相融合而得到的一种新型进化算法，属于一个交叉学科研究方向。由于该算法的提出仅仅只有几年时间，虽然已经取得了一定的成果，如PBBO、OBBO、QBBO、BBO/ES/RE、BBO/DE、ePSO/BBO和多目标的BBO等算法改进思路，但这些改进都是从实验仿真结果说明算法的性能，算法的收敛性及复杂度分析鲜有涉及。另外，为了进一步提高算法性能可尝试借鉴生物学中一些新的研究成果，以研究BBO算法更有效的进化模式。同时，也可与确定性算法相结合或将智能计算中一些技术，如：模糊逻辑、神经网络、混沌技术等有效融入BBO算法以改进算法[44] [45] 。

3) 扩大应用领域

目前BBO算法已经在电力系统，图像处理，参数估计，离散变量函数优化，旅行推销员问题，排列流水车间调度问题，无线传感网中最优潮流布局问题，机器人的轨迹规划等领域有成功的应用。类似于其他进化算法，BBO算法可进一步扩大应用领域用来求解一些复杂优化问题，如：信息安全、图像处理、数据挖掘、调度优化、噪声环境下优化问题、混沌系统的控制与同步、生物信息学领域等。

NOTES

^*通讯作者。

参考文献