Penerapan binary flower pollination algorithm dalam penyelesaian knapsack sharing problem

Abstract

Knapsack Sharing Problem (KSP) adalah suatu permasalahan pengalokasian sumber daya yang terbatas pada beberapa kelas. Pada KSP juga terdapat kapasitas terbatas yang dimodelkan dengan tas. Tujuan dari KSP adalah mencari keuntungan yang seimbang untuk setiap kelas yang ada sehingga fungsi objektif dari KSP adalah mencari keuntungan minimal terbesar atau dalam kata lain memaksimasi nilai minimum. Solusi dari KSP adalah kombinasi keputusan barang yang akan dimasukkan dalam tas berbentuk angka biner. KSP adalah permasalahan yang tergolong NP-hard dimana tingkat kesulitan akan naik secara eksponensial jika masalah bertambah besar. Sehingga digunakan metode pendekatan meta heuristik dalam penyelesaian KSP. Pada penilitian ini digunakan Binary Flower Pollination Algorithm yang diadaptasikan untuk menyelesaikan KSP. BFPA terinspirasi dari alam yang mengikuti perilaku dari penyerbukan bunga yang memiliki dua jenis penyerbukan. Pada BFPA dilakukan binary decoding dengan sigmoid function untuk proses decoding. Penggunaan binary decoding bertujuan untuk mengubah proses pencarian yang bernilai kontinu menjadi diskrit sesuai dengan KSP. BFPA yang dirancang telah diimplementasikan pada 12 kasus benchmark dengan 27 kombinasi parameter dan dilakukan lima replikasi untuk setiap kombinasinya. Hasil dari implementasi tersebut menunjukan bahwa BFPA mampu menemukan 6 solusi optimal dari 12 kasus benchmark yang ada. Performansi BFPA juga dibandingkan dengan 2 algoritma pembanding yaitu Elephant Herding Optimization, dan Dragonfly Algorithm. Hasil dari perbandingan menunjukan bahwa performansi BFPA dalam menemukan solusi optimal KSP pada kasus benchmark tidak lebih baik dari algoritma pembanding tetapi untuk kasus dengan kelas besar BFPA bisa memberikan solusi dengan variasi yang lebih kecil.