Kiptiyah, R.A.Mariyatul (2008) Optimasi Minimum Spanning Tree (MST) dengan menggunakan Algoritma Genetik. Sarjana thesis, Universitas Brawijaya.
Abstract
Minimum spanning tree merupakan bentuk penyelesaian optimasi dari bentuk graf yang dapat diaplikasikan pada permasalahan- permasalahan seperti jaringan telepon, jaringan listrik maupun pencarian jarak terpendek. Penyelesaian masalah-masalah ini pada dasarnya adalah menentukan semua spanning tree yang mungkin dibuat dan memperhitungkan weight yang terkecil. Pada penelitian ini dibahas mengenai optimasi masalah minimum spanning tree menggunakan algoritma genetika. Algoritma genetik adalah algoritma pencarian solusi neighborhood berdasarkan mekanisme seleksi alam (natural selection) dan genetika alam (natural genetics) yang dapat digunakan untuk memecahkan combinatorial optimization problems yang sulit, seperti permasalahan minimum spanning tree. Hasil akhir dari penelitian ini, berdasarkan uji coba yang telah dilakukan, algoritma genetik dapat digunakan sebagai alternatif dalam menyelesaikan permasalahan minimum spanning tree. Pada individu 150 dan Generasi 500 populasi mencapai konvergensi. Nilai fitness yang dihasilkan dipengaruhi oleh nilai probabilitas perkawinan silang, dimana nilai fitness terbaik didapat pada probabilitas perkawinan silang 75%. Tetapi pada saat probabilitas crossover diubah dari 75% ke 100% nilai minimum fitness mengalami penurunan.
| Item Type: | Thesis (Sarjana) |
|---|---|
| Identification Number: | SKR/MIPA/2008/186/050802167 |
| Subjects: | 500 Natural sciences and mathematics > 510 Mathematics |
| Divisions: | Fakultas Matematika dan Ilmu Pengetahuan Alam > Matematika |
| Depositing User: | Unnamed user with email repository.ub@ub.ac.id |
| Date Deposited: | 04 Sep 2008 08:31 |
| Last Modified: | 09 Mar 2022 06:51 |
| URI: | http://repository.ub.ac.id/id/eprint/151843 |
Preview |
Text
050802167.pdf Download (2MB) | Preview |
Actions (login required)
 |
View Item |