Програмна модель для визначення оптимальних маршрутів у комп’ютерній мережі за двоколоніальним мурашиним алгоритмом

V. M Pakhomova; A. O Opriatnyi

doi:10.15802/stp2021/242046

Authors

V. M. Pakhomova Dnipro National University of Railway Transport named after Academician V. Lazaryan, Ukraine https://orcid.org/0000-0002-0022-099X
A. O. Opriatnyi Dnipro National University of Railway Transport named after Academician V. Lazaryan, Ukraine https://orcid.org/0000-0001-7145-9677

DOI:

https://doi.org/10.15802/stp2021/242046

Keywords:

railway transport, computer network; router; delay; two-colonial ant algorithm; pheromone; deposition; evaporation; search time, computer network, router, delay, two-colonial ant algorithm; pheromone; deposition; evaporation; search time, two-colonial ant algorithm, pheromone, deposition, evaporation, search time

Abstract

Purpose. At present, the computer networks of the information and telecommunication system (ITS) of railway transport use the OSPF protocol, which does not allow taking into account several metrics when determining the optimal route. Therefore, there is a need to study the possibility of organizing routing in computer networks of rail transport ITS using a two-colonial ant algorithm. Methodology. According to the Two-ACO software model, created in the Python language based on the two-colonial ant algorithm, the optimal route in a computer network was determined. Two-ACO model inputs: computer network parameters (network adjacency matrix, number of routers); parameters of the ant algorithm (number of iterations; number of ants in the colony; number of elite ants; initial pheromone level; evaporation rate; parameter for adjusting the amount of pheromone deposition). Findings. The results of the Two-ACO model are presented in the form of graphs depicting the optimal paths: the criterion of the total delay on the routers (for the first colony of ants) and the number of hops (for the second colony of ants). Originality. According to the created Two-ACO software model for a computer network of 7 routers and 17 channels, a study of the time for determining the optimal path in a computer network by the number of ordinary and elite ants, evaporation rate and deposited pheromone was conducted. It is determined that it is enough to use the number of ants equal to the number of routers and have 2 elite ants in the colony, with 1000 iterations, evaporation rate from 0.2 to 0.7, and pheromone deposition by ants close to one. Practical value. Created Two-ACO software model using two colonies of ants on the following criteria: the total delay on the routers (for the first colony of ants) and the number of hops that make up the route (for the second colony of ants) allows you to parallel determine the optimal routes in a computer network of railway transport. It is estimated that for a computer network of 15 routers and 17 channels, it is sufficient to have 30 agents (two ants on top), the value of the pheromone deposited by the agents is close to one, and the evaporation rate is 0.4.

References

Glushko, S. I., & Kakatunova, Т. V. (2013). Fuzzy modification of the algorithm of ant colonies. Scientific Review, 1, 377-381. (in Russian)

Pavlenko, A. I., & Titov, Yu. P. (2012). Sravnitelnyy analiz modifitsirovannykh metodov muravinykh koloniy. Prikladnaya informatika, 4(40), 100-112. (in Russian)

Pakhomova, V. M., & Opriatny, А. A. (2020). Determination of the optimal route in a secure computer network using a two-colonial ant algorithm. International scientific-practical conference «International scientific integration’2020». USA. (in Ukrainian)

Skakov, E., & Malysh, V. (2016). Bee colony optimization algorithm for wireless network planning problem solving. SOFTWARE & SYSTEMS, 4(67), 67-73. DOI: https://doi.org/10.15827/0236-235X.115.067-073 (in Russian)

Smirnova, O. S., Bogoradnikova, A. V., & Blinov, M. Yu. (2015). Opisanie roevykh algoritmov, ins-pirirovannykh nezhivoy prirodoy i bakteriyami, dlya ispolzovaniya v ontologicheskoy modeli. International Journal of Open Information Technologies, 3(12), 28-37. (in Russian)

Shtovba, S. D. (2003). Muravinye algoritmy. Exponenta Pro. Matematika v prilozheniyakh, 4, 70-75. (in Russian)

Davidovic, T., Teodorovic, D., & Selmic, M. (2015). Bee Colony Optimization-Part I: The Algorithm Overview: Invited survey. Yugoslav Journal of Operations Research, 25(1), 33-56. DOI: https://doi.org/10.2298/YJOR131011017D (in English)

Dli, M. I., Glushko, S. I., & Ivanova, I. V. (2012). Ant algorithms as a tool of infrastructure project management. European Science and Technology: materials of the III research and practice conference (pp. 127-129). Munich, Germany. (in English)

Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53-66. DOI: https://doi.org/10.1109/4235.585892 (in English)

Hussein, W. A., Sahran, S., & Sheikh Abdullah, S. N. H. (2016). The variants of the Bees Algorithm (BA): a sur-vey. Artificial Intelligence Review, 47(1), 67-121. DOI: https://doi.org/10.1007/s10462-016-9476-8 (in English)

Kumar, K., Zindani, D., & Davim, J. P. (2019). Bees Algorithm. Optimizing Engineering Problems through Heuris-tic Techniques (pp. 43-50). DOI: https://doi.org/10.1201/9781351049580-5 (in English)

Pakhomova, V. M., & Mandybura, Y. S. (2019). Optimal route definition in the railway information network using neural-fuzzy models. Science and Transport Progress, 5(83), 81-98. DOI: https://doi.org/10.15802/stp2019/184385 (in English)

Pakhomova, V. M., & Tsykalo, I. D. (2018). Optimal route definition in the network based on the multilayer neural model. Science and Transport Progress, 6(78), 126-142.DOI: https://doi.org/10.15802/stp2018/154443 (in English)

Vaishali, S. Nature-All Mathematics. Retrieved from http://thebridge.psgtech.ac.in/index.php/2014/11/12/nature-all-mathematics (in English)

Ying, Tan. (2018). Survey of swarm intelligence. Swarm Intelligence-Vol. 1: Principles, current algorithms and methods, 1-28. DOI: https://doi.org/10.1049/pbce119f_ch1 (in English)