基于适应度指导交配限制策略的重组算子与多目标优化研究

汪禹宏，张屹

1 引言

目前，大多数多目标进化算法仍是直接采用为单目标进化算法而设计的重组算子［1］. 事实上，单目标优化问题存在一个或多个全局最优解，而多目标优化问题则是呈现出良好规则流形结构的Pareto 解集（Pareto optimal set，PS），即连续多目标优化问题的PS 在变量空间上呈现连续分段的（m-1）维流形结构. 由于单目标优化与多目标优化最优解的拓扑结构存在本质区别，所以直接将单目标进化算法的重组算子应用于多目标进化算法，并不能保证达到最理想的求解效果［2，3］.

有研究表明，在多目标优化算法中，与相似个体进行交配可以提高新解的质量，加速算法的收敛［4，6］. 这种做法实际上增强了算法的局部搜索，局部搜索机制的成功在于它隐含地利用了PS 的连通性和正则性［7］.聚类算法［8］是一类将未知标签的数据对象集进行分组的无监督学习方法，它将数据样本划分为多个类，同一类中的个体具有较大的相似性，可以被当作是彼此的邻居个体，而不同类中的个体相似度较差. 因此，我们可以在优化算法进化的过程中利用聚类算法发掘所求解问题Pareto 解集的结构，利用此结构信息引导个体重组，从而加速算法收敛.

近年来，围绕多目标优化问题特性的利用，一些基于聚类算法的交配限制策略便成为研究热点［1，9］. 张虎等［10］为了平衡开采与勘探，用一个预定义的交配限制概率δ从同一类中挑选父代，并以1-δ的概率从所有解中挑选父代. 文献［11］中，在利用预定义交配限制概率构建交配池的基础上加入了自适应的更新策略，即根据两种父代来源在过去进化代数中的重组效用，自适应调整该参数δ的数值. 李欣［12］提出分别以β和1-β的概率从同一类个体和整个种群中挑选交配父代，每代演化之后又根据类的整体质量自适应地更新该交配限制概率. 此外，还有许多基于聚类的交配限制策略［13，14］被提出. 目前此类算法大多是采用不确定性的交配限制策略，即利用概率值去确定新解进行全局勘探或近邻重组，这种做法缺少对个体质量信息的关注. 在实际的演化过程中，每一个体在收敛性和多样性上表现不同，质量较好的个体需要更多的开采；而质量较差的个体需要更多的勘探［9，12］. 可以认为每一代所产生的非支配解拥有较高的质量，而每一代所产生的支配解的质量较差. 因此我们可以将种群结构化信息与个体质量信息相融合以提升算法性能，即引入聚类算法从全局角度发掘种群结构化信息，设置以个体质量信息为主导的交配限制策略去完成两类信息的融合.

基于以上分析，本文利用K-means聚类算法对种群进行聚类，以此来优化种群分布结构. 基于以上种群结构化信息，设计了一种适应度指导的交配限制策略（Fitness Guided Mating Restriction Strategy，FGMS）. 该策略根据适应度值这一确定性信息来判断解的支配关系，对非支配解进行近邻重组，对支配解做全局勘探. 将其集成至改进的Pareto强度进化算法（Improving the Strength Pareto Evolu‑tionary Algorithm，SPEA2）框架中，最终提出了基于Kmeans聚类适应度指导交配限制策略的多目标进化算法KFGEA（K-means clustering-based Fitness Guided mating re‑striction multi-objective Evolutionary Algorithm）. 与传统单目标重组算子相比，KFGEA利用K-means聚类算法发掘种群规则特性来引导算法搜索，弥补了其只利用个体的质量信息引导算法搜索的不足. 与现有的交配限制策略相比，本文首次提出利用确定性信息（适应度值）去指导后续的交配限制，充分考虑到了对个体质量信息的利用.

2 基于适应度指导交配限制策略的多目标进化算法

2.1 KFGEA算法框架描述

