Penyelesaian masalah knapsack dengan menggunakan algoritma migrating birds optimization

Abstract

Masalah knapsack adalah suatu permasalahan untuk memilih objek-objek yang memiliki bobot dan nilai lalu akan dimasukkan ke dalam knapsack sehingga tidak melebihi kapasitas dari knapsack dan memperoleh keuntungan maksimal dari objek-objek yang dimasukkan. Permasalahan knapsack aplikasinya banyak digunakan dalam dunia nyata di berbagai bidang. Penelitian knapsack sering digunakan untuk membahas hal-hal masalah kargo loading, penjadwalan mesin, alokasi sumber daya atau memori, dan optimisasi terhadap sumber daya. Namun permasalahan ini cukup rumit karena kompleksitas yang tinggi dalam menyelesaikan permasalahan ini dan termasuk ke dalam masalah NP-complete problem. NP-complete problem adalah permasalahan yang dalam pencarian solusinya tidak dapat diselesaikan dengan waktu polynomial. Waktu polynomial adalah waktu yang berbentuk suku banyak yang memiliki variabel, koefisien, dan konstanta. Contohnya adalah n2. Pada skripsi ini, untuk menyelesaikan permasalahan knapsack digunakan sebuah algoritma yang bernama Migrating Birds Optimization. Migrating Birds Optimization merupakan algoritma yang terinspirasi dari sekumpulan burung yang sedang melakukan migrasi dan membentuk formasi V. Formasi ini terdiri dari burung pemimpin dan burung tetangga. Tiap kumpulan burung tersebut akan merepresentasikan solusi yang berisi kombinasi dan nilai dari bendabenda yang diambil dan tidak melebihi kapasitas. Burung pemimpin dan burung tetangga tersebut akan dibandingkan satu sama lain sehingga burung dengan nilai terbaik akan menjadi burung pemimpin. Migrating Birds Optimization ini akan digunakan dengan mencari kombinasikombinasi dari kumpulan benda yang tersedia dalam setiap permasalahan knapsack dan akan dibandingkan terhadap kombinasi yang tersedia sehingga dapat menghasilan solusi yang optimal. Penelitian pada skripsi dengan menggunakan algoritma Migrating Birds Optimization ini akan dibangun dengan menggunakan bahasa pemrograman java. Hasil pengujian dari perangkat lunak yang dibangun adalah solusi optimal dari setiap permasalahan knapsack berupa nilai fitness dan kombinasi benda yang terpilih. Hasil pengujian yang didapat dengan menggunakan algoritma Migrating Birds Optimization juga diukur kinerjanya dalam menemukan solusinya dan didapat MSE (Mean Squared Error) dari pengujian yang dilakukan adalah 2670,65 dan 4513,975