Penerapan algoritma genetika untuk menyelesaikan Asymmetric Travelling Salesman Problem

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.