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

Abstrak

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. Dari hasil uji yang dilakukan dengan menggunakan parameter  1,  0.5 ,  0.1 ,  0.5,Q = 100, dan NCmax = 10 diperoleh kesimpulan bahwa ACS dapat dijadikan sebagai alternatif untuk memecahkan masalah MST meskipun tidak selalu memberikan solusi yang optimal, dikarenakan cara kerja ACS yang bersifat heuristik.

Kata kunci : Optimasi, Minimum spanning tree, Ant Colony System, Heuristik

Pendahuluan

Kemajuan Teknologi komunikasi berkembang pesat seiring dengan meningkatnya kebutuhan informasi. Komunikasi adalah salah satu sarana untuk mendapatkan informasi dengan cepat, sebagai contohnya adalah telepon. Dengan telepon, manusia tidak lagi memerlukan waktu yang lama untuk menyampaikan informasi walaupun berbeda kota, propinsi dan negara. Tetapi masih ada kota yang belum bisa terjangkau dengan jaringan telepon, sehingga pendistribusian jaringan telepon tersebut belum optimum. Suatu jaringan yang optimum harus mampu menghubungkan semua kota atau semua tempat agar dapat berkomunikasi, dengan jarak sependek mungkin sehingga akan meminimumkan penggunaan kabel.

Peneliti: Irawan Afrianto

Untuk lebih lengkapnya silahkan download di link berikut: