差分迁移和趋优变异的生物地理学优化算法

张新明，康 强，王 霞，程金凤

1(河南师范大学 计算机与信息工程学院，河南 新乡 453007)

2(河南省高校计算智能与数据挖掘工程技术研究中心，河南 新乡 453007)

1 引 言

进化算法是一类模拟自然现象和生物行为的优化算法，主要通过群智能的方法在解空间区域搜索最优解，具有比传统优化方法更高的搜索效率，常用于处理科学和工程领域中的优化问题.已有的知名进化算法包括粒子群(Particles swarm optimization，PSO)算法[1]，人工蜂群(Artificial bee colony，ABC)算法[2]，差分进化(Differential evolution，DE)算法[3]等，近几年还不断有各种新的算法被提出.

生物地理学优化(Biogeography-based optimization，BBO)算法是进化算法之一，于2008年由Simon[4]首次提出，得到众多学者的青睐，然而，该算法的两个主要算子(迁移算子和变异算子)都存在着一些缺陷，且算法收敛速度慢，计算复杂度高，从而影响了算法的优化性能和运行速度.

许多学者在改善BBO算法方面进行了大量研究，主要分为以下四个角度：一、分析调整BBO算法的模型和参数，例如，Ma[5]提出了6种不同的迁移模型，分析了各模型下迁入率和迁出率的变化曲线，并在不同的种群数量、问题维度、变异率、最大迁入率和最大迁出率下对6种模型的优化性能进行测试，验证了余弦迁移模型具有最好的优化性能，该模型后来也被一些其它研究所采用[6,7]；二、改变算法的拓扑结构，例如，Zheng等人[8]提出了3种不同的局部拓扑BBO算法，使算法中的迁移只能在相邻区域发生，从而降低计算复杂度，并通过实验验证了3种局部拓扑BBO算法的优化性能；三、改进算法的更新方式，例如，Guo等人[9]提出了一种回溯BBO算法来克服迁移算子中的缺点，提高算法的优化性能；四、算法之间的混合，例如，Gong等人[10]将DE算法和BBO算法混合生成DE/BBO算法，有效地结合了DE算法的探索能力和BBO算法的开采能力，增强了算法的优化效率.需要注意的是，现代算法改进策略已不限于单从上述某一个角度改进BBO算法，很多研究都会从几个角度同时对算法进行改进.虽然这些研究一定程度上达到了改善BBO算法的目的，却无法保证算法的性能最大化，随着社会发展，现实中要不断面临各种复杂的优化问题，对算法的优化性能发出巨大挑战，目前，BBO算法在优化性能方面依然有着可提升空间及研究意义.

算法的优化性能体现在三个方面，一是寻优能力，即能否搜索到问题的最优解或高精度的解；二是稳定性，即能否经常搜索到满意解，而非偶然事件；三是收敛速度，即能否用较少的迭代次数完成搜索.此外，在增强算法优化性能的同时还应考虑运行时间的平衡，避免以大量时间消耗为代价而得不偿失.为了增强BBO算法的优化性能，降低其运行的时间消耗，提出了一种差分迁移和趋优变异的BBO算法(DGBBO).对BBO算法的迁移算子进行改进，增强全局搜索能力，平衡探索和开采，对BBO算法的变异算子进行改进，加快收敛速度，又从多个角度降低算法的计算复杂度，减少运行时间.在一组常用的基准函数上进行仿真实验，对比其它state-of-the-art算法，对DGBBO算法的优化性能和运行速度进行了验证.

2 生物地理学优化算法

在生物地理学理论中，一个种群由若干栖息地组成，栖息地通过生存适应度指数(Habitat Suitability Index，HSI)描述其生存环境的优劣，影响生存适宜度指数的因素称为生存适宜度指数变量(Suitability Index Variables，SIVs)，其中每一个SIV都是一个独立变量.

BBO算法是受生物地理学理论启发而提出的，对于求解式(1)所示的d维全局优化问题，

minf(x)，x∈D

(1)

其中，D为解空间区域，用x=(x1，x2，…xd)表示该优化问题的候选解，f(x)是该候选解对应的目标函数值.

定义1. 生态系统(种群)HN由N个栖息地组成，其中，N为种群数量.

定义2. 栖息地Hi(i=1，2，…，N)的生存适宜度指数变量SIVs=(Hi(SIV1)，Hi(SIV2)，…，Hi(SIVd))，表示所求优化问题的一个候选解.

定义3. 栖息地Hi(i= 1，2，…，N)的生存适宜度指数HSI表示该候选解对应的目标函数值，与该栖息地物种数量Si成正关系.

定义4. 栖息地Hi的迁入率λi是其HSI或物种数量Si的单调递增函数，迁出率μi是其HSI或物种数量Si的单调递减函数，通常算法根据图1所示的线性迁移模型计算迁入率和迁出率，计算分别如式(2)和式(3)所示：

λi=I(1-Si/Smax)

(2)

μi=E(Si/Smax)

(3)

其中，I表示最大迁入率，E表示最大迁出率，Smax表示最大物种数量.

图1 线性迁移模型Fig.1 Linear migration model

定义5. 迁移操作Ω(λ，μ)是一个概率性运算，栖息地Hi被其它栖息执行特征迁入的概率与其迁入率λi成正比，栖息地HSI对其它执行特征迁出的概率与其迁出率μSI成正比，迁移操作可表示为式(4)所示：

Hi(SIVj)←HSI(SIVj)

(4)

其中，Hi为迁入栖息地，HSI为迁出栖息地，j=1，2，…d.

BBO算法的迁移算子的伪代码如算法1所示，其中，rand表示均匀分布在(0，1)之间的随机实数.

算法1. 迁移算子

01 fori= 1 toNdo

02 forj= 1 toddo

03 ifrand<λithen

04 用轮赌选择法选出迁出栖息地HSI

05 通过式(4)更新Hi(SIVj)

06 end if

07 end for

08 end for

需要注意的是，通过迁移算子更新之后的Hi(SIVj)不能越出解的可行区域D.

定义6. 变异操作M(λ，μ)是一个概率性运算，基于栖息地存在的先验概率对栖息地生存环境随机性改变，栖息地Hi的变异率mi计算如式(5)所示：

mi=mmax(1-Pi/Pmax)

(5)

其中，mmax表示最大变异概率；Pi是物种数量概率，其迁入率和迁出率存在的关系如式(6)所示，Pmax= max(Pi)：

(6)

变异算子的伪代码如算法2所示.

算法2. 变异算子

01 fori=1 toNdo

02 通过式(5)计算变异率mi

03 forj=1 toddo

04 ifrand

05 在取值范围内用随机生成的SIV取代Hi(SIVj)

06 end if

07 end for

08 end for

同样的，通过变异算子更新之后的Hi(SIVj)不能越出解的可行区域D.

定义7. 种群更新操作Ψ(N，d，λ，μ，Ω，M)是将一次优化迭代更新后的所有栖息地组成的新种群用于下一次优化迭代.BBO算法的总流程如算法3所示,其中，MaxDT表示最大迭代次数.

算法3. BBO算法总流程

01 设置相关参数，随机初始化种群

02 评价每个栖息地的HSI，按HSI由优至劣对种群排序

03 fort= 1 toMaxDTdo

04 计算每个栖息地的迁入率和迁出率，保留精英栖息地

05 通过算法1的迁移算子更新种群

06 通过算法2的变异算子更新种群

07 对每个栖息地进行越界限制

08 评价每个栖息地的HSI，按HSI由优至劣对种群排序，用精英栖息地替换较差的栖息地

09 按HSI由优至劣对每个栖息地排序

10 end for

11 输出最优解

3 改进的生物地理学优化算法

3.1 算法改进动机

鉴于BBO算法的迁移算子采用式(4)所示的直接取代式迁移操作，虽然提供了一定的局部搜索能力，但迁移方式单一，栖息地间共享的信息少，可搜索位置局限，又由于现代群智能优化算法在改进时，若一味地追求全局搜索或者局部搜索单方面的提升，反而不能解决复杂优化问题，需考虑二者的平衡，整体上提高算法的优化性能，故将两种差分扰动操作与原迁移操作有机融合，形成差分迁移算子，有效地结合了原迁移操作的局部搜索和差分扰动操作的全局搜索，整体上提升算法的全局搜索能力并平衡了探索和开采.

