Kombinasi Firefly Algorithm-Tabu Search untuk Penyelesaian Traveling Salesman Problem

Riyan Naufal Hay's

doi:10.15575/join.v2i1.63

Kombinasi Firefly Algorithm-Tabu Search untuk Penyelesaian Traveling Salesman Problem

Riyan Naufal Hay's

Abstract

Traveling Salesman Problem (TSP) adalah masalah optimasi kombinatorial klasik dan memiliki peran dalam perencanaan, penjadwalan, dan pencarian pada bidang rekayasa dan pengetahuan (Dong, 2012). TSP juga merupakan objek yang baik untuk menguji kinerja metode optimasi, beberapa metode seperti Cooperative Genetic Ant System (CGAS) (Dong, 2012), Parallelized Genetic Ant Colony System (PGAS) Particle Swarm Optimization and Ant Colony Optimization Algorithms (PSO–ACO) (Elloumi, 2014), dan Ant Colony Hyper-Heuristics (ACO HH) (Aziz, 2015) 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 (Layeb, 2014). FA merupakan algoritma yang berpotensi kuat dalam memecahkan kasus optimasi dibanding algoritma yang ada termasuk Particle Swarm Optimization (Yang, 2010). Namun, FA memiliki kekurangan dalam memecahkan masalah optimasi dengan skala besar (Baykasoğlu dan Ozsoy, 2014). Tabu Search (TS) merupakan metode optimasi yang terbukti efektif untuk memecahkan masalah optimasi dengan skala besar (Pedro, 2013). 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.

Keywords

Firefly Algorithm; Tabu Search; Traveling Salesman Problem

Full Text:

PDF (Bahasa Indonesia)

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.

Article Statistics

Abstract view : 1075 times
PDF (Bahasa Indonesia) - 1010 times

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

Refbacks

JOIN has been indexed by :

This work is licensed under a Creative Commons Attribution-NoDerivs 2.0 Generic License.

Jurnal Online Informatika

Kombinasi Firefly Algorithm-Tabu Search untuk Penyelesaian Traveling Salesman Problem

Abstract

Keywords

Full Text:

References

Article Statistics

Refbacks

User

Notifications

Journal Content

Browse

Language

About Us Journal

More Info