Распараллеливание гибридного алгоритма муравьиной колонии с изменяющимися с помощью генетического алгоритма параметрами
Автор: Микулик И.И., Благовещенская Е.А.
Журнал: Проблемы информатики @problem-info
Рубрика: Параллельное системное программирование и вычислительные технологии
Статья в выпуске: 2 (59), 2023 года.
Бесплатный доступ
В работе рассмотрена возможность использования параллельной реализации гибридного метода оптимизации, использующего муравьиный и генетический алгоритмы, для решения задачи коммивояжера. Известно, что алгоритм муравьиной колонии чувствителен к изменению параметров, поэтому поиск подходящих параметров муравьиного алгоритма рассматривается в качестве задачи оптимизации, решение которой предоставляется генетическому алгоритму. Целью распараллеливания вычислений является сокращение временных затрат, но не все алгоритмы имеют эффективную параллельную реализацию. Известно, что генетический алгоритм и алгоритм муравьиной колонии распараллеливаются. В работе изучается возможность построения параллельных вычислений и для представленного гибридного метода. Задача коммивояжера, на которой проводится исследование, является NP-полной задачей и часто применяется для тестирования алгоритмов комбинаторной оптимизации. Показано, что распараллеливание используемого метода приводит к увеличению скорости выполнения работы алгоритма.
Распараллеливание, задача коммивояжера, методы оптимизации, муравьиные алгоритмы, генетический алгоритм, параллельные вычисления
Короткий адрес: https://sciup.org/143181003
IDR: 143181003 | УДК: 519.854.2 | DOI: 10.24412/2073-0667-2023-2-86-97
Parallel implementation of the ant colony algorithm with parameters update using the genetic algorithm
The paper considers the possibility of using a joint implementation of a hybrid method using the ant colony optimization with genetic algorithm for solving traveling salesman problem. It is known that the ant colony optimization is sensitive to its parameters, so the search for the optimal parameters of the ant colony is suitable as a problem, the solution of which is related to the genetic algorithm. The one of the purposes of calculations parallelization is to reduce execution time, but not every algorithm has an effective parallel implementation. It is known that the genetic algorithm and the ant colony optimization are parallelized. The paper studies the possibility of constructing parallel computations for the hybrid method presented. The traveling salesman problem on which the research is conducted is an NP-complete problem and it is often used to test combinatorial optimization algorithms. It is shown that parallelization of the method used leads to an increase in the speed of the algorithm.
Список литературы Распараллеливание гибридного алгоритма муравьиной колонии с изменяющимися с помощью генетического алгоритма параметрами
- 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.