算法1 给出了KFGEA 的算法框架. 在初始化阶段，首先获得初始种群P，计算初始种群的适应度值fiti，设置初始交配限制概率β（第1 行）. 在迭代过程中，对种群P执行K-means 聚类获得若干子种群，其中类内个体具有极高的相似度，而类与类之间存在较大差异（第3 行）. 对于非支配解，以概率β设置同一类中的邻居个体构成交配池，否则以概率1-β设置全局子种群（由相互差异较大的个体构成）作为交配池；对于支配解，设置全局子种群构成交配池. 基于交配池Qi，利用差分进化算子（Differential Evolution，DE）生成当前解xi的新解yi（第5、6 行）. 新解产生过程结束以后，执行环境选择过程对种群个体进行更新（第8 行）.

2.2 K-means聚类算法

K-means 聚类算法是应用最为广泛的聚类算法之一，它是一种基于划分的聚类方法. 所谓基于划分的聚类算法，就是根据数据对象间的相似性将数据对象集划分到各个独立的子集中［8］. K-means 聚类算法将数据对象间的相似性具体化为每个对象与预先选取的各聚类中心之间的距离［15］. 该算法把每个对象分配到与之距离最近的聚类中心，以此来形成一个聚类，并通过迭代去优化平方误差准则进而改善各聚类质量.

在FGMS 中，K-means 算法用来发掘种群中解的分布结构（邻居关系）［16］. 然后基于发掘的结构，对于种群中的每个个体，根据适应度这一确定性信息去判断每个解的支配关系，进而去决定从相同类或整个种群中挑选父个体进行交配.

2.3 新解产生

算法1中SolGen操作的作用是产生新解.本文将MOEA/D-DE（Multi-Objective Evolutionary Algorithm based on De‑composition with Differential Evolution operator）算法 中新解生成方法直接应用于KFGEA，具体细节见算法2. 生成新解的过程由DE 算子生成初始解，然后对新生成的解应用多项式变异算子进行变异操作. 为了使新的解可行，根据变异操作前后的情况对新解进行修复.

2.4 环境选择

SPEA2 的适应度值由粗糙适应度值和密度估计值共同构成. 密度估算机制的引入使得SPEA2 的适应度值得以精确地反映解的支配关系，这也使其成为了一种优秀的确定性信息去指导交配池的构建.

因此，KFGEA 使用SPEA2 算法［17］中提出的强度Pareto 环境选择方法用来对种群进行更新. 算法3给出了其具体步骤，其要点如下. 将所有P中的个体复制到P'，如果种群个数超过N，采用截断操作；如果合并后的种群个数少于N则用P中的支配解填充P'. 截断操作：迭代过程中，与其它个体具有最小距离的个体被移除，如果多个个体同时拥有最小的距离，则通过比较第二最小距离打破这个平局.

算法4 描述了适应度分配的步骤. 其中，一个小的适应度fiti意味着较少的个体支配与之对应的xi，并且xi与其它个体之间存在着较大的距离. 当fiti＜1 时，则表示rfi=0，即其与之对应的xi是一个非支配解.

3 实验设置

3.1 测试函数与性能指标

本文选取了GLT1~GLT6 和LZ1~LZ9，15 个目标测试函数测试KFGEA 算法的性能. 其中，GLT 测试集有着复杂PF（Pareto Front）前沿，而LZ 测试集有着复杂PS 结构. 性能测度指标选用反转世代距离IGD（Inverted Generation Distance）［2］和超体积HV（Hyper‑volume）［18］.

（1） 反世代距离评价指标

反世代距离评价指标是一个综合性能评价指标，它主要通过计算Pareto 面上均匀点到非支配解集上最小距离的平均值，来评价算法的收敛性能和分布性能［19］. 其定义如下：

其中d(x*,P)是指点x*与算法获取的个体种群P之间的最短欧氏距离，|P*|是指P*中点的个数［20］.IGD 值越小，则代表算法的综合性能（收敛性和多样性）越好.

（2） 超体积指标

