Penerapan algoritma Grey Wolf Optimizer untuk menyelesaikan Knapsack Sharing Problem

Abstract

Knapsack Sharing Problem (KSP) merupakan salah satu masalah pengalokasian suatu sumber daya terbatas kepada beberapa pihak yang memiliki kepentingannya masing-masing. Di dalam model KSP terdapat sebuah tas yang terbagi menjadi kelas-kelas. Setiap kelas ingin memasukan benda-benda yang memiliki bobot dan keuntungan yang berbeda-beda sebanyak mungkin. Tujuan dari model KSP adalah untuk menyeimbangkan keuntungan yang bisa didapatkan oleh setiap kelas, maka fungsi tujuan dari KSP adalah maksimasi nilai minimum dari keuntungan yang bisa didapat setiap kelas. Solusi dari model KSP adalah kombinasi benda-benda yang diputuskan masuk ke dalam tas. Pada penelitian ini, algoritma Grey Wolf Optimizer (GWO) diadaptasi untuk menyelesaikan KSP. Algoritma GWO terinspirasi dari strata sosial serigala dan kegiatan berburu mangsa yang dilakukan oleh serigala. Algoritma GWO dirancang dengan menggunakan invers sigmoid function untuk metode encoding dan sigmoid function untuk metode decoding. Hal ini dilakukan agar proses pencarian yang dirancang untuk kontinu dapat digunakan untuk masalah diskrit. Rancangan algoritma GWO telah diimplementasikan pada 10 kasus benchmark dengan 27 kombinasi parameter. Hasil implementasi menunjukkan bahwa GWO mampu memberikan solusi optimal di 4 kasus benchmark. Performansi GWO dibandingkan dengan Tabu Search (TS), Cuckoo Search (CS), dan Cat Swarm Optimization (CSO) yang menunjukkan bahwa GWO lebih baik dari CS dan CSO tetapi lebih buruk dari TS. Uji parameter dilakukan untuk 3 parameter yaitu jumlah populasi serigala (ssa), nilai awal a (a) dan jumlah iterasi (l). Hasil uji menunjukkan bahwa parameter ssa berpengaruh pada 4 kasus, parameter a berpengaruh pada 9 kasus, dan parameter l berpengaruh pada 2 kasus. Terdapat juga pengaruh dari interaksi antara parameter ssa serta pengaruh interaksi antara parameter a dan l masing-masing pada 2 kasus.