高凯歌，郑向伟

（1.山东师范大学 信息科学与工程学院，山东 济南250014；2.山东省分布式计算机软件新技术重点实验室，山东 济南250014）

0 引 言

2008年，美国学者 Dan Simon在IEEE Transactions on Evolutionary Computation提出了一种新型的基于种群的仿生智能优化算法——生物地理学优化算法 （biogeographybased optimizer，BBO）。BBO算法模拟了自然界中生物种群的动态变化，即物种在栖息地上的分布、迁移、繁殖、灭绝的过程。

由于BBO的迁移算子采用已知的栖息地替换策略，所以新的栖息地的精确度受到限制，导致BBO算法收敛速度慢。另一方面，受到变异策略的影响，BBO容易陷入局部最优解，以致难以获得真正最优解。MCBBO算法从新的角度对BBO算法的两个核心算子——迁移算子和变异算子进行改进，即把中值定理应用在迁移算子，把柯西变异应用在变异算子中，提出一种基于中值迁移和柯西变异的MCBBO算法。在仿真实验中，通过四个基准函数验证了MCBBO算法更有优势：MCBBO得到的解比BBO、PSO和GA的解更加接近理论最优解，而且MCBBO算法的收敛速度更快。

1 BBO算法和相关研究

1.1 BBO算法

BBO算法思想来源于生物种群在自然界中的动态变化过程［1］。大环境是在一个小生态系统中存在多个栖息地。若是其中某个栖息地的环境十分适合生物的生存和繁殖，表示该栖息地有较高的栖息地适宜度指数；反之，则表示这个栖息地有较低的适宜度指数。与栖息地适宜度指数相关的因素有许多，每种因素的变化都会改变栖息地的环境，进而对该栖息地物种分布和迁移等产生某种程度的影响。概括说来，栖息地适宜度指数和生物种群数量的关系是：具有高适宜度的栖息地相对来说可以容纳较多的物种，具有较低适宜度的栖息地则只能容纳较少的物种。所以，栖息地的适宜度和该栖息地的物种数量成正比。

BBO算法中的术语和定义包括如下几个［2－3］。

（1）生态系统：数学模型中的最大范围。

（2）栖息地 （Hi，i＝1，2，…，n）：生态系统中包含若干栖息地，每个栖息地可被看作一个相对独立的物种生存区域。数学模型中物种之间的迁移操作是以栖息地为界的。

（3）栖息地适宜度指数 （HSI）：用数值衡量栖息地是否适合物种的生存和发展。

（4）适宜度指数变量 （SIV）：每个变量都是影响栖息地的一个因素，采用整数表示。

（5）适宜度指数向量 （SIVs）：一个采用整数编码的d－维向量表示整个优化问题的一个可行解。

（6）迁入率 （λ）：栖息地被更改的概率。

（7）迁出率 （μ）：栖息地被作为信息引入源的概率。

（8）变异率 （Pmod）：栖息地发生变异的概率。

（9）迁移算子：根据栖息地的迁入率、迁出率以及迁移策略，进行迁移操作。

（10）变异算子：根据栖息地的变异率以及变异策略，进行变异操作。

1.2 相关研究

已有不少针对BBO研究和改进。文献 ［4］提出一类基于物种迁移优化的进化算法，比较分析了SMO与其他智能算法的优缺点，其仿真实验结果表明这类算法是有价值的。文献 ［5］提出了BBO算法优化过程中可以采用4种迁移模型，并分别测试了这4中迁移模型的性能。文献［6］提出6种生物迁移模式，测试得到采用新迁移策略的BBO算法的性能得到了提高。文献 ［7］给出一种结合精英策略的BBO算法，实验结果表明对于该算法的适用问题来说，结合精英策略的BBO算法性能是有明显改进的。文献［8］将进化策略应用于BBO算法，并采用一种新的迁移拒绝方法。文献 ［9］利用DE算法的差分进化算子改进BBO算法的迁移算子，基准函数的测试结果表明改进后的算法性能同时优于DE算法和BBO算法。文献 ［10］引入对立学习机制 （OBL），提出了OBBO算法，仿真实验结果表明OBBO比BBO表现的更优秀。

总体而言，BBO算法在算法的收敛速度和摆脱局部最优的能力仍然不够理想。

2 基于中值定理和柯西变异的生物地理学优化算法

2.1 基于中值定理的迁移算子

BBO算法通过迁移算子来实现栖息地之间的信息共享，进而更新栖息地得到更大更丰富的解集合，以便优化过程结束后得到更优解。考虑到使用中值定理可以扩大信息源的范围，信息源就不会仅局限于某个已存在的解，这样理论上得到更优解的可能性就大了。下面在三维立体空间中说明中值定理扩大引入信息源的原理。

