Knapsack problem adalah permasalah untuk memilih n barang dari N barang yang tersedia dimana n barang tadi akan dimasukan kedalam sebuah kantong. Namun terdapat masalah dimana kekuatan kantong untuk menahan beban terbatas kekuatannya. Sehingga n barang yang terpilih harus memiliki berat maksimum namun masih bisa menahan berat dari n benda yang terpilih tadi.
sumber : vi.wikipidia.org
Untuk menyelesaikan masalah ini diperlukan sebuah metode atau algoritma untuk mencari n barang dengan berat maksimum yang dapat ditempuh tersebut. misalnya kita memiliki 10 barang dimana akan diambil beberapa barang untuk dimasukkan kedalam kantong, kita akan menggunakan algoritma genetika. Individu didifinisikan sebagai daftar barang-barang yang dimasukan kedalam kantong, misalnya diantaranya adalah (1000010000) dan (1110000001) dimana 1 dinyatakan barang masuk kedalam kantong dan 0 tidak dimasukan sehingg untuk individu petama hanya barang 1 dan 6 yang masuk sedangkan untuk individu kedua hanya barang 1,2,3 dan 10 yang akan masuk. masing-masing individu akan dihitung nilai fitnessnya dimana fungsinya menyatakan selisih antara kapasitas maksimum kantong dikurangi berat benda-benda yang akan dimasukan. Fungsi dinyatakan maksimum jika mendekati 0 dan tidak negatif. Semua individu akan di crossoverkan dan dimutasikan sehingga misalnya sampai pada generasi ke 10 maka didapat sebuah solusi optimal dengan individu terpilih (1111000011) dimana hanya barang 1,2,3,4,9 dan 10 yang hanya dimasukan.
Tidak ada komentar:
Posting Komentar