多目标的混合生物地理学优化算法研究

张丹丽，高彦杰

（上海电力大学电子与信息工程学院，上海 200090）

多目标优化是指目标函数在两个以上且不同目标不能进行比较的问题。在实际生活与科学应用中，多目标优化的问题（MOPs）随处可见。这些目标的优化之间有时会相互产生抵触，致使一个子目标的更新或者修复会导致另一个子目标的性能被破坏。MOPs 解表现为一组折中解，即为Pareto 最优解。进化算法（MOEAs）以其搜索的全局解逐渐成为解决MOP 问题的有效工具。

BBO 算法是美国学者Simon 基于生物地理学理论，于2008 年提出的一种群智能优化算法[1]。BBO 算法模拟了自然界物种在不同栖息地之间的迁移行为以及栖息地自身生态环境的变异现象。栖息地通过迁移信息的互换以及共享，通过变异改变生存环境，因此，BBO 算法已经引起了学术界学者广泛的兴趣，但关于BBO 应用于MOPs 的研究却很少。

本文提出了一种生物地理学多目标优化算法来求解MOPs。在该算法中，将BBO 与NSGA-II[2]结合，采用种群的非支配可行解以及拥挤距离对个体进行综合评价；然后提出了改进的迁移算子，增强其多样性，通过与经典的NSGA-II、MOEA/D、MOPSO 算法[2-4]进行比较，所得结果表明了所提算法的有效性。

1 多目标进化的概念

以最小化为例的MOPs 可以用表达式（1）写成以下形式[1]：

式中，x=（x1，...xn）∈X⊂Rn是n 维的决策变量；X 是n 维的决策空间；y=（y1，...ym）∈Y⊂Rm是m 维的目标向量；Y是m 维的目标空间；F（x）定义为由决策空间向目标空间映射的函数。

2 基于生物地理学优化的多目标优化算法

BBO 算法是通过模拟种群的物种迁移实现一个寻优的过程。其中，栖息地（Habitat）为优化问题的一些可能解，而栖息地指数变量（suitability index variable，SIV）则代表的是解变量，栖息地的好坏程度则是适应度指数（habitat suitability index，HSI）表示的[1]。

由于BBO 算法自身不具有处理MOPs 的能力，本文则建立了针对于BBO 算法的多目标的优化模型。首先，对于栖息地适应度指数进行了重新定义，将它与经典的进化的多目标算法NSGA-II[2]框架结合。因为原BBO 的进化策略以及它的改进方法只能适用于单目标优化问题，并不能充分满足多目标优化的需求。下面为栖息地适应度指数的重新定义。

2.1 栖息地适应度指数的确定机制

在SOPs 中，BBO 中的HSI 则被认为是一个相当于对应优化问题的目标函数。然而，与单目标优化不同的地方就是，多目标优化不仅包含只有唯一一个解，是使用一组折中解Pareto 的非支配解集来实现平衡每个目标。所以，先前关于HSI 的确定和计算方法不能再广泛应用于MOBBO 中，我们可以通过个体的Pareto 的支配关系对其HSI 重新进行定义。

本文采用与NSGA-II[2]相同的适应度评价方法，计算个体的适应度。在计算个体的的适应度时，不仅考虑支配它的个体，并用他们之间的距离计算拥挤距离，利用拥挤距离修改每一个个体的适应度。

2.2 迁移算子

在BBO 中，有两种类型的算子被认为是主要的：一种是变异算子，另一种类型就是迁移算子。文中的迁移算子是BBO 迁移算子的一个推广。随着迭代次数的增加，解Hi比解Hj更合适。解决方案不仅受好的解决方案的影响且受解决方案本身的影响，避免种群陷入局部收敛，增强了种群的多样性。修改后的迁移公式可以定义为：

其中，Hi是迁入岛屿，Hk是迁出岛屿，Hi（j）是第i 个解的第j 维，上式方程意味着解Hi和Hk改变了解Hi的特征。换句话说，迁移后的新解决方案由两个组件组成：从自身迁移功能和另一个解决方案。特征从自身以及另一个解决方案迁移。

2.3 变异算子

在BBO 中，变异操作将被随机生成新的解集去代替。其会影响BBO 算法的搜索性能，将DE 合并到单目标优化问题的迁移过程中。我们的算法在变异过程中加入了DE。该算法在最优解附近进行调整，从而找到非支配解。在MOBBO 中，通过结合DE 对变异算子进行修改，得到新的可行解。根据下式产生突变个体：

