Penerapan algoritma Elephant Herding Optimization untuk knapsack problem

Abstract

Penelitian ini akan membahas mengenai penerapan algoritma metaheuristik untuk menyelesaikan permasalahan knapsack. Permasalahan knapsack yang digunakan dalam penelitian ini adalah 0-1 knapsack problem. Permasalahan knapsack ini sebelumnya pernah diselesaikan menggunakan algoritma metaheuristik viral systems (Kartika, 2010). Penelitian ini akan membandingkan hasil penelitian sebelumnya menggunakan algoritma metaheuristik baru yaitu elephant herding optimization (EHO). Algoritma elephant herding optimization dirancang oleh Wang, Deb, dan Coelho (2015) dengan memodelkan perilaku kawanan gajah. Dalam algoritma elephant herding optimization ini, kawanan gajah akan dipimpin oleh seekor matriarch dan akan ada satu gajah jantan muda setiap generasi yang meninggalkan kawanan dan digantikan dengan gajah yang baru. Pada penelitian yang dilakukan oleh Wang et al. (2015) algoritma elephant herding optimization diujikan untuk 15 test function dan hasilnya cukup baik. Pada penelitian ini, algoritma elephant herding optimization akan digunakan untuk menyelesaikan permasalahan knapsack dengan menggunakan bantuan perangkat lunak Netbeans. Perancangan algoritma elephant herding optimization untuk knapsack problem terdiri menjadi beberapa bagian. Bagian pertama adalah penentuan ruang solusi awal untuk nantinya dilakukan perhitungan. Bagian kedua yaitu melakukan perhitungan clan updating operator untuk masing-masing gajah dan untuk gajah matriarch. Bagian ketiga adalah melakukan perhitungan clan separating operator untuk gajah dengan nilai fitness terburuk. Ada beberapa parameter pada algoritma elephant herding optimization. Parameter tersebut adalah jumlah gajah, jumlah clan, alpha, beta, dan jumlah iterasi. Dari empat kasus permasalahan knapsack yang diselesaikan, algoritma elephant herding optimization mampu mendapatkan hasil yang lebih baik dibandingkan dengan penelitian sebelumnya.