Evolutionary Augmented Reinforcement Learning for Neural Combinatorial Optimization
提出进化增强机制，将深度强化学习的学习效率与进化算法的全局搜索能力结合，用于解决旅行商、车辆路径等组合优化问题，提升解质量和训练效率。
Combinatorial optimization is challenging due to its discrete structure and exponentially large search spaces. Recent advances in deep reinforcement learning enable heuristics learned directly from data, but such methods often exhibit limited exploration and can be trapped in local optima. By contrast, evolutionary algorithms such as genetic algorithms offer strong global exploration but are typically sample inefficient and computationally intensive.We propose the Evolutionary Augmentation Mechanism, a plug-and-play framework that combines the learning efficiency of deep reinforcement learning with the global search power of evolutionary operators. The method generates solutions from a learned policy, refines them via crossover and mutation, and reinjects selected solutions into policy training to enhance exploration and accelerate convergence. We provide a theoretical analysis that bounds the Kullback–Leibler divergence between the evolved-solution distribution and the policy distribution, ensuring stable updates. The framework is model agnostic and integrates with attention-based and symmetry-aware neural combinatorial optimization solvers. Across benchmarks including the Traveling Salesman Problem, the Capacitated Vehicle Routing Problem, the Prize-Collecting Traveling Salesman Problem, and the Orienteering Problem, the approach improves solution quality and training efficiency.