Conference proceeding
Exploring Trade-offs in Parallel Beam-ACO
2021 IEEE 11th Annual Computing and Communication Workshop and Conference (CCWC), pp.1525-1534
01/27/2021
DOI: 10.1109/CCWC51732.2021.9376177
Abstract
The Traveling Salesman Problem is a conceptually simple problem that is computationally difficult due to the size of the search space, which grows factorially with the number of cities. Beam-ACO is an Ant Colony Optimization heuristic that combines classical ACO with beam search. Beam-ACO is quite effective at finding high quality approximate solutions but it is more computationally demanding than the more classical ACO algorithms. In this work we propose a parallel version of Beam-ACO based on work-stealing. Our parallel Beam-ACO algorithm runs both the ant search and beam evaluation and pruning in parallel. Our experiments verify both that Beam-ACO is indeed one of the most effective ACO metaheuristics and that our parallel Beam-ACO is faster than more traditional parallelization schemes such as multi-colony or ant parallel.
Details
- Title: Subtitle
- Exploring Trade-offs in Parallel Beam-ACO
- Creators
- Jeff Hajewski - Salesforce (United States)Suely Oliveira - University of IowaDavid E Stewart - University of IowaLaura Weiler - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- 2021 IEEE 11th Annual Computing and Communication Workshop and Conference (CCWC), pp.1525-1534
- DOI
- 10.1109/CCWC51732.2021.9376177
- Publisher
- IEEE
- Language
- English
- Date published
- 01/27/2021
- Academic Unit
- Computer Science; Mathematics
- Record Identifier
- 9984240768502771
Metrics
17 Record Views