Wilhelmina Michelle Djema Pengarang ADRIANA FANGGIDAE Dosen Pembimbing 1 TIWUK WIDIASTUTI Dosen Pembimbing 2 Adriana Fanggidae Ketua Penguji Tiwuk Widiastuti Penguji 1 Arfan Yeheskiel Mauko Penguji 2

Knapsack Problem 0/1 merupakan sebuah permasalahan dimana terdapat beberapa objek yang masing-masing memiliki berat dan profit yang akan dimasukkan ke dalam sebuah knapsack atau ransel tanpa melebihi kapasitas knapsack tersebut. Knapsack Problem 0/1 termasuk ke dalam kelas NP-Hard (Non Polynomial Hard), dimana NP-Hard merupakan sekelompok masalah dimana tidak ada algoritma yang dapat menemukan solusi optimal untuk masalah tersebut dalam waktu polynomial (kompleksitas waktu berbentuk fungsi polinom). Alternatif yang disarankan adalah dengan menggunakan metode heuristik yang dianggap lebih efisien dan mampu mendapatkan solusi yang cukup optimal, salah satu metode heuristik yang paling sering digunakan untuk menyelesaikan kasus knapsack problem 0/1 adalah algoritma genetika. Pengujian dibagi ke dalam 4 kelompok barang yaitu 15, 30, 45, dan 60 barang serta masing-masing pengujian dilakukan sebanyak 100 kali. Parameter-parameter yang digunakan adalah jumlah populasi = 50, konvergensi populasi (threshold) = 90%, maksimum generasi = 100, kapasitas knapsack = 300 kg, pc = 0.3, 0.25, 0.2, dan pm = 0.1, 0.05, 0.01. Hasil pengujian dari metode crossover SPX, MPX, dan CX dalam menyelesaikan knapsack problem 0/1 menunjukkan bahwa dalam memberikan nilai fitness terbaik metode MPX unggul di 3 kelompok barang yaitu kelompok 15, 45, dan 60 barang dengan nilai pc = 0,3 dan pm = 0,05, ini dikarenakan terdapat dua daerah yang dipertukarkan dalam crossover dan ini berakibat pada waktu komputasi yang lama. Kata kunci : Knapsack problem 0/1, algoritma genetika, metode SPX, metode CX, metode MPX