超体积表示获得的Pareto 解集与参考点所围成的超立方体的体积，以实现对算法综合性能的评价［21］. 其定义如下：

其中r=(r1,…,rm)表示目标空间中Pareto 最优解的参考点，[f(x),r],(x∊P)表示参考点和非支配个体所构成的超体积，VOL(·)表示Lebesgue 测度［20］，文献［22］指出了Lebesgue 测度的具体计算方法. HV 值越大，算法的性能越好.

3.2 参数设置

为了验证KFGEA的性能，本文选择多目标差分进化算法MOEA/D-DE［18］、改进的Pareto强度进化算法（Improv‑ing the Strength Pareto Evolutionary Algorithm，SPEA2）［17］、快速非支配排序遗传算法（Nondominated Sorting Genet‑ic Algorithm II，NSGA-II）［23］、自组织多目标进化算法（Self-Organizing Multiobjective Evolutionary Algorithm，SMEA）［10］以及基于规则模型的多目标分布估计算法（Regularity Model-based Multiobjective Estimation of Dis‑tribution Algorithm，RM-MEDA［2］作为对照算法. 所有对照算法使用原始文献中的最佳参数. 公共参数以及每种算法的具体参数设置如下：

公共参数设置：种群大小N=100；最大进化代数T=300；DE 参数F=0.5，CR=1；变异参数

MOEA/D-DE 参数设置：近邻规模大小NS=5；近邻搜索概率β=0.9；最大替换数目nr=2.

RM-MEDA 参数设置：Local PCA 聚类数目K=5；采样扩展率ϕ=0.25.

SMEA 参数设置：初始学习率τ=0.7；近邻池近邻数目H=5；交配限制概率β=0.9.

KFGEA 参数设置：聚类数目K=8；交配限制概率β=0.4.

其中SPEA2 和NSGA-II 除公共参数外不需要设置特殊参数. 所有算法均在Matlab 中编程实现.

4 对比结果

为了验证KFGEA 的性能，我们在本节分别从性能指标值统计结果、搜索效率和可视化对比三个方面分析了KFGEA 和对比算法的结果. 在搜索效率和可视化对比方面，我们选择了GLT1~GLT6 测试套件进行代表性分析.

4.1 性能指标值统计分析

表1、表2为MOEA/D-DE、SPEA2、NSGA-II、SMEA、RM-MEDA 以及KFGEA 算法分别独立计算GLT 测试集和LZ 测试集30次获得的IGD 和HV 指标值的平均值和标准差. 对于5%显著水平下Wilcoxon 秩和检验的结果，分别标记“+”，“-”和“=”，表示在相应测试题上，对照算法优于、劣于或相似于KFGEA. 上述测试问题的最优统计结果被突出显示.

表1 显示了IGD 指标的分析结果，其中MOEA/DDE、SPEA2、NSGA-II、SMEA、RM-MEDA 和KFGEA 分别取得2、0、0、2、1 和10 个最佳指标值；表2 显示了HV指标的分析结果，上述每个算法分别获得2、0、1、2、2和8 个最佳指标值. 在所有其他对照算法的30 个比较结果中，对于5%显著水平下Wilcoxon 秩和检验的表现，KFGEA 算法获得了18、24、25、22 和19 个显著优势IGD 和HV 指标.

总体来说，与对照算法相比，KFGEA 在具有复杂PF 的GLT 测试集以及具有复杂PS 的LZ 测试集上具有一定优势.

4.2 搜索效率分析

为了分析KFGEA算法的搜索效率，图1给出了所有算法对GLT 测试题进行30次独立运算后的最优IGD 指标值的演化曲线. 从图1中可以看出，对于GLT2、GLT3、GLT4、GLT5、GLT6，KFGEA均能够以最快的速度获得最小的IGD 指标值；对于GLT1，KFGEA 虽然未表现出最快的收敛速度，但是最终会获得最小的IGD 指标值. 图中对比结果显示，对于GLT 系列问题KFGEA 算法总体上具有不俗的收敛速度和最高的搜索效率.

