Kombinasi EVO&STBO Untuk Penyelesaian Masalah Modifikasi Knapsack Kuadratik Terbatas Multikendala

Abstract

Penelitian ini berfokus pada penyelesaian permasalahan optimasi, khususnya permasalahan knapsack yang bertujuan menentukan kombinasi barang untuk memaksimalkan keuntungan tanpa melampaui kapasitas. Varian yang digunakan adalah permasalahan knapsack kuadratik terbatas multikendala, yang melibatkan batas jumlah barang, banyak kendala, serta keuntungan interaksi antarbarang. Berbagai algoritma metaheuristik telah digunakan untuk menangani permasalahan knapsack, seperti EHO, PeSOA, MBO, PSO, GEO, HCPSO, GSA&CSO, Tabu Search, dan Branch and Bound. Namun, penerapan dua algoritma metaheuristik yaitu Energy Valley Optimizer (EVO) dan Sewing Training Based Optimization (STBO) pada permasalahan ini masih sangat terbatas dalam literatur. EVO memiliki kelebihan pencarian secara global (eksplorasi) dan STBO unggul dalam pencarian secara lokal (eksploitasi). Berdasarkan kondisi tersebut, penelitian ini mengusulkan metode kombinasi EVO&STBO untuk menggabungkan kemampuan eksplorasi dan eksploitasi secara seimbang guna meningkatkan performa pencarian solusi. Penelitian ini mencakup penerapan dan evaluasi efektivitas algoritma kombinasi dibandingkan algoritma pembangunnya, serta analisis pengaruh variasi parameter terhadap kualitas solusi yang dihasilkan. Tahapan pelaksanaan dimulai dengan pembangkitan data simulasi di MATLAB untuk membentuk parameter permasalahan, meliputi berat, volume, harga beli, harga jual, serta batas jumlah barang. Implementasi algoritma dilakukan secara bertahap, meliputi penerapan algoritma EVO, STBO, dan kombinasi EVO&STBO dengan mekanisme eksplorasi menggunakan EVO yang dilanjutkan eksploitasi menggunakan STBO. Seluruh proses pemrograman dan simulasi dilakukan di MATLAB, dimana setiap konfigurasi parameter algoritma dieksekusi sebanyak 30 kali untuk memastikan hasil eksperimen yang stabil. Tahap akhir penelitian berupa analisis perbandingan untuk menilai performa ketiga algoritma dan dilanjutkan dengan pengujian sensitivitas parameter. Parameter yang diuji meliputi banyaknya kandidat solusi (𝑁), maksimum evaluasi fungsi (𝐹𝐸𝑆𝑚𝑎𝑥), dan iterasi (𝑇). Hasil pengujian parameter menunjukkan bahwa kombinasi EVO&STBO menghasilkan performa terbaik dibandingkan jika kedua algoritma digunakan secara terpisah. Jumlah kandidat solusi (𝑁) diubah maka performa KOMBINASI EVO&STBOtetap stabil, sedangkan performa EVO menurun dan STBO hanya meningkat sedikit tetapi tetap tidak lebih baik dari algoritma kombinasi. Pada pengujian maksimum evaluasi fungsi (𝐹𝐸𝑆𝑚𝑎𝑥), kombinasi EVO&STBO mengalami peningkatan performa yang sangat signifikan karena mekanisme eksplorasi EVO dan eksploitasi STBO memanfaatkan tambahan evaluasi dengan baik. Berbeda dengan itu, performa EVO memang meningkat tetapi cepat mencapai batas kejenuhan. Jumlah iterasi (𝑇) dalam performa kombinasi EVO&STBO terus meningkat secara konsisten meskipun perlahan, sementara STBO naik sedikit lalu berhenti meningkat. Secara keseluruhan, algoritma kombinasi EVO&STBO terbukti lebih unggul dan stabil, terutama dipengaruhi oleh parameter 𝐹𝐸𝑆𝑚𝑎𝑥 dan 𝑇, karena kemampuan eksplorasi dan eksploitasi yang seimbang membuatnya mampu menghasilkan solusi yang lebih optimal untuk permasalahan knapsack kuadratik terbatas multikendala.