Abstract:
Knapsack sharing problem (KSP) merupakan salah satu jenis dari permasalahan
Knapsack, yaitu pengalokasian sumber daya kepada suatu wadah dengan kapasitas
tertentu, dimana setiap sumber daya tersebut memiliki pembagian kelompok tersendiri.
Tujuan utama dari KSP adalah memaksimalkan total keuntungan minimum dari masingmasing
kelompok. KSP merupakan permasalahan NP-hard (Non-determinitstic
Polynomial-time Hard), dimana semakin bertambah jumlah variabelnya, maka lama waktu
dalam pengerjaannya akan bertambah secara eksponensial sehingga penyelesaian
permasalahan tersebut dengan metode analitis membutuhkan waktu yang sangat lama.
Dalam penelitian ini, KSP akan diselesaikan dengan pendekatan metode
metaherusitik yaitu Harmony Search Algorithm (HSA). HSA merupakan sebuah algoritma
studi yang terinspirasi dari para pemusik yang sedang mencari harmoni terbaik dari nadanada
yang dihasilkan oleh alat-alat musiknya. Berdasarkan inspirasi tersebut, maka HSA
mempunyai tiga kegiatan utama yaitu, memory consideration, pitch adjustment, dan
randomization dengan tiga parameter yaitu, harmony memory size, harmony memory
consideration rate, dan pitch adjustment rate. Berdasarkan kegiatan tersebut, HSA
mempunyai pergerakan pencarian solusi yang didasarkan dari harmoni-harmoni yang
sudah ditemukan sebelumnya yang membantu dalam pencarian solusi optimal.
Pada penelitian ini dilakukan penerapan HSA pada 10 kasus benchmark KSP yang
bervariasi dari jumlah barang, jumlah kelas, dan hubungan antara keuntungan dengan
beratnya dengan menggunakan 8 kombinasi parameter. Hasil dari penelitian ini adalah
HSA dapat menemukan solusi optimal pada 5 kasus benchmark dan dengan
menggunakan ANOVA didapatkan beberapa parameter yang berpengaruh terhadap
performansi HSA. Hasil perbandingan dengan algoritma lain adalah HSA menghasilkan
performansi lebih baik dari algoritma Cuckoo Search dan Cat Swarm Optimization, tetapi
tidak sebaik performansi Dragonfly Algorithm dan Tabu Search.
