Abstract:
Knapsack problem merupakan sebuah permasalahan untuk menentukan
kombinasi barang yang dapat dimasukkan ke dalam tas dengan kapasitas
tertentu dengan
tujuan mendapatkan keuntungan maksimum. Knapsack problem merupakan
permasalahan yang Non-deterministic Polynomial-time Hard (NP-hard)
sehingga metode
metaheuristik merupakan metode yang paling baik untuk menyelesaikan
masalah tersebut.
Pada penelitian ini dilakukan penerapan algoritma Improved Raven
Roosting Optimization
(IRRO) dalam menyelesaikan knapsack problem.
IRRO merupakan algoritma berbasis swarm intelligence baru yang
terinspirasi
dari aktivitas roosting dan mencari makan yang dilakukan burung
gagak. IRRO memiliki 8
buah parameter yaitu jumlah agen pencari (n), jumlah iterasi
maksimum (mi), konstanta
radius leader (kRlead), konstanta radius persepsi (kRpept), jumlah
langkah (s), jumlah
persepsi (t), proporsi follower (Pf), dan proporsi weak (wpp). Pada
penelitian ini parameter
yang diuji adalah kRlead, kRpept, Pf, dan wpp, dengan kRlead dan
kRpept yang bernilai
3,6 dan 1,8, serta Pf dan wpp yang bernilai 0,2 dan 0,4. 16 buah
kombinasi parameter
digunakan untuk menyelesaikan 8 kasus benchmark.
Dilakukan uji ANOVA untuk mengetahui parameter yang berpengaruh
terhadap
nilai solusi. KRpept berpengaruh pada semua kasus kecuali kasus 1
dan 2, sedangkan
interaksi antara kRlead dan kRpept berpengaruh terhadap kasus 4,5,
dan 6. Performansi
IRRO dibandingkan dengan algoritma Viral System (VS), Elephant
Herding Optimization
(EHO), dan Whale Optimization Algorithm (WOA) untuk 3 kasus pertama,
serta algoritma
Harmony Search (HS), Artificial Bee Colony (ABC), dan WOA untuk
kasus 4 sampai 8.
IRRO berhasil memperoleh solusi optimal pada 3 kasus pertama serta
memiliki
performansi terbaik dibandingkan algoritma lainnya untuk kasus
keempat sampai
kedelapan.
