Ant colony optimization parameter selection for shortest path problem

N. Zarrinpanjeh, F. Dadrass Javan*, H. Azadi, P. De Maeyer, F. Witlox

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

Abstract

The shortest path problem has been studied to be solved through diverse deterministic and also stochastic approaches such as Ant Colony Optimization. One of the most challenging issues with the implication of Ant Colony Optimization to solve the shortest path problem is parameter selection and tuning which is found crucial to improve the computational performance of problem-solving. To tune parameters, it is vital to observe the response of each parameter to different values and study their effect on the final results. In this research, two experiments are designed and conducted to study the behavior of parameters in terms of generated results and computational performance. In the first experiment, evaporation, updating, and transition rule parameters are studied by iterative execution of shortest path generation between nodes considering different parameter values. In the second experiment, the number of initial ants is studied. Inspecting the results, it is observed that to avoid premature stagnation decreasing α value is recommended. On the other hand, ρ is observed to be considered for tuning of speed and number of diffusions of the algorithm. Moreover, it is realized that a high Q value would result in more correct results. Inspecting the initial number of ants, a threshold is realized where increasing the number of ants over this threshold would drastically result in more optimized paths.

Original languageEnglish
Title of host publicationISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences
Subtitle of host publicationXXIV ISPRS Congress, Commission IV
EditorsN. Paparoditis, C. Mallet, F. Lafarge, S. Zlatanova, S. Dragicevic, G. Sithole, G. Agugiaro, J.J. Arsanjani, P. Boguslawski, M. Breunig, M.A. Brovelli, S. Christophe, A. Coltekin, M.R. Delavar, M. Al Doori, E. Guilbert, C.C. Fonte, J. Hayworth, U. Isikdag, I. Ivanova, Z. Kang, K. Khoshelham, M. Koeva, M. Kokla, Y. Liu, M. Madden, M.A. Mostafavi, G. Navratil, D.R. Paudyal, C. Pettit, A. Spano, E. Stefanakis, W. Tu, G. Vacca, L. Diaz-Vilarino, S. Wise, H. Wu, X.G. Zhou
PublisherInternational Society for Photogrammetry and Remote Sensing (ISPRS)
Pages147-154
Number of pages8
VolumeV-4-2020
DOIs
Publication statusPublished - 3 Aug 2020
Externally publishedYes
Event2020 24th ISPRS Congress - Technical Commission IV on Spatial Information Science - Nice, Virtual, France
Duration: 31 Aug 20202 Sep 2020

Publication series

NameISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences
PublisherCopernicus
ISSN (Print)2194-9042

Conference

Conference2020 24th ISPRS Congress - Technical Commission IV on Spatial Information Science
CountryFrance
CityNice, Virtual
Period31/08/202/09/20

Keywords

  • Ant Colony Optimization
  • Geo-Informatics
  • Parameter Selection
  • Shortest Path Problem
  • ITC-CV

Fingerprint

Dive into the research topics of 'Ant colony optimization parameter selection for shortest path problem'. Together they form a unique fingerprint.

Cite this