Pemecahan masalah multiple Knapsack dengan algoritma genetika
| Main Author: | LasmiRahmawati |
|---|---|
| Format: | Thesis NonPeerReviewed Book |
| Bahasa: | eng |
| Terbitan: |
, 2007
|
| Subjects: | |
| Online Access: |
http://repository.ub.ac.id/151598/1/050701803.pdf http://repository.ub.ac.id/151598/ |
Daftar Isi:
- Masalah knapsack termasuk dalam persoalan optimasi kombinatorial. Nama knapsack berasal dari masalah dalam mengatasi cara memilih objek untuk dimasukkan ke dalam suatu karung. Masalah knapsack termasuk permasalahan NP-Complete (Non Deterministic Polynomial - time Completed) dimana tidak ada penyelesaian paling optimal selain mencoba semua kemungkinan penyelesaian yang ada. Akan tetapi hal tersebut membutuhkan waktu komputasi yang sangat besar, sehingga untuk kasus NP- complete dengan jumlah input yang besar bisa diselesaikan dengan program berkecepatan tinggi. Pemecahan masalah multiple knapsack diperlukan agar pengaturan muatan suatu komoditi barang mendapatkan cost yang paling kecil. Algoritma genetika sebagai alternatif solusi untuk membantu memecahkan masalah multiple knapsack. Tahapan dalam penelitian ini adalah mencari beberapa solusi urutan barang yang akan dimasukkan ke dalam karung, dengan syarat jumlah maksimal bobot barang yang akan dimasukkan ke dalam karung kurang dari atau sama dengan kapasitas maksimal masing-masing karung. Kemudian dilakukan pembagian barang setelah didapatkan solusi yang paling optimum. Pembagian barang ke dalam karung dilakukan urut mulai urutan pertama sampai urutan yang ditentukan berdasarkan kapasitas maksimal karung. Hasil akhir dari pemecahan masalah multiple knapsack diperoleh dari kromosom yang memiliki nilai fitness yang tertinggi dan cost terendah. Berdasarkan uji coba yang dilakukan, untuk contoh uji 1 probabilitas crossover yang optimal digunakan adalah 0.9 pada ukuan populasi 30, untuk contoh uji 2 probabilitas crossover yang optimal digunakan adalah 0.8 pada ukuan populasi 25, sedangkan untuk contoh uji 3 probabilitas crossover yang optimal digunakan adalah 0.6 pada ukuan populasi 20.