M. Afrizal Ady Asmara Pengarang YULIANTO TRIWAHYUADI POLLY Dosen Pembimbing 2 ADRIANA FANGGIDAE Dosen Pembimbing 1 Juan Rizky Manuel Ledoh, S.Kom., M.Cs Penguji 1 Clarissa Elfira Amos Pah, S.Kom., M.T.I Penguji 2 Derwin Rony Sina, S.Kom., M.Cs Ketua Penguji

Minimum Spanning Tree (MST) merupakan suatu graf yang berbentuk pohon dengan jumlah bobot terkecil, dan termasuk salah satu persoalan optimasi. Salah satualgoritma yang dapat digunakan dalam persoalan optimasi adalah algoritma genetika. Pada penelitian ini dilakukan perbandingan metode crossover Partial Mapped Crossover (PMX) dan Heuristic Crossover (HX) dalam algoritma genetika untuk menyelesaikan persoalan MST. Pengujian dilakukan sebanyak 100 kali dengan parameter uji yaitu probabilitas crossover = 0,85, probabilitas mutasi = 0,01, jumlah generasi = 1000, populasi = 100, threshold = 90%, dan jumlah kota sebanyak = {20, 30, 40, 50}. Hasil pengujian menunjukkan bahwa kinerja algoritma genetika dengan crossover HX memberikan rata-rata fitness sebesar 613,915 dengan rata-rata waktu komputasi 130,87 detik. Sedangkan algoritma genetika dengan crossover PMXmemberikan rata-rata fitness sebesar 719,25 dengan rata-rata waktu komputasi 87,56detik. Pada penelitian ini juga terlihat bahwa variasi jumlah kota tidak signifikan dalam mempengaruhi performa kedua algoritma dalam mencari fitness terbaik. Dalam presentase konvergensi metode HX memiliki eksploitasi yang lebih baik dari metode PMX tetapi kalah dalam eksplorasi.