鉴于BBO算法的变异算子采用算法2第05行所示的随机方向的变异操作，可能破坏优质解，导致种群退化，故将原变异操作去掉，克服上述缺陷，为弥补变异操作的缺失，将趋优操作融入原变异算子中，提升了算法的收敛能力.鉴于BBO算法一些计算过程繁琐，故从多个角度降低了算法的计算复杂度.利用算法的已有的局部搜索能力并对全局搜索能力进行提升有利于增强算法的寻优能力，对于算法探索和开采的平衡有利于强化算法的稳定性，对于算法收敛能力的提升有利于加快收敛速度，对于算法计算复杂度的降低有利于降低运行的时间消耗，最终得到具有优秀优化性能且运行时间较少的改进算法.

3.2 差分迁移算子

DE算法是一个知名的进化算法，其优化原理是根据当前种群中个体间的距离和方向信息，通过差分计算引导种群搜索最优解[3].DE算法具有优秀的全局搜索能力，其中起到关键作用的差分思想被很多其它改进算法所借鉴.

对于BBO算法的迁移算子，将式(7)和式(8)所示两种差分扰动操作与原迁移操作有机融合，形成差分迁移算子.

Hi(SIVj)←Hi(SIVj)+α*(Hrn1(SIVj)-Hrn2

(SIVj)+Hrn3(SIVj)-Hrn4(SIVj))

(7)

Hi(SIVj)←Hi(SIVj)+α*(Hbest(SIVj)-

Hi(SIVj)+Hrn1(SIVj)-Hrn2(SIVj))

(8)

其中，α是缩放因子，Hbest当前迭代种群中最优的栖息地，Hrn1、Hrn2、Hrn3和Hrn4是随机选择的4个栖息地，满足rn1、rn2、rn3、rn4、i∈[1，N]且rn1 ≠rn2 ≠rn3 ≠rn4 ≠i.

由式(7)可以看出，差分扰动操作将4个随机选择的栖息地同一维SIV通过差分计算得到差分向量，将差分向量赋予权值，加到栖息地Hi的相应SIV上，从而实现对该SIV值的扰动，生成差分SIV.差分扰动可以使栖息地之间共享更多样化的信息，增加了种群多样性.式(8)的原理与式(7)类似，两种不同的差分扰动操作同时使用是为了确保足够的种群多样性.

缩放因子α是用来调整差分扰动范围的参数，两种差分扰动操作均采用了指数缩放因子，避免缩放因子参数设置步骤，并增加算法的可操作性，其计算如式(9)所示：

α=randβ

(9)

其中，β是指数参数.

除了两种差分扰动操作外，对于在差分迁移算子中同时融入的原直接取代式的迁移操作不做修改，但对迁出栖息地的选择，采用了榜样学习法替换轮赌选择法[11]，有利于大幅降低算法计算复杂度.

差分迁移算子的伪代码如算法4所示.

算法4. 差分迁移算子

01 fori=1 toNdo

02 通过式(9)计算缩放因子α

03 forj=1 toddo

04 ifrand<λithen

05 用榜样学习法选出迁出的栖息地HSI

06 通过式(4)更新Hi(SIVj)

07 else

08 ifrand<0.5 then

09 通过式(7)更新Hi(SIVj)

10 else

11 通过式(8)更新Hi(SIVj)

12 end if

13 end if

14 end for

15 end for

由于差分迁移算子融入了原直接取代式迁移操作，故其具有一定的局部搜索能力，又由于差分扰动操作增加了种群多样性，故相较于原迁移算子整体上提升了全局搜索能力，两种能力的结合也使得算法的探索和开采得以平衡.

3.3 趋优变异算子

对于BBO算法的变异算子，去掉了其随机方向的变异操作，从而克服了可能破坏优质解的缺陷，又融入了式(10)所示的趋优操作弥补变异操作的缺失，形成趋优变异算子.

