基于领域无关实例生成的并行算法组合演化方法

Evolving Generalizable Parallel Algorithm Portfolios via Domain-Agnostic Instance Generation

摘要 Abstract

泛化能力是优化器从数据中训练时的核心目标。然而,有限的训练样本往往限制了优化器的泛化能力。协同进化方法通过同时演化一个并行算法组合(PAP)和实例种群来解决这一挑战,最终获得具有良好泛化能力的PAP。然而,当应用于特定问题类时,这些方法存在一个主要局限性:它们需要从业者提供专门针对该问题类设计的实例生成器,而这类生成器的设计往往并不容易。本文提出了一种通用的、开箱即用的PAP构建方法,称为参数化搜索的领域无关协同演化(DACE),用于决策变量取值为0或1的二元优化问题。DACE的关键创新之处在于其基于神经网络的领域无关实例表示和生成机制,这消除了对领域特定实例生成器的需求。DACE的强大泛化能力在三个现实世界的二元优化问题中得到了验证:互补影响最大化问题(CIMP)、编译器参数优化问题(CAOP)以及污染控制问题(CCP)。给定这三个问题类中仅有的少量训练样本,DACE无需领域知识即可构造出比现有方法(尽管这些方法使用了领域特定的实例生成器)在所有三类问题上具有更好泛化性能的PAP。

Generalization is the core objective when training optimizers from data. However, limited training instances often constrain the generalization capability of the trained optimizers. Co-evolutionary approaches address this challenge by simultaneously evolving a parallel algorithm portfolio (PAP) and an instance population to eventually obtain PAPs with good generalization. Yet, when applied to a specific problem class, these approaches have a major limitation. They require practitioners to provide instance generators specially tailored to the problem class, which is often non-trivial to design. This work proposes a general-purpose, off-the-shelf PAP construction approach, named domain-agnostic co-evolution of parameterized search (DACE), for binary optimization problems where decision variables take values of 0 or 1. The key novelty of DACE lies in its neural network-based domain-agnostic instance representation and generation mechanism that eliminates the need for domain-specific instance generators. The strong generality of DACE is validated across three real-world binary optimization problems: the complementary influence maximization problem (CIMP), the compiler arguments optimization problem (CAOP), and the contamination control problem (CCP). Given only a small set of training instances from these problem classes, DACE, without requiring domain knowledge, constructs PAPs with even better generalization performance than existing approaches on all three classes, despite their use of domain-specific instance generators.

基于领域无关实例生成的并行算法组合演化方法 - arXiv