李昌兴, 张 颖

(西安邮电大学 理学院， 陕西 西安 710121)

生物地理学优化(biogeography-based optimization, BBO)算法是一种基于生物学种群迁移理论的进化算法[1]，BBO算法具有良好的性能，目前已被广泛应用到多目标规划[2]、复杂系统优化[3]等多个领域中。BBO算法具有独特的迁移算子和变异算子，具有良好的全局搜索能力、较强的开发能力和信息共享能力[4]，但其探索能力较弱，局部搜索能力不强，特别是在迭代后期，算法搜索动力不足，容易陷入局部最优，导致收敛慢或者无法收敛，其稳定性和精度较差[5]。需要对该算法进行改进，以平衡算法的开发能力、探索能力[6]以及跳出局部最优的能力，提高收敛速度。

差分进化(differential evolution, DE)算法具有较强的探索能力，且能够快速定位全局最小区域[7]，可将BBO算法与DE算法相结合，以平衡算法开发能力和探索能力，目前已存在很多将BBO算法与DE算法相结合的研究，如文献[8]将DE算法的局部搜索策略与BBO算法的迁移策略相结合，融入DE算法中的选择操作，提出了基于局部搜索策略的BBO算法。文献[9]将DE算法与BBO算法相结合，提出一种两阶段差分BBO算法。文献[10]结合DE算法和BBO算法的迁移策略，改进BBO算法中的迁移算子和变异算子，给出了二重迁移算子和二重变异算子，使得栖息地个体具有更高的进化概率。文献[11]将DE算法的差分算子引入个体迁移，并将改进的个体迁移与传统的基因迁移相结合。这些改进均在一定程度上提高了算法的优化性能，但在收敛精度、速度以及稳定性上仍有待提高。

为了进一步加快BBO算法的收敛速度，提高算法的收敛精度和稳定性，本文拟提出一种基于双模式迁移策略生物地理学优化(dual-mode migration BBO, DMMBBO)算法，在标准的BBO算法基础上，采用更接近自然规律的余弦迁移率模型，引入自适应的差分变异算子，改进迁移算子，并将改进后迁移算子与标准的迁移算子相结合形成双迁移模式，在迭代过程中利用参数平衡两种迁移模式，优化DMMBBO算法的性能。为了验证改进算法的性能，采用10个基准测试函数进行仿真实验，并将改进后算法的优化结果和优化曲线与两种单模式算法进行比较，验证改进后算法的收敛速度、收敛精度和稳定性。

1 标准BBO算法

BBO算法是一种基于生物学种群迁移理论的进化算法。该算法的基本思想是通过物种迁移的方式，实现不同栖息地之间的交流与共享，从而寻求问题的最优解[1]。BBO算法主要描述了生物如何从一个栖息地迁徙到另一个栖息地，物种数量在栖息地上如何上升或者下降。因每个栖息地在地理上与其他栖息地独立，故只能通过迁移方式进行物种交换。适合物种生存的栖息地具有较高的适宜度指数(habitat suitability index, HSI)。用适宜度指数变量(suitable index vector, SIV)来描述与HSI相关的因素，如栖息地的温度、湿度、降雨量等，各适宜度变量被称为SIVs[1]。在BBO算法中，每一个栖息地代表问题的一个解决方案，SIV等同于遗传算法(genetic algorithm, GA)中的基因。HSI相当于GA中的适应度值，将这些解决方案按照HSI进行排序，其中，HSI较高的栖息地被认为是更优的解决方案。此外，每个栖息地都有迁入率λ和迁出率μ两个属性，它们的大小取决于栖息地的HSI。一个栖息地的HSI越低，它的迁入率就越低，迁出率越高。

BBO算法是由初始化、迁移和变异3个过程组成。

(1) 初始化

对栖息地的适宜度指数变量SIV进行初始化，令n个栖息地的D维适宜度指数变量可用矩阵

X=[X1,X2,…,Xn]

表示，第i(i=1,2,…,n)个栖息地的SIV表示为

Xi=(xi,1,xi,2,…,xi,D)，

栖息地Xi的第j(j=1,2,…,D)个元素可表示为

xi,j=Lj+rand×(Uj-Lj)。

(1)

其中，Lj表示第j列变量的下限，Uj表示第j列变量的上限。

(2) 迁移

为实现栖息地之间的信息流通，采用迁移操作模拟生物地理学的迁徙机制。将所有栖息地的解按照HSI从小到大的顺序排列，对排序后栖息地编号赋予新的i值，计算栖息地的种群数量