Hi(SIVj)←Hbest(SIVcn)，cn=ceil(rand*d)

(10)

由式(10)可以看出，变异栖息地Hi的SIV直接接受当前迭代种群中最优的栖息地Hbest的随机一个SIV，从而可以向Hbest方向迅速收敛.通常Hbest是当前迭代种群中最接近全局最优解的栖息地，故趋优操作实质是使所有变异栖息地向最优解位置迅速聚集，而采用随机的SIV可以防止种群中出现大量相似的栖息地，避免算法陷入局部最优.

此外，趋优变异算子采用线性降方法计算栖息地的变异率，如式(11)所示：

mp=mpmax-(mpmax-mpmin)*(t-1)/MaxDT

(11)

其中，mp是变异率，t是当前迭代次数，mpmax和mpmin分别是mp取值的上界和下界.由式(11)可知，随着迭代次数t线性增加，变异率mp的值逐渐降低.在算法优化过程前期，mp的值较大，更倾向于执行趋优变异算子，较差的栖息地可以向当前迭代种群中最优的栖息地方向迅速收敛；在算法优化过程后期，大量栖息地聚集在某一区域，mp的值较小，执行趋优变异的概率较小，一定程度上避免了优质解被破坏.相较于原变异率计算法方法，线性降方法计算变异率还降低了计算复杂度.

趋优变异算子的伪代码如算法5所示.

算法5. 趋优变异算子

01 通过式(11)计算变异率mp

02 fori=1 toNdo

03 forj=1 toddo

04 ifrand

05 通过式(10)更新Hi(SIVj)

06 end if

07 end for

08 end for

3.4 DGBBO算法总流程

除上述改进外，还将BBO算法的精英保留策略换成了贪婪选择法[11]，在保证栖息地HSI总是有效的前提下，将迁入率计算步骤移至算法的迭代循环外[12]，这些改进能够进一步降低了计算复杂度，最终形成了DGBBO算法.

总的来说，DGBBO算法在BBO算法的基础上，整体提升了全局搜索能力，平衡了探索和开采，加快了收敛速度，大幅度降低了计算复杂度.DGBBO算法总流程伪代码如算法6所示.

对比DGBBO算法和BBO算法，它们的相同点在于均采用迁移和变异两个主要算子更新种群.它们的不同点分为三方面：1.从算法3和算法6的对比中可以看出，总流程上DGBBO算法的栖息地迁入率计算步骤在迭代循环外，采用榜样学习法选择迁出栖息地从而不需要计算迁出率，采用贪婪选择法从而每次迭代需对栖息地排序一次，而BBO算法的迁入迁出率计算步骤均在迭代循环内，采用精英保留机制每次迭代需对所有栖息地排序两次；2.从算法1和算法4的对比中可以看出，DGBBO算法的差分迁移算子包含三种不同的操作，分别是直接取代式的迁移操作和两种差分扰动操作，不仅对执行迁入的栖息地进行了更新，还对未执行迁入的栖息地进行了更新，而BBO算法的迁移算子只采用直接取代式的迁移操作更新执行迁入的栖息地，对不执行迁入的栖息地不更新；3.从算法3和算法5的对比中可以看出，DGBBO算法的趋优变异算子其变异率的计算步骤在种群循环外，即每次迭代所有栖息地都使用同一变异率，而BBO算法的变异算子其变异率计算步骤在种群循环内，每个栖息地都拥有各自的变异率且这些变异率各不相同.

表1 基准函数Table 1 Benchmark functions

算法6. DGBBO算法总流程

01 设置相关参数，随机初始化种群

02 评价每个栖息地的HSI，按HSI由优至劣对种群排序

03 计算每个栖息地的迁入率

04 fort= 1 toMaxDTdo

05 通过算法4的差分迁移算子更新种群

06 通过算法5的趋优变异算子更新种群

07 对每个栖息地进行越界限制

08 评价每个栖息地的HSI，按HSI由优至劣对种群排序，执行贪婪选择法更新种群

09 end for

10 输出最优解

4 仿真实验与分析

