PENYELESAIAN MASALAH MINIMUM SPANNING TREE (MST) MENGGUNAKAN ANT COLONY SYSTEM (ACS)

Irawan Afrianto

Sari


Masalah optimasi jaringan menjadikan adanya
kebutuhan untuk mencari nilai terkecil (minimal)
pada suatu keadaan jaringan . Salah satu masalah
optimasi jaringan adalah Minimum spanning tree
(MST), yaitu suatu keadaan dimana semua node
dalam graf terhubung, namun tidak boleh terdapat
loop didalamnya dan dihitung bobot tree yang
terkecil. .Salah satu aplikasi MST adalah pembuatan
jaringan komunikasi atau telepon yang akan
menghubungkan semua stasiun telepon pada suatu
kota yang ada. Permasalahannya adalah mencari
jarak terpendek antara kota-kota tersebut sehingga
penggunaan kabel akan lebih sedikit yang berarti
menghemat biaya pembangunan jaringan telepon
tersebut.
Ant Colony System (ACS) adalah salah satu
algoritma heuristik yang dapat digunakan untuk
menyelesaikan masalah MST tersebut. Dalam
pencarian solusi kasus MST, Permasalahan
direpresentasi seperti sekumpulan semut yang
bekerja sama untuk menetukan solusi MST yang
paling baik, semut-semut bekerja sama melalui
komunikasi tidak langsung dengan menggunakan
jejak pheromone yang disimpan pada sisi-sisi dari
graph MST.


Teks Lengkap:

PDF (English)

Refbacks

  • Saat ini tidak ada refbacks.