J~ICON, Vol. 2 No. 2, Oktober 2014, pp. 84 ~ 91
84
PENYELESAIAN MINIMUM SPANNING TREE (MST) PADA GRAF LENGKAP DENGAN ALGORITMA GENETIKA MENGGUNAKAN TEKNIK PRUFER SEQUENCES
Emsi M. Y. Monifani 1, Adriana Fanggidae 2, Tiwuk Widiastuti 3 1,2,3
Jurusan Ilmu Komputer, Fakultas Sains dan Teknik, Universitas Nusa Cendana
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 yang digunakan 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.
ABSTRACT Graph theory is a branch of mathematics whose applications are often found in the real world such as the Minimum Spanning Tree (MST) using a genetic algorithm. MST is an optimization problem that aims to find Spanning Tree with a small amount of the weight of a graph. Graph to be searched in this study is a complete graph, undirected and weighted. Chromosome using Prüfer Sequences encoding to encode trees generated from a graph, so that the MST problem can be solved by genetic algorithm. Genetic algorithms are algorithms used to solve optimization problems and works based on the mechanism of natural selection and genetics concepts. Genetic algorithm parameters used in this study, namely: probability of crossover (pc) 0.75, 0.85 and 0.95, the probability of mutation (pm) 0.01, 0.03 and 0.05, a total population of 100, threshold as much as 0.90, Maximal Generation 1000, and the number of vertices of 4, 7 and 10. In this study, using Prüfer Sequences encoding chromosome is able to complete the MST. The ability of a genetic algorithm in providing an optimal solution that is equal to the Kruskal algorithm, ie for 4 vertex by 100%, 7 vertex was 100% and 10 vertex was 100%. Keywords: complete graph, undirected graph, weighted graph, minimum spanning tree, Prüfer Sequences, genetic algorithms.
I.
PENDAHULUAN
Teori graf pertama kali diperkenalkan oleh Leonhard Euler pada tahun 1736 ketika mencoba membuktikan kemungkinan untuk melewati empat daerah yang terhubung dengan tujuh jembatan di atas sungai Pregel di Konigsberg, Rusia dalam sekali waktu. Aplikasi dari teori graf sangat luas dan dipakai dalam berbagai disiplin ilmu maupun dalam kehidupan sehari-hari, dalam implementasinya teori ini banyak digunakan di dalam bidang kelistrikan (jaringan listrik), kimia (memodelkan senyawa dalam bentuk graf) dan informatika (penerapan graf pada jaringan). Penggunaan teori graf yang ISSN 2337-7631
85
ISSN 2337-7631
sangat umum digunakan pada pencarian pohon merentang minimum (Minimum Spanning Tree), Travelling Salesman Problem (TSP) dan coloring graph. Graf terdiri dari graf lengkap dan graf tak lengkap, graf lengkap adalah graf sederhana, dimana setiap verteks-nya tidak mengandung gelang (garis yang kedua verteksnya sama) dan garis ganda (dua garis yang memiliki verteks asal dan verteks tujuan yang sama), graf tak lengkap adalah graf yang memiliki satu atau beberapa verteks yang tidak terhubung tetapi tidak mengandung sebuah verteks terpencil. Ada beberapa algoritma yang digunakan untuk menyelesaikan graf, yaitu: algoritma Greedy, algoritma Kruskal, algoritma Solin, algoritma Prim, algoritma heuristik, Ant Colony System (ACS), algoritma Dijkstra, algoritma genetika dan lain-lain. Penyelesaian Minimum Spanning Tree dengan menggunakan algoritma genetika telah dilakukan oleh peneliti-peneliti sebelumnya dengan bermacam-macam teknik pengkodean kromosom, diantaranya: pengkodean string. Dalam penelitian ini penulis membedakan teknik pengkodean kromosom menggunakan Prufer Sequences untuk melihat keberhasilan dari teknik pengkodean tersebut dalam mencari Minimum Spanning Tree. II.
MATERI DAN METODE
2.1
Definisi Algoritma genetika Algoritma genetika terinspirasi dari prinsip genetika dan seleksi alam (teori evolusi Darwin) yang ditemukan oleh John Holland (1975) dari Universitas Michigan, Amerika Serikat, melalui sebuah penelitian yang berjudul “Adaptation in Natural and Artificial System”. Konsep dasar algoritma genetika dirancang untuk mensimulasikan proses-proses dalam sistem alam yang diperlukan untuk evolusi, khususnya teori evolusi yang dicetuskan oleh Charles Darwin, yaitu survival of the fittest. Algoritma genetika adalah teknik pencarian heuristik yang didasarkan pada gagasan evolusi seleksi alam dan genetik. Algoritma ini memanfaatkan proses seleksi alamiah yang dikenal dengan proses evolusi. Dalam proses evolusi, individu secara terus-menerus mengalami perubahan gen untuk menyesuaikan dengan lingkungan hidupnya. “Hanya individu-individu yang kuat yang mampu bertahan”[5]. Beberapa pengertian dasar yang perlu diketahui dalam algoritma genetika: a. Gen (Genotype) adalah variabel dasar yang membentuk suatu kromosom, dalam algoritma genetika, gen ini bisa bernilai biner, float, integer, maupun karakter. b. Allele adalah nilai dari suatu gen, bisa berupa biner, float, integer, maupun karakter. c. Kromosom adalah gabungan dari gen-gen yang membentuk arti tertentu. Ada beberapa macam bentuk kromosom, yaitu : a. Kromosom biner, adalah kromosom yang disusun dari gen-gen yang bernilai biner. b. Kromosom float, adalah kromosom yang disusun dari gen-gen yang bernilai pecahan. c. Kromosom string, adalah kromosom yang disusun dari gen-gen yang bernilai string. Individu adalah kumpulan gen, bisa dikatakan sama dengan kromosom. Populasi adalah sekumpulan individu yang akan diproses secara bersama sama dalam satu siklus proses evolusi. Generasi menyatakan satu satuan siklus proses evolusi. Nilai fitness menyatakan seberapa baik nilai dari suatu individu atau solusi yang didapatkan. Nilai inilah yang dijadikan acuan untuk mencapai nilai optimal. Algoritma genetika bertujuan untuk mencari individu yang mempunyai nilai fitness yang paling optimal (bisa maksimum atau minimum, tergantung pada kebutuhan). 2.2
Siklus algoritma genetika David Goldberg adalah orang yang pertama kali memperkenalkan siklus algoritma genetika yang digambarkan seperti pada Gambar 1. Siklus dimulai dari membuat populasi awal secara acak, kemudian menghitung nilai fitness dari setiap individu. Proses berikutnya adalah menyeleksi individu terbaik, kemudian dilanjutkan oleh proses crossover dan mutasi sehingga terbentuk populasi baru. Selanjutnya populasi baru ini mengalami siklus yang sama dengan populasi sebelumnya, proses ini berlangsung terus hingga maksimal generasi[5].
J~ICON, Vol. 2 No. 2, Oktober 2014 : 84 ~ 91
J-ICON
ISSN 2337-7631
Populasi awal
Evaluasi fitness
Populasi baru
86
Seleksi individu
Reproduksi: Cross-over dan mutasi
Gambar 1. Siklus algoritma genetika oleh David Goldber Minimum Spanning Tree Minimum Spanning Tree (MST) merupakan variasi dari persoalan rute terpendek yang perbedaannya terletak pada lintasan yang dicari. Pada lintasan terpendek dicari lintasan dari sumber ke tujuan yang memberi total jarak minimum, sedangkan pada pencarian Minimum Spanning Tree ini yang dipersoalkan adalah menentukan garis yang menghubungkan verteks yang ada pada pada jaringan, sehingga diperoleh panjang garis total minimum[3]. Pada penelitian ini, pencarian Minimum Spanning Tree adalah mencari minimum biaya (minimum cost) spanning tree dari setiap garis suatu graf membentuk pohon (tree). Dalam mendapatkan solusi yang diharapkan maka akan dipilih garis menurut kriteria optimasi yang menghasilkan biaya minimum. Dengan demikian penambahan jumlah biaya relatif kecil dari setiap garis yang telah terpilih dalam membentuk spanning tree. 2.3
2.4
Metode prufer sequences Metode prufer sequences ditemukan oleh Heinz Prufer untuk membuktikan rumus Cayley di tahun 1918. Metode prufer sequences dibagi menjadi 2 bagian yaitu encoding dan decoding kromosom awal. Setelah variabel awal telah mengalami encoding dan decoding, maka akan dilanjutkan pada tahap selanjutnya sampai dengan mendapatkan biaya terendah dalam sebuah graf [4]. 2.4.1.1 Encoding Encoding (pengkodean) berguna untuk mendekode gen-gen pembentuk individu agar nilainya tidak melebihi range yang telah ditentukan dan sekaligus menjadi nilai variabel yang akan dicari sebagai solusi permasalahan. Adapun langkah-langkah pengkodean (encoding) Prufer Sequences dari sebuah pohon antara lain:[2] a. Misalkan verteks i merupakan verteks derajat 1, pilih verteks dengan kode ASCI terkecil dan garis yang terhubung dengan verteks tersebut hanya ada satu. b. Pengkodean disusun dari kiri ke kanan. Misal j adalah digit pertama hasil pengkodean, dimana j merupakan verteks yang terhubung langsung dengan verteks i, maka digit selanjutnya dimasukan dalam P. c. Hapus verteks i dan garis yang menghubungkan verteks i dan j. Sehingga pohon tersebut hanya mengandung n-1 verteks. Ulangi langkah 1 sampai 3 sampai garis yang tertinggal hanya ada satu. Hasil akhir dari pengkodean ini disebut Prufer Sequences dan berupa kumpulan string sebanyak n-2, dimana n adalah jumlah verteks dari graf, P adalah Prufer Sequences, dan string ini mewakili kode dari verteks[5]. 2.4.2
Decoding Decoding (pengkodean) berguna untuk mendekode gen-gen pembentuk individu agar nilainya tidak melebihi range yang telah ditentukan dan sekaligus menjadi nilai variabel yang akan dicari sebagai solusi permasalahan. Setelah pohon berhasil dikompresi, dibutuhkan cara untuk pengkodean kode tersebut hingga dapat kembali dibaca sebagai pohon. Berikut adalah langkahlangkah yang harus dilakukan[2]: Diberikan sebuah string S dengan panjang n-2 dalam {v1,...,vn} dengan v1 < v2 < ... < vn. Ulangi proses berikut hingga S kosong dan label berukuran dua:
Pencarian Minimum Spanning Tree (MST) Dengan Teknik Pengkodean (Emsi M. Y. Monifani)
87
ISSN 2337-7631
a. Identifikasi nilai terendah yang tidak muncul pada string, sebut sebagai P serta elemen pertama pada string, sebut sebagai V, b. Tambahkan P pada graf yang dibentuk, kemudian hubungkan dengan V (apabila V belum terdapat dalam graf, tambahkan terlebih dahulu), c. Hapus P serta elemen pertama pada string tersebut. Proses tersebut dilakukan terus-menerus sampai n-2 kali, setelah pengulangan selesai, hubungkan dua nilai yang tersisa pada string, maka didapatlah hasil sebuah pohon yang memiliki kode prufer S. Pemetaan dari kode prufer ke dalam pohon disebut bijektif[5]. 2.5
Bagan alir (flowchart) sistem Flowchart berasal dari kata flow dan chart. Flow adalah aliran dan chart berarti gambar atau simbol-simbol. Jadi, flowchart merupakan metode yang menggambarkan tahapan dalam memecahkan suatu masalah dengan mempresentasikan simbol-simbol tertentu yang mudah dimengerti, mudah digunakan dan sudah standart. Sistem flowchart merupakan diagram alir yang menggambarkan suatu sistem peralatan komputer yang digunakan dalam proses pengolahan data serta hubungan antar alat di dalam komputer tersebut. Sistem flowchart ini tidak menggambarkan urutan langkah dalam memecahkan suatu masalah tetapi hanya menggambarkan prosedur dalam sistem tersebut[1]. Pada sistem ini, algoritma genetika merupakan suatu metode pencarian yang didasarkan pada parameter-parameternya, algoritma genetika merupakan solusi menyelesaikan pencarian pada graf lengkap untuk mengkodekan atau menyandikan nilai gen-gen pembentuk kromosom, pencarian Minimum Spanning Tree untuk mencari minimum biaya (cost) spanning tree dari setiap garis suatu graf pembentuk pohon (tree), flowchart sistem dapat dilihat pada Gambar 2[2]. Mulai Jumlah masimal generasi. Jumlah populasi. Probabilitas mutasi. Probabilitas crossover. Threshold. Tentukan jumlah verteks. generate bobot dari garis untuk representasi graf ke dalam bentuk matriks Populas awal Encoding prufer sequences Evaluasi kromosom Seleksi kromosom Kawin silang
Tidak
Decoding prufer sequences Mutasi Decoding prufer sequences yabaru Populasi
Generesi maksimum ? ya Selesai
Gambar 2 Flowchart sistem Pada gambar 2 algoritma genetika dimulai dengan pembentukan sejumlah alternatif pemecahan yang disebut populasi awal, pembentukan populasi awal dalam algoritma genetika dilakukan dengan cara bangkitkan kromosom secara acak ini akan menghasilkan sejumlah kromosom sebanyak Pop_Size yang terdiri dari beberapa verteks, hasil akhir dari prosedur populasi awal ini adalah urutan verteks dalam setiap kromosom yang merepresentasikan kemungkinan jalur yang akan terpilih sebagai solusi. Setelah itu, penyandian atau encoding nilai gen pembentuk kromosom menggunakan metode Prufer Sequences ini bertujuan untuk mengkodekan pohon-pohon yang dihasilkan dari graf, agar masalah Minimum Spanning Tree dapat diselesaikan dengan algoritma genetika. Kemudian evaluasi kromsom, dimana proses ini akan menghitung nilai fitness dari setiap J~ICON, Vol. 2 No. 2, Oktober 2014 : 84 ~ 91
J-ICON
ISSN 2337-7631
88
kromosom yang telah dibangkitkan secara random pada tahap populasi populasi awal. Proses berikutnya seleksi kromosom yang digunakan pada proses seleksi ini adalah metode roulette wheel, pada tahap ini akan dilakukan penyeleksian kromosom berdasarkan nilai fitness-nya untuk memilih kromosom mana yang akan megalami proses perkawinan atau pindah silang, kromosom yang benilai fitness rendah memiliki kesempatan terpilih lebih besar. Namun, tidak menutup kemungkinan kromosom yang bernilai fitness tinggi akan terpilih juga. Pada proses roulette wheel ini akan dihitung nilai komulatif dari probabilitas fitness masing-masing kromosom, selanjutnya pindah silang adalah prosedur untuk mengkawinkan dua induk yang telah dipilih pada proses roulette wheel, namun tidak semua induk akan mengalami pindah silang karena proses pindah silang ini banyak dikendalikan oleh beberapa bilangan random, metode roulette-wheel dapat diimplementasikan dalam pemrograman dengan beberapa langkah. Pertama, dibuat interval nilai komulatif (dalam interval [0 1]) dari nilai fitness masing masing kromosom dibagi total fitness dari semua kromosom. Sebuah kromosom akan terpilih jika bilangan random yang dibangkitkan berada dalam interval akumulatifnya, kemudian dilanjutkan dengan proses pindah silang (crossover) akan dilakukan pada beberapa kromoson pada setiap generasi, setiap crossover dikontrol oleh nilai probabilitas crossover (pc). Dengan kata lain, algoritma akan membangkitkan nilai random antara [0 1] untuk setiap kromoson. Jika nilai yang dibangkitkan lebih kecil dari nilai probabilitas crossover, maka crossover dapat dilakukan pada kromoson tersebut. Setelah proses kawin silang, selanjutnya menghitung nilai fitness dari spanning tree hasil kawin silang, yaitu nilai fitness dari kromosom tetapi sebelumnya harus dilakukan decoding prufer sequences ke dalam bentuk spanning tree. Setelah proses menghitung nilai fitness menggunakan decoding prufer sequences selanjutnya proses mutasi berfungsi untuk menggantikan gen yang hilang dari populasi selama proses seleksi serta menyediakan gen yang tidak ada dalam populasi awal, sehingga mutasi akan meningkatkan variasi populasi. Setelah proses mutasi, selanjutnya dihitung nilai fitness dari spanning tree hasil mutasi, yaitu nilai fitness dari kromosom tetapi sebelumnya harus dilakukan decoding prufer sequences ke dalam bentuk spanning tree. Hasil dari proses mutasi dalam pencarian Minimum Spanning Tree dengan teknik pengkodean kromosom menggunakan Prufer Sequences pada graf lengkap dengan algoritma genetika adalah minimum biaya (cost) spanning tree dari setiap garis suatu graf membentuk pohon (tree). Dari bobot yang minimum akan diproses dalam hasil pencarian Minimum Spanning Tree untuk memperoleh jarak, hasil dari proses ini merupakan output. III.
HASIL DAN PEMBAHASAN
3.1
Hasil Halaman ini disediakan agar pengguna dapat mengetahui cara kerja dari algoritma genetika, pada halaman ini memerlukan inputan data-data dari pengguna berupa: jumlah maksimal generasi, jumlah populasi, probabilitas mutasi, probabilitas crossover, threshold dan penentuan jumlah verteks yang akan digunakan untuk menyelesaikan pencarian minimum spanning tree. Setelah menginputkan data-data, pengguna dapat langsung klik run. Setelah klik run, maka pengguna dapat melihat halaman hasil pengujian, halaman menu proses dapat dilihat pada Gambar 3[2].
Pencarian Minimum Spanning Tree (MST) Dengan Teknik Pengkodean (Emsi M. Y. Monifani)
89
ISSN 2337-7631
Gambar 3 Halaman Proses Halaman hasil pengujian Halaman ini menampilkan matriks dan urutan generasi kromosom melalui proses-proses genetika, matriks ini merupakan visualisasi dari jenis graf yang dipilih pengguna, halaman hasil pengujian dapat dilihat pada Gambar 4[2].
Gambar 4 Hasil pengujian Parameter algoritma genetika yang digunakan dalam pengujian ini, yaitu : (1) probabilitas crossover = 0,75, 0,85 dan 0,95; (2) probabilitas mutasi = 0,01, 0,03 dan 0,05; (3) pop_size = 100; (4) threshold = 0,95; (4) Max_generasi = 1000; dan (5) Jumlah verteks = 4, 7 dan 10. Pengujian dilakukan sebanyak 9 kali dengan bobot setiap garis yang berbeda dilakukan secara random. Hasil pengujian dapat dilihat pada Tabel 1[2]. Pengujian dengan sistem dan algoritma Kruskal. J~ICON, Vol. 2 No. 2, Oktober 2014 : 84 ~ 91
J-ICON
ISSN 2337-7631
90
Tabel 1 Hasil pengujian untuk jumlah verteks 10 Algoritma genetika
Algoritma Kruskal
Pengujian ke Parameter algoritma genetika Prufer Probabilitas Probabilitas Generasi Nilai Sequences Jumlah terbaik fitness crossover (pc) mutasi (pm) bobot
MST
1
0,75
0,01
971
72
2-3-2-5-7-2-07
72
2-1,4-3,2-4,7-5,7-6,28,0-2,7-0,7-9
2
0,85
0,01
717
92
95
3
0,95
0,01
9-6-6-6-55-8-2 3-9-9-1-67-2-2
3-6,0-4,0-9,9-2,2-8,78,7-5,6-5,3-6 5-1,1-6,6-7,2-7,2-8,03,4-9,3-9,2-9
4
0,75
0,03
662
58
6-5-4-5-51-1-7
61
7-9,7-1,1-5,5-2,5-4,34,0-6,6-5,0-6
5
0,85
0,03
927
62
64
6
0,95
0,03
706
51
7
0,75
0,05
717
42
8
0,85
0,05
732
59
9
0,95
0,05
1000
66
4-5-5-6-56-6-6 3-1-5-5-53-1-3 8-0-7-5-41-1-5 8-6-5-5-87-6-4 0-6-7-3-33-5-7
0-9,1-7,3-6,5-6,6-8,04,1-5,2-8,5-4 3-5,1-4,3-0,4-5,5-6,29,5-7,2-1,1-3 1-8,2-8,0-7,2-8,4-7,03,1-4,5-1,6-5 2-5,6-7,1-6,0-8,4-6,35,5-8,7-8,4-9 8-3,0-6,0-1,2-7,6-0,17,3-4,3-5,0-3
968
42
42
55 42 59 67
Pada Tabel 1 terdapat 8 detail kolom, kolom pertama adalah banyaknya pengujian, kolom ke2 adalah parameter algoritma genetika probabilitas crossover (pc), kolom ke-3 adalah parameter algoritma genetika probabilitas mutasi (pm), kolom ke-4 adalah generasi terbaik, kolom ke-5 adalah nilai fitness, kolom ke-6 merupakan Prufer sequences, kolom ke-7 adalah jumlah bobot algoritma Kruskal, kolom ke-8 merupakan MST dari algoritma Kruskal. Dari Tabel 1, terlihat bahwa dari 9 kali pengujian dengan bobot yang berbeda (dibangkitkan secara random) diperoleh jumlah bobot dari algoritma Kruskal dan nilai fitness dari algoritma genatika sama yaitu sebesar 100% algoritma Kruskal lebih optimal dibandingkan dengan algoritma genetika. 3.2
Pembahasan Aplikasi secara umum dirancang untuk mencari Minimum Spanning Tree dengan teknik pengkodean kromosom menggunakan Prufer Sequences untuk graf lengkap dengan algoritma genetika dengan total fitness yang terkecil. Pada Tabel 1 dari 9 kali pengujian dengan bobot yang berbeda (dibangkitkan secara random) diperoleh algoritma genetika memiliki rata-rata nilai fitness yang sama dibandingkan dengan jumlah bobot algoritma Kruskal sebesar 100%. Dilihat dari semua pengujian algoritma Kruskal lebih optimal dibandingkan dengan algoritma genetika karena dalam algoritma Kruskal pertama yang dilakukan adalah mengurutkan setiap bobot garis di dalam graf mulai dari garis dengan bobot terkecil sampai terbesar, sedangkan dalam algoritma genetika setiap garis dipilih secara acak dan populasi yang digunakan pada penelitian ini sebanyak 100 kromosom sehingga pohon yang dihasilkan optimal. Sedangkan teknik pengkodean kromosom menggunakan Prufer Sequences terbukti dari semua pengujian tidak terdapat kegagalan dalam mengkodekan kromosom. IV.
KESIMPULAN DAN SARAN
4.1
Kesimpulan Dari pembahasan dan analisis yang telah dilakukan, Pencarian Minimum Spanning Tree dengan teknik pengkodean kromosom menggunakan Prufer Sequences untuk graf lengkap dengan algoritma genetika, dapat diambil beberapa kesimpulan sebagai berikut: 1. Pada penelitian ini pengkodean kromosom menggunakan Prufer Sequences mampu menyelesaikan Minimum Spanning Tree.
Pencarian Minimum Spanning Tree (MST) Dengan Teknik Pengkodean (Emsi M. Y. Monifani)
91
ISSN 2337-7631
2. Kemampuan algoritma genetika dalam memberikan solusi optimal yang sama dengan algoritma Kruskal, yaitu untuk 4 verteks sebesar 100%, 7 verteks sebesar 100%, 10 verteks sebesar 100%. 4.2
Saran Dari pembahasan dan analisis yang telah dilakukan, maka dapat diambil beberapa kesimpulan sebagai berikut: 1. Pada penelitian ini masih menggunakan operator-operator algoritma genetika standar, operator algoritma genetika standar yang dimaksud seperti crossover menggunakan metode one-cutpoint, mutasi menggunakan flip one bit, dan seleksi menggunakan metode roullete wheel. Disarankan pada penelitian selanjutnya dapat menggunakan metode-metode yang di atas standar. 2. Pada penelitian ini output yang dihasilkan berupa deretan kode Prufer, untuk pengembangan selanjutnya, input maupun output dari masalah Minimum Spanning Tree ini dapat disajikan dalam bentuk graf. 3. Jumlah populasi kromosom dinaikan untuk mendapatkan solusi optimal dalam pencarian Minimum Spanning Tree dengan menggunakan algoritma genetika.
DAFTAR PUSTAKA [1] Jogiyanto, 2005, Analisis dan Desain Sistem Informasi; Pendekatan Terstruktur Teori dan Praktek Aplikasi Bisnis, Edisi III, Andi, Yogyakarta. [2] Monifani, Emsi M.Y. 2014. Pencarian Minimum Spanning Tree (Mst) dengan teknik pengkodean kromosom menggunakan Prufer Sequences pada graf lengkap dengan Algoritma Genetika. Skripsi. Kupang. [3] Munir, Rinaldi. 2005. Matematika Diskrit. Bandung : Informatika.Bandung. [4] Pratama, Y.S.Mangontang. 2012. Kompresi pohon dengan kode prufer. Sekolah Teknik Elektro dan Informatika Institut Teknologi Bandung. Bandung. [5] Sutojo, Edy Mulyanto dan Vincent Suhartono. 2010. Kecerdasan Buatan. Yogyakarta : Penerbit Andi. Yogyakarta.
J~ICON, Vol. 2 No. 2, Oktober 2014 : 84 ~ 91
