PENERAPAN ALGORITMA GENETIKA HYBRID PADA PERMASALAHAN BOUNDED KNAPSACK

Abstract

Knapsack Problem merupakan masalah dimana seseorang dihadapkan pada persoalan optimasi pada pemilihan benda yang akan dimasukkan ke dalam sebuah wadah yang memiliki sebuah keterbatasan ruang atau daya tampung. Wadah atau tempat tersebut hanya dapat menyimpan beberapa objek dengan ketentuan total satuan objek tersebut lebih kecil atau sama dengan satuan kapasitasnya. Ada tiga macam masalah knapsack, salah satunya adalah bounded knapsack. Bounded knapsack adalah permasalahan pengambilan sebagian atau semua objek dari beberapa objek yang jumlahnya terbatas. Penelitian ini mengaplikasikan algoritma genetika hybrid pada permasalahan bounded knapsack. Selain untuk mengetahui konsep dan hasil dari algoritma, penelitian ini juga untuk mengetahui peranan dari probabilitas algoritma dalam pencarian nilai optimum. Serta membandingkan solusi optimal algoritma genetika dan algoritma genetika hybrid dari segi hasil maupun waktu yang dibutuhkan. Hasil penelitian menunjukkan bahwa algoritma genetika hybrid dapat diimplementasikan pada permasalahan bounded knapsack dengan baik. Penggunaan algoritma tabu search pada proses crossover memberikan hasil yang optimal yakni dapat mengurangi waktu pencarian solusi. Dari 15 pasang parameter probabilitas yang di uji dengan 10 kali running, 3 pasang probabilitas menunjukkan hasil profit maksimal yang sama yaitu Rp. 4.872.900, namun pada probabilitas crossover 0,9 dan probabilitas mutasi 0,05 membutuhkan waktu sedikit lebih cepat (1,3719 detik) dibandingkan dua pasang probabilitas yang lain. Sedangkan hasil perbandingan menunjukkan algoritma genetika hybrid dari pada algoritma genetika karena menghasilkan profit lebih maksimal dan running time lebih cepat di banding algoritma genetika