Kombinasi Firefly Algorithm-Tabu Search untuk Penyelesaian Traveling Salesman Problem

Authors

  • Riyan Naufal Hay's

DOI:

https://doi.org/10.15575/join.v2i1.63

Keywords:

Firefly Algorithm, Tabu Search, Traveling Salesman Problem

Abstract

Traveling Salesman Problem (TSP) adalah masalah optimasi kombinatorial klasik dan memiliki peran dalam perencanaan, penjadwalan, dan pencarian pada bidang rekayasa dan pengetahuan. TSP juga merupakan objek yang baik untuk menguji kinerja metode optimasi, beberapa metode seperti Cooperative Genetic Ant System (CGAS), Parallelized Genetic Ant Colony System (PGAS) Particle Swarm Optimization and Ant Colony Optimization Algorithms (PSO–ACO), dan Ant Colony Hyper-Heuristics (ACO HH) telah dikembangkan untuk memecahkan TSP. Sehingga, pada penelitian ini diimplementasikan kombinasi metode baru untuk meningkatkan akurasi penyelesaian TSP. Firefly Algorithm (FA) merupakan salah satu algoritma yang dapat digunakan untuk memecahkan masalah optimasi kombinatorial. FA merupakan algoritma yang berpotensi kuat dalam memecahkan kasus optimasi dibanding algoritma yang ada termasuk Particle Swarm Optimization. Namun, FA memiliki kekurangan dalam memecahkan masalah optimasi dengan skala besar. Tabu Search (TS) merupakan metode optimasi yang terbukti efektif untuk memecahkan masalah optimasi dengan skala besar. Pada penelitian ini, TS akan diterapkan pada FA (FATS) untuk memecahkan kasus TSP. Hasil FATS akan dibandingkan terhadap penelitian sebelumnya yaitu ACOHH. Perbandingan hasil menunjukan peningkatan akurasi sebesar 0.89% pada dataset Oliver30, 0.14% dataset Eil51, 3.81% dataset Eil76 dan 1.27% dataset KroA100.

References

Ade Trisnawati, I. B. (2011). Implementasi Tabu Search untuk Penjadwalan Kelas. Seminar Nasional Teknologi Informasi (pp. 1-15). Jakarta: Universitas Tarumanegara.

Adil Hashmi, N. G. (2013). Firefly Algorithm for Unconstrained Optimization. Journal of Computer Engineering , 1-4.

Ahmed Ahmed El-Sawy, E. M.-A. (2013). A Novel Hybrid Ant Colony Optimization and Firefly Algorithm for Solving. Journal of Natural Sciences and Mathematics , 1-22.

Ahmed Ahmed El-Sawy, E. M.-A. (2013). Hybridizing Ant colony Optimization With Firefly Algorithm For Unconstrained Optimization Problems. The Online Journal on Computer Science and Information Technology , 1-9.

Alam, M. N. (2016, March 8). Particle Swarm Optimization: Algorithm and its Codes in MATLAB. pp. 1-11.

Ali, N. (2014). A Review Of Firefly Algorithm. ARPN Journal of Engineering and Applied Sciences , 1-5.

Aulia Rahma Amin, M. I. (2005). Traveling Salesman Problem. Bandung: Departemen Teknik Informatika, Institut Teknologi Bandung.

Aziz, Z. A. (2015). Ant Colony Hyper-heuristics for Travelling Salesman Problem. IEEE International Symposium on Robotics and Intelligent Sensors , 1-5.

Benayad, Z. (2014). A Novel Firefly Algorithm Based Ant Colony Optimization. International Journal of Computer Science and Applications , 1-19.

Buyukozkan, K. (2015). Lexicographic bottleneck mixed-model assembly line balancing. Expert Systems With Applications , 1-16.

Dong, G. (2012). Solving the traveling salesman problem using cooperative genetic ant systems. Expert Systems with Applications , 1-6.

Dr.T.Govindaraj1, V. (2014). Firefly Algorithm for Optimal Power Flow Considering Control Variables. International Journal Of Innovative Research In Electrical, Electronics, Instrumentation And Control Engineering, 1-6.

Eduardo Rodriguez-Tello, H.-M. G.-T. (2014). Tabu Search for The Cyclic Bandwidth Problem. Computers & Operations Research , 1-16.

Elloum, W. (2014). A comparative study of the improvement of performance using a PSOmodified by ACO applied to TSP. Applied Soft Computing , 1-8.

Glove,F, (2012),”Candidate List strategies and Tabusearch”, CAAI Research report, University Of Colorado, Boulder.

