Penerapan algoritma Pigeon Inspired Optimization pada Multidimensional Knapsack Problem

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.