Implementasi Algoritma Evolusi FHO, MVPA, dan HHO pada TSP di Tempat Pariwisata Pulau Bali
DOI:
https://doi.org/10.52985/insyst.v5i1.260Keywords:
Algoritma Optimasi, Evolutionary Computation, Travelling Salesman ProblemAbstract
Kegiatan berlibur merupakan kegiatan yang diperlukan baik perseorangan maupun bersama keluarga. Pembuatan rute perjalanan yang optimal dari banyak wisata liburan terkadang menjadi permasalahan rumit dan perlu dipikirkan rute optimalnya secara keseluruhan. Dalam ilmu komputer, permasalahan mencari rute optimal pada sebuah jaringan ini dikenal dengan Traveling Salesman Problem. Untuk mendapatkan rute yang baik, diperlukan algoritma khusus yang mampu mengevaluasi rute perjalanan dan memberikan hasil perjalanan yang cukup optimal. Di dalam penelitian ini, 4 algoritma Evolutionary Computation yaitu HHO (Harris Hawk Optimization), FHO (Fire Hawk Optimization), MVPA (Most Valuable Player Algorithm) dan modifikasi dari algoritma MVPA dibandingkan untuk menyelesaikan permasalahan TSP pada 55 lokasi wisata di Pulau Bali. Setelah dilakukan beberapa percobaan, HHO merupakan algoritma dengan nilai fitness terbaik dan konsisten tetapi dengan waktu eksekusi yang lebih lama. Sementara algoritma FHO memiliki waktu eksekusi yang lebih cepat tetapi nilai fitness yang lebih buruk dibandingkan dengan HHO dan MVPA. Algoritma MVPA yang telah dimodifikasi dapat memberikan hasil yang lebih baik meskipun masih belum bisa sebaik HHO. Secara kualitatif, algoritma HHO memberikan hasil perjalanan yang lebih baik dengan jarak tempuh tidak terlalu bervariasi setiap harinya. Hal ini membantu pelaku wisata agar dapat memanfaatkan waktu lebih banyak dalam menikmati lokasi wisata dibandingkan waktu perjalanan yang terbuang.
References
D. L. Applegate, R. E. Bixby, V. Chvátal, and W. J. Cook, The traveling salesman problem: A computational study. 2011.
A. A. Heidari, S. Mirjalili, H. Faris, I. Aljarah, M. Mafarja, and H. Chen, “Harris hawks optimization: Algorithm and applications,” Future Generation Computer Systems, vol. 97, pp. 849–872, Aug. 2019, doi: 10.1016/j.future.2019.02.028.
A. P. Engelbrecht, “Appendix A: Optimization Theory,” Comput Intell, pp. 551–579, 2007, doi: 10.1002/9780470512517.app1.
B. Galvan, G. D., P. J., M. Sefrioui, and G. Winter, “Parallel Evolutionary Computation for Solving Complex CFD Optimization Problems : A Review and Some Nozzle Applications,” in Parallel Computational Fluid Dynamics 2002, Elsevier, 2003, pp. 573–604. doi: 10.1016/B978-044450680-1/50072-3.
M. Azizi, S. Talatahari, and A. H. Gandomi, “Fire Hawk Optimizer: a novel metaheuristic algorithm,” Artif Intell Rev, vol. 56, no. 1, pp. 287–363, Jan. 2023, doi: 10.1007/s10462-022-10173-w.
H. R. E. H. Bouchekara, “Most Valuable Player Algorithm: a novel optimization algorithm inspired from sport,” Operational Research, vol. 20, no. 1, pp. 139–195, Mar. 2020, doi: 10.1007/s12351-017-0320-y.
Nature-Inspired Optimization Algorithms. Elsevier, 2014. doi: 10.1016/C2013-0-01368-0.
J. C. Bean, “Genetic Algorithms and Random Keys for Sequencing and Optimization,” ORSA Journal on Computing, vol. 6, no. 2, pp. 154–160, May 1994, doi: 10.1287/ijoc.6.2.154.
C. H. Papadimitriou, “The Euclidean travelling salesman problem is NP-complete,” Theor Comput Sci, vol. 4, no. 3, pp. 237–244, Jun. 1977, doi: 10.1016/0304-3975(77)90012-3.
S. S. Skiena, The Algorithm Design Manual. 1998.
E. Guanabara, K. Ltda, E. Guanabara, and K. Ltda, The Traveling Salesman Problem and Its Variations, vol. 12. in Combinatorial Optimization, vol. 12. Boston, MA: Springer US, 2007. doi: 10.1007/b101971.
S. M. Elsayed, R. A. Sarker, and D. L. Essam, “A new genetic algorithm for solving optimization problems,” Eng Appl Artif Intell, vol. 27, pp. 57–69, 2014, doi: 10.1016/j.engappai.2013.09.013.
“Google Maps Platform Documentation | Places API | Google Developers.” https://developers.google.com/maps/documentation/places/web-service (accessed Apr. 20, 2023).
“Google Maps Platform Documentation | Distance Matrix API | Google Developers.” https://developers.google.com/maps/documentation/distance-matrix (accessed Apr. 20, 2023).
C. Fu, L. Zhang, X. Wang, and L. Qiao, “Solving TSP problem with improved genetic algorithm,” 2018, p. 40057. doi: 10.1063/1.5039131.
T. V Maia, “Avoidance Learning,” in Encyclopedia of the Sciences of Learning, Boston, MA: Springer US, 2012, pp. 403–406. doi: 10.1007/978-1-4419-1428-6_968.
J. M. Bland and D. G. Altman, “Statistics notes: Measurement error,” BMJ, vol. 312, no. 7047, p. 1654, Jun. 1996, doi: 10.1136/bmj.312.7047.1654.
J. Kennedy and R. Eberhart, “Particle swarm optimization,” in Proceedings of ICNN’95 - International Conference on Neural Networks, IEEE, pp. 1942–1948. doi: 10.1109/ICNN.1995.488968.
N. Van Thieu and S. Mirjalili, “MEALPY: a Framework of The State-of-The-Art Meta-Heuristic Algorithms in Python.” zenodo, Jun. 22, 2022.
Downloads
Additional Files
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 INSYST: Journal of Intelligent System and Computation
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