为验证DGBBO算法的优化性能和运行速度，在一组常用基准函数上进行了仿真实验，这些基准函数如表1所示.所有实验均在操作系统为 Windows 7、CPU为主频3.10GHz和内存为4GB的PC上进行的，编程语言采用MATLAB R2014a.

4.1 DGBBO算法自身对比实验

第一组实验用DGBBO算法与其变体算法进行对比，这些变体算法包括：DRBBO算法，即差分迁移和原始变异的BBO算法；EGBBO算法，即榜样选择法的原始迁移和趋优变异的BBO算法；RGBBO算法，即轮赌选择法的原始迁移和趋优变异的BBO算法.

4种算法分别在50维f1-f15和200维f16上进行了测试.为公平起见，统一设置每种算法的种群数量N= 20，最大迭代次数MaxDT=4000，最大迁入和迁出率分别为I=1，E=1，变异率mp的取值上限和下限分别为mpmax=0.03，mpmin=0.001，指数参数β=4.为避免偶然事件，4种算法在每个基准函数上分别独立运行50次，取统计得到平均值(Mean)、标准差值(Std)和运行时间(Time/s，s表示单位为“秒”)用于对比.4种算法的结果对比如表2所示，其中，加粗的为最优结果.

对比DGBBO算法和DRBBO算法可以看出，拥有差分迁移算子的DGBBO算法获得平均值和标准差值总是更优，且在一些基准函数上优势巨大，运行时间上两者没有明显差距.对比DGBBO算法和EGBBO算法可以看出，拥有趋优变异算子的DGBBO算法获得的平均值和标准差值总是更优，且在一些基准函数上优势巨大，但运行时间更长.对比EGBBO算法和RGBBO算法可以看出，两种算法获得的平均值和标准差值都不理想，但在运行时间上，EGBBO算法优势明显.总的来说，DGBBO算法获得的的平均值和标准差值总是4种算法中最优的，EGBBO算法的运行时间总是4种算法中最短的.

表2 DGBBO算法与其变体算法的对比Table 2 Comparisons among DGBBO and its variants

4种算法在16个函数上的收敛曲线对比如图2所示，其中，横坐标是迭代次数，纵坐标是平均优化结果.从图2可以看出，除了DGBBO算法外，其它算法都出现了过早收敛，在f6、f8、f9和f10上，DGBBO算法用了很少的迭代次数便搜索到了函数最优解，特别是在f6上，几乎看不到DGBBO算法的收敛曲线，其快速的收敛速度得以体现.

第一组实验的结果对比表明，榜样学习法对于算法优化性能影响不明显，但对降低算法运行时间有明显作用，差分迁移算子和趋优变异算子对增强算法的优化性能，加快算法的收敛速度作用明显，虽然差分迁移算子的使用增加了算法的运行时间，但综合考虑优化性能和运行时间的平衡，DGBBO算法的结果是最可取的，从而也证明了本研究对BBO算法的这3项改进都是不可或缺的.

4.2 DGBBO算法与同类算法对比实验

第二组实验用DGBBO与state-of-the-art同类进行对比，由于BBO算法适用于离散型优化问题，在连续型优化问题上性能较差，而本文实验仿真的是连续型优化问题，故没有用BBO算法作为对比算法，而使用在连续型优化问题上表现更优的BBO改进及混合算法用于对比.

图2 DGBBO与其变体算法的收敛曲线Fig.2 Convergence curve of DGBBO and its variants

首先，用DGBBO算法对比LBBO算法[13].选取LBBO算法进行对比是因为该算法具有很强的竞争性.

2种算法分别在不同维度的16个基准函数上进行实验，它们的最大迭代次数MaxDT动态调整以适应不同维度的优化问题，为公平起见，它们种群数量统一设置为N= 20，DGBBO算法的其它参数不变，LBBO的其它参数设置同其相应参考文献，2种算法在每个基准函数上独立运行50次,对比结果如表3所示.

