Conference proceeding
gBeam-ACO: a greedy and faster variant of Beam-ACO
Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion, pp.1434-1440
GECCO '20
07/08/2020
DOI: 10.1145/3377929.3398081
Abstract
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.
Details
- Title: Subtitle
- gBeam-ACO: a greedy and faster variant of Beam-ACO
- Creators
- Jeff Hajewski - University of IowaSuely Oliveira - University of IowaDavid E Stewart - University of IowaLaura Weiler - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion, pp.1434-1440
- Series
- GECCO '20
- DOI
- 10.1145/3377929.3398081
- Publisher
- ACM
- Language
- English
- Date published
- 07/08/2020
- Academic Unit
- Computer Science; Mathematics
- Record Identifier
- 9984241053902771
Metrics
13 Record Views