让神经组合优化同时处理多个解,提升搜索效率与多样性。
Enabling Population-Based Architectures for Neural Combinatorial Optimization
- 设计可同时处理一组解的神经策略,实现群体演化。
- 在最大割和最大独立集问题上,性能优于单解优化方法。
- 适合对组合优化中探索与利用平衡感兴趣的读者。
神经组合优化(NCO)通常学习单一候选解的策略,或从头构建或逐步改进。而传统元启发式方法表明,维护并演化解的种群能增强鲁棒性与探索能力,常取得更优结果。为弥合这一差距,我们研究如何使NCO显式地基于种群:学习作用于候选解集合的策略。首先提出一种种群感知水平的简单分类,揭示两个关键设计挑战:(i) 如何在神经网络中表示整个种群,(ii) 如何学习平衡强化(生成优质解)与多样化(保持多样性)的种群动态。为此,我们提出两种互补工具:一是利用全种群共享信息改进现有解;二是生成兼具高质量与多样性的新解。在最大割(Max Cut)和最大独立集(Max Independent Set)上的实验表明,引入种群结构显著提升学习优化方法的表现,并建立起NCO与经典种群搜索之间的新联系。
原文摘要 · Abstract (English)
Neural Combinatorial Optimization (NCO) has mostly focused on learning policies, typically neural networks, that operate on a single candidate solution at a time, either by constructing one from scratch or iteratively improving it. In contrast, decades of work in metaheuristics have shown that maintaining and evolving populations of solutions improves robustness and exploration, and often leads to stronger performance. To close this gap, we study how to make NCO explicitly population-based by learning policies that act on sets of candidate solutions. We first propose a simple taxonomy of population awareness levels and use it to highlight two key design challenges: (i) how to represent a whole population inside a neural network, and (ii) how to learn population dynamics that balance intensification (generating good solutions) and diversification (maintaining variety). We make these ideas concrete with two complementary tools: one that improves existing solutions using information shared across the whole population, and the other generates new candidate solutions that explicitly balance being high-quality with diversity. Experimental results on Maximum Cut and Maximum Independent Set indicate that incorporating population structure is advantageous for learned optimization methods and opens new connections between NCO and classical population-based search.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。