•  
  •  
 

Abstract

Permasalahan knapsack merupakan salah satu masalah optimisasi. Masalah knapsack merupakan suatu permasalahan bagaimana memilih objek dari beberapa objek yang akan dimasukkan ke media penyimpanan dengan masing-masing objek memiliki bobot dan total bobot dari objek yang dipilih tidak boleh melebihi kapasitas media penyimpanannya, sehingga diperoleh nilai yang maksimal. Ketika objek yang dimasukkan ke dalam media penyimpanan bersifat harus dimasukkan semua atau tidak sama sekali, permasalahan ini dikenal dengan nama knapsack 0-1. Salah satu metode penyelesaian masalah knapsack 0-1 adalah dengan menggunakan metode meta-heuristic. Terdapat beberapa metode meta-heuristic seperti algoritma migrating birds optimization dan particle swarm optimization. Paper ini membahas bagaimana algoritma migrating birds optimization dan particle swarm optimization digunakan dalam menyelesaikan permasalahan knapsack 0-1. Kemudian dilakukan perbandingan kinerja kedua algoritma tersebut berdasarkan nilai fungsi tujuan untuk beberapa studi kasus. Berdasarkan hasil penelitian ini algoritme migrating birds optimization mempunyai nilai hasil fungsi objektif yang lebih baik dibandingkan dengan algoritma particle swarm optimization.


Migrating Birds Optimization Algorithm and Particle Swarm Optimization Algorithm: Knapsack problem solving 0-1

Abstract

The knapsack problem is one of the optimization problems. The knapsack problem is a problem of how to select objects from several objects to be inserted into the storage with each object having a weight and the total weight of the selected object must not exceed the capacity of the storage so that the maximum value is obtained. When objects that are inserted into the storage have the character of having to be included all or nothing, this problem is known as the 0-1 knapsack. One of the methods of solving the 0-1 knapsack problem is by using the meta-heuristic method. There are several meta-heuristic methods such as the migrating birds optimization algorithm and particle swarm optimization. This paper discusses how migrating birds optimization and particle swarm optimization algorithms are used to solve the 0-1 knapsack problem. Then the performance of the two algorithms is compared based on the objective function values for several case studies. Based on the results of this study, the migrating birds optimization algorithm has better objective function values than the particle swarm optimization algorithm.

Included in

Mathematics Commons

Share

COinS