Распараллеливание гибридного алгоритма муравьиной колонии с изменяющимися с помощью генетического алгоритма параметрами
Автор: Микулик И.И., Благовещенская Е.А.
Журнал: Проблемы информатики @problem-info
Рубрика: Параллельное системное программирование и вычислительные технологии
Статья в выпуске: 2 (59), 2023 года.
Бесплатный доступ
В работе рассмотрена возможность использования параллельной реализации гибридного метода оптимизации, использующего муравьиный и генетический алгоритмы, для решения задачи коммивояжера. Известно, что алгоритм муравьиной колонии чувствителен к изменению параметров, поэтому поиск подходящих параметров муравьиного алгоритма рассматривается в качестве задачи оптимизации, решение которой предоставляется генетическому алгоритму. Целью распараллеливания вычислений является сокращение временных затрат, но не все алгоритмы имеют эффективную параллельную реализацию. Известно, что генетический алгоритм и алгоритм муравьиной колонии распараллеливаются. В работе изучается возможность построения параллельных вычислений и для представленного гибридного метода. Задача коммивояжера, на которой проводится исследование, является NP-полной задачей и часто применяется для тестирования алгоритмов комбинаторной оптимизации. Показано, что распараллеливание используемого метода приводит к увеличению скорости выполнения работы алгоритма.
Распараллеливание, задача коммивояжера, методы оптимизации, муравьиные алгоритмы, генетический алгоритм, параллельные вычисления
Короткий адрес: https://sciup.org/143181003
IDR: 143181003 | DOI: 10.24412/2073-0667-2023-2-86-97
Список литературы Распараллеливание гибридного алгоритма муравьиной колонии с изменяющимися с помощью генетического алгоритма параметрами
- Zhang N. Moore’s law is dead, long live moore’s law! // arXiv preprint arXiv:2205.15011, 2022.
- 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).
- 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.
- 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.
- Ong B. W., Schroder J. B. Applications of time parallelization // Computing and Visualization in Science, 2020. V. 23, N 1. P. 1-15.
- 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.
- Stutzle T. Parallelization strategies for ant colony optimization //in International Conference on Parallel Problem Solving from Nature. Springer, 1998. P. 722-731.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Whitley D. Next generation genetic algorithms: a user’s guide and tutorial //in Handbook of metaheuristics. Springer, 2019. P. 245-274.
- 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.
- Singh G., Gupta N. A study of crossover operators in genetic algorithms //in Frontiers in Nature-Inspired Industrial Optimization. Springer, 2022. P. 17-32.
- 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.
