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

Olief Ilmandira Ratu Farisi, Budi Setiyono, R. Imbang Danandjojo

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.


Full Text:

PDF

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.




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

Refbacks

  • There are currently no refbacks.