WeCon: 一种高效的多目标组合优化问题权重条件神经求解器

# WeCon：一种用于多目标组合优化问题的高效权重条件神经求解器

来源：https://arxiv.org/html/2605.22876

\\文章类型 研究论文\\年2025\\月1月\\卷68\\期1\\DOI\\文章编号\\收稿日期\\修回日期\\录用日期\\在线日期\\作者标记\\作者引用

WeCon：一种用于多目标组合优化问题的高效权重条件神经求解器

[email protected]

陈金彪 李阳 李文杰 吴崇光 李远树 肖玉斌 苗春燕 周游 王迪

教育部符号计算与知识工程重点实验室，计算机科学与技术学院，吉林大学，长春 130012，中国
工业系统工程与管理系，新加坡国立大学，新加坡 117576，新加坡
软件学院，吉林大学，长春 130012，中国
软件学院，清华大学，北京 100084，中国
计算与信息系统学院，新加坡管理大学，新加坡 178902，新加坡
南洋理工大学-不列颠哥伦比亚大学联合老龄积极生活卓越研究中心，南洋理工大学，新加坡 639798，新加坡

###### 摘要

现有的多目标组合优化问题（MOCOP）神经求解器通常采用基于分解的策略，将MOCOP标量化为多个与不同权重向量相关的子问题。然而，它们要么仅在解码时注入权重，限制了权重条件上下文建模，要么主要在编码时注入，导致解码时权重信号被稀释。此外，偏好优化方法依赖于纯随机采样来构建求解器训练的解对，这往往产生信息量较少的解对，从而降低训练效果。为了更好地解决这些局限性，我们提出了一种高效的权重条件神经求解器（WeCon）。具体来说，我们设计了一个编码器层，包含三个注意力块和我们提出的门控残差融合（GRF）块，以促进实例特征和权重之间的和谐交互，从而生成信息丰富的权重条件上下文。我们进一步在解码器中引入了一个即插即用的残差融合（RF）块，以缓解权重信号稀释。最后，我们提出了高效偏好优化（EPO），该方法构建高质量的解，从而生成信息量更大的解对以提高训练效果。在四种不同问题规模和分布模式的MOCOP变体上的实验表明，WeCon实现了与SOTA求解器POCCO-W相当的HyperVolume（HV）值，同时推理时间减少了40%。消融研究验证了所有设计的贡献。

###### 关键词：神经组合优化，多目标问题，偏好优化，注意力模型

## 1 引言

组合优化问题（COP）是数学优化的核心课题，旨在离散搜索空间中找到最优解，因其广泛的现实世界相关性而长期吸引持续的研究关注[31,36,52,41]。求解COP的传统算法大致可分为三类，即精确方法、近似方法和启发式方法[42,1]。然而，大多数方法无法从历史的COP实例中获取洞察，导致大量计算开销[16,49,46]。为了高效求解COP，近年来的研究越来越多地开发神经求解器，这些求解器从大量历史实例中学习，能够有效搜索最优解[47,24,35,21,54,20,45]。尽管取得了这些进展，现有研究主要集中在单目标COP（SOCOP）上，而多目标COP（MOCOP）相对较少被探索。然而，许多现实世界中的决策必须平衡多个考量（例如成本和便利性）。因此，开发针对MOCOP定制的神经求解器至关重要[19,5,42]。

