PERBANDINGAN UNJUK KERJA METODE DECODER DENGAN METODE PENALTY DALAM MENYELESAIKAN KNAPSACK PROBLEM 0/1 MENGGUNAKAN ALGORITMA GENETIKA
Abstract: Knapsack problem 0/1
adalah optimasi kombinatorial yang bertujuan memilih objek-objek mana yang
harus dimasukan ke dalam knapsack sedemikian hingga menghasilkan profit
maksimum. Knapsack problem 0/1 dapat diselesaikan menggunakan algoritma
genetika dengan pendekatan representasi biner yang dapat menghasilkan
infeasible solution. Masalah infeasible solution dapat diselesaikan dengan dua
metode, yaitu metode decoder dan metode penalty, pada penelitian ini dilakukan
perbandingan untuk kedua metode tersebut. Siklus algoritma genetika yang
digunakan dalam penelitian ini adalah siklus yang dicetuskan oleh Zbigniew
Michalewis. Parameter perbandingan yang digunakan adalah rata-rata jumlah
feasible solution dan standar deviasi dari nilai fitness kromosom terbaik,
dengan menggunakan 8 data set yang diujikan terhadap kedua metode dengan
variasi jumlah objek mulai dari 10 sampai 80 objek. Objek-objek yang diujikan
dalam penelitian ini diasumsikan merupakan benda mati yang tidak mengalami
penurunan kualitas, dimensi dari objek yang diujikan pada masalah knapsack 0/1
ini tidak diperhitungkan. Setiap data set diujikan sebanyak 5 kali,
perbandingan yang didapatkan yaitu metode decoder berhasil mengeliminasi
infeasible solution dari 5 kali pengujian untuk setiap data set, rata-rata
metode decoder memberikan 5 feasible solution, sedangkan metode penalty belum
berhasil mengeliminasi infeasible solution, dari 5 kali pengujian untuk setiap
data set, rata-rata metode penalty memberikan 4 infeasible solution. Metode
decoder juga unggul dalam tingkat kekonsistenan dalam memberikan solusi yang
sama, dari 5 kali pengujian untuk setiap data set, metode decoder memiliki rata-rata
standar deviasi sebesar 12,7875, sedangkan metode penalty memiliki rata-rata
standar deviasi sebesar 100,85, sehingga metode decoder merupakan metode yang
dianjurkan untuk digunakan dalam menyelesaikan knapsack problem 0/1.
Kata Kunci: Masalah Knapsack
0/1, Algoritma Genetika, Representasi Biner, Infeasible Solution, Unjuk Kerja Metode Decoder dan
Metode Penalty
Penulis: Arini Aha Pekuwali,
Adriana Fanggidae, Yulianto T. Polly
Kode Jurnal: jptkomputerdd130232
