Penerapan algoritma Elephant Herding Optimization untuk menyelesaikan Knapsack Sharing Problem

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.