Simulation-guided Beam Search for Neural Combinatorial Optimization
Neural approaches for combinatorial optimization (CO) equip a learning mechanism to discover powerful heuristics for solving complex real-world problems. While neural approaches capable of high-quality solutions in a single shot are emerging, state-of-the-art approaches are often unable to take full advantage of the solving time available to them. In contrast, hand-crafted heuristics perform highly effective search well and exploit the computation time given to them, but contain heuristics that are difficult to adapt to a dataset being solved. With the goal of providing a powerful search procedure to neural CO approaches, we propose simulation-guided beam search (SGBS), which examines candidate solutions within a fixed-width tree search that both a neural net-learned policy and a simulation (rollout) identify as promising. We further hybridize SGBS with efficient active search (EAS), where SGBS enhances the quality of solutions backpropagated in EAS, and EAS improves the quality of the policy used in SGBS. We evaluate our methods on well-known CO benchmarks and show that SGBS significantly improves the quality of the solutions found under reasonable runtime assumptions.
Code (1)
Tasks
Combinatorial OptimizationSimilar Papers 제목 키워드 기반
A reinforcement learning application of guided Monte Carlo Tree Search algorithm for beam orientation selection in radiation therapy
Due to the large combinatorial problem, current beam orientation optimization algorithms for radiotherapy, such as column generation (CG), are typically heuristic or greedy in nature, leading to suboptimal solutions. We …
Anatomyreinforcement-learningReinforcement LearningReinforcement Learning (RL)Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems
In this article we propose a heuristic algorithm to explore search space trees associated with instances of combinatorial optimization problems. The algorithm is based on Monte Carlo tree search, a popular algorithm in g…
Combinatorial OptimizationSchedulingScaling 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 Traveli…
Combinatorial OptimizationDeep Reinforcement LearningMulti-rendezvous Spacecraft Trajectory Optimization with Beam P-ACO
The design of spacecraft trajectories for missions visiting multiple celestial bodies is here framed as a multi-objective bilevel optimization problem. A comparative study is performed to assess the performance of differ…
Bilevel OptimizationNCO4CVRP: Neural Combinatorial Optimization for the Capacitated Vehicle Routing Problem
Neural Combinatorial Optimization (NCO) has emerged as a powerful framework for solving combinatorial optimization problems by integrating deep learning-based models. This work focuses on improving existing inference tec…