Penyelesaian permasalahan Knapsack Multidimensional dengan algoritma Grey Wolf Optimization dan algoritma Primal Effective-Capacity Heuristic

Abstract

Multidimensional Knapsack Problem adalah salah satu variasi Knapsack Problem. Multidimensional Knapsack Problem merupakan permasalahan optimasi pemilihan benda yang dapat dimasukkan ke dalam sebuah penampung yang memiliki batasan daya tampung. Benda yang tersedia memiliki weight lebih dari satu dimensi yang menggunakan kapasitas penampung, dan menghasilkan sejumlah profit. Pilihan benda-benda yang dimasukkan ke dalam knapsack harus menghasilkan total profit tertinggi dari seluruh kemungkinan pilihan yang memungkinkan, serta tidak melebihi batasan daya tampung knapsack. Multidimensional Knapsack Problem dapat diselesaikan dengan beberapa jenis algoritma, antara lain meta-heuristic, greedy-type heuristic, dan lain-lain. Pada skripsi ini, digunakan satu algoritma meta-heuristic, yaitu algoritma Grey Wolf Optimization, dan satu algoritma greedy-type heuristic, yaitu algoritma Primal Effective-Capacity Heuristic. Algoritma Grey Wolf Optimization menirukan perilaku berburu yang dilakukan oleh kawanan serigala, dan mengimplementasi hierarki kepemimpinan dalam kawanan serigala. Serigala menyimbolkan sebuah solusi dalam Multidimensional Knapsack Problem. Terdapat tiga serigala pemimpin yang dianggap sebagai serigala yang memiliki pengetahuan paling baik terhadap keberadaan mangsa. Tiga serigala pemimpin menyimbolkan tiga solusi Multidimensional Knapsack Problem dengan total profit tertinggi. Secara iteratif, setiap solusi dalam kumpulan solusi akan diperbarui sehingga mendekati perkiraan solusi optimal yang ditentukan oleh solusi-solusi terbaik. Solusi yang memiliki total profit yang lebih tinggi, dibandingkan salah satu solusi terbaik, akan ditetapkan sebagai solusi terbaik baru, menggantikan solusi terbaik sebelumnya. Akhirnya, satu solusi dengan total profit yang paling tinggi akan diambil sebagai hasil akhir. Algoritma Primal Effective-Capacity Heuristic merupakan algoritma yang bertipe greedy, dengan menggunakan nilai effective capacity benda sebagai nilai efisiensi benda. Setiap benda akan menghasilkan effective profit berdasarkan nilai effective capacity yang dimilikinya. Secara iteratif, benda dengan nilai effective profit terbesar akan dimasukkan ke dalam penampung, mengurangi sisa kapasitas yang tersedia, dan menambahkan profit ke dalam solusi. Proses berakhir ketika seluruh benda telah dimasukkan ke dalam penampung, atau tidak ada benda yang dapat dimasukkan ke dalam sisa kapasitas penampung. Skripsi ini bertujuan untuk mengimplementasikan algoritma Grey Wolf Optimization dan algoritma Primal Effective-Capacity Heuristic untuk menyelesaikan Multidimensional Knapsack Problem, serta melakukan pengukuran kinerja kedua algoritma dalam menyelesaikan Multidimensional Knapsack Problem. Untuk mencapai tujuan tersebut, dibangun perangkat lunak yang mengimplementasikan kedua algoritma tersebut. Perangkat lunak yang dibangun dapat menerima pilihan algoritma, input Multidimensional Knapsack Problem atau import dataset, memproses input sesuai algoritma yang dipilih, dan menampilkan output algoritma. Hasil implementasi dan pengujian kedua algoritma pada perangkat lunak menunjukkan bahwa algoritma Grey Wolf Optimization dengan parameter optimal, memiliki nilai rata-rata pencapaian profit tertinggi sebesar 99.37%, lebih baik sebesar 1.13% dibandingkan dengan algoritma Primal Effective-Capacity Heuristic yang memiliki nilai rata-rata pencapaian profit tertinggi sebesar 98.24%.