Abstract
Permasalahan yang dihadapi masyarakat sekarang adalah penyakit degenerative yang disebabkan oleh hidup yang tidak sehat. Salah satu cara hidup sehat adalah perencanaan menu makanan sehat. Menu makanan sehat merupakan permasalahan kombinatorial yang kompleks sehingga dibutuhkan metode kombinatorial yang tepat. Penelitian ini mengimplementasikan Multi-Dimensional Knapsack Problem (MDKP) dan algoritma genetika untuk alokasi penempatan perencanaan makanan yang akan dikonsumsi dalam satu hari. Alokasi waktu makan masing-masing memiliki kapasitas dan dilakukan pembobotan sesuai dengan kebutuhan perhari berdasarkan energi yang dibutuhkan. Optimasi MDKP menggunakan algoritma genetika menggunakan pencarian heuristik dari variasi kromosom yang dihasilkan dari penyandian dengan simbol, dari masing-masing kromosom merepresentasikan variasi solusi yang berbeda-beda. Kromosom membentuk suatu menu makanan sehat untuk pagi, siang dan malam yang akan dievaluasi melalui fungsi fitness yang didapatkan dari pinalti yang dibentuk berdasarkan konstrain yang terdapat dalam MDKP. Berdasarkan hasil pengujian didapatkan menu makanan sehat yang diperoleh dengan fitness sebesar 0.0449 pada kondisi pelatihan algoritma genetika dengan parameter probabilitas mutasi sebesar 50%, probabilitas crossover sebesar 70%, generasi sebanyak 100 generasi dan individu awal yang dibangkitkan sebanyak 7 individu.
