本文旨在向中文研究人员介绍一篇题为“自适应相似性特征构造的跨本体匹配：一种多层混合遗传编程方法”（Adaptive Similarity Feature Construction for Ontology Matching via Multi-layer Hybrid Genetic Programming）的学术论文。该论文由薛兴斯（Xingsi Xue，IEEE 高级会员）、梅一（Yi Mei，IEEE 高级会员）、赵宝忠（Baozhong Zhao）和张孟杰（Mengjie Zhang，IEEE Fellow）共同完成。第一作者薛兴斯在论文完成时受聘于新西兰惠灵顿维多利亚大学工程与计算机科学学院，并隶属于福建理工大学福建省大数据挖掘与应用重点实验室。该研究得到了中国国家自然科学基金（项目号：62172095）的资助。此文已被 IEEE Transactions on Evolutionary Computation 期刊接收，作为作者预印本，预计将于2025年正式出版。
本研究的核心科学领域是本体匹配（Ontology Matching, OM），这是语义网（Semantic Web）中的一项关键技术。本体通过定义概念、属性及关系来建立领域知识的共享理解，而本体匹配旨在识别不同本体中语义相似的实体，是实现异构数据源互操作的关键。
研究团队开展此项工作的主要背景和动机如下： 1. 本体匹配的复杂性：现实世界中，不同组织或社区针对相同或相关领域构建的本体，在词汇、结构和假设上存在显著差异。这种异构性使得需要一个自动化的匹配过程来建立实体间的对应关系。匹配本质上是一个二元分类问题，而分类的基础在于相似性特征（Similarity Features, SFs）。不同的SF可以从文本、语言、结构等不同角度衡量实体间的相似度。 2. 现有方法的局限性：虽然遗传算法（Genetic Algorithms, GA）和遗传编程（Genetic Programming, GP）已被证明在构造SF方面是有效的，但现有方法存在四个主要缺陷： * 依赖默认分类策略：大多数GP方法仅优化SF组合结构，而使用固定的分类规则（如设定阈值）来生成最终匹配结果，这限制了匹配结果的精确度。 * 高维特征数量固定且需人工确定：现有方法通常仅构造一个高层SF，或在构造多个高层SF时，其数量需要根据经验预先设定。这限制了相似性评估的视角，可能导致次优的匹配结果。 * SF子集选择问题：如何从众多基础SF中选择一个高质量的子集进行组合，对于匹配的效率和效果至关重要。盲目选择过多特征会增加计算开销并引入噪声；而GP算法缺乏有效机制来平衡所选特征的置信度（衡量其产生逻辑一致的匹配对的能力）和多样性（覆盖不同的相似性维度）。 * 难以优化组合参数：GP在演化特征组合树结构时，难以同时有效地优化树中的数值常量（常数矩阵），这些常量对于微调组合特征的效果非常重要。
因此，本文的主要目标是克服上述限制，开发一种新的多层混合遗传编程（Multi-layer Hybrid Genetic Programming, MLHGP）方法，以自适应地、自动化地构造高质量的高层相似性特征，从而显著提升本体匹配结果的质量。
该研究提出了一种名为多层混合遗传编程的完整算法框架，其核心思想是将本体匹配的三个主要阶段——相似性特征构造、实体对分类、匹配结果聚合——整合到一个统一的、可协同优化的遗传编程框架中。算法流程（如Algorithm 1所示）基于标准GP，并引入了多项关键创新。以下详述其核心流程与创新点：
（一） 多层个体表示设计 这是MLHGP算法的基石，它从根本上改变了GP在OM问题中的搜索空间结构。设计了一种三层树状结构的个体表示法： 1. 构造层（Construction Layer）：位于GP树底部，负责基础SF的选择和高层SF的组合构造。其节点是基础SF和常数矩阵，函数则是算数运算符（如加、减、乘、除、最大、最小、平均等）。 2. 分类层（Classification Layer）：位于中层，负责将构造层输出的相似度值矩阵转换为二值匹配矩阵。其函数是不同的分类策略，例如top1（每行最高值设为匹配）、top30percent（每行最高的30%值设为匹配）、median（高于中位数的设为匹配）和thres（基于阈值判断）。 3. 聚合层（Aggregation Layer）：位于树顶层，负责将多个分类层产生的二值矩阵聚合成最终的二值匹配矩阵。其函数是逻辑操作，如and（交集）和or（并集）。
这三层按照固定顺序排列（从底到顶：构造层->分类层->聚合层）。这种表示法巧妙地将GP的类型约束（确保输入输出数据类型匹配）与结构化语法（确保层的顺序和功能）结合起来，使得算法能够同时探索SF的构造结构、分类策略以及如何聚合多个部分匹配结果，从而自动确定所需高层SF的数量和最佳组合方式。
（二） 基于权重的相似性特征选择策略 为了解决SF选择中置信度与多样性的平衡问题，研究提出了一种新颖的权重机制，该策略贯穿于初始化、变异等多个环节。 1. 置信度权重（w_con）：根据SF产生的匹配结果中存在的逻辑冲突数量来评估其置信度。逻辑冲突定义为：如果两个类映射（c1, c2）和 (c1‘, c2’)中，c1是c1‘的超类（或子类），但c2却不是c2’的超类（或子类），则视为冲突。冲突越少，置信度越高，相应SF被选中的概率越大。 2. 多样性权重（w_cat）：根据SF所属的类别（如基于语法的SF、基于语言的SF、基于结构的SF）来调整权重。在初始化或变异过程中，当一个类别的SF被频繁选择后，该类别后续的SF被选中的权重会按公式w_cat = e^(-cat_i)递减，其中cat_i是个体中该类别的SF数量。这鼓励算法选择不同类别的SF以保持多样性。 这种双重权重机制被应用于一个两阶段的轮盘赌选择过程中：先根据类别权重选择SF类别，再在该类别内根据置信度权重选择具体的SF。
（三） 新初始化和自适应变异算子 1. 新初始化方法（Algorithm 2）：不同于随机初始化，该方法在利用“生长法”构建GP树时，采用上述的权重SF选择策略来生成构造层的叶子节点。此外，引入一个概率参数β来控制从当前层选择函数进入下一层的概率，这有助于生成结构合理且质量较高的初始种群。 2. 自适应变异算子：当对GP树进行子树变异时，被替换的子树同样使用权重SF选择策略来重新生成。这确保了变异操作不仅引入新变化，还能持续优化所选SF子集的置信度和多样性。
（四） 适应度评估函数 由于在真实匹配任务中通常没有标准的参考对齐结果（Ground Truth），研究设计了一种近似F值（Fa） 来评估个体（即一个匹配解决方案）的优劣。Fa的计算模拟了信息检索中F-measure的逻辑： * 近似召回率（Recall_A）：通过计算两个本体中被匹配实体的总数与本体总实体数之比来近似。 * 近似精确率（Precision_A）：通过计算匹配对平均相似度值（ASV）与匹配结果基数（Cardinality） 的几何平均数来近似。基数反映了匹配结果遵循“一一对应”映射约束的程度（理想情况下，一个源实体只对应一个目标实体）。 最终，Fa = 2 * Recall_A * Precision_A / (Recall_A + Precision_A)。这个设计巧妙地结合了匹配覆盖率（召回）、匹配对的相似强度（精度基础）和映射约束（精度调节），从而能够在没有黄金标准的情况下有效指导算法进化。
（五） 紧凑遗传算法优化的常数优化 为了解决GP难以优化树中常数的问题，研究引入了紧凑遗传算法（Compact Genetic Algorithm, CGA）作为局部优化器。在每代进化后，算法从排名前50%的个体中选取一定比例（rationco）的精英个体。对于每个被选个体，识别出其GP树构造层中的所有常数矩阵，将其编码为二进制基因。CGA通过维护一个概率向量来模拟种群分布，不断采样并评估新的常数组合，以梯度上升的方式更新概率向量，最终找到针对当前GP树结构最优的常数设置。这个过程显著提升了所构造特征的精细化程度。
（六） 两阶段父代选择 在进行子树交叉时，采用了一种两阶段选择机制来挑选父本：首先基于适应度值通过轮盘赌选择一批候选个体；然后将他们分组，在每组中选择适应度最高的个体，再从中选择树规模较小的个体作为父本。这引入了简约性压力，有助于控制GP树的复杂度，防止其过度膨胀。
研究团队在本体匹配评估倡议（Ontology Alignment Evaluation Initiative, OAEI）的基准测试集上对MLHGP进行了全面评估。该基准包含多个系列（101-104， 201-210， 221-247， 248-262），从简单的本体到在词汇、语言、结构三方面均高度异质的本体，难度递增。
（一） 与先进匹配方法的对比 MLHGP与OAEI竞赛的顶尖参与者（如Lily, CroMatch, AML, MapSSS等）以及一种先进的生成对抗神经网络（GANN）方法进行了对比。实验结果显示： * 在较为简单的测试用例（101-247系列）中，MLHGP几乎全部获得了完美的F值（1.00），与其他顶尖方法表现相当或更优。 * 在最具挑战性的13个测试用例（248-262系列）中，MLHGP的平均F值达到了0.89，显著优于第二名CroMatch（0.65）和第三名Lily（0.62）。例如，在用例249、250和257中，MLHGP取得了接近完美的结果（0.94， 0.92， 0.99），而其他方法在这些用例上表现显著下滑。统计检验（Wilcoxon秩和检验）表明，在绝大多数测试用例上，MLHGP的性能显著优于或与其他顶尖方法持平。
（二） 与进化算法方法的对比 MLHGP与传统的GA、结合随机爬山法的GA（GA-SHC）以及标准GP进行了详细对比。在所有47个测试用例中，MLHGP的表现全部显著优于基础GA；与GA-SHC相比，在28个用例上显著更优，其余19个持平；与标准GP相比，在21个用例上显著更优，其余26个持平。这证明了MLHGP提出的多层表示法和各项改进措施的有效性。
（三） 关键创新点有效性分析 1. 多层表示法的有效性：通过将其与仅遵循严格语法的GP（G-GP）和仅遵循类型约束的GP（ST-GP）进行对比，证明了MLHGP集两者之长的优越性。特别是在复杂测试用例（如202， 249， 257）上，MLHGP的表现显著优于G-GP和ST-GP，验证了其整合优化三个匹配阶段的能力。 2. 权重选择策略的有效性：通过将MLHGP与其变体——随机选择（MLHGP_ran）、仅考虑多样性（MLHGP_div）、仅考虑置信度（MLHGP_con）进行对比，发现完整的MLHGP在多数复杂用例上表现最佳。这证实了同时权衡SF置信度和多样性对于构建鲁棒的高层特征至关重要。 3. 算法组件分析：论文还通过一个具体用例（205）的解码示例，直观展示了MLHGP如何构造多个互补的高层SF子树，并通过聚合层将它们有效融合，最终得到的匹配结果（F=0.95）优于任一子树单独的结果（F=0.90, 0.88, 0.84），体现了算法集成学习的优势。
本研究的主要结论是：所提出的多层混合遗传编程（MLHGP）方法能够自适应地、自动化地构造高质量的相似性特征，用于解决复杂的本体匹配问题。该方法通过创新的多层个体表示法，统一并协同优化了特征构造、分类和聚合全过程；通过基于权重的特征选择机制，平衡了所选特征的置信度与多样性；并通过集成紧凑遗传算法，精细优化了特征组合中的参数。这些创新使得MLHGP在标准基准测试中取得了超越当前最先进方法（包括传统方法和最新机器学习方法）的匹配性能。
研究的科学价值与应用价值在于： 1. 方法论贡献：为进化计算在复杂组合优化问题（特别是特征工程）中的应用提供了新的思路和范式。MLHGP框架展示了如何通过设计特定的表示法和搜索算子，将领域知识（如OM的分阶段特性）深度融合到进化过程中。 2. 本体匹配领域贡献：提供了一种强大的、全自动的匹配工具，减少了对领域专家经验和手动调参的依赖。特别是在处理高度异构、信息有限的本体时，其自适应特征构造能力显示出巨大优势。 3. 潜在扩展性：该方法的框架和思想（如多层优化、置信度-多样性平衡）有望迁移到其他需要复杂特征构造和集成的领域，如更广泛的模式识别、数据集成和知识图谱对齐任务。