Si=Smax-i(i=1,2,…,n)。

其中Smax为所有栖息地包含物种数的最大值，一般设Smax=n。

定义栖息地Xk的迁入率λk和迁出率μk，即令

(2)

其中k为栖息地Xk所包含的物种数量，I为最大迁入率，E为最大迁出率。

首先，根据全局迁移率Pmod选择需要迁入的栖息地Xk，确定Xk后，以栖息地Xk的迁入率λk依概率选择各SIV变量决定是否迁入。其次，根据迁出率μi(i≠k)选择迁出地Xi，以栖息地Xi的对应的SIV，替换栖息地Xk的SIV。

(3) 变异

为增加种群的多样性，采用变异操模拟自然环境中的一些突发情况。首先，根据各栖息地的种群数量概率P(j)计算对应的变异概率m(j)，突变概率函数与该栖息地的种群数量概率成反比，其相应的函数关系为

其中，mmax为用户自定义突变率的最大值，Pmax为P(j)中的最大值。

其次，以变异概率m(j)选择进行突变操作的栖息地Xj，在给定范围内随机产生一个SIV对Xj中的SIV进行替换。

2 DMMBBO算法

DMMBBO算法是BBO算法的一种改进，DMMBBO算法在标准的BBO算法的基础上做了两个方面改进：一方面，采用余弦迁移率模型代替标准BBO算法的线性迁移率模型；另一方面，引入自适应差分变异算子对迁移算子进行改进，并提出一种双模式的迁移策略。

2.1 余弦迁移率模型

BBO算法对于迁移模型非常敏感。标准的BBO算法采用线性迁移率模型，其迁入、迁出率表达式如式(2)所示，该模型过于简单，且不符合自然规律。实际上，接近自然规律的迁移率模型性能要优于简单的线性迁移率模型[12]，因此，选择较接近自然规律的余弦迁移率模型，其迁移模型如图1所示。

图1 余弦迁移模型

从图1中可以看出，当栖息地物种数量较少或较多时，迁入率和迁出率变化较平稳，而当物种数量处于中间数量时，迁入率和迁出率变化较快。迁入、迁出率表达式分别为[12]

2.2 双模式迁移策略

在标准BBO算法的基础上，提出一种双模式的迁移策略。迁移模式1引入一种带有自适应的差分迁移算子，迁移模式2为经典的迁移算子。为了平衡两种迁移模式，添加一个参数Pb来平衡这两种迁移策略。

首先，随机生成一个0～1之间的随机数Pdr，当Pdr>Pb时，迁移方式选择模式2，即标准BBO算法迁移模式。当Pdr

(1)从1～n中随机选取两个数r1和r2，选择条件为r1≠r2≠k≠GBest，其中，k为本次根据迁入率选择迁入地的栖息地标号，Gbest为本次迭代的最优栖息地标号。

(2)引入差分变异算子，产生的新的候选解

(3)

其中，Hi为第i个候选解，i=1,2,…,n；Hr1、Hr2为2个不同的候选解；HBest为当前最优的候选解，F为缩放因子。

将差分变异算子与原迁移算子相结合，得到

(4)

其中，xBest,j、xr1,j、xr2,j分别为当前最优栖息地和2个随机选中栖息地第j维的值；F1=(μBest+μk)/2，F2=(μr1+μr2)/2。

(5)

采用公式(5)对种群进行迁移操作，其中，ω为0～1之间的随机数。

双模式的迁移策略，其流程如图2所示。

图2 双模式迁移策略的流程

3 实验结果及分析

3.1 测试函数

为了测试算法的性能，选取10个基准测试函数对优化的结果进行测试。

所选取的基准测试函数，如表1 所示。其中，f1～f5皆为仅有一个极值点的单峰函数，用于测试算法的收敛特性。f6为只有一个极值点的梯状函数，f7为一个带有噪声的多峰函数，极值点随均匀分布随机数的变化而变化。f8～f10皆为具有多个局部极值点的多峰函数，其极值点的个数随问题的维数呈指数式增加[13]，用于测试算法跳出局部最优能力和逼近全局最优能力。

表1 基准测试函数

3.2 参数设置

算法参数设置为，种群规模n=50，测试函数的维数D=20，迭代次数为G=50，最大迁入率I=1，最大迁出率E=1，变异率Pmutate=0.01，全局迁移率Pmod=1，精英个体保留数量为2。由于算法存在一定的随机性，为了避免误差，所有算法独立运行20次。

