PNACO: Parallel Algorithm for Neighbour Joining Hybridized with Ant Colony Optimization on Multi-Core System

Одними из наиболее интересных и актуальных подходов к решению задач оптимизации являются параллельные алгоритмы, которые работают одновременно с большим количеством задач. В этой статье представлен новый параллельный алгоритм для NACO, т.е. гибридный алгоритм, который состоит из метода оптимизации колонии муравьев в сочетании с методом объединения соседей для получения точных и эффективных результатов при решении задачи коммивояжера. Результаты, полученные на практике при проведении всесторонних экспериментов с использованием большого количества реальных наборов данных и многоядерной системы, показали, что разработанная программа превосходит NACO с точки зрения времени выполнения и потребляемого дискового пространства. Доступность и реализация: исходные коды в MATLAB 2017 размещены в открытом доступе в сети Интернет.

Ключевые слова

оптимизация колонии муравьев; метод объединения соседей; задача коммивояжера; параллельный алгоритм; многоядерная система.

Литература

1. Yahia W.B., Al-Neama M.W., Arif G.E. A Hybrid Optimization Algorithm of Ant Colony Search and NeighbourJoining Method to Solve the Travelling Salesman Problem. Advanced Mathematical Models and Applications, 2020, vol. 5, no. 1, pp. 95-110.
2. Hsu-Chih Huang. SoPC-Based Parallel ACO Algorithm and Its Application to Optimal Motion Controller Design for Intelligent Omnidirectional Mobile Robots. IEEE Transactions on Industrial Informatics, 2012, vol. 9, no. 4, pp. 1828-1835.
3. Yi Zhou, Fazhi He, Yimin Qiu. Dynamic Strategy Based Parallel Ant Colony Optimization on GPUs for TSPs. Science China Information Sciences, 2017, vol. 60, no. 6, article ID: 068102, 12 p. DOI: 10.1007/s11432-015-0594-2
4. Al-Neama M.W., Naglaa M.R., Fayed F.G. An Improved Distance Matrix Computation Algorithm for Multicore Clusters. Journal of Biomedicine and Biotechnology, 2014, article ID: 406178, 13 p. DOI: 10.1155/2014/406178
5. Kotenko I.V., Saenko I.B., Kushnerevich A.G. Architecture of the Parallel Big Data Processing System for Security Monitoring of IOT Networks. SPIIRAS Proceedings, 2018, vol. 59, pp. 5-30.
6. Al-Neama M.W., Naglaa M.R. A Study of Parallel Algorithms for Multiple Sequence Alignment. Ph.D. Thesis, Al-Azhar University, 2014.
7. Nikiforov V.V., Shkirtil V.I. Estimation of Blocking Factor for Tasks in Real-Time Systems with Multi-Core Processors. SPIIRAS Proceedings, 2013, vol. 27, pp. 93-106.
8. The Math Works, Computer Software. Available at: https://www.mathworks.com (accessed 13.11.2020).
9. Peng Li, Hua Zhu. Parameter Selection for Ant Colony Algorithm Based on Bacterial Foraging Algorithm. Mathematical Problems in Engineering, 2016, article ID: 6469721, 10 p. DOI: 10.1155/2016/6469721
10. Yongbo Yuan, Kai Wang, Le Ding. A Solution to Resource-Constrained Project Scheduling Problem: Based on Ant Colony Optimization Algorithm. Ninth International Conference on Hybrid Intelligent Systems, Shenyang, China, 2009, vol. 1, article ID: 10891196, 13 p. DOI: 10.1109/HIS.2009.92