Abidatul Izzah, 080810799 (2012) ARTIFICIAL BEE COLONY (ABC) SEBAGAI ALGORITMA PENDEKATAN UNTUK DEGREE - CONSTRAINED MINIMUM SPANNING TREE (DC-MST) PROBLEM Artificial Bee Colony (ABC) Approach to The Degree Constrained Minimum Spanning Tree (dc-MST) Problem. Skripsi thesis, UNIVERSITAS AIRLANGGA.

Preview	Text (ABSTRAK) gdlhub-gdl-s1-2012-izzahabida-21636-5.abstr-k.pdf Download (223kB) | Preview
	Text (FULLTEXT) FULLTEXT.pdf Restricted to Registered users only Download (1MB) | Request a copy

Abstract

Permasalahan graf sering digunakan untuk memecahkan persoalan jarak terpendek. Dalam perkembangannya timbul suatu permasalahan, yakni jalur yang terbentuk harus melewati semua titik tanpa sikel dengan meminimumkan biaya pada masing-masing garis dan juga memperhitungkan derajat maksimum pada setiap titik. Permasalahan tersebut dapat dirumuskan sebagai permasalahan degree constrained Minimum Spanning Tree (dc-MST). Skripsi ini bertujuan untuk menyelesaikan permasalahan dc-MST dengan menggunakan algoritma artificial bee colony. Artificial Bee Colony (ABC) merupakan algoritma yang diadopsi dari perilaku sekumpulan lebah madu saat mencari sumber makanan. Dalam proses pencarian sumber makanan ini, lebah dibagi menjadi tiga – employed, scout, dan onlooker. Algoritma ini diawali dengan setiap employed membangkitkan food source (solusi) di daerah fisibel dan mencari neighborhood. Langkah selanjutnya adalah seleksi dan pencarian neighborhood dari hasil seleksi oleh onlooker. Hasil yang lebih baik akan menggantikan food source sebelumya. Langkah terakhir adalah local search yang dilakukan terus menerus sampai iterasi yang dilakukan gagal memperbaiki solusi. Skripsi ini menggunakan dua data sebagai contoh kasus yang diselesaikan, yakni data jarak 9 kota di Jawa Timur yang diselesaikan secara manual dan program serta data jarak 100 kota di Jawa yang diselesaikan menggunakan program. Data tersebut diambil dari Workshop Integer Programming, 2004. Program dibuat menggunakan bahasa pemrograman Java dengan NetBean IDE 6.5. Dalam penerapan kasus pada jarak 9 kota dengan parameter numBee = 20 dan bt = 0.8 dengan satu kali trial diperoleh bobot 775 km sebagai solusi dari perhitungan manual dan dengan 100 kali trial diperoleh bobot 626 km sebagai solusi dari perhitungan program. Sedangkan untuk data 100 kota dengan parameter numBee = 60, bt = 0.8, dan 200 kali trial diperoleh bobot 8206 km sebagai solusi optimal.

Actions (login required)

View Item