从表3可以看出，大多数情况下，DGBBO算法比LBBO算法获得了更优的平均值和标准差值，在一些基准函数上，DGBBO算法的优势巨大.例如，在 100维f1上，DGBBO算法的平均值和标准差值精度分别达到1e-162和1e-162，而LBBO算法只分别达到1e-27和1e-26.在运行时间的对比中，DGBBO算法的运行时间总是比LBBO算法更少.

其次，用DGBBO算法与BBOFWA算法[14]、POLBBO算法[15]和PRBBO算法[16]进行对比.这三种算法都是近几年提出的BBO改进及混合算法，具有很强的竞争性.

对比算法的结果分别取自其相应的参考文献，由于不同文献对算法的测试函数集不同，故只选取4种算法在相同维度的相同基准函数上获得的结果进行对比，为使对比结果可靠，DGBBO算法的最大函数评价次数(MNFE)总是小于对比算法.4种算法的结果对比如表4所示，其中，NA表示原文献未提供该数据.

从表4可以看出，在MNFE更少的前提下，DGBBO算法在14个基准函数中获得了11次最优或与其它算法并列最优的平均值及10次最优或与其它算法并列最优的标准差值.在f7和f12上，虽然DGBBO算法获得的结果不如POLBBO算法和PRBBO算法，但差距很小.在f14上，DGBBO算法与PLOBBO算法和PRBBO算法获得了相同的平均值，在标准差值上略微不如另外两种算法.在f5上，DGBBO算法的结果较POLBBO算法和PRBBO算法差距较大，但是另外两种算法的MNFE约是DGBBO算法的10倍.

第二组实验结果表明，DGBBO算法与state-of-the-art同类算法相比，其结果是很可取的.

4.3 DGBBO算法与其它类算法对比实验

第三组实验用DGBBO算法与state-of-the-art其它类算法进行对比，选取的对比算法有SLPSO算法[17]、DELLU算法[18]和ILABC算法[19]，选取这些算法对比是因为它们包含了近年来提出的ABC改进算法、PSO改进算法和DE改进算法，具有很强竞争性，在同类算法中又具有一定代表性.

表4 DGBBO算法与同类算法的对比(d=30)Table 4 Comparisons among DGBBO and the same types of algorithms(d=30)

对比算法的结果分别取自其相应的参考文献，只选取4种算法在相同维度的相同基准函数上获得的结果进行对比，DGBBO算法的MNFE总是小于或近似等于其它算法.4种算法的结果对比如表5所示.

从表5可以看出，DGBBO算法在所有情况下获得的平均值都是最优或者与其它算法并列最优的，其标准差值虽然在f13、f14和f16上不如其它算法，但在MNFE远小于其它算法的前提下也达到了很高的精度.

第三组实验结果表明，DGBBO算法与state-of-the-art其它类算法相比，其结果依然是很可取的.

4.4 DGBBO算法实验结果讨论

以表3结果为例，对DGBBO算法进行讨论.观察DGBBO算法获得的平均值可以发现，不论在30维、50维还是100维基准函数上，其在多数情况下都获得了高精度的结果，例如，在f1和f3上，DGBBO算法的结果精度达到了三位数，在f6、f8、f9和f10上，DGBBO算法搜索到了函数最优解，相比之下，LBBO算法的结果精度则不理想，从而证明了DGBBO算法的寻优能力显著，在多数优化问题上能够搜索到优化问题的最优解或高精度解.

当基准函数维度的增加时，问题的复杂度进一步增加，通常一个算法在处理更高维度的优化问题时，其解的精度会有所下降.横向观察DGBBO算法在不同维度的同一基准函数的结果发现，除了f5外，DGBBO算法在所有基准函数上的结果精度都没有明显下降，由于测试更高维基准函数时增加了最大迭代次数，所以在f1、f2、f3、f4、f6、f8、f9，f10、f13、f14、f15和f16上，DGBBO算法的结果保留了高精度或得到了更高的精度，相比之下，LBBO算法在多数情况下的结果精度有所下降，从而再次证明DGBBO算法的寻优能力显著，还证明了其具有较强的稳定性，在面对不同复杂度的优化问题时能够保持较好的寻优能力.表3中DGBBO算法获得的标准差值同样体现出了其较强的稳定性.

