Contoh Penggunaan dan Penyelesaian Knapsack Problem


Apa itu Knapsack Problem ?

Knapsack problem merupakan masalah optimasi kombinasi dengan tujuan untuk memaksimalkan total nilai dari barang-barang yang dimasukkan ke dalam knapsack atau suatu wadah tanpa melewati kapasitas wadah tersebut. Knapsack problem atau rucksack problem adalah masalah optimasi kombinatorial. Namanya berasal dari masalah maksimasi untuk pilihan paling tepat dari barang-barang yang akan dibawa dalam sebuah tas pada sebuah perjalanan. Sejumlah barang yang tersedia ini, masing-masing memiliki berat dan nilai, yang menentukan jumlah barang yang dapat dibawa sehingga total berat tidak melebihi kapasitas tas dan dengan total nilai yang sebesar mungkin.

Pengertian Algoritma Genetika

Algoritma genetika adalah algoritma pencarian yang didasarkan atas mekanisme dari seleksi alam yang lebih dikenal dengan proses evolusi. Dalam proses evolusi, individu secara terus-menerus mengalami perubahan gen untuk menyesuaikan dengan lingkungan hidupnya. Hanya individu-individu yang kuat yang mampu bertahan. Proses seleksi alamiah ini melibatkan perubahan gen yang terjadi pada individu melalui proses perkembangbiakan. Dalam algoritma genetika, proses perkembangbiakan ini menjadi proses dasar yang menjadi perhatian utama, dengan dasar berpikir: Bagaimana mendapatkan keturunan yang lebih baik.

Permasalahan yang akan diselesaikan pada Knapsack Problem ini adalah optimasi pemilihan buah kemasan kotak pada proses distribusi barang untuk menekan biaya pengiriman dan memaksimalkan keuntungan. Adapun parameter-parameter yang digunakan adalah sebagai berikut:

Hanya terdapat satu item paket buah kemasan kotak yang sejenis dan memiliki profit, tingkat kebutuhan pasar, berat, volume, dan masa awet buah yang akan dipilih.

Berat ataupun volume total dari item buah kemasan kotak yang dipilih tidak boleh melebihi kapasitas dari Knapsack. Parameter-parameter pada algoritma genetika dapat diubah-ubah sesuai keinginan user seperti: ukuran populasi, probabilitas mutasi, dan probabilitas crossover.

Sistem akan menampilkan solusi optimal dari hasil pencarian yang berupa terpilih atau tidaknya suatu item untuk bisa dimasukkan ke dalam Knapsack, nilai keuntungan total, berat total, dan volume total dari item yang terpilih.

Dari pengembangan dan uji coba yang telah dilakukan terkait dengan implementasi algoritma genetika pada knapsack problem, dapat disimpulkan beberapa hal, yaitu:
  1. Algoritma genetika cukup baik digunakan pada knapsack problem.
  2. Peningkatan jumlah populasi akan memberikan nilai fitness yang semakin tinggi, yang berarti bahwa solusi optimal yang ditemukan semakin baik. Karena dengan peningkatan jumlah populasi akan memberikan ruang solusi yang semakin banyak.

Belum ada Komentar untuk "Contoh Penggunaan dan Penyelesaian Knapsack Problem"

Posting Komentar

Iklan Atas Artikel

Iklan Tengah Artikel 1

Iklan Tengah Artikel 2

Iklan Bawah Artikel