PENERAPAN ALGORITMA GENETIKA DAN ALGORITMA HARMONY SEARCH PADA PERMASALAHAN KNAPSACK 0-1

Abstract

Masalah knapsack adalah suatu masalah bagaimana cara menentukan pemilihan barang dari sekumpulan barang dimana setiap barang tersebut mempunyai berat dan keuntungan masing-masing yang berbeda, sehingga dari pemilihan barang tersebut didapatkan keuntungan yang maksimum. Masalah knapsack sering terjadi pada media transportasi ketika akan mengangkut banyak barang, dimana berat barang yang diangkut tidak boleh melebihi kapasitas media transportasi yang digunakan. Penelitian ini membandingkan algoritma Genetika dan algoritma Harmony Search. Selain untuk mengetahui konsep dan hasil dari kedua algoritma ini juga bertujuan untuk mengetahui algoritma mana yang lebih baik untuk menyelesaikan permasalahan knapsack 0-1 dengan membandingkan hasil, running time, dan konvergensi dari kedua algoritma. Hasil penelitian menunjukkan bahwa algoritma Genetika lebih baik daripada algoritma Harmony Search dalam menyelesaikan permasalahan knapsack 0-1 pada studi kasus UD. Permata Indah Situbondo. Hasil profit yang ditunjukkan oleh algoritma Genetika lebih stabil daripada algoritma Harmony Search yaitu pada nilai Rp 6.343.000,-, sedangkan hasil yang ditunjukkan algoritma Harmony Search mengalami perubahan yang fluktuatif sejak percobaan ketiga. Dilihat dari sisi yang lain, algoritma Genetika memiliki running time yang lebih lama daripada algoritma Harmony Search. Akan tetapi, algoritma Genetika mencapai konvergen lebih cepat daripada algoritma Harmony Search.