PENYELESAIAN MASALAH POHON RENTANG MINIMUM DENGAN ALGORITME GENETIKA YANG DISEDERHANAKAN SUATU ADOPSI OPERATOR DARI SISTEM KEKEBALAN BUATAN

Abstract

Masalah pohon rentang minimum adalah bagaimana menemukan busur-busur pembentuk pohon dalam suatu jaringan yang menghubungkan semua simpul dengan jumlah bobot busur sekecilkecilnya. Masalah ini merupakan bentuk pemodelan masalah praktis, seperti minimasi kabel instalasi listrik, minimasi kabel serat optik jaringan telekomunikasi, minimasi pipa instalasi air bersih dan sebagainya. Masalah ini memegang peranan penting dalam kehidupan nyata, sehingga usaha untuk memperbaiki kualitas penyelesaiannya merupakan kajian yang dilakukan, baik bersifat konseptual maupun aplikatif. Penelitian yang diusulkan merupakan penelitian konseptual yang bertujuan untuk memperbaiki metode penyelesaian masalah pohon rentang minimum dengan Algoritme Genetika. Gagasan perbaikan metode didapat dari adanya kesamaan prinsip algoritme ini dengan Sistem Kekebalan Buatan, yang berupa penyederhanaan langkah-langkah dalam Algoritme Genetika. Penyederhanaan yang diusulkan adalah pengabaikan operator penyilangan sebagaimana yang berlaku pada Sistem Kekebalan buatan. Selain itu, penyederhanaan juga dilakukan dari aspek representasi kromosom. Usulan telah diujikan dengan menggunakan data pengujian penelitian lain yang sudah diketahui solusinya. Hasil penelitian menunjukkan bahwa penyederhanaan Algoritme Genetika yang diusulkan tidak mengurangi tingkat kualias solusi yang dihasilkan. Hal ini berarti adanya perbaikan kinerja algoritme dari aspek waktu komputasi dan memori komputer yang dibutuhkan untuk proses komputasi. Penelitian ini dapat dikembangkan lagi di masa yang akan datang, baik dengan data pengujian yang lebih kompleks maupun dengan penyederhanaan penanganan parameter algoritma.