Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptation
원문 초록
We introduce Limited Rollout Beam Search (LRBS), a beam search strategy for deep reinforcement learning (DRL) based combinatorial optimization improvement heuristics. Utilizing pre-trained models on the Euclidean Traveling Salesperson Problem, LRBS significantly enhances both in-distribution performance and generalization to larger problem instances, achieving optimality gaps that outperform existing improvement heuristics and narrowing the gap with state-of-the-art constructive methods. We also extend our analysis to two pickup and delivery TSP variants to validate our results. Finally, we employ our search strategy for offline and online adaptation of the pre-trained improvement policy, leading to improved search performance and surpassing recent adaptive methods for constructive heuristics.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization
Unraveling the Rainbow: can value-based methods schedule?
Synergizing Reinforcement Learning and Genetic Algorithms for Neural Combinatorial Optimization
Preference-Driven Multi-Objective Combinatorial Optimization with Conditional Computation
Solving the Pod Repositioning Problem with Deep Reinforced Adaptive Large Neighborhood Search
Deep Reinforcement Learning with Gradient Eligibility Traces
토론
이 논문과 연결된 포럼 글이 아직 없습니다.