Penyelesaian Masalah Knapsack 0-1 Menggunakan Algoritme Migrating Birds Optimization dan Particle Swarm Optimization

Abstract

Masalah knapsack merupakan permasalahan optimisasi kombinatorial yang diklasifikasikan sebagai NP-complete problem. Tujuannya adalah untuk memperoleh keuntungan maksimum tanpa melebihi kapasitas knapsack dengan objek yang dipilih. Ada beberapa metode yang dikembangkan untuk permasalahan ini, salah satunya adalah metode meta-heuristic. Pada karya ilmiah ini, digunakan metode meta-heuristic migrating birds optimization (MBO) dan particle swarm optimization (PSO) untuk menyelesaikan masalah knapsack. Hasil yang diperoleh menunjukkan bahwa algoritme MBO menghasilkan keuntungan yang relatif lebih besar dibandingkan algoritme PSO.

Knapsack problem is a combinatorial optimization problem which is classified as an NP-complete problem. Its aim is to achieve maximum benefit without exceeding the capacity of the knapsack with the selected objects. There are several methods developed for this problem, one of them is a meta-heuristic method. In this manuscript, migrating birds optimization (MBO) and particle swarm optimization (PSO) as meta-heuristic methods will be used to solve the knapsack problem. The result obtained shows that the MBO algorithm produces a relatively larger benefit than the PSO algorithm.