Abstract:
Knapsack sharing problem (KSP) merupakan model permasalahan
pengalokasian sumber daya ke dalam knapsack yang memiliki kapasitas tertentu. KSP
merupakan variasi dari knapsack problem yang setiap sumber dayanya tergolong dalam
kelas-kelas tertentu. Fungsi objektif dalam KSP adalah memperoleh keuntungan yang
sebesar-besarnya untuk setiap kelas, atau dengan kata lain memaksimasi nilai minimum
dari keuntungan yang diperoleh di setiap kelas.
Elephant herding optimization (EHO) merupakan algoritma metaheuristik yang
terinsipirasi dari perilaku berkumpul dan berpindah tempat klan gajah. Di habitatnya, klan
gajah hidup bersama di bawah kepemimpinan seekor gajah matriarch. Pergerakan gajah
dalam suatu klan dipengaruhi oleh gajah matriarch dan seluruh gajah dalam klan. Di setiap
periode, seekor gajah jantan dalam setiap klan akan meninggalkan klan karena beranjak
dewasa.
EHO yang telah dirancang untuk menyelesaikan KSP diimplementasikan pada
12 kasus benchmark dengan 27 kombinasi parameter dan 5 replikasi di setiap
kombinasinya. Berdasarkan hasil implementasi, diperoleh solusi optimal pada 8 kasus.
Sedangkan untuk 4 kasus lain, EHO memperoleh solusi yang baik dengan penyimpangan
terkecil terhadap solusi optimal sebesar 0.020% dan penyimpangan terbesar sebesar
0.251%. Hasil implementasi EHO juga dibandingkan dengan algoritma lain, yaitu cuckoo
search (CS), memetic algorithm (MA), tabu search (TS), dan dragonfly algorithm (DA).
EHO memiliki performansi yang lebih baik daripada CS dan MA, serta memiliki performansi
yang sama baiknya dengan TS dan DA. Terdapat 3 parameter yang diuji pengaruhnya
terhadap performansi EHO, yaitu alfa, beta, dan jumlah klan. Berdasarkan hasil pengujian,
diketahui bahwa terdapat pengaruh dan interaksi antar parameter terhadap performansi
EHO di semua kasus benchmark yang diujikan.