对于DGBBO算法的收敛速度已在图2的收敛曲线对比中进行讨论，本节不再重复论述.

综上所述，DGBBO算法在寻优能力、稳定性和收敛速度上表现优良，其优秀的优化性能得以体现.

4.5 DGBBO算法计算复杂度分析

在相同的运行环境下，影响算法运行时间的因素主要有二，一是最大函数评价次数，这是由于算法在优化过程中，对候选解的函数评价过程最为耗时；二是算法自身流程的复杂程度.本文在运行时间的对比实验中，设置所有算法具有相同的种群数量和最大迭代次数，使它们的MNFE近似相等，故DGBBO算法运行速度快的原因不在于MNFE，而是由于在流程设计中从多个角度降低了计算复杂度.

参照BBO算法，对DGBBO算法的计算复杂度进行对比分析.对于算法的总流程，DGBBO算法将栖息地迁入率计算移至迭代循环外，又因为在交叉迁移中采用榜样学习法选择迁出栖息地，不需要栖息地的迁出率，因此在整个算法优化过程中，只需要对所有栖息地的迁入率计算1次，其计算次数为N，而BBO算法每次迭代都需要对所有栖息地的迁入率和迁出率进行计算，其计算次数为2*N*MaxDT，故DGBBO算法大幅降低了计算复杂度.BBO算法每次迭代都采用的是精英保留策略更新种群，需对所有栖息地排序2次，若以简单排序方法为例，其计算次数为N2，而DGBBO算法采用贪婪选择法更新种群，每次迭代只需对所有栖息地排序一次，其计算次数为N2/2，再次降低计算复杂度.迁移算子的对比中，虽然DGBBO算法的差分迁移算子较BBO算法的原迁移算子多出一些判断步骤，但没有增加额外的循环步骤，BBO算法采用轮赌选择法选择迁出栖息地，其计算次数大于1小于N，平均计算次数为(1+N)/2，而DGBBO算法采用的榜样学习法选择迁出栖息地，其计算次数为1，整体上DGBBO算法降低了计算复杂度.在变异算子的对比中，DGBBO算法采用线性降方法计算变异，每次迭代只需要对变异率计算1次，而BBO算法每次迭代需要对每个栖息地都计算变异率，计算次数为N，且变异率计算需要先计算栖息地物种数量概率，其计算量较大，故DGBBO算法进一步大幅降低计算复杂度.

表5 DGBBO算法与其它类算法的对比(d=30)Table 5 Comparisons among DGBBO and the other types of algorithms(d=30)

综上所述，DGBBO算法在BBO算法的基础上，从多个角度降低计算复杂度，从而达到了减少了算法运行时间的目的，表3中算法的运行时间对比也验证了该结论.

4.6 实验总结

为验证DGBBO算法的优化性能和运行速度，在一组常用基准函数上进行大量仿真实验.实验结果证明了DGBBO算法中3项主要的改进都是不可或缺的，又通过与state-of-the-art同类型及不同类型算法的结果进行对比、讨论及分析，表明了DGBBO算法寻优能力显著，稳定性强，收敛速度快，运行时间少，验证了其优秀的优化性能.

5 结束语

为了增强BBO算法的优化性能，降低其运行的时间消耗，根据算法改进动机，提出了一种差分迁移和趋优变异的生物地理学优化算法(DGBBO).将两种差分扰动操作与BBO算法的迁移操作有机融合，形成差分迁移算子，提升全局搜索能力并平衡探索和开采；将趋优操作融入到BBO算法的变异算子中，替换原变异操作，形成趋优变异算子，克服了原变异算子存在的缺陷，加快收敛速度；又从多个角度降低算法的计算复杂度.在一组常用基准函数上进行了仿真实验，与其它state-of-the-art算法进行对比，验证了DGBBO算法优秀的优化性能.下一步研究会将算法用于工程领域，处理现实中更为复杂优化问题[20].

：

[1] Liu Y，Mu C，Kou W，et al.Modified particle swarm optimization-based multilevel thresholding for image segmentation [J].Soft Computing，2015，19(5)：1311-1327.

