Parallel Artificial Bee Colony Algorithm for the Traveling Salesman Problem

Abstract:

Artificial Bee Colony Algorithm (ABCA) is a novel swarm intelligence algorithm which a colony of artificial bees cooperate in finding good solutions for numerical optimization problems and combinatorial optimization problems. Traveling Salesman Problem (TSP) is a famous combinatorial optimization problem which has been used in many fields such as network communication, transportation, manufacturing and logistics. However, it requires a considerably large amount of computational time and resources for solving TSP. To dealing with this problem, we present a Parallel Artificial Bee Colony Algorithm (PABCA) in several computers which operation system is Linux based on the Message Passing Interface (MPI). The entire artificial bee colony is divided into several subgroups by PABCA equally. Each subgroup performs an ABCA for TSP on each processor node, respectively. Each sub-colony on every processor node communicates the current best fitness function and parameters of current best fitness function according to ring topological structure during calculation process. Some well-known benchmark problems in TSP are used to evaluate the performance of ABCA and PABCA. Meanwhile, the performance of PABCA is compared with Genetic Algorithm (GA) and Particle Swarm Optimization (PSO). Experimental results show that the PABCA can obtain solutions with equal precision and reduce the time of computation obviously in comparison with serial ABCA. And PABCA have much better performance in contrast with GA and PSO.

• Periodical: Advanced Materials Research (Volumes 756-759)
• Pages: 3254-3259
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.756-759.3254
• Online since: September 2013
• Authors: Kun Xu, Ming Yan Jiang, Dong Feng Yuan
• Keywords: Artificial Bee Colony Algorithm, Message Passing Interface, Parallel Algorithm, Traveling Salesman Problem (TSP)

References

[1] J.R.L. Fournier , S. Pierre, Assigning cells to switches in mobile networks using an ant colony optimization heuristic, , Computer Communications., vol. 28, pp.65-73, (2005).

DOI: 10.1016/j.comcom.2004.07.006

[2] J.E. Bella, P.R. McMullen, Ant colony optimization techniques for the vehicle routing problem, Advanced Engineering Informatics., vol. 18, pp.41-48, (2004).

DOI: 10.1016/j.aei.2004.07.001

[3] T.P. Bagchi, IN.D. Gupta, C. Sriskandarajah, A review of TSP based approaches for flowshop scheduling, European Journal of Operational Research, pp.816-854, (2006).

DOI: 10.1016/j.ejor.2004.06.040

[4] C.A. Silvaa, J.M.C. Sousaa, T.A. Runkler, Rescheduling and optimization of logistic processes using GA and ACO, Engineering Applications of Artificial Intelligence, vol. 21, pp.343-352, (2008).

DOI: 10.1016/j.engappai.2007.08.006

[5] Jiang Mingyan, Yuan Dongfeng, Artificial Fish Swarm Algorithm and its applications,. Science Press, Beijing, China, (2012).

[6] Jiang-wei Zhang, Wen-jian Si, Improved Enhanced Self-Tentative PSO algorithm for TSP, Proceedings of the Sixth International Conference on Natural Computation, p.2638 – 2641, (2010).

DOI: 10.1109/icnc.2010.5583011

[7] Wei-xin Ling, Huan-ping Luo, An Adaptive Parameter Control Strategy for Ant Colony Optimization, Proceedings of the 2007 International Conference on Computational Intelligence and Security, p.142 – 146, (2007).

DOI: 10.1109/cis.2007.156

[8] Kun Xu, Mingyan Jiang, Optimal Tuning of Robust Controller Based on Artificial Bee Colony Algorithm, Advanced Materials Research Vols. 562-564, pp.1668-1672, 30 April. (2012).

DOI: 10.4028/www.scientific.net/amr.562-564.1668