Abstract:
Knapsack sharing problem (KSP) merupakan suatu permasalahan
pengalokasian sumber daya ke beberapa kelas. KSP menganalogikan sebuah tas sebagai
pihak penerima sumber daya. Tas tersebut dipisahkan menjadi beberapa sekat. Tujuan
dari model permasalahan ini adalah untuk memaksimalkan nilai minimum keuntungan dari
setiap kelas yang ada di dalam tas atau dengan kata lain menyamaratakan keuntungan
yang diperoleh oleh seluruh sekat di dalam tas. Solusi dari permasalahan ini berbentuk
suatu model kombinasi 0-1 yang menunjukkan masuk atau tidaknya beda ke dalam tas.
Dalam dunia nyata, KSP dapat digunakan dalam permasalahan penyeimbangan seperti
line balancing.
Dalam penelitian ini, KSP diselesaikan menggunakan binary firefly algorithm
(BFA). BFA merupakan algoritma metaheuristik yang terinspirasi dari cara hidup kunangkunang.
Dalam algoritma ini, solusi dari KSP dianalogikan sebagai kunang-kunang.
Aktivitas yang dilakukan kunang-kunang adalah bergerak dan berkumpul disuatu lokasi.
Aktivitas tersebut menjadi penentu kunang-kunang dalam mencari solusi KSP serta
dipengaruhi oleh 3 parameter yaitu alpha, gamma, dan beta. Parameter alpha merupakan
parameter penentu dalam kunang-kunang bergerak acak, parameter gamma merupakan
nilai absorbsi cahaya suatu kunang-kunang melihat cahaya kunang-kunang lain, dan
parameter beta adalah absorbsi cahaya suatu kunang-kunang ketika melihat cahayanya
tersendiri.
BFA yang telah dirancang diimplementasikan pada 10 kasus benchmark KSP
dengan 9 kombinasi parameter untuk setiap kasus benchmark dan diulang sebanyak 5 kali
untuk setiap kombinasi. Terdapat 3 level untuk setiap parameter, serta terdapat 2
parameter yang diuji pengaruhnya terhadap performansi dari BFA. Berdasarkan hasil
implementasi diketahui bahwa BFA mampu menghasilkan solusi terbaik mencapai nilai
optimal pada 6 kasus benchmark. Sedangkan sisa 4 kasus lainnya belum mencapai solusi
optimal dengan selisih terbesar sebesar 0,4% dan terkecil 0,039%. Selain itu, diketahui
pula parameter yang berpengaruh terhadap performansi BFA hanyalah parameter alpha.
Hasil implementasi tersebut dibandingkan dengan 3 algoritma pembanding lainnya antara
lain Dragonfly Algorithm, Cat Swarm Optimization, dan Tabu search.
