用无序生成提升组合优化采样效率，避免传统方法失败
Black-Box Combinatorial Optimization with Order-Invariant Reinforcement Learning
- 用随机变量顺序训练生成模型，让其对顺序不敏感
- 在多种问题上表现最佳，采样效率显著提升
- 适合需要稳定高效搜索的组合优化场景
我们提出一种无序不变的强化学习框架，用于黑箱组合优化。传统估计分布算法常依赖显式变量依赖图，成本高且难以捕捉复杂交互。本文参数化一个多变量自回归生成模型，训练时采用随机生成顺序，相当于信息保留型丢弃，促使模型对变量顺序不变，增强搜索空间多样性，并聚焦关键变量依赖，提升采样效率。我们适配了组相对策略优化（GRPO）方法，实现从尺度不变优势函数中稳定的策略梯度更新。在多种基准算法和不同规模的问题实例上，该方法频繁取得最优性能，且持续避免灾难性失败。
原文摘要 · Abstract (English)
We introduce an order-invariant reinforcement learning framework for black-box combinatorial optimization. Classical estimation-of-distribution algorithms (EDAs) often rely on learning explicit variable dependency graphs, which can be costly and fail to capture complex interactions efficiently. In contrast, we parameterize a multivariate autoregressive generative model trained without a fixed variable ordering. By sampling random generation orders during training, a form of information-preserving dropout, the model is encouraged to be invariant to variable order, promoting search-space diversity, and shaping the model to focus on the most relevant variable dependencies, improving sample efficiency. We adapt Group Relative Policy Optimization (GRPO) to this setting, providing stable policy-gradient updates from scale-invariant advantages. Across a wide range of benchmark algorithms and problem instances of varying sizes, our method frequently achieves the best performance and consistently avoids catastrophic failures.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。