Ant Colony Optimization (ACO) and a Variation of Bee Colony Optimization (BCO) in Solving TSP Problem: A Comparative Study

Print
International Journal of Computer Applications
© 2014 by IJCA Journal
Volume 96 - Number 9
Year of Publication: 2014
Authors:
Muhammed Basheer Jasser
Mohamad Sarmini
Rauf Yaseen
10.5120/16819-6587

Muhammed Basheer Jasser, Mohamad Sarmini and Rauf Yaseen. Article: Ant Colony Optimization (ACO) and a Variation of Bee Colony Optimization (BCO) in Solving TSP Problem: A Comparative Study. International Journal of Computer Applications 96(9):1-8, June 2014. Full text available. BibTeX

@article{key:article,
	author = {Muhammed Basheer Jasser and Mohamad Sarmini and Rauf Yaseen},
	title = {Article: Ant Colony Optimization (ACO) and a Variation of Bee Colony Optimization (BCO) in Solving TSP Problem: A Comparative Study},
	journal = {International Journal of Computer Applications},
	year = {2014},
	volume = {96},
	number = {9},
	pages = {1-8},
	month = {June},
	note = {Full text available}
}

Abstract

Traveler sales man problem is known research problem which has a lot of industrial applications. A lot of algorithms has been proposed to solve TSP, some of Ant Colony Optimization (ACO) and Bee Colony Optimization (BCO) algorithms. BCO algorithm has variations and enhancements to improve the performance. In this paper, a experimental comparison study between the basic Ant Colony Optimization and enhanced Bee Colony Optimization algorithms is done. Both ACO and enhanced BCO have been implemented using MATLAB. The comparison study includes comparing the time consumed, solution quality and algorithmic complexity in order to prove the effictivness and efficiency of each. The experimental study showed that the basic ACO outperforms the enhanced BCO in the required consumed time to get the solution path, while enhanced BCO proved to provide better solution quality.

References

  • David L Applegate. The traveling salesman problem: a computational study. Princeton University Press, 2006.
  • Mandeep Kaur Bedi and Sheena Singh. Fault detection techniques prioritization using bee colony optimization and then comparison with ant colony optimization. International Journal of Computer Applications, 69(17), 2013.
  • Aditi Chikhalikar and Avanti Darade. Swarm intelligence techniques: Comparative study of aco and bco. self, 4:5, 1995.
  • Marco Dorigo and Luca Maria Gambardella. Ant colony system: a cooperative learning approach to the traveling salesman problem. Evolutionary Computation, IEEE Transactions on, 1(1):53–66, 1997.
  • Xiutang Geng, Zhihua Chen, Wei Yang, Deqian Shi, and Kai Zhao. Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search. Applied Soft Computing, 11(4):3680–3689, 2011.
  • Wang Hui. Comparison of several intelligent algorithms for solving tsp problem in industrial engineering. Systems Engineering Procedia, 4:226–235, 2012.
  • Fozia Hanif Khan, Nasiruddin Khan, Syed Inayatullah, and Shaikh Tajuddin Nizami. Solving tsp problem by using genetic algorithm. International Journal of Basic & Applied Sciences, 9(10), 2009.
  • Evelia Liz´arraga, Oscar Castillo, and Jos´e Soria. A method to solve the traveling salesman problem using ant colony optimization variants with ant set partitioning. In Recent Advances on Hybrid Intelligent Systems, pages 237–246. Springer, 2013.
  • Mei Mi, Xue Huifeng, Zhong Ming, and Gu Yu. An improved differential evolution algorithm for tsp problem. In Intelligent Computation Technology and Automation (ICICTA), 2010 In-ternational Conference on, volume 1, pages 544–547. IEEE, 2010.
  • Eneko Osaba and Fernando D´ýaz. Comparison of a memetic algorithm and a tabu search algorithm for the traveling salesman problem. In Computer Science and Information Systems (FedCSIS), 2012 Federated Conference on, pages 131–136. IEEE, 2012.
  • DT Pham, A Ghanbarzadeh, E Koc, S Otri, S Rahim, and M Zaidi. The bees algorithm-a novel tool for complex optimisation problems. In Proceedings of the 2nd Virtual International Conference on Intelligent Production Machines and Systems (IPROMS 2006), pages 454–459, 2006.
  • R Sagayam and Mrs K Akilandeswari. Comparison of ant colony and bee colony optimization for spam host detection.
  • SN Sivanandam and SN Deepa. Genetic Algorithm Optimization Problems. Springer, 2008.
  • Li-Pei Wong, Malcolm Yoke Hean Low, and Chin Soon Chong. Bee colony optimization with local search for traveling salesman problem. International Journal on Artificial Intelligence Tools, 19(03):305–334, 2010.
  • Yong-Quan Zhou, Zheng-Xin Huang, and Hong-Xia Liu. Discrete glowworm swarm optimization algorithm for tsp problem. Dianzi Xuebao(Acta Electronica Sinica), 40(6):1164– 1170, 2012.
  • Nur Ariffin Mohd Zin, Siti Norul Huda Sheikh Abdullah, Noor Faridatul Ainun Zainal, and Esmayuzi Ismail. A comparison of exhaustive, heuristic and genetic algorithm for travelling salesman problem in prolog. International Journal on Advanced Science, Engineering and Information Technology, 2(6):49–53, 2012.

Keywords