Abstract:
Travelling Salesman Problem (TSP) adalah suatu pencarian rute perjalanan terpendek. TSP
dibagi menjadi dua tipe yaitu TSP simetri dan TSP asimetri. TSP dikatakan simetri jika jarak
kota i ke kota j sama dengan jarak kota j ke kota i, sedangkan TSP dikatakan asimetri jika jarak
kota i ke kota j tidak sama dengan jarak kota j ke kota i. Penyelesaian TSP dapat menggunakan
metode optimasi atau dengan metode pendekatan. Pada skripsi ini akan membahas mengenai
metode Algoritma Genetika untuk menyelesaikan masalah TSP. Algoritma Genetika adalah
metode Metaheuristik yang dikembangkan berdasarkan prinsip genetika dan proses alamiah.
Pada Algoritma Genetika dikenal dengan adanya proses seleksi alam yang mempertahankan
individu dengan tingkat kebugaran yang tinggi saja yang dapat bertahan hidup. Tingkat
kebugaran suatu kromosom disebut dengan nilai fitness. Adapun struktur Algoritma Genetika
yaitu inisialisasi populasi, evaluasi populasi, proses penyilangan dan proses mutasi. Parameter
yang berpengaruh pada hasil Algoritma Genetika adalah jumlah populasi, peluang penyilangan
dan peluang mutasi. Berdasarkan hasil analisis sensitivitas hanya peluang penyilangan yang
berpengaruh terhadap pengurangan jarak. Jumlah populasi dan peluang mutasi tidak terlalu
berpengaruh terhadap pengurangan jarak.