Isra Natheer Alkallak, R. Z. (2008). Tabu Search Method for Solving the Traveling salesman Problem. Raf. J. of Comp. & Math’s. , Vol. 5, No. 2 , 1-13.

Jayaswal, S. (2015). A Comparative Study of Tabu Search and Simulated Annealing for Traveling Salesman Problem. University of Waterloo: Department of Management Sciences.

Katagiri, H. (2012). A hybrid algorithm based on tabu search and ant colony optimization for k-minimum spanning tree problems. Expert Systems with Applications , 1-6.

Kratika Chandra, S. S. (2014). Firefly Algorithm to Solve Two Dimensional Bin Packing Problem. International Journal of Computer Science and Information Technologies , 1-6.

Krishna H. Hingrajiya, R. K. (2012). An Ant Colony Optimization Algorithm for Solving Travelling Salesman Problem. International Journal of Scientific and Research Publications, Volume 2 , 1-6.

Kumbharana, S. N. (2013). Solving Travelling Salesman Problem using Firefly Algorithm. International Journal for Research in Science & Advanced Technologies , 1-5.

Latifa DEKHICI, K. B. (2012). Firefly Algorithm for Economic Power Dispatching With Pollutants Emission. Informatica Economic? vol. 16, no 2 , 1-13.

M. K. A. Ariyaratne, T. G. (2014). A Comparative Study on Nature Inspired Algorithms with Firefly Algorithm. International Journal of Engineering and Technology , 1-7.

Mardlijah, A. J. (2013). A New Combination Method Of Firefly Algorithm And T2fsmc For Mobile Inverted Pendulum Robot. Journal of Theoretical and Applied Information Technology , 1-8.

Pedro, O. (2013). A Tabu Search Approach for the Prize. Electronic Notes in Discrete Mathematics , 1-8.

Puspitorini, S. (2011). Penyelesaian Masalah Traveling Salesman. Media Informatika, Vol. 6, No. 1 , 1-17.

Rabindra Kumar Sahu, S. P. (2015). A hybrid firefly algorithm and pattern search technique for automatic. Electrical Power and Energy Systems , 1-15.

Retrieved from MP-TESTDATA - The TSPLIB Symmetric Traveling Salesman Problem Instances: http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html

Retrieved from ScienceDirect: http://www.sciencedirect.com/

Retrieved from SCI-HUB: http://sci-hub.io/

Salari, M. (2015). Combining ant colony optimization algorithm and dynamic. Computers & Industrial Engineering , 1-8.

Sh. M. Farahani, A. A. (2011). A Gaussian Firefly Algorithm. International Journal of Machine Learning and Computing , 1-6.

Singh, S. A. (2013). The Firefly Optimization Algorithm: Convergence Analysis and Parameter Selection. International Journal of Computer Applications , 1-5.

Su, S. (2014). Comparisons of Firefly Algorithm with Chaotic Maps. Computer Modelling & New Technologies , 1-7.

Teams, Y. (2016). Retrieved from Yarpiz: http://yarpiz.com/259/ypea112-firefly-algorithm

The MathWorks, Inc. (2016). Retrieved March 2016, from Mathworks:http://www.mathworks.com/help/optim/ug/travelling-salesman-problem.html

Vittorio Maniezzo, L. M. (2013). Ant Colony Optimizatio. The Future & Emerging Technologies.

Wang, X. (2011). Hybrid Differential Evolution Algorithm for Traveling. Advanced in Control Engineeringand Information Science , 1-5.

Xin-SheYang. (2010). Engineering Optimization. New Jersey: John Wiley & Sons, Inc.

Yang, X.-S. (2010). Firefly Algorithm, Stochastic Test Functions and Design. Department of Engineering, University of Cambridge , 1-12.

Yang, X.-S. (2009). Firefly Algorithms for Multimodal Optimization. pp. 1-10.

Yang, X.-S. (2013). Swarm Intelligence and Bio-Inspired Computation. London: Elsevier.

Downloads

Published

2017-07-01

Issue

Vol. 2 No. 1 (2017)

Section

Article

Citation Check

License

Copyright (c) 2017 Jurnal Online Informatika

Creative Commons License

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

You are free to:

 

Under the following terms:

  • Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.

  • NoDerivatives — If you remix, transform, or build upon the material, you may not distribute the modified material.

  • No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.

 

Notices:

  • You do not have to comply with the license for elements of the material in the public domain or where your use is permitted by an applicable exception or limitation.
  • No warranties are given. The license may not give you all of the permissions necessary for your intended use. For example, other rights such as publicity, privacy, or moral rights may limit how you use the material.

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