4.3 可视化对比分析

为了进一步求证KFGEA 的性能，图2 绘制了当MOEA/D-DE、SMEA、RM-MEDA 和KFGEA 求解GLT3和GLT5时获得的平均IGD 值的代表性帕累托前沿. 图2 显示对于GLT3 测试问题，相较于对照算法KFGEA 表现出了优异的收敛性与多样性. 对于GLT5 测试问题，MOEA/D-DE 虽然收敛到了该问题真实的帕累托前沿，但其多样性较差；SMEA 没有很好地贴合真实的帕累托前沿；RM-MEDA 和KFGEA 在该问题上有着不错的表现，但显然是KFGEA具有更出色的收敛性和一致性.

秦虹路现状东西向下穿宁芜铁路，涵洞车道规模（双向两车道）与限高（仅3m）均收到较大制约，极易造成拥堵。优化后，将铁路走廊改造为城市支路和绿道，同时对该节点竖向进行优化，消除净空不足的安全隐患，也与周边地块竖向实现良好衔接。同时对新平面交叉口进行渠化设计，合理分配机动车与慢行空间路权。

表1 MOEA/D‑DE、SPEA2、NSGA‑II、SMEA、RM‑MEDA和KFGEA求解GLT和LZ测试集30次的IGD的平均值（标准差）

表2 MOEA/D‑DE、SPEA2、NSGA‑II、SMEA、RM‑MEDA和KFGEA求解GLT和LZ测试集30次的HV的平均值（标准差）

综上所述，通过性能指标值的统计比较、收敛速度和可视化比较，可以得出结论：相较于MOEA/D-DE、SPEA2、NSGA-II、SMEA 和RM-MEDA，KFGEA 对于PS或PF 形状复杂的MOPs具有最佳的解性能.

图1 MOEA/D-DE,SPEA2,NSGA-II,SMEA,RM-MEDA和KFGEA求解GLT测试集30次获得最优IGD 指标值得变化曲线

图2 MOEA/D-DE,SMEA,RM-MEDA和KFGEA 获得的代表性分布前沿(Approximation Fronts,AF)

5 算法控制参数灵敏度分析

在KFGEA 算法性能参数灵敏度的分析中，选用GLT 测试集对每个具有不同参数的KFGEA 算法进行20 次运算，并分析性能指标值的统计结果.

由图3 可见，在β值均为0.4；不同聚类数目的条件下，KFGEA 的IGD 指标值在GLT3、GLT4 和GLT6 测试问题中产生了轻微波动，对于其余测试问题聚类数目对算法的性能指标影响很小. 这表明聚类数目对算法整体性能的影响不大.

从图4 中可以看出，在聚类数目K=8；不同β值的条件下，除了在GLT6 和GLT3 测试问题中IGD 值出现了一些浮动，其余测试问题中KFGEA 性能指标的波动很小. 这表明交配限制概率β值对算法整体性能的影响不大.

综上所述，KFGEA 对控制参数值不是特别敏感，该算法具有良好的鲁棒性.

图3 KFGEA 算法在不同K值下GLT 系列套件独立运行20 次的IGD指标值的平均值和标准差

图4 KFGEA 算法在不同β值下GLT 系列套件独立运行20 次的IGD指标值的平均值和标准差

6 结束语

本文选择了带有复杂PF 结构的GLT 测试集和具有复杂PF 结构的LZ 测试集作为求解问题；选取五种经典多目标优化算法与KFGEA 算法进行对比测试. 实验结果表明KFGEA 算法在IGD 和HV 指标、搜索效率和可视化对比三个方面均具有明显的优势. 这说明Kmeans 聚类算法的引进可以充分利用多目标优化问题的规则特性，进而去提高进化算法的性能；FGMS 能提高搜索效率，利用适应度这一确定性信息去维持算法收敛性与多样性的平衡. 后续工作将围绕KFGEA 算法的实际应用而展开.