PENYELESAIAN MINIMUM SPANNING TREE (MST) PADA GRAF LENGKAP DENGAN ALGORITMA GENETIKA MENGGUNAKAN TEKNIK PRUFER SEQUENCES
ABSTRAK: Teori graf merupakan
cabang ilmu matematika yang aplikasinya banyak dijumpai dalam dunia nyata misalnya
Minimum Spanning Tree (MST) dengan menggunakan algoritma genetika. MST
merupakan sebuah masalah optimasi yang bertujuan mencari Spanning Tree dengan
jumlah bobot paling kecil dari sebuah graf. Graf yang akan dicari dalam
penelitian ini adalah graf lengkap, tak berarah dan berbobot. Pengkodean
kromosom menggunakan Prufer Sequences untuk mengkodekan pohon-pohon yang dihasilkan
dari sebuah graf, agar masalah MST dapat diselesaikan dengan algoritma
genetika. Algoritma genetika adalah algoritma yang digunakan untuk
menyelesaikan masalah optimasi dan bekerja berdasarkan mekanisme seleksi alami
dan konsep genetika. Parameter algoritma genetika yangdigunakan dalam
penelitian ini, yaitu : probabilitas crossover (pc) 0,75, 0,85 dan 0,95,
probabilitas mutasi (pm) 0,01, 0,03 dan 0,05, jumlah populasi sebanyak 100,
threshold sebesar 0,90, Max_Generasi sebesar 1000, dan Jumlah vertex dari 4, 7
dan 10. Pada penelitian ini pengkodean kromosom menggunakan Prufer Sequences
mampu menyelesaikan MST. Kemampuan algoritma genetika dalam memberikan solusi
optimal yang sama dengan algoritma Kruskal, yaitu untuk 4 verteks sebesar 100%,
7 verteks sebesar 100% dan 10 verteks sebesar 100%.
Kata kunci: Graf lengkap, graf
tak berarah, graf berbobot, Minimum spanning tree, Prufer Sequences, algoritma
genetika
Penulis: Emsi M. Y. Monifani
Kode Jurnal: jptkomputerdd140292
