Multi-objective Optimization by Learning Space Partitions
Multi-objective Optimization by Learning Space Partitions
复制标题
DOI：
--
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
Yiyang Zhao;Linnan Wang;Kevin Yang;Tianjun Zhang;Tian Guo;Yuandong Tian
中科院分区：
文献类型：
--
作者：
Yiyang Zhao;Linnan Wang;Kevin Yang;Tianjun Zhang;Tian Guo;Yuandong Tian
与单目标优化（SOO）不同，多目标优化（MOO）需要优化器找到帕累托前沿，即不受其他可行解支配的可行解的一个子集。在本文中，我们提出了LaMOO，一种新颖的多目标优化器，它从观察到的样本中学习一个模型来划分搜索空间，然后关注可能包含帕累托前沿子集的有希望的区域。这种划分基于支配数，它衡量一个数据点在现有样本中与帕累托前沿的“接近程度”。为了考虑由于样本有限和模型不匹配可能导致的划分错误，我们利用蒙特卡洛树搜索（MCTS）在探索可能后来被证明包含良好解的次优区域的同时，开发有希望的区域。从理论上讲，我们在某些假设下证明了通过LaMOO进行学习空间划分的有效性。在经验上，在超体积（HV）基准（一种流行的MOO度量标准）上，LaMOO在多个现实世界的MOO任务中显著优于强大的基线，在Nasbench201上的神经架构搜索中，样本效率提高了高达225%，在分子设计中提高了高达10%。
In contrast to single-objective optimization (SOO), multi-objective optimization (MOO) requires an optimizer to find the Pareto frontier, a subset of feasible solutions that are not dominated by other feasible solutions. In this paper, we propose LaMOO, a novel multi-objective optimizer that learns a model from observed samples to partition the search space and then focus on promising regions that are likely to contain a subset of the Pareto frontier. The partitioning is based on the dominance number, which measures"how close"a data point is to the Pareto frontier among existing samples. To account for possible partition errors due to limited samples and model mismatch, we leverage Monte Carlo Tree Search (MCTS) to exploit promising regions while exploring suboptimal regions that may turn out to contain good solutions later. Theoretically, we prove the efficacy of learning space partitioning via LaMOO under certain assumptions. Empirically, on the HyperVolume (HV) benchmark, a popular MOO metric, LaMOO substantially outperforms strong baselines on multiple real-world MOO tasks, by up to 225% in sample efficiency for neural architecture search on Nasbench201, and up to 10% for molecular design.