Penerapan algoritma Ant Lion Optimizer untuk Knapsack Problem

Abstract

Knapsack problem secara sederhana merupakan suatu permasalahan untuk menentukan benda yang akan dimasukkan ke dalam tas yang memiliki kapasitas tertentu dengan tujuan benda yang dimasukkan ke dalam tas dapat memaksimalkan keuntungan yang diperoleh. Knapsack problem tergolong ke dalam masalah Non-deterministic Polynomial-time Hard (NP-hard) sehingga saat jumlah benda yang tersedia untuk dimasukkan ke dalam tas menjadi sangat besar maka penyelesaian masalah dengan metode eksak akan menjadi sulit dan memakan waktu yang lama. Oleh karena itu, dalam penelitian ini knapsack problem diselesaikan dengan metode metaheuristik, yaitu menggunakan algoritma Ant Lion Optimizer (ALO). ALO merupakan algoritma metaheuristik berbasis populasi baru yang terinspirasi dari perilaku berburu undur-undur (antlion). Saat hendak berburu semut, antlion akan membuat lubang perangkap berbentuk kerucut kemudian diam bersembunyi di dasar lubang perangkap sambil menunggu semut yang bergerak acak mencari makan terperangkap ke dalam lubang perangkapnya. ALO memiliki 4 buah parameter yaitu jumlah agen pencari (N), jumlah iterasi maksimum (max_iter), batas bawah (lb), dan batas atas (ub). Parameter lb dan ub digunakan untuk mengatur batas gerak acak dari semut. 16 buah kombinasi parameter ALO digunakan untuk menyelesaikan 9 kasus benchmark. Performansi ALO dibandingkan dengan Elephant Herding Optimization (EHO) dan Whale Optimization Algorithm (WOA) untuk 3 kasus berdimensi kecil (20-50 benda). Selain itu, performansi ALO juga dibandingkan dengan Harmony Search (HS), Artificial Bee Colony (ABC), Soccer League Competition (SLC), dan WOA untuk 6 kasus berdimensi besar (100-1.500 benda). ALO berhasil memperoleh solusi optimal pada 2 kasus berdimensi kecil serta mengungguli algoritma lain untuk 1 kasus berdimensi kecil lainnya dan 1 kasus berdimensi besar. Performansi ALO untuk 5 kasus berdimensi besar lainnya hanya kalah dari SLC. Berdasarkan uji ANOVA, interaksi antara lb dan range dari lb dan ub memiliki pengaruh terhadap nilai solusi untuk semua kasus kecuali untuk 1 kasus berdimensi kecil.