Ant colony optimization parameter selection for shortest path problem

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

doi:10.5194/isprs-Annals-V-4-2020-147-2020

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 proceeding › Chapter › Academic › peer-review

1 Citation (Scopus)

29 Downloads (Pure)

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 language	English
Title of host publication	ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences
Subtitle of host publication	XXIV ISPRS Congress, Commission IV
Editors	N. 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
Publisher	International Society for Photogrammetry and Remote Sensing (ISPRS)
Pages	147-154
Number of pages	8
Volume	V-4-2020
DOIs	https://doi.org/10.5194/isprs-Annals-V-4-2020-147-2020
Publication status	Published - 3 Aug 2020
Externally published	Yes
Event	24th ISPRS Congress 2020 - online, Nice, Virtual, France Duration: 31 Aug 2020 → 2 Sept 2020 Conference number: 24 https://www.int-arch-photogramm-remote-sens-spatial-inf-sci.net/XLIII-B5-2020/1/2020/

Publication series

Name	ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences
Publisher	Copernicus
ISSN (Print)	2194-9042

Conference

Conference	24th ISPRS Congress 2020
Country/Territory	France
City	Nice, Virtual
Period	31/08/20 → 2/09/20
Internet address	https://www.int-arch-photogramm-remote-sens-spatial-inf-sci.net/XLIII-B5-2020/1/2020/

Keywords

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

Access to Document

10.5194/isprs-Annals-V-4-2020-147-2020Licence: CC BY

isprs-annals-V-4-2020-147-2020Final published version, 1.86 MBLicence: CC BY

Cite this

Zarrinpanjeh, N., Dadrass Javan, F., Azadi, H., De Maeyer, P., & Witlox, F. (2020). Ant colony optimization parameter selection for shortest path problem. In N. 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 (Eds.), ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences: XXIV ISPRS Congress, Commission IV (Vol. V-4-2020, pp. 147-154). (ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences). International Society for Photogrammetry and Remote Sensing (ISPRS). https://doi.org/10.5194/isprs-Annals-V-4-2020-147-2020

Zarrinpanjeh, N. ; Dadrass Javan, F. ; Azadi, H. et al. / Ant colony optimization parameter selection for shortest path problem. ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences: XXIV ISPRS Congress, Commission IV. editor / N. 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. Vol. V-4-2020 International Society for Photogrammetry and Remote Sensing (ISPRS), 2020. pp. 147-154 (ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences).

@inbook{74cfa3d354a2410eb03a66e9f7fe0fcc,

title = "Ant colony optimization parameter selection for shortest path problem",

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. ",

keywords = "Ant Colony Optimization, Geo-Informatics, Parameter Selection, Shortest Path Problem, ITC-CV",

author = "N. Zarrinpanjeh and {Dadrass Javan}, F. and H. Azadi and {De Maeyer}, P. and F. Witlox",

year = "2020",

month = aug,

day = "3",

doi = "10.5194/isprs-Annals-V-4-2020-147-2020",

language = "English",

volume = "V-4-2020",

series = "ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences",

publisher = "International Society for Photogrammetry and Remote Sensing (ISPRS)",

pages = "147--154",

editor = "N. Paparoditis and C. Mallet and F. Lafarge and S. Zlatanova and S. Dragicevic and G. Sithole and G. Agugiaro and J.J. Arsanjani and P. Boguslawski and M. Breunig and M.A. Brovelli and S. Christophe and A. Coltekin and M.R. Delavar and {Al Doori}, M. and E. Guilbert and C.C. Fonte and J. Hayworth and U. Isikdag and I. Ivanova and Z. Kang and K. Khoshelham and M. Koeva and M. Kokla and Y. Liu and M. Madden and M.A. Mostafavi and G. Navratil and D.R. Paudyal and C. Pettit and A. Spano and E. Stefanakis and W. Tu and G. Vacca and L. Diaz-Vilarino and S. Wise and H. Wu and X.G. Zhou",

booktitle = "ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences",

note = "24th ISPRS Congress 2020 ; Conference date: 31-08-2020 Through 02-09-2020",

url = "https://www.int-arch-photogramm-remote-sens-spatial-inf-sci.net/XLIII-B5-2020/1/2020/",

}

Zarrinpanjeh, N, Dadrass Javan, F, Azadi, H, De Maeyer, P & Witlox, F 2020, Ant colony optimization parameter selection for shortest path problem. in N Paparoditis, C Mallet, F Lafarge, S Zlatanova, S Dragicevic, G Sithole, G Agugiaro, JJ Arsanjani, P Boguslawski, M Breunig, MA Brovelli, S Christophe, A Coltekin, MR Delavar, M Al Doori, E Guilbert, CC Fonte, J Hayworth, U Isikdag, I Ivanova, Z Kang, K Khoshelham, M Koeva, M Kokla, Y Liu, M Madden, MA Mostafavi, G Navratil, DR Paudyal, C Pettit, A Spano, E Stefanakis, W Tu, G Vacca, L Diaz-Vilarino, S Wise, H Wu & XG Zhou (eds), ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences: XXIV ISPRS Congress, Commission IV. vol. V-4-2020, ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, International Society for Photogrammetry and Remote Sensing (ISPRS), pp. 147-154, 24th ISPRS Congress 2020, Nice, Virtual, France, 31/08/20. https://doi.org/10.5194/isprs-Annals-V-4-2020-147-2020

Ant colony optimization parameter selection for shortest path problem. / Zarrinpanjeh, N.; Dadrass Javan, F.; Azadi, H. et al.
ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences: XXIV ISPRS Congress, Commission IV. ed. / N. 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. Vol. V-4-2020 International Society for Photogrammetry and Remote Sensing (ISPRS), 2020. p. 147-154 (ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

TY - CHAP

T1 - Ant colony optimization parameter selection for shortest path problem

AU - Zarrinpanjeh, N.

AU - Dadrass Javan, F.

AU - Azadi, H.

AU - De Maeyer, P.

AU - Witlox, F.

N1 - Conference code: 24

PY - 2020/8/3

Y1 - 2020/8/3

N2 - 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.

AB - 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.

KW - Ant Colony Optimization

KW - Geo-Informatics

KW - Parameter Selection

KW - Shortest Path Problem

KW - ITC-CV

U2 - 10.5194/isprs-Annals-V-4-2020-147-2020

DO - 10.5194/isprs-Annals-V-4-2020-147-2020

M3 - Chapter

AN - SCOPUS:85092142786

VL - V-4-2020

T3 - ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences

SP - 147

EP - 154

BT - ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences

A2 - Paparoditis, N.

A2 - Mallet, C.

A2 - Lafarge, F.

A2 - Zlatanova, S.

A2 - Dragicevic, S.

A2 - Sithole, G.

A2 - Agugiaro, G.

A2 - Arsanjani, J.J.

A2 - Boguslawski, P.

A2 - Breunig, M.

A2 - Brovelli, M.A.

A2 - Christophe, S.

A2 - Coltekin, A.

A2 - Delavar, M.R.

A2 - Al Doori, M.

A2 - Guilbert, E.

A2 - Fonte, C.C.

A2 - Hayworth, J.

A2 - Isikdag, U.

A2 - Ivanova, I.

A2 - Kang, Z.

A2 - Khoshelham, K.

A2 - Koeva, M.

A2 - Kokla, M.

A2 - Liu, Y.

A2 - Madden, M.

A2 - Mostafavi, M.A.

A2 - Navratil, G.

A2 - Paudyal, D.R.

A2 - Pettit, C.

A2 - Spano, A.

A2 - Stefanakis, E.

A2 - Tu, W.

A2 - Vacca, G.

A2 - Diaz-Vilarino, L.

A2 - Wise, S.

A2 - Wu, H.

A2 - Zhou, X.G.

PB - International Society for Photogrammetry and Remote Sensing (ISPRS)

T2 - 24th ISPRS Congress 2020

Y2 - 31 August 2020 through 2 September 2020

ER -

Zarrinpanjeh N, Dadrass Javan F, Azadi H, De Maeyer P, Witlox F. Ant colony optimization parameter selection for shortest path problem. In Paparoditis N, Mallet C, Lafarge F, Zlatanova S, Dragicevic S, Sithole G, Agugiaro G, Arsanjani JJ, Boguslawski P, Breunig M, Brovelli MA, Christophe S, Coltekin A, Delavar MR, Al Doori M, Guilbert E, Fonte CC, Hayworth J, Isikdag U, Ivanova I, Kang Z, Khoshelham K, Koeva M, Kokla M, Liu Y, Madden M, Mostafavi MA, Navratil G, Paudyal DR, Pettit C, Spano A, Stefanakis E, Tu W, Vacca G, Diaz-Vilarino L, Wise S, Wu H, Zhou XG, editors, ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences: XXIV ISPRS Congress, Commission IV. Vol. V-4-2020. International Society for Photogrammetry and Remote Sensing (ISPRS). 2020. p. 147-154. (ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences). doi: 10.5194/isprs-Annals-V-4-2020-147-2020

Ant colony optimization parameter selection for shortest path problem

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this