3.3 测试结果及分析

为了比较算法的性能，应用基准测试函数对改进后的DMMBBO与标准的生物地理学算法(standard biogeography-based optimization, SBBO)和引入自适应差分迁移算子的单模式BBO算法(single-mode migration BBO, SMBBO)进行比较。以平均值和标准差对算法的优化能力进行评价。平均值用于评价算法的精度和可靠性，平均值越小，该算法的精度越高，可靠性越强。标准差用于评价算法的稳定性，标准差越小，该算法稳定性越高。3种算法的测试结果，如表2所示。

表2 3种算法对10个标准函数优化的测试结果

从表2可见，不论单峰函数还是多峰函数，在参数相同的情况下，DMMBBO算法相较于SMBBO算法和SBBO算法更能收敛到较小值，结果更逼近于最优解。DMMBBO算法的收敛精度更高，收敛性更强。改进算法的平均值和标准差都相对较小，说明DMMBBO的算法的稳定性更强，特别是函数f1，其平均值和标准差均达到了10-6数量级，相对于BBO算法和SBBO算法提高了6个数量级，算法的性能提升较大。这可能是因为引入差分变异算子产生的结果。DE算法具有较强的探索能力，在迁移算子中引入差分变异算子有效平衡了算法的开发能力和探索能力，使得算法能够快速定位全局最优位置，提升全局优化能力。为了进一步评价算法的收敛速度以及平衡参数Pb对算法收敛速度的影响，通过描绘算法的收敛曲线分析其性能。不同算法的最优值收敛曲线，如图3所示。

(a) 测试函数f1(b) 测试函数f2

(c) 测试函数f3 (d) 测试函数f4

(e) 测试函数f6 (f) 测试函数f7

(g) 测试函数f8 (h) 测试函数f9

图3中，横坐标表示各函数的迭代次数，纵坐标表示优化得到的最小值。由于测试函数在迭代后期所得数值数量级差距较大，为便于观察，纵坐标的数值都取10为底的对数。当平衡参数Pb取0～0.50时，测试函数均出现了早熟现象。图3画出了当Pb分别取0、0.50、0.65、0.75、0.85、1.00时，函数f1～f4、f6～f9的最优值收敛曲线，对应曲线分别命名为SBBO、DMMBBO-0.50、DMMBBO-0.65、DMMBBO-0.75、DMMBBO-0.85，DMMBBO-1.00。

从图3收敛曲线的趋势可以看出，当参数Pb取0时，在迭代中后期，SBBO算法因探索能力较弱，使得收敛速度过慢，易陷入局部最优解；当参数Pb值从0.50不断增大时，随着迭代次数的增加，DMMBBO算法的收敛速度明显加快，但当Pb取值过高时(如DMMBBO-1.00)，收敛速度又会变慢；如图3(a)、图3(b)、图3(c)、图3(d)和图3(h)所示，对于单峰函数f1～f4和多峰函数f9，当参数Pb取0.75时DMMBBO-0.75曲线的收敛速度最快，算法能够收敛到更小值；如图3(e)、图3(f)和图3(g)所示，对于测试函数f6～f8，比较参数Pb分别取0.50、0.65、0.75和0.85时的4种收敛曲线，发现当参数Pb取0.65时DMMBBO-0.65曲线收敛速度最快，算法能够收敛到更小值。

从图3中的8种函数的收敛曲线可以发现，不论单峰函数还是多峰函数，改进后算法的收敛速度都有了较大提升，且平衡参数Pb取过大或过小都会损害DMMBBO算法的性能，导致算法收敛速度过慢，出现早熟等现象，当参数Pb取0.65～0.75时DMMBBO算法的性能达到最优。

4 结语

标准的BBO算法存在局部探索能力不足，收敛速度过慢、收敛精度不高、算法不稳定等问题，为此提出了一种基于双模式迁移策略的生物地理学算法，该算法采用余弦迁移模型，在标准迁移策略的基础上进行了修改，将带有自适应差分算子的迁移策略与标准迁移策略结合，然后通过调节参数Pb平衡两种迁移模式，以提升算法的性能。为了验证改进后算法的性能，将DMMBBO算法应用于10个基准的测试函数上进行测试，测试结果表明，DMMBBO算法相较于两种单模式算法，收敛速度、收敛精度和算法稳定性都有了较大的提升，并通过调整平衡参数，当Pb取0.65～0.75时算法改进的效果最佳。