مسئله کوله پشتی یا Knapsack Problem یکی از مسائل معروف هوش مصنوعی و بهینه سازی و تحقیق در عملیات می باشد ، اهمیت این مسئله از آن جهت است که مسائل دنیای واقعی را میتوان به آن نگاشت کرد و با حل کردن کوله پشتی میتوان مسائل دنیای واقعی مانند رمزنگاری ، تخصیص منابع و غیره را بهینه کرد.
در مسئله کوله پشتی ، هدف این است که از بین اشیای موجود که هرکدام وزن و ارزش خاص خود را دارند آنهایی را انتخاب کنیم که : بیشترین ارزش را برای ما تولید کنند و مجموع وزن آنها بیشتر از ظرفیت کوله پشتی نشود.
انواع مدلهای مسئله کوله پشتی
- کوله پشتی 0 و 1
- کوله پشتی کسری
- کوله پشتی چند بعدی
- کوله پشتی با کران
- کوله پشتی بیکران
هر کدام از مدلهای مختلف مسئله کوله پشتی ، تعریف ریاضی خاص خود را دارد. و برای اینکه بتوان آنها را حل کرد ابتدا باید فرمول ریاضی آنها را بدست آورد.
روشهای حل مسئله کوله پشتی
مسئله کوله پشتی را میتوان با روشهای مختلف مانند :
- حل کوله پشتی با برنامه نویسی پویا
- حل کوله پشتی با الگوریتم حریصانه
- حل کوله پشتی با الگوریتم عقبگرد
- حل کوله پشتی با الگوریتم ژنتیک یا GA
- حل کوله پشتی با الگوریتم تبرید یا SA
- حل کوله پشتی با الگوریتم ملخ یا GOA
- حل کوله پشتی با الگوریتم گرگ خاکستری یا GWO
- حل کوله پشتی با الگوریتم سنجاقک یا DA
- حل کوله پشتی با الگوریتم توده ذرات یا PSO
- حل کوله پشتی با الگوریتم تکامل تفاضلی یا DE
و سایر الگوریتم های تکاملی و فرابتکاری حل کرد.
ما در تیم برنامه نویسی هوشمند ، حل مسئله کوله پشتی با الگوریتم های مختلف را آماده کرده ایم و در نرم افزار Matlab پیاده سازی کرده ایم که میتوانید در لینک زیر به آنها دسترسی داشته باشید.