![图1](https://arxiv.org/html/2605.22876#S1.F1 "图1：我们提出的WeCon与现有求解MOCOP的NCO模型的对比说明。")

为了应对MOCOP带来的挑战，一些神经求解器[44,51]采用了基于分解的方法，将MOCOP分解为一系列与不同权重向量相关的子问题。先驱方法称为多模型求解器，为每个子问题训练或微调一个单独的模型[4,23]。然而，由于大量训练或微调开销，以及对训练中未见权重的泛化能力有限，这些方法可能不切实际[37]。因此，近年来的研究旨在训练一个能泛化到广泛权重的单一求解器[5,10]，并能生成动态适应输入权重的解，即实现权重条件决策。如图1(a)和1(b)所示，现有的单模型求解器通常仅将权重注入解码器（例如PMOCO[23]）或主要在编码器中（例如WE-CA[3]）。然而，这两种设计虽然直接，但可能阻碍对权重的泛化。具体来说，仅解码注入可能无法提供信息丰富的权重条件上下文，而主要编码注入可能在解码过程中稀释权重信号。为了提升性能，Fan等人[11]提出了基于混合专家（MoE）的条件计算（CCO）块，放置在解码器中，用于将子问题路由到不同的专家。然而，这种门控和路由过程引入了额外的运行时开销（见第5.2节），这可能限制模型在时间敏感场景中的实用性，例如交通信号控制[28]。这种低效性反映出这种设计并没有从根本上解决现有求解器的关键局限性，即编码器和解码器中权重的利用不足。因此，在这项工作中，我们研究以下研究问题：能否在不显著增加运行时间的情况下，通过有效生成信息丰富的权重条件上下文并在解码过程中防止权重信号稀释，来实现高水平性能的求解器？

此外，最近的研究[11]采用了文献[29]中提出的偏好优化（PO）来训练求解器。具体来说，PO在当前策略下为每个实例随机采样r个候选解，并根据其目标值进行两两比较，构建r(r-1)/2个偏好对，其中每个对包含一个更好解π_w和一个较差解π_l。这些对然后为训练求解器提供比较性监督。然而，纯随机采样不能保证足够数量的（接近）最优解，这限制了PO的利用能力，并对训练效果产生不利影响[22]。

为了更全面地解决上述局限性，我们提出了一种权重条件神经求解器（WeCon）。如图1(c)所示，WeCon让权重向量在编码器和解码器中都发挥关键作用，旨在通过在两者之间共享权重条件上下文来实现高水平性能。具体来说，编码器由堆叠的层组成，这些层交替对实例特征应用多头自注意力（MHSA）块，然后使用两个多头注意力（MHA）块以及我们提出的门控残差融合（GRF）块来整合实例和权重嵌入（见第4.1节），从而生成信息丰富的权重条件上下文。在解码器中，WeCon首先利用一个MHA层以及我们提出的残差融合（RF）块，在每个解码步骤以更有效的方式注入权重信号（见第4.2节）。通过采用这种设计，WeCon缓解了权重信号稀释，并在不显著增加运行时间的情况下实现了高水平性能（见第5.2节）。我们认为在解码器中采用RF使WeCon与主要利用编码器中权重的现有求解器（见图1(b)）有本质区别。例如，WE-CA将权重嵌入视为一个额外的标记，沿着节点维度附加到实例嵌入上（针对车辆路径问题），然后将其作为解码器MHA层的键/值输入[3]。而WeCon的解码器首先在MHA层内利用权重嵌入，随后将其广播到所有节点，在此基础上RF根据权重显式地调节每个节点嵌入（见图2）。此外，RF是一个即插即用模块，可以轻松集成到各种解码器架构中。为了展示RF的通用性，我们提出了一个变体WeCon-CCO，它采用文献[11]的解码器，并用RF模块对其进行增强。

为了提高训练效果，我们扩展了PO并提出了高效偏好优化（EPO）。具体来说，EPO不是为每个实例随机采样r个解，而是执行引导采样生成⌈r/c⌉个解，而剩余的(r-⌈r/c⌉)个解随机采样。这种引导采样约束每个决策步骤，仅从具有最高概率的前k个可行节点中选择下一个节点（见第4.3节）。这种设计使EPO能够获得足够高质量的解，从而构建具有更大质量差距的信息更丰富的偏好对，以提高训练效果。据我们所知，WeCon是第一个同时实现SOTA性能和运行时效率的神经求解器，它通过在编码器和解码器中有效利用权重来实现。本研究的主要贡献如下：

I) 我们设计了一个编码器，其中每一层对实例特征应用自注意力，然后在实例和权重特征之间执行双向注意力，最后通过提出的GRF模块整合它们以生成权重条件上下文。

II) 我们开发了一个解码器，该解码器将MHA层与提出的即插即用RF块相结合，以缓解权重信号稀释并实现更有效的权重条件决策。

III) 为了提高训练效果，我们提出了EPO策略，该策略高效地生成足够高质量的解，从而构建信息更丰富的偏好对。

IV) 为了评估所提出的WeCon和WeCon-CCO的有效性，我们在四种不同问题规模和分布模式的MOCOP上进行了大量实验。实验表明，WeCon实现了与SOTA求解器POCCO-W相当的HyperVolume（HV）值，同时推理时间减少约40%。WeCon-CCO实现了最佳的整体HV性能，尽管以增加推理时间为代价。消融研究验证了我们的编码器、解码器架构以及EPO的有效性。

## 2 相关工作

在本节中，我们回顾相关文献。

**MOCOP的神经求解器：** 为解决MOCOP，先驱研究[40,19,51]采用了MOEA/D框架[50]，该框架将MOCOP分解为与不同权重向量相关的一组子问题，并为每个子问题训练一个单独的模型。这类方法被称为多模型求解器。然而，训练多个模型需要大量计算资源。为了克服这一限制，Lin等人[23]提出了一种单模型求解器，将权重向量融入解码器，生成动态适应不同权重向量的解，即实现权重条件决策。随后，单模型求解器成为解决MOCOP的主流[10,44,12]。例如，Chen等人[3]提出了一种带有条件注意力机制的编码器，用于将权重与实例特征整合。然而，现有的求解器通常粗略地利用权重向量，要么主要在编码器中，要么仅在解码器中（见图1），这可能在解码过程中稀释权重信号，或无法提供信息丰富的权重条件上下文。为了更好地克服这一局限性，我们重新思考权重向量在MOCOP中的作用，并分别设计了编码器和解码器架构，以产生信息丰富的权重条件上下文并缓解权重信号稀释。

**偏好优化：** 大多数神经求解器使用强化学习（RL）进行训练，而少数采用监督学习（SL）[42,16]。因为RL不需要最优解作为训练标签，采用RL大大降低了标注成本[13,33,43]。然而，RL方法，例如广泛使用的REINFORCE[39]，通过将采样奖励与基线进行比较来更新策略[16]。随着训练的进行，策略梯度信号可能会减弱，导致收敛缓慢[29]。为了缓解这个问题，Pan等人[29]提出了PO作为R的替代方案。