Penerapan Binary Firefly Algorithm untuk menyelesaikan Knapsack Sharing Problem

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.