Ant colony optimization with distributed colonies for dynamic environments on multiple GPUs
| dc.contributor.author | Wiens, Emanuel | |
| dc.contributor.examiningcommittee | Mohammed, Noman (Computer Science) | |
| dc.contributor.examiningcommittee | Ferens, Ken (Electrical and Computer Engineering) | |
| dc.contributor.supervisor | Thulasiraman, Parimala | |
| dc.date.accessioned | 2024-09-10T19:22:13Z | |
| dc.date.available | 2024-09-10T19:22:13Z | |
| dc.date.issued | 2024-08-25 | |
| dc.date.submitted | 2024-08-26T00:21:38Z | en_US |
| dc.degree.discipline | Computer Science | |
| dc.degree.level | Master of Science (M.Sc.) | |
| dc.description.abstract | Dynamic environments pose many challenges as the search space is irregular, un- structured, with the data and problem space changing over time. The algorithms executing on these environments should adapt to the varying dynamic conditions. In this research we consider Ant Colony Optimization algorithm (ACO), a technique inspired by real ants in nature and therefore, should be adaptable to dynamic environ- ments. However, some studies in the literature show the contrary. Population-based ACO was introduced, a hybrid technique that combines concepts from Genetic Algo- rithms for solving problems in dynamic environments. In this thesis, we argue and show that ACO is as good as PACO or even better in some cases, by incorporating lo- cal search techniques to exploit the search space, tuning parameters in the algorithm to explore the search space and, using migration between multiple colonies (or island model) for convergence. The multiple colonies are implemented on multiple GPUs for efficiency. We perform various experiments on a dynamic travelling salesperson dataset and compare ACO and PACO with local search and island model. We also show that the parameter tuning has a significant influence on the accuracy. | |
| dc.description.note | October 2024 | |
| dc.identifier.uri | http://hdl.handle.net/1993/38558 | |
| dc.language.iso | eng | |
| dc.rights | open access | en_US |
| dc.subject | Nature-Inspried | |
| dc.subject | CUDA | |
| dc.subject | Ant Colony Optimization | |
| dc.subject | Combinatorial Optimization Problems | |
| dc.subject | Evolutionary Algorithms | |
| dc.title | Ant colony optimization with distributed colonies for dynamic environments on multiple GPUs | |
| dc.type | master thesis | en_US |
| local.subject.manitoba | no |