Penerapan Algoritma Genetika Dan Algoritma Migrating Birds Optimization (Mbo) Pada Permasalahan Knapsack 0-1

Abstract

Permasalahan optimasi sering dihadapi dalam kehidupan sehari-hari. Salah satu dari permasalahan optimasi adalah pemilihan barang-barang yang akan dimasukkan ke dalam sebuah wadah dengan harapan memperoleh keuntungan yang maksimal. Permasalahan optimasi tersebut merupakan permasalahan knapsack. Permasalahan knapsack merupakan permasalahan tentang pemilihan barang dari sejumlah barang yang ada sehingga diperoleh keuntungan yang maksimal tanpa melebihi kapasitas dari wadah yang disediakan. Barang-barang tersebut memiliki bobot dan keuntungan atau nilai yang bervasiasi. Permasalahan knapsack dalam tiga jenis, yaitu permasalahan knapsack 0-1, permasalahan bounded knapsack, permasalahan unbounded knapsack. Pengelompokan tersebut didasarkan pola penyimpanan barang dengan bobot dan nilai yang bervariasi. Pengelompokan tersebut dilakukan agar dalam pemecahan masalahnya dapat ditemukan solusi yang optimal dan efisien. Penelitian kali ini membahas tentang permasalahan knapsack 0-1. Permasalahan knapsack 0-1 merupakan permasalahan penyimpanan barang, dimana barang akan dimasukkan secara keseluruhan atau tidak sama sekali. Penelitian ini akan menyelesaikan permasalahan knapsack 0-1 menggunakan algoritma genetika dan algoritma Migrating Birds Optimization (MBO) dan untuk mengetahui hasil dan waktu komputasi dari penerapan algoritma tersebut. Data yang digunakan pada penelitian kali ini adalah data UD Permata Indah ketika membeli barang barang dan akan dijual kembali. Isi dari data tersebut antaralain nama barang, jumlah barang, harga beli, dan harga jual. Penyelesaian dibantu software MATLAB R2015b dan dijalankan pada laptop dengan spesifikasi Intel(R) Core(TM) i5-3337U CPU @1.80GHz, RAM 4,00 GB dan 64-bit OS. Hasil penelitian menunjukkan bahwa profit dan berat barang yang diangkut menunjukkan hasil yang sama yaitu dengan profit sebesar Rp 6.343.000,00 dengan total berat barang yang diangkut sebanyak 986 kg. Barang yang diangkut sebagai berikut. Berdasarkan hasil penelitian, kekonvergenan dan running time dipengaruhi oleh parameter-parameter yang digunakan. Secara umum penggunaan parameter pada masing-masing algoritma tidak berpengaruh signifikan terhadap hasil (keuntungan maksimum), kekonvergenan dan running time jika dilihat dari hasil terbaik 15 kali running. Namun jika dilihat dari rata-rata hasil yang didapatkan, jumlah populasi yang digunakan sangat berpengerauh terhadap hasil kekonvergenan dan running time. Hasil rata-rata saat populasi sebanyak 21 menunjukkan bahwa algoritma MBO konvergen pada iterasi 15 dengan running time 94,29 detik dan algoritma genetika konvergen pada iterasi 146 dengan running time 79,36 detik. Hasil rata-rata saat populasi sebanyak 31 menunjukkan bahwa algoritma MBO konvergen pada iterasi 14 dengan running time 99,07 detik dan algoritma genetika konvergen pada iterasi 88 dengan running time 76,55 detik. Rata-rata dari hasil terbaik 15 kali running menunjukkan bahwa algoritma MBO lebih cepat konvergen daripada algoritma genetika, akan tetapi algoritma MBO memiliki running time yang lebih lama daripada algoritma genetika. Hasil tersebut menunjukan bahwa Algoritma MBO lebih baik daripada algoritma genetika karena algoritma MBO membutuhkan iterasi yang lebih sedikit dari pada algoritma genetika untuk memperoleh solusi yang optimal.