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

One of the most interesting and relevant approaches for solving optimization problems are parallel algorithms that work simultaneously with a large number of tasks. The paper presents a new parallel algorithm for NACO that is a hybrid algorithm that consists of the Ant Colony Optimization method combined with the Neighbour Joining method to get accurate and efficient results when solving the Traveling Salesman Problem. Through carrying out comprehensive experiments using a wide variety of real dataset sizes and the multi-core system, the practical results show that the developed program outperforms NACO in terms of execution time and consumed storage space. Availability and implementation: source codes in MATLAB 2017 are publicly available at Internet\footnotehttps://in.mathworks.com/matlabcentral/fileexchange/79131-parallel-naco-for-tsp?s_tid=srchtitle.

Keywords

ant colony optimization; neighbour joining method; traveling salesman problem; parallel algorithm; multi-core system.

References

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