将解的形式定义为 （x，y，z）。假设A：（x1，y1，z1）已确定要进行迁移操作，B：（x2，y2，z2）则是信息的来源。若是在进行迁移操作时，仅简单的用B：（x2，y2，z2）中的变量依概率替换掉A：（x1，y1，z1）中的变量，显然得到的解集只有8个元素。现在使用 ［0，1］之间的3个随机实数：α1，α2，α3，分别作为3个对应变量的系数。依概率用α1x1＋（1－α1）x2，α2y1＋ （1－α2）y2，α3z1＋ （1－α3）z2分别替换A：（x1，y1，z1）中的变量x1，y1，z1。这样，信息的来源就不仅局限在有限的几个变量，而是有无数种可能。

2.2 基于柯西分布的变异算子

突变是指生物的生存环境在短时间内发生了急剧的变化，如由瘟疫疾病、自然灾害等原因导致栖息地环境发生彻底改变。突变操作丰富了解集合，提高了找到更优解的可能性。在原有变异算子的基础上提出一种新的、基于柯西随机数的变异算子，即在进行变异操作时得到的随机数是服从柯西分布的。

由于柯西分布函数的概率分布特性：在水平方向上越接近水平轴，变化得越缓慢。因此柯西分布可以看作是无限的，它产生一个远离原点的随机数的概率高于正态分布，所以产生的随机数有更大的分布范围。这意味着在优化过程中陷入局部极值后，利用柯西变异更有可能跳出局部极值。

对确定发生变异的栖息地Hi的状态：Xi＝ （xi，1，xi，2，……，xi，d）做 柯 西 变 异， 定 义 是：Xi＇ ＝ Xi ＋Xi＇＊Cauchy（0，1）。其 中，Cauchy （0，1）是 标 准 柯西分布。

2.3 MCBBO算法

MCBBO算法具体步骤如下：

步骤1 初始化算法参数。包括最大物种容纳数量Smax、迁移率Pmod、最大迁入率Imax、最大迁出率Emax和最大变异率Mmax。

步骤2 初始化一组栖息地向量。每个向量都是问题的一个可行解。

步骤3 根据映射关系f：SIVs—＞HSI，将每一个栖息地向量对应的SIVs映射到HSI。并判断是否满足程序终止条件，若满足则输出最优解，退出程序，否则继续步骤4。

步骤4 对于每一个栖息地，计算其迁入率和迁出率，根据结合中值定理的迁移算子修改栖息地，进行相关计算。

具体迁移过程为：①设定栖息地的全局迁移率Pmod，范围是 ［0，1］。由全局迁移率Pmod决定栖息地是否进行迁移操作，即，信息的引入。例如，我们设Pmod＝1，说明每个栖息地都会被更新。若设Pmod＝0.5，说明栖息地有一半的概率会被更改。②循环判断每个栖息地是否被选中做迁移操作。若第i个栖息地Hi被选中，利用Hi的迁入率λi判断决定Hi的栖息地向量SIVs每个变量是否发生更改。λi是 ［0，1］之间的实数，由公式λk＝Imax＊（1－k／Smax）［1］求得。③循环判断栖息地Hi的每个变量是否被选中做迁移操作。若栖息地Hi的第k个变量Hi，k已被选中，根据所有其它栖息地Hi（i！＝j）的迁出率μj，利用轮盘选择法或其它方法以决定是引入了哪个栖息地的信息。假如，得到是第j个栖息地Hj。迁出率μ是由公式μk＝Ek／Smax得到。至此，可以确定被引入信息的来源。④为了扩大解的范围，在确定了信息的来源之后，不再是用源的对应变量替换发生迁入的变量 （即Hj，k替换Hi，k），而是结合α系数－中值定理，用α1x1＋（1－α1）x2，α2y1＋（1－α2）y2，α3z1＋（1－α3）z2分别替换相应变量。

步骤5 根据柯西变异算子更新栖息地，并进行相关计算。

具体变异过程为：①设定栖息地最大变异概率Mmax。例如，Mmax＝0.005，说明所有的可行解发生突变的最大概率为0.005。②根据栖息地Hi的适宜度向量SIVs，可以得到该栖息地的相关数据，包括种群数量si。根据公式

可得到栖息地Hi种群数量为si的概s率P（si）。根据公式mi＝Mmax＊（1－P（si）／Pmax）［1］可以得到此时 Hi的变异概率mi。由mi决定Hi是否发生变异操作。③假设Hi已被选中发生变异操作。采用柯西变异算子，即用Xi′＝Xi＋Xi＊Cauchy（0，1）来替换随机得到的栖息地向量Xi″。

步骤6 转至步骤3进行下一次迭代过程。

3 仿真实验

3.1 实验准备

仿真实验部分对4种仿生智能优化算法：MCBBO、基本BBO、PSO和GA进行比较，通过4个代表性的测试函数验证MCBBO算法的性能。为了提高实验结果的可靠性，选取了在函数极值个数、极值点分布方面有代表性的4个函数作为测试函数：Sphere、Rosenbrock、Fletcher、Griewank四个函数，分别记为1—4号函数。

算法相关参数设置。种群大小，n＝20；解向量维度，d＝20；迁移率，Pmod＝1；最大突变概率，Mmax＝0.005；一次实验中算法迭代次数，Generation＝50。

3.2 实验结果

在Matlab7.6中完成仿真实验。表1是进行100次Monte Carlo实验得到的结果，包括极小值、平均值、最大极小值。最小值代表了算法的最优性能，平均值量化了算法的平均性能，最大极小值则是反映了算法求极小值的最坏性能。其中加粗显示的数据是比较4种优化算法结果得到的最优解。图1和图2分别是得到每种算法基于Fletcher函数和Griewank函数，得到平均极小值的优化过程曲线。

3.3 结果分析

由表1可知，经过100次Monte Carlo实验的验证，在求四个测试函数的极小值、平均极小值和最大极小值的算法性能上，MCBBO优于PSO和GA。同时，MCBBO算法在求函数Sphere、Rosenbrock和Griewank的极小值，求函数Sphere、Rosenbrock和Griewank的平均极小值，求函数Rosenbrock、Fletcher和Griewank的最大极小值上优于基本BBO算法。基本BBO算法只在求Fletcher函数的极小值，求Fletcher函数的平均极小值，求Sphere函数的最大极小值上略有优势。所以，采用MCBBO算法求解4种测试函数，相较于其它算法更加接近理论上的最优极值。

表1 算法极值 （A：algorithm V：value F：function）

由图1和图2可知，MCBBO算法的收敛过程曲线比其它算法的收敛过程更稳定，收敛速度也更快。

以上两点结论表明，将中值定理应用到迁移算子，将柯西变异应用到变异算子确实在一定程度上提高了BBO算法的性能，所以MCBBO算法是有效的。

4 结束语

本文通过将中值定理应用到BBO算法的迁移算子、将柯西变异应用到变异算子，改进基本BBO算法，提出MCBBO算法。MCBBO算法希望把迁移算子结合中值定理从而扩大引入信息的来源，将变异算子结合柯西变异以达到即使在优化过程中一时陷入局部最优也能尽快跳出局部最优目的。在Matlab7.6中通过4个测试函数进行的仿真实验结果显示，与基本BBO、PSO、GA相比较，无论在获得最优极值和多次Monte Carlo实验得到的平均值与理论上最优极值的相近程度上，还是算法的收敛速度上，MCBBO算法都更有效。

目前，MCBBO算法还有待进一步研究完善。包括，在实现上是受某些条件限制，选择采用的迁移模型是最简单、最利于实验实现的线性模型；对一些参数值的设定只是确定它在某个合理有效的范围内，并不能保证这里所设定的参数数值能最大限度的发挥算法优势。

［1］DAN Simon.Biogeography－based optimization ［J］.IEEE Transactions on Evolutionary Computation，2008，12 （6）：702－713.

［2］ZHANG Jianke.Research on optimization algorithm for biogeography ［J］.Computer Engineering and Design，2011，32 （7）：2497－2500 （in Chinese）. ［张建科.生物地理学优化算法研究 ［J］.计算机工程与设计，2011，32 （7）：2497－2500.］

［3］WANG Cunrui，WANG Nannan，DUAN Xiaodong，et al.Survey of biogeography－based optimization ［J］.Computer Science，2010，37 （7）：34－38 （in Chinese）.［王存睿，王楠楠，段晓东，等.生物地理学优化算法综述 ［J］.计算机科学，2010，37 （7）：34－38.］

［4］MA Haiping，CHEN Zidong，PAN Zhangxin.A kind of evolutionary algorithm optimization based on the migration of species［J］.Control and Decision，2009，24 （11）：1620－1624 （in Chinese）.［马海平，陈子栋，潘张鑫.一类基于物种迁移优化的进化算法 ［J］.控制与决策，2009，24 （11）：1620－1624.］

［5］MA Haiping，CHEN Xiaolei.Equilibrium species counts and migration model tradeoffs for biogeography－based optimization［C］／／Shanghai，P.R.China：48th IEEE Conference on Decision and Control，2009：3306－3310.

［6］MA Haiping.An analysis of the equilibrium of migration models for biogeography－based optimization ［J］.Information Sciences，2010，180 （18）：3444－3464.

［7］Dan Simon，Mehmet Ergezer，Dawei Du.Population distributions in biogeography－based optimization algorithms with elitism ［C］／／San Antonio，TX，USA：Proceedings of the IEEE International Conference on Systems Man and Cybernetics，2009：991－996.

［8］DU Dawei，DAN Simon，Mehmet Ergezer.Biogeography－based optimization combined with evolutionary strategy and immigration refusal ［OL］. ［2012－06－03］.http：／／embeddedlab.csuohio.edu／BBO／BBO＿Papers／mbbo.pdf.

［9］GONG Wenyin，CAI Zhihua，Charles X Ling.DE／BBO：A hybrid differential evolution with biogeography－based optimization for global numerical optimization ［OL］.［2012－06－03］http：／／embedded lab.csuohio.edu／BBO／BBO＿Papers／Gong2.pdf.

［10］Ergezer M，Simon D，DU Dawei.Oppositional biogeographybased optimization ［C］／／San Antonio，Texas，USA：IEEE International Conference on Systems Man and Cybernetics，2009：1009－1014.