提出新算法，高效求解多目标离散优化问题
Pareto-NRPA: A Novel Monte-Carlo Search Algorithm for Multi-Objective Optimization
- 基于嵌套策略迭代，同时探索多个解空间区域
- 在约束空间上优于现有进化算法，解集更优且多样
- 适合需要平衡多个目标的智能搜索任务
我们提出 Pareto-NRPA，一种针对离散搜索空间中多目标优化问题的新蒙特卡洛算法。该算法扩展了原本用于单目标问题的嵌套回溯策略适应（NRPA）方法，将嵌套搜索与策略更新机制推广至多目标场景。算法通过一组策略并行探索解空间的不同区域，并在每层搜索中维护非支配前沿。策略适应基于帕累托前沿内序列的多样性与隔离性进行。我们在两类问题上进行基准测试：一个新型双目标带时间窗旅行商问题（MO-TSPTW）和在知名基准上的神经架构搜索任务。结果表明，Pareto-NRPA 在收敛性和解集多样性方面均达到领先水平，尤其在约束搜索空间上显著优于现有进化多目标算法。据我们所知，这是首次将 NRPA 扩展到多目标设置。
原文摘要 · Abstract (English)
We introduce Pareto-NRPA, a new Monte-Carlo algorithm designed for multi-objective optimization problems over discrete search spaces. Extending the Nested Rollout Policy Adaptation (NRPA) algorithm originally formulated for single-objective problems, Pareto-NRPA generalizes the nested search and policy update mechanism to multi-objective optimization. The algorithm uses a set of policies to concurrently explore different regions of the solution space and maintains non-dominated fronts at each level of search. Policy adaptation is performed with respect to the diversity and isolation of sequences within the Pareto front. We benchmark Pareto-NRPA on two classes of problems: a novel bi-objective variant of the Traveling Salesman Problem with Time Windows problem (MO-TSPTW), and a neural architecture search task on well-known benchmarks. Results demonstrate that Pareto-NRPA achieves competitive performance against state-of-the-art multi-objective algorithms, both in terms of convergence and diversity of solutions. Particularly, Pareto-NRPA strongly outperforms state-of-the-art evolutionary multi-objective algorithms on constrained search spaces. To our knowledge, this work constitutes the first adaptation of NRPA to the multi-objective setting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。