Penerapan Harmony Search Algorithm dalam penyelesaian Knapsack Sharing Problem

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.