[2] Kiran M S，Hakli H，Gunduz M，et al.Artificial bee colony algorithm with variable search strategy for continuous optimization [J].Information Sciences，2015，300：140-157.

[3] Storn R，Price K.Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces [J].Journal of Global Optimization，1997，11(4)：341-359.

[4] Simon D.Biogeography-based optimization [J].IEEE Transactions on Evolutionary Computation，2008，12(6)：702-713.

[5] Ma H.An analysis of the equilibrium of migration models for biogeography-based optimization [J].Information Sciences，2010，180(18)：3444-3464.

[6] Feng Q，Liu S，Zhang J，et al.Biogeography-based optimization with improved migration operator and self-adaptive clear duplicate operator [J].Applied Intelligence，2014，41(2)：563-581.

[7] Guo W，Wang L，Ge S S，et al.Drift analysis of mutation operations for biogeography-based optimization [J].Soft Computing，2015，19(7)：1-12.

[8] Zheng Y J，Ling H F，Wu X B，et al.Localized biogeography-based optimization [J].Soft Computing，2014，18(11)：2323-2334.

[9] Guo W，Chen M，Wang L，et al.Backtracking biogeography-based optimization for numerical optimization and mechanical design problems [J].Applied Intelligence，2016，44(4)：894-903.

[10] Gong W Y，Cai Z H，Ling C X.DE/BBO：a hybrid differential evolution with biogeography-based optimization for global numerical optimization [J].Soft Computing，2010，15(4)：645-665.

[11] Zhang Xin-ming，Yin Xin-xin，Tu Qiang.High-dimensional multilevel thresholding based on BBO with dynamic migration and salt & pepper mutation [J].Optics and Precision Engineering，2015，23(10)：2943-2951.

[12] Zhang Xin-ming，Tu Qiang，Yin Xin-xin.Efficient BBO algorithm based on Hybrid migration and its application in image segmentation [J].Journal of Frontiers of Computer Science and Technology，2016，10(10)：1459-1468.

[13] Simon D，Omran M G H，Clerc M.Linearized biogeography-based optimization with re-initialization and local search [J].Information Sciences，2014，267：140-157.

[14] Zhang B，Zhang M X，Zheng Y J.A hybrid biogeography-based optimization and fireworks algorithm [C].IEEE Congress on Evolutionary Computation (CEC)，2014：3200-3206.

[15] Xiong G，Shi D，Duan X.Enhancing the performance of biogeography-based optimization using polyphyletic migration operator and orthogonal learning [J].Computers & Operations Research，2014，41(1)：125-139.

[16] Feng Q，Liu S，Zhang J，et al.Improved biogeography-based optimization with random ring topology and Powell′s method [J].Applied Mathematical Modelling，2016，41：630-649.

[17] Cheng R，Jin Y.A social learning particle swarm optimization algorithm for scalable optimization [J].Information Sciences，2015，291(6)：43-60.

[18] Zhou Xiao-gen，Zhang Gui-jun，Hao Xiao-hu，et al.Differential evolution algorithm based on local lipschitz underestimate supporting hyperplanes [J].Chinese Journal of Computers，2016，39(12)：2631-2651.

[19] Gao W F，Huang L L，Liu S Y，et al.Artificial bee colony algorithm based on information learning [J].IEEE Transactions on Cybernetics，2015，45(12)：2827-2839.

[20] Xu X，Shi X W.Multi-objective based spectral unmixing for hyperspectral images [J].Isprs Journal of Photogrammetry & Remote Sensing，2017，124：54-69.

附中文参考文献：

[11] 张新明，尹欣欣，涂 强.动态迁移和椒盐变异融合生物地理学优化算法的高维多阈值分割 [J].光学精密工程，2015，23(10)：2943-2951.

[12] 张新明，涂 强，尹欣欣.混合迁移的高效BBO算法及其在图像分割中的应用 [J].计算机科学与探索，2016，10(10)：1459-1468.

[18] 周晓根，张贵军，郝小虎，等.一种基于局部Lipschitz下界估计支撑面的差分进化算法 [J].计算机学报，2016，39(12)：2631-2651.