Perbandingan Implementasi Evolutionary Algorithm (EPO, FHO, dan CFA) pada Kasus Travelling Salesman Problem untuk Tempat Pariwisata di Surabaya

Authors

  • Christian Chen Institut Sains dan Teknologi Terpadu Surabaya
  • David Cahyadi Institut Sains dan Teknologi Terpadu Surabaya
  • Jonathan Arelio Bevan Institut Sains dan Teknologi Terpadu Surabaya
  • Williandy Takhta Institut Sains dan Teknologi Terpadu Surabaya
  • Ariel Lesmana Institut Sains dan Teknologi Terpadu Surabaya
  • Christopher Poernomo Institut Sains dan Teknologi Terpadu Surabaya
  • Widean Nagari Institut Sains dan Teknologi Terpadu Surabaya

DOI:

https://doi.org/10.52985/insyst.v5i1.258

Keywords:

Cuttlefish Algorithm, Emperor Penguin Optimizer, Fire Hawk Optimizer, Travelling Salesman Problem

Abstract

Traveling merupakan bisnis yang tumbuh pesat di seluruh dunia, dan Indonesia tidak terkecuali. Di Indonesia, khususnya Surabaya, industri pariwisata telah mengalami peningkatan dalam beberapa tahun terakhir, dan diharapkan akan terus tumbuh dalam beberapa tahun ke depan. Dengan peningkatan tersebut, pencarian rute untuk pariwisata harus efisien dan cepat, salah satu solusi yang populer saat ini adalah Evolutionary Algorithms (EA). Algoritma evolusi adalah jenis teknik optimisasi yang meniru proses evolusi alami untuk menemukan solusi terhadap masalah yang kompleks. Salah satu permasalahan yang dapat diselesaikan dengan efektif menggunakan algoritma evolusi adalah Traveling Salesman Problem (TSP). Permasalahan tersebut melibatkan pengunjungan pada beberapa kota dan menemukan rute terpendek untuk kembali ke titik awal. Beberapa algoritma evolusi telah dicadangkan untuk menyelesaikan TSP, seperti algoritma Cuttlefish (CFA), Emperor Penguin Optimizer (EPO) dan Fire Hawk Optimizer (FHO). Algoritma sotong didasarkan pada perilaku sotong liar, EPO terinspirasi oleh perilaku berkerumun dari penguin kaisar, sedangkan FHO menggunakan prinsip propagasi api. Semua algoritma yang telah disebutkan tadi memiliki potensi untuk menyelesaikan TSP dengan keunikannya masing-masing. Kesimpulan kami untuk semua algoritma yang digunakan dalam penelitian ini adalah bahwa EPO berhasil menemukan solusi terbaik diikuti dengan solusi dari CFA dan FHO. Berdasarkan hasil percobaan kami, didapatkan EPO menghasilkan solusi 39.97% lebih baik dari CFA serta 14.75% lebih baik dari FHO secara rata-rata. Serta EPO juga memiliki waktu komputasi rata-rata lebih cepat (69.59% lebih cepat dari CFA dan 178.34% lebih cepat dari FHO).

References

A. E. Eiben and G. Rudolph, “Theory of evolutionary algorithms: a bird’s eye view,” 1999. [Online]. Available: www.elsevier.com/locate/tcs

A. N. Sloss and S. Gustafson, “2019 Evolutionary Algorithms Review,” Jun. 2019, [Online]. Available: http://arxiv.org/abs/1906.08870

T. Bartz-Beielstein, J. Branke, J. Mehnen, and O. Mersmann, “Evolutionary Algorithms,” Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, vol. 4, no. 3. Wiley-Blackwell, pp. 178–195, 2014. doi: 10.1002/widm.1124.

K. L. Hoffman and M. Padberg, “Traveling salesman problem,” in Encyclopedia of Operations Research and Management Science, New York, NY: Springer US, 2001, pp. 849–853. doi: 10.1007/1-4020-0611-X_1068.

Z. Hashim and W. R. Ismail, “Applications of Travelling Salesman Problem in Optimizing Tourist Destinations Visit in Langkawi,” in Regional Conference on Science, Technology and Social Sciences (RCSTSS 2014), Springer Singapore, 2016, pp. 265–273. doi: 10.1007/978-981-10-0534-3_25.

O. Nurdiawan, F. A. Pratama, D. A. Kurnia, Kaslani, and N. Rahaningsih, “Optimization of Traveling Salesman Problem on Scheduling Tour Packages using Genetic Algorithms,” in Journal of Physics: Conference Series, 2020, vol. 1477, no. 5. doi: 10.1088/1742-6596/1477/5/052037.

F. Hanif Khan, N. Khan, and S. Inayatullah, “SOLVING TSP PROBLEM BY USING GENETIC ALGORITHM,” Article in International Journal of Basic & Applied Sciences, vol. 28, p. 170, 2010, [Online]. Available: https://www.researchgate.net/publication/236009452

J. Juwairiah, D. Pratama, H. C. Rustamaji, H. Sofyan, and D. B. Prasetyo, “Genetic Algorithm for Optimizing Traveling Salesman Problems with Time Windows (TSP-TW),” International Journal of Artificial Intelligence & Robotics (IJAIR), vol. 1, no. 1, pp. 1–8, Nov. 2019, doi: 10.25139/ijair.v1i1.2024.

M. Tryana Sembiring and S. Chailes, “Ant Colony Optimization Implementation on Traveling Salesman Problem to Achieve the Shortest Logistic Route,” in IOP Conference Series: Materials Science and Engineering, Dec. 2020, vol. 1003, no. 1. doi: 10.1088/1757-899X/1003/1/012045.

A. Sabry Eesa, A. Mohsin Abdulazeez, Z. Orman, A. Mohsin, and A. Brifcani, “A Novel Bio-Inspired Optimization Algorithm Analysis of Health Data with Heuristic Learning Methods View project A New Dimensional Reduction Approach Based on Cuttlefish Algorithm and K-Nearest Neighbor for Gene Expression Data View project Cuttlefish Algorithm-A Novel Bio-Inspired Optimization Algorithm,” Article in International Journal of Scientific and Engineering Research, vol. 4, no. 9, 2013, [Online]. Available: http://www.ijser.org

G. Dhiman and V. Kumar, “Emperor penguin optimizer: A bio-inspired algorithm for engineering problems,” Knowl Based Syst, vol. 159, pp. 20–50, Nov. 2018, doi: 10.1016/j.knosys.2018.06.001.

M. Azizi, S. Talatahari, and A. H. Gandomi, “Fire Hawk Optimizer: a novel metaheuristic algorithm,” Artif Intell Rev, 2022, doi: 10.1007/s10462-022-10173-w.

Dr. James B. Wood, “http://www.thecephalopodpage.org/.”

H. Armanto, R. Kevin, and C. Pickerling, “Perencanaan Perjalanan Wisata Multi Kota dan Negara dengan Algoritma Cuttlefish,” INSYST, vol. 1, no. 2, pp. 99–109, Dec. 2019.

A. S. Eesa, Z. Orman, and A. M. A. Brifcani, “A novel feature-selection approach based on the cuttlefish optimization algorithm for intrusion detection systems,” Expert Syst Appl, vol. 42, no. 5, pp. 2670–2679, Apr. 2015, doi: 10.1016/j.eswa.2014.11.009.

R. Li, J. Yang, X. Tuo, and R. Shi, “Research on Fitness Function of Two Evolution Algorithms Using for Neutron Spectrum Unfolding,” 2021.

Downloads

Additional Files

Published

2023-04-13

How to Cite

[1]
C. Chen, “Perbandingan Implementasi Evolutionary Algorithm (EPO, FHO, dan CFA) pada Kasus Travelling Salesman Problem untuk Tempat Pariwisata di Surabaya”, INSYST, vol. 5, no. 1, pp. 23–38, Apr. 2023.