LasmiRahmawati (2007) Pemecahan masalah multiple Knapsack dengan algoritma genetika. Sarjana thesis, Universitas Brawijaya.
Abstract
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.
| Item Type: | Thesis (Sarjana) |
|---|---|
| Identification Number: | SKR/MIPA/2007/050701803 |
| Subjects: | 500 Natural sciences and mathematics > 510 Mathematics |
| Divisions: | Fakultas Matematika dan Ilmu Pengetahuan Alam > Matematika |
| Depositing User: | Unnamed user with email repository.ub@ub.ac.id |
| Date Deposited: | 27 Jul 2007 00:00 |
| Last Modified: | 22 Oct 2021 03:17 |
| URI: | http://repository.ub.ac.id/id/eprint/151598 |
Preview |
Text
050701803.pdf Download (3MB) | Preview |
Actions (login required)
 |
View Item |