Penerapan Dragonfly Algorithm untuk menyelesaikan Knapsack Sharing Problem

Abstract

Knapsack sharing problem (KSP) merupakan permasalahan pengalokasian atau pendistribusian sumber daya terbatas kepada pihak-pihak yang membutuhkan. Pada KSP dianalogikan terdapat sebuah tas yang memiliki kapasitas tertentu dan terbagi menjadi beberapa kelas. Tas dengan benda-benda yang memiliki berat dan keuntungan yang berbeda-beda. Tujuannya adalah maksimisasi nilai minimum dari keuntungan yang diperoleh setiap kelas dalam tas. Solusi model KSP berupa kombinasi benda yang dimasukkan ke dalam setiap kelas pada tas. Di dunia nyata, model KSP digunakan untuk menyelesaikan permasalahan pengalokasian dana dan line balancing pabrik manufaktur. Pada penelitian ini, KSP diselesaikan dengan menggunakan dragonfly algorithm. Dragonfly algorithm merupakan algoritma metaheuristik yang terinspirasi dari perilaku berkerumun yang dimiliki capung. Aktivitas yang dilakukan kerumunan capung tersebut adalah mencari sumber makanan, menghindari pemangsa, menghindari tabrakan dengan capung lain, rnenyeimbangkan kecepatan dengan capung lain, dan cenderung untuk berada di pusat kerumunan capung. Kelima hal tersebut menjadi faktor penentu posisi capung dalam melakukan pencarian solusi. Dragonfly algorithm yang telah dirancang diimplementasikan pada 10 kasus benchmark KSr dengan 16 kombinasi parameter dan di setiap kombinasi dilakukan 5 replikasi. Dari hasil implementasi diketahui bahwa dragonfly algorithm mampu menghasilkan solusi optimal pada 6 kasus. Untuk 4 kasus lainnya, dragonfly algorithm menghasilkan solusi dengan penyimpanan terbesar sebesar 0,251 % dan penyimpangan terkecil sebesar 0,025% dari solusi optimal. Hasil implementasi tersebut dibandingkan dengan cat swarm optimization, cuckoo search, dan tabu search. Dragonfly algorithm memiliki performansi yang lebih baik daripada cat swarm optimization dan cuckoo search serta memiliki performansi yang sama baiknya dengan tabu search. Terdapat 4 parameter dragonfly algorithm yang diuji pengaruhnya terhadap performansi algoritma, yaitu batas atas w (ubw}, batas bawah w (lbw), batas atas my_c (ubc), dan batas bawah rny_c (lbc). Hasil pengujian menunjukkan adanya pengaruh dan interaksi antar parameter terhadap performansi dragonfly algorithm di seluruh kasus benchmark yang diuji.