gBeam-ACO: a greedy and faster variant of Beam-ACO
원문 초록
Beam-ACO, a modification of the traditional Ant Colony Optimization (ACO) algorithms that incorporates a modified beam search, is one of the most effective ACO algorithms for solving the Traveling Salesman Problem (TSP). Although adding beam search to the ACO heuristic search process is effective, it also increases the amount of work (in terms of partial paths) done by the algorithm at each step. In this work, we introduce a greedy variant of Beam-ACO that uses a greedy path selection heuristic. The exploitation of the greedy path selection is offset by the exploration required in maintaining the beam of paths. This approach has the added benefit of avoiding costly calls to a random number generator and reduces the algorithms internal state, making it simpler to parallelize. Our experiments demonstrate that not only is our greedy Beam-ACO (gBeam-ACO) faster than traditional Beam-ACO, in some cases by an order of magnitude, but it does not sacrifice quality of the found solution, especially on large TSP instances. We also found that our greedy algorithm, which we refer to as gBeam-ACO, was less dependent on hyperparameter settings.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
S$^*$: A Heuristic Information-Based Approximation Framework for Multi-Goal Path Finding
Multi-objective Evolution of Heuristic Using Large Language Model
SQL-o1: Automatic Text-to-SQL Program Synthesis via Self-Reward Heuristic Search
Collaborative Problem-Solving in an Optimization Game
A Survey on Mathematical Reasoning and Optimization with Large Language Models
Destroy and Repair Using Hyper Graphs for Routing
토론
이 논문과 연결된 포럼 글이 아직 없습니다.