Penerapan Binary Bat Algorithm dalam penyelesaian Knapsack Sharing Problem

Abstract

Dalam kehidupan nyata permasalahan kelangkaan sumber daya sering terjadi sehingga pengalokasian sumber daya yang baik diperlukan untuk mendapatkan keuntungan yang maksimal dari sumber daya yang terbatas tersebut. Permasalahan alokasi sumber daya dapat dimodelkan dalam Knapsack Sharing Problem. Knapsack Sharing Problem (KSP) adalah permasalahan pencarian kombinasi benda dengan keuntungan dan berat masingmasing untuk dimasukan ke dalam wadah dengan kapasitas terbatas dengan tujuan memaksimasi keuntungan grup benda terkecil. Kapasitas yang terbatas tersebut merupakan sumber daya sedangkan benda merupakan penggunaan sumber daya. Pada penelitian ini Binary Bat Algorithm (BBA) digunakan untuk menyelesaikan permasalahan KSP. Binary Bat Algorithm adalah salah satu algoritma metaheuristik yang terinspirasi dari pergerakan dan tingkah laku kelelawar dalam mencari mangsa. Setiap kelelawar memiliki 3 fase pergerakan yang dimulai dari pergerakan dengan mengubah frekuensi, pergerakan random walk, dan pergerakan random search. BBA dapat secara otomatis menyeimbangkan eksplorasi dan eksploitasinya dengan mengubah parameter, BBA juga menggunakan v-shaped transfer function untuk meningkatkan solusi. Pada BBA terdapat 5 parameter yaitu frekuensi maksimal, loudness awal, pulse rate awal, serta alfa dan gamma yaitu konstanta perubahan loudness dan pulse rate. Pada penelitian ini Binary Bat Algorithm dirancang untuk dapat menyelesaikan permasalahan KSP dan selanjutnya diterapkan pada 10 kasus benchmark KSP. Parameter yang paling berpengaruh adalah pulse rate yang berpengaruh pada 8 kasus dan dilanjutkan dengan frekuensi maksimal dan loudness. Alfa dan gamma hanya berpengaruh pada 1 kasus. Selain itu terdapat pula interaksi antar parameter. Interaksi yang paling banyak berpengaruh adalah interaksi antara frekuensi maksimal dan pulse rate yang berpengaruh pada 6 kasus benchmark. Solusi terbaik yang diperoleh BBA dalm setiap kasus dibandingkan dengan 4 algoritma metaheuristik lainnya yaitu Dragonfly Algorithm (DA), Cat Swarm Optimization (CSO), Tabu Search (TS), dan Shark Smell Optimization (SSO). BBA berhasil mencapai solusi optimal pada 6 kasus benchmark yang diujikan. Pada kasus yang tidak mencapai optimal dihasilkan solusi yang mendekati optimal dengan error terbesar 0,85% dan error terkecil 0,05% yang masih berada di bawah DA dan TS tetapi berada di atas SSO dan CSO.