Abstract:
Multidimensional Knapsack Problem atau biasa disingkat MKP merupakan
model permasalahan pengalokasian sumber daya dengan beberapa wadah, dimana
setiap benda memiliki bobot tertentu di setiap wadahnya. MKP sendiri merupakan
pengembangan dari knapsack problem. Tujuan MKP adalah mencari keuntungan
sebesar-besarnya dengan mempertimbangkan kapasitas dan bobot setiap wadah dan
benda.
MKP akan diselesaikan menggunakan Pigeon Inspired Optimization atau biasa
disingkat PIO dalam penelitian ini. Algoritma PIO merupakah salah satu algoritma
metaheuristik yang tergolong dalam population-based swarm intelligent yang didasarkan
pada tingkah laku burung merpati yang mengetahui letak rumahnya meskipun telah pergi
jauh. Algoritma PIO ini memiliki 2 macam operator, yaitu map and compass operator
yang merupakan proses eksplorasi dan landmark operator yang merupakan proses
eksploitasi.
Perancangan algoritma PIO dilakukan untuk dapat menyelesaikan MKP.
Implementasi algoritma PIO terhadap MKP diterapkan terhadap 2 jenis kasus yang
memiliki karakteristik yang berbeda menggunakan metode OFAT sebanyak 5 kali
replikasi untuk mendapatkan nilai parameter terbaik. Terdapat 2 kombinasi nilai
parameter terbaik, yang pertama untuk kasus dengan jumlah knapsack yang banyak dan
yang kedua untuk kasus dengan jumlah item yang banyak. Kombinasi pertama nilai
parameter terbaik adalah Nc1max sebesar 1450, Nc2max sebesar 6, Np sebesar 450,
dan R sebesar 0.3. Kombinasi kedua nilai parameter terbaik adalah Nc1max sebesar
1150, Nc2max sebesar 4, Np sebesar 300, dan R sebesar 0.8. Hasil implementasi dari
kedua kombinasi nilai parameter terbaik Pada penerapan algoritma PIO terhadap MKP
untuk 10 kasus yang dibandingkan dengan algoritma Particle Swarm Optimization,
algoritma Intelligent Water Drops, dan algoritma genetika didapatkan hasil yang
memuaskan. Penyimpangan terbesar diantara penerapan 10 kasus adalah sebesar
1.03% dari hasil terbaik yang diketahui selama ini dan penyimpangan terkecil diantara
penerapan 10 kasus adalah sebesar 0% dari hasil terbaik yang diketahui selama ini.
Penyimpangan rata-rata untuk penerapan 10 kasus adalah sebesar 0.27% dari hasil
terbaik yang diketahui selama ini.
