A Hybrid Firefly Algorithm - Ant Colony Optimization for Traveling Salesman Problem

Authors

  • Olief Ilmandira Ratu Farisi Study Program Mathematics, Faculty of Mathematics and Science, Institut Teknologi Sepuluh Nopember
  • Budi Setiyono Study Program Mathematics, Faculty of Mathematics and Science, Institut Teknologi Sepuluh Nopember
  • R. Imbang Danandjojo Badan Penelitian dan Pengembangan Perhubungan, Kementerian Perhubungan Republik Indonesia Kementerian Perhubungan Republik Indonesia

DOI:

https://doi.org/10.24002/jbi.v7i1.484

Abstract

Abstract. In this paper, we develop a novel method hybrid firefly algorithm-ant colony optimization for solving traveling salesman problem. The ACO has distributed computation to avoid premature convergence and the FA has a very great ability to search solutions with a fast speed to converge. To improve the result and convergence time, we used hybrid method. The hybrid approach involves local search by the FA and global search by the ACO. Local solution of FA is normalized and is used to initialize the pheromone for the global solution search using the ACO. The outcome are compared with FA and ACO itself. The experiment showed that the proposed method can find the solution much better without trapped into local optimum with shorter computation time.

Keywords: Traveling Salesman Problem, Firefly Algorithm, Ant Colony Optimization, hybrid method.


Abstrak. Pada penelitian ini dikembangkan suatu metode baru yaitu hybrid firefly algorithm-ant colony optimization (hybrid FA-ACO) untuk menyelesaikan masalah traveling salesman problem (TSP). ACO memiliki komputasi terdistribusi sehingga dapat mencegah konvergensi dini dan FA memiliki kemampuan konvergensi yang cepat dalam pencarian solusi. Untuk memperbaiki solusi dan mempercepat waktu konvergensi, digunakan metode kombinasi. Pendekatan kombinasi ini meliputi pencarian solusi dengan FA dan pencarian global dengan ACO. Solusi lokal dari FA dinormalisasi dan digunakan untuk menginisialisasi feromon untuk pencarian global ACO. Hasil dari hybrid FA-ACO dibandingkan dengan FA dan ACO. Hasil penelitian menunjukkan bahwa metode yang diusulkan dapat menemukan solusi yang lebih baik tanpa terjebak lokal optimum dengan waktu komputasi lebih pendek.

Kata kunci: Traveling Salesman Problem, Firefly Algorithm, Ant Colony Optimization, metode hybrid.

References

. Braun, H. 1991. On Solving Travelling Salesman Problems by Genetic Algorithm. In: 1st Workshop, PPSN I Dortmund, FRG, October 1–3, 1990 Proceedings, vol. 496, Springer-Verlag, Berlin, Heidelberg, Lecture Notes in Computer Science, 129-133.

. Clerc, M. 2004. Discrete Particle Swarm Optimization, illustrated by Traveling Salesman Problem. New Optimization Techniques in Engineering, Springer-Verlag, Berlin, Heidelberg, Studies in Fuzziness and Soft Computing vol. 141, 219-239.

. Dorigo, M., Maniezzo, V, & Colorni, A. 1996. The Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on System, Man, and Cybernetics-Part B: Cybernetics, 26(1): 29-41.

. Hassan, M.R., Hasan, M.K., & Hashem, M.M.A. 2013. An Improved ACS Algorithm for the Solutions of Larger TSP Problems. In: Proceedings of the ICEECE December 22-24, Dhaka, Bangladesh.

. Hlaing, Z.C.S.S. & Khine, M.A. December 2011. Solving Traveling Salesman Problem by Using Improved Ant Colony Optimization Algorithm. International Journal of Information and Education Technology, 1(5): 404-409.

. Jati, G.K. & Suyanto. 2011. Evolutionary Discrete Firefly Algorithm for Travelling Salesman Problem. In: Proceedings of Second International Conference ICAIS 2011, LNAI 6943, Eds. Bouchachia, A., University of Klagenfurt, Klagenfurt, 393-403.

. Jati, G.K., Manurung, R., & Suyanto. 2013. Discrete Firefly Algorithm for Traveling Salesman Problem: A New Movement Scheme. Swarm Intelligence and Bio-Inspired Computation, 295-312.

. Jellouli, O., 2001. Intelligent dynamic programming for the generalized traveling salesman problem. In: Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, vol. 4. IEEE Computer Society, Washington, DC, 2765-2768.

. Jiang, H., Zhou, Z., Zhou, P., & Chen, G.L. 2005. Union Search: A New Metaheuristic Algorithm to the Traveling Salesman Problem. J. Univ. Sci. Technol. China, 35: 367-375.

. Land, A., & Doig, A.1960. An Automatic Method of Solving Discrete Programming Problems. Econometrica. 28 (3), 497-520.

. Lenstra, J.K. & Rinnooy Kan, A.H.G. 1975. Some Simple Applications of Travelling Salesman Problem. Opl Res. Q., Pergamon Press, 26(4): 717-733.

. Lin, S., & Kernighan, B. 1973. “An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Oper. Res, 21(2): 498-516.

. TSPLIB95: Ruprecht—Karls—Universitat Heildelberg, 2011. (Online), (http://www.iwr.uini-heidelberg.de/groups/comopt/software/TSPLIB95/, accessed May 10th, 2015).

. Yang, X.S. 2010. Nature-Inspired Metaheuristic Algorithm, 2nd edition. United Kingdom: Luniver Press.

Downloads

Published

2016-01-31

Issue

Vol. 7 No. 1 (2016): Jurnal Buana Informatika Volume 7 Nomor 1 Januari 2016

Section

Articles

License

Copyright of this journal is assigned to Jurnal Buana Informatika as the journal publisher by the knowledge of author, whilst the moral right of the publication belongs to author. Every printed and electronic publications are open access for educational purposes, research, and library. The editorial board is not responsible for copyright violation to the other than them aims mentioned before. The reproduction of any part of this journal (printed or online) will be allowed only with a written permission from Jurnal Buana Informatika.

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.