Optimization of the Travelling Salesman Problem Based on Genetic Algorithm with Adaptive Crossover and Mutation Probabilitie

Chichi Rizka Gunawan

doi:10.70340/jirsi.v3i3.166

Penulis

Chichi Rizka Gunawan Universitas Samudra

DOI:

https://doi.org/10.70340/jirsi.v3i3.166

Kata Kunci:

crossover, mutation, optimization, NP-Hard , fitness

Abstrak

Travelling Salesman Problem (TSP) merupakan masalah optimasi kombinatorial yang bertujuan menemukan rute terpendek untuk mengunjungi setiap kota satu kali dan kembali ke kota asal. Karena tergolong NP-hard, penyelesaian TSP membutuhkan pendekatan heuristik. Penelitian ini menggunakan Algoritma Genetika untuk menyelesaikan TSP dengan mengintegrasikan probabilitas crossover dan mutasi adaptif. Pendekatan adaptif ini memungkinkan parameter crossover dan mutasi disesuaikan secara dinamis berdasarkan kondisi populasi pada setiap generasi, sehingga meningkatkan efisiensi pencarian solusi optimal. Penelitian dimulai dengan representasi kromosom sebagai urutan kota, dilanjutkan dengan inisialisasi populasi awal secara acak. Evaluasi fitness dilakukan berdasarkan total jaralk perjalanan untuk menentukan kualitas solusi. Seleksi individu terbaik, crossover adaptif, dan mutasi adaptif diterapkan untuk menghasilkan populasi baru yang lebih baik. Elitisme digunakan untuk menjaga agar solusi terbaik tidak hilang. Iterasi algoritma berlangsung hingga mencapai jumlah generasi maksimum atau ambang batas fitness tertentu.. Hasil penelitian menunjukkan bahwa pendekatan adaptif menghasilkan rute perjalanan optimal dengan total jarak minimum. Jalur optimal divisualisasikan dengan menyambungkan titik-titik kota, dan perkembangan fitness memperlihatkan peningkatan signifikan pada generasi awal serta stabilisasi pada generasi akhir. Dengan parameter probabilitas crossover sebesar 0.8 dan mutasi sebesar 0.005, algoritma mampu menjaga keseimbangan antara eksplorasi dan eksploitasi ruang solusi, mencegah konvergensi prematur, dan menghasilkan solusi yang efisien.. Penelitian ini membuktikan bahwa algoritma genetika dengan pendekatan adaptif efektif dalam menyelesaikan TSP dengan jumlah kota yang moderat. Selain itu, pendekatan ini dapat diadaptasi untuk dataset yang lebih besar atau dibandingkan dengan metode optimasi lainnya, seperti Ant Colony Optimization (ACO) dan Particle Swarm Optimization (PSO), guna mengevaluasii kinerjanya lebih lanjut.

Unduhan

Data unduhan belum tersedia.

Referensi

G. E. Yuliastuti, W. F. Mahmudy, and A. M. Rizki, “Implementation of Genetic Algorithm to Solve Travelling Salesman Problem with Time Window (TSP-TW) for Scheduling Tourist Destinations in Malang City,” J. Inf. Technol. Comput. Sci., vol. 2, no. 1, pp. 1–10, 2017, doi: 10.25126/jitecs.20172122.

M. Boulif and A. Gharbi, “A new node-shift encoding representation for the travelling salesman problem,” 2023, [Online]. Available: http://arxiv.org/abs/2305.09257

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),” Int. J. Artif. Intell. Robot., vol. 1, no. 1, pp. 1–8, 2019, doi: 10.25139/ijair.v1i1.2024.

J. Zheng, J. Zhong, M. Chen, and K. He, “A reinforced hybrid genetic algorithm for the traveling salesman problem,” Comput. Oper. Res., vol. 157, pp. 1–17, 2023, doi: 10.1016/j.cor.2023.106249.

D. Fadhillah A, N. Ega, D. Sofisyah A, A. Riski, and E. Sakti, “Genetic Algorithm Design on Traveling Salesman Problem,” Informatics Softw. Eng., vol. 1, no. 1, pp. 24–29, 2023, doi: 10.58777/ise.v1i1.60.

S. Lukas, T. Anwar, and W. Yuliani, “Penerapan Algoritma Genetika Untuk Traveling Salesman Problem Dengan Menggunakan Metode Order Crossover Dan Insertion Mutation,” Semin. Nas. Apl. dan Teknol. Inf. (SNATI 2005), vol. 2005, no. Snati, pp. 1–5, 2005.

A. V. Eremeev and Y. V. Kovalenko, “Genetic Algorithm with Optimal Recombination for the Asymmetric Travelling Salesman Problem,” pp. 1–8, 2017, doi: 10.1007/978-3-319-73441-5_36.

S. Mahmoudinazlou and C. Kwon, “A hybrid genetic algorithm with type-aware chromosomes for Traveling Salesman Problems with Drone,” Eur. J. Oper. Res., vol. 318, no. 3, pp. 719–739, 2024, doi: 10.1016/j.ejor.2024.05.009.

A. Yusron Mubarok and U. Chotijah, “Penerapan Algoritma Genetika Untuk Mencari Optimasi Kombinasi Jalur Terpendek Dalam Kasus Travelling Salesman Problem,” J. Teknol. Terpadu, vol. 7, no. 2, pp. 77–82, 2021, doi: 10.54914/jtt.v7i2.424.

S. Rohman, L. Zakaria, A. Asmiati, and A. Nuryaman, “Optimisasi Travelling Salesman Problem dengan Algoritma Genetika pada Kasus Pendistribusian Barang PT. Pos Indonesia di Kota Bandar Lampung,” J. Mat. Integr., vol. 16, no. 1, p. 61, 2020, doi: 10.24198/jmi.v16.n1.27804.61-73.