### Algoritma Genetika pada Optimasi Persoalan Knapsack 0/1

Abdullah Husein - Jurusan Matematika Universitas Negeri Padang
Dewi Murni - Jurusan Matematika Universitas Negeri Padang
Meira Dewi - Jurusan Matematika Universitas Negeri Padang

#### Abstract

Abstract – The problem of 0/1 Knapsack is an issue in the selection of objects from the set of objects that each object have a decision "selected" or "not selected". The decision to choose a object is prioritized by the weight and profit of these objects, for example, to maximize profits or minimize costs. The main issue of this problem, it take to many processes and time to find the optimum solution. Therefore, we need a method and a program to find aproximate solutions to this problem so that decisions can be made quickly with fixed gain maximum profit. The purpose of this study is to obtain an efficient way to finding the optimum solution of this problem. Optimization method that used in this research is genetic algorithm, while the program is made in Python programming language. Based on this research, it is known that the genetic algorithm is able to obtain the optimum solution knapsack problem in a fairly short time.

Keywords – 0/1 knapsack problem, finding the optimal solution, genetic algorithm

PDF

#### References

Martello, Silvano & Paolo Toth. 1990. Knapsack Problems Algorithms and Computer Implementations. England: John Willey & Sons Ltd.

Hristakeva, Maya & Dipti Shrestha. 2004. “Different Approaches to Solve the 0/1 Knapsack Problem”. Paper. Computer Science Department, Simpson College.

Hristakeva, Maya & Dipti Shrestha. 2004. “Solving the 0/1 Knapsack Problem with Genetic Algorithm”. Paper. Computer Science Department, Simpson College.

Zukhri, Zainudin. 2014. Algoritma Genetika: Metode Komputasi Evolusioner untuk Menyelesaikan Masalah Optimasi. Yogyakarta: Penerbit Andi.

Talbi, El-Ghazali. 2009. Metaheuristic From Design to Implementation. New Jersey: John Willey & Sons, Inc.

Husein, Abdullah. 2016. “Algoritma Genetika pada Optimasi Persoalan Knapsack 0/1”. Skripsi. Padang: UNP

DOI: http://dx.doi.org/10.24036/unpjomath.v6i2.11551