Grace Catherine Eky Pengarang YULIANTO TRIWAHYUADI POLLY Dosen Pembimbing 2 ADRIANA FANGGIDAE Dosen Pembimbing 1 Sebastianus Adi Santoso Mola Penguji 2 Juan Rizky Manuel Ledoh, S.Kom., M.Cs Ketua Penguji Derwin Rony Sina, S.Kom., M.Cs Penguji 1

Minimum spanning tree (MST) merupakan sebuah tree dalam graf dengan bobot minimum, sehingga MST termasuk salah satu persoalan optimasi. Pendistribusian dan suplai air PDAM merupakan salah satu persoalan optimasi yang dapat diselesaikan dengan algoritma genetika. Pada penelitian ini, digunakan algoritma genetika dengan pengkodean prufer sequences untuk menyelesaikan kasus MST distribusi dan suplai air PDAM di Kabupaten Sleman. Pengujian dilakukan sebanyak 5 kali dengan penetapan parameter probabilitas crossover (pc)={0,5,0,7,0,75,0,8,0,85,0,9,0,95} , probabilitas mutasi (pm) = {0,01,0,05,0,1,0,2,0,3,0,4,0,5}, jumlah generasi sebesar 5000, populasi sebesar 100 dan threshold sebesar 90. Hasil pengujian menunjukkan bahwa probabilitas crossover (pc) sebesar 0,85 dan probabilitas mutasi (pm) sebesar 0,01 memberikan hasil jarak minimum sebesar 10.384. Pengujian selanjutnya menggunakan probabilitas crossover dan probabilitas mutasi hasil pengujian pertama beserta jumlah generasi 500 dan 5000. Hasil pada pengujian ini, terdapat penurunan jarak sebesar 2,34% dan peningkatan waktu sebesar 112,3%. Kata kunci : Minimum spanning tree, distribusi dan suplai air, algoritma genetika, prufer sequences