Hi（j）=Hi（j）+c1*（Hbest（j）-Hi（j））+c1*（Hr1（j）-Hr2（j）），（3）其中Hi（j）为突变个体，c1为突变比例因子，其值通常设置为0.5。Hr1，Hr2是随机选取的两个解，Hbest（j）是当前迭代的最佳解决方案。这种突变方案倾向于增加种群间的多样性。它作为一个微调单元，有助于实现全局最优解。

3 MOBBO 的算法描述

基于生物地理学多目标优化算法（MOBBO）主要特点是通过生物迁移机制算子、变异机制算子和NSGA-II等机制来实现对不同种群的环境和优化生态更新。改进的一种迁移机制算子可以使得优秀的生物个体信息经过获取后能够得到实时共享，增强收敛性；同时采用了变异机制算子，可以进一步提高和大大改进对于群体的多样性，并极大可能地产生更优秀的个体；本文提出的MOBBO 算法具体步骤如下所示。

步骤1 初始化I、E、α、c1、c2这些参数。随机的生成N个个体，则其初始种群为H={xi，i=1，2，...N}。

步骤2 利用NSGA-II，计算每个个体的适应度H（xi）=（H1（xi），H2（xi），...Hm（xi）），并确定当前H 中的非支配个体。

步骤3 判断是否满足终止条件。若满足终止条件，则转到步骤6，否则继续步骤4。

步骤4 根据迁入率λi和迁出率μi，按式（2）和（3）对个体进行迁移和变异操作，产生新的种群H'。

步骤5 合并H 和H'作为父代种群H，转到步骤2。步骤6 输出非支配种群Hn。

4仿真实验与结果分析

为了对本文所提出的MOBBO 算法对于如何解决MOPs 的有效性问题进行了验证，将其结果与NSGA-II、MOEA/D、MOPSO 这三种类型的MOEAs 在两个目标ZDT和三个目标DTLZ 的测试问题上的结果进行了实验分析对比。MOBBO 与其他三种算法的初始种群规模设置为100。MOBBO 中I=E=1，α=0.9，c1=c2=0.5。其余三种算法设置参考文献[2-4]。

4.1 性能评价指标

本文采用世代距离指标评价[2]标准来测试MOBBO的性能。

其中，nPF为近似Pareto 前沿的解的数目；di为近似Pareto前沿上第i 个解到理想Pareto 前沿之间的最小欧式距离。GD 越小，表明近似Pareto 前沿解集越逼近理想Pareto 前沿面，算法收敛性越好[2]。

4.2 结果分析

图1 中（a）～（d）给出了MOBBO 算法对ZDT1-ZDT4系列测试函数的理想Pareto 解的近似；图中（e）、（f）给出了对DTLZ1-DTLZ2 系列测试函数的理想Pareto 解的近似。可以更加直观地看出该算法求解多目标的性能。该算法对于ZDT1-ZDT4 均能从分布上收敛到真正的Pareto前沿，且它的分布性和收敛性良好，对于DTLZ 系列的两个被用来进行测试的函数，该算法中MOBBO 解集尽管它们都能在实践中收敛并达到真正的Pareto 前沿，但其中的分布性相对比较差。

图1 MOBBO 对ZDT 和DTLZ 系列测试函数所得Pareto 前沿

表1 4 种算法分别用于测试函数ZDT 和DTLZ 下的GD 指标

表1 给出MOBBO 及3 种算法进行ZDT 和DTLZ 测试函数的实验结果，包括平均值（含在括号外）和标准差（含在括号内）。由表1 可以看出算法MOBBO 与3 种经典算法相比，MOBBO 具有一定的优势。

5 结束语

鉴于目前多目标优化算法所存在的求解复杂多目标优化问题时存在的收敛性较差等问题。本文提出了一种生物地理学优化算法MOBBO。首先，该算法将BBO 本身的机制与NSGA-II 模型相结合，构建了一个适用于BBO的MOEAs 模型。其次，改进BBO 的迁移机制算子应用于群体的进化，增强了种群的多样性；最后，提出一种经过改进的变异算子，防止种群陷入局部收敛。通过在ZDT和DTLZ 测试函数上进行的仿真实践结果表明，本文所研究的MOBBO 算法相比于现有的多种MOEAs 还是具有一定竞争性的，并且能够有效地求解复杂的多目标优化问题。