Penerapan algoritma Improved Raven Roosting Optimization dalam penyelesaian Knapsack Problem

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.