Abstract
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.
Abstract (translated)
我们引入了Pareto-NRPA，这是一种为离散搜索空间中的多目标优化问题设计的新蒙特卡洛算法。该算法扩展了最初为单目标问题制定的嵌套滚动策略调整（NRPA）算法，并将嵌套搜索和策略更新机制推广到了多目标优化中。该算法使用一组策略同时探索解决方案空间的不同区域，并在每一级搜索过程中保持非支配前沿。通过序列间的多样性和隔离性，对策略进行适应性调整。我们在两类问题上对Pareto-NRPA进行了基准测试：一种是旅行推销员问题的时间窗口变体的新型双目标版本（MO-TSPTW），另一种是在知名基准上的神经架构搜索任务。结果表明，Pareto-NRPA在收敛性和解决方案多样性方面均达到了与现有最佳多目标算法相当甚至更好的性能。特别是在受限制的搜索空间中，Pareto-NRPA显著优于现有的进化型多目标优化算法。据我们所知，这项工作首次将NRPA应用于多目标场景。
URL
https://arxiv.org/abs/2507.19109
