РАСПАРАЛЛЕЛИВАНИЕ ГИБРИДНОГО АЛГОРИТМА МУРАВЬИНОЙ КОЛОНИИ С ИЗМЕНЯЮЩИМИСЯ С ПОМОЩЬЮ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ПАРАМЕТРАМИ

EDN: HBTPLC

В работе рассмотрена возможность использования параллельной реализации гибридного метода оптимизации, использующего муравьиный и генетический алгоритмы, для решения задачи коммивояжера. Известно, что алгоритм муравьиной колонии чувствителен к изменению параметров, поэтому поиск подходящих параметров муравьиного алгоритма рассматривается в качестве задачи оптимизации, решение которой предоставляется генетическому алгоритму. Целью распараллеливания вычислений является сокращение временных затрат, но не все алгоритмы имеют эффективную параллельную реализацию. Известно, что генетический алгоритм и алгоритм муравьиной колонии распараллеливаются. В работе изучается возможность построения параллельных вычислений и для представленного гибридного метода. Задача коммивояжера, на которой проводится исследование, является NP-полной задачей и часто применяется для тестирования алгоритмов комбинаторной оптимизации. Показано, что распараллеливание используемого метода приводит к увеличению скорости выполнения работы алгоритма.

Список литературы

1. Zhang N. Moore’s law is dead, long live moore’s law! // arXiv preprint arXiv:2205.15011, 2022.

2. Pujol R., Jorba J., Tabani H., Kosmidis L., Mezzetti E., Abella J., Cazorla F. Vector extensions in cots processors to increase guaranteed performance in real-time systems, 2022. ACM Transactions on Embedded Computing Systems (TECS).

3. Zhou K. Feng X. A collaborative grouping aggregation query scheme on heterogeneous computing systems //in 2022 7th International Conference on Cloud Computing and Big Data Analytics (ICCCBDA), 2022. P. 53-61.

4. Regassa D., Yeom H., Son Y. Harvesting the aggregate computing power of commodity computers for supercomputing applications // Applied Sciences, 2022. V. 12, N 10, P. 5113.

5. Ong B. W., Schroder J. B. Applications of time parallelization // Computing and Visualization in Science, 2020. V. 23, N 1. P. 1-15.

6. Blagoveshchenskaya E., Zuev D., Kuznecova I., Tihomirov S. Prilozheniya algoritmov prvamvh razlozhenii abelevvh grupp bez krucheniva k zadacham rasparallelivaniva vvchislitel’nvh i konstruktivnyh processov //in Mezhdunarodnye Kolmogorovskie chteniya-XIV, posvyashchennye 100- letiyu professora Z. A. Skopeca, 2017. P. 38-40.

7. Stutzle T. Parallelization strategies for ant colony optimization //in International Conference on Parallel Problem Solving from Nature. Springer, 1998. P. 722-731.

8. Hassan M., Hasan M., Hashem M. et al. An improved acs algorithm for the solutions of larger tsp problems. arXiv preprint arXiv:1304.3763, 2013.

9. Liang D., Zhan Z.-H., Zhang Y., Zhang J. An efficient ant colony system approach for new energy vehicle dispatch problem // IEEE Transactions on Intelligent Transportation Systems, 2019. V. 21. N 11. P. 4784-4797.

10. Zhou X., Ma H., Gu J., Chen H., Deng W. Parameter adaptation-based ant colony optimization with dynamic hybrid mechanism // Engineering Applications of Artificial Intelligence, 2022. V. 114. P. 105139.

11. Olivas F., Valdez F., Castillo O., Gonzalez С. L, Martinez G., Melin P. Ant colony optimization with dynamic parameter adaptation based on interval type-2 fuzzy logic systems // Applied Soft Computing, 2017. V. 53. P. 74-87.

12. Blagoveshchenskaya E. A., Mikulik I. I., Strbungmann L. H. Ant colony optimization with parameter update using a genetic algorithm for travelling salesman problem // Models and Methods for Researching Information Systems in Transport 2020 (MMRIST 2020), 2020. N 1. P. 20-25.

13. Baydogmus G. К. A parallelization based ant colony optimization for travelling salesman problem //in 2022 1st International Conference on Information System & Information Technology (ICISIT). IEEE, 2022. P. 166-169.

14. Liu G., Xu X., Wang F., Tang Y. Solving traveling salesman problems based on artificial cooperative search algorithm // Computational Intelligence and Neuroscience, 2022. V. 2022.

15. El-Khatib S. , Skobtsov Y. , Rodzin S. , Zakharov V. Comparison of modified object detected graph cut and hybrid ant colony optimization-k-means for mri images segmentation //in Computer Science On-line Conference. Springer, 2021. P. 701-708.

16. Brand M., Masuda M., Wehner N., Yu X.-H. Ant colony optimization algorithm for robot path planning //in 2010 international conference on computer design and applications, V. 3. IEEE, 2010. P. V3-436.

17. Whitley D. Next generation genetic algorithms: a user’s guide and tutorial //in Handbook of metaheuristics. Springer, 2019. P. 245-274.

18. Katoch S., Chauhan S. S., Kumar V. A review on genetic algorithm: past, present, and future // Multimedia Tools and Applications, 2021. V. 80, N 5. P. 8091-8126.

19. Singh G., Gupta N. A study of crossover operators in genetic algorithms //in Frontiers in Nature-Inspired Industrial Optimization. Springer, 2022. P. 17-32.

20. Lambora A., Gupta K., Chopra K. Genetic algorithm-a literature review //in 2019 international conference on machine learning, big data, cloud and parallel computing (COMITCon). IEEE, 2019. P. 380-384.

Библиографическая ссылка: Микулик И. И., Благовещенская Е. А. Распараллеливание гибридного алгоритма муравьиной колонии с изменяющимися с помощью генетического алгоритма параметрами // Проблемы информатики. 2023.  № 2. С. 86-97. DOI: 10.24412/2073-0667-2023-2-86-97