پاورپوینت الگوریتم باینری بهینه سازی تعادل دودویی برای مشکلات کوله پشتی

پاورپوینت “الگوریتم باینری بهینه سازی تعادل دودویی برای مشکلات کوله پشتی ۰-۱”

درس: شبکه های عصبی

موضوع: کوله پشتی

به همراه شکل و نمودارهای مرتبط

دارای نتیجه گیری و بحث نهایی

مناسب دانشجویان کارشناسی ارشد و دکتری

گارانتی: دارد

ترجمه مقاله اصلی این پاورپوینت: لینک دریافت

مسئله کوله پشتی:

مسئله کوله‌ پشتی که با نام‌ های Knapsack یا Rucksack مطرح می‌ شود مسئله‌ ای در بهینه‌ سازی ترکیبیاتی است. فرض کنید مجموعه‌ ای از اشیا که هر کدام داری وزن و ارزش خاصی هستند در اختیار دارید. به هر شی تعدادی را تخصیص دهید به‌ طوری‌ که وزن اشیا انتخاب شده کوچکتر یا مساوی حدی از پیش تعیین شده. و ارزش آن‌ ها بیشینه شود. علت نام گذاری این مسئله، جهانگردی است که کوله‌ پشتی‌ ای با اندازه محدود دارد و باید آن را با مفیدترین صورت ممکن از اشیا پر کند.

مشکلات کوله پشتی:

اگر اندازه کوله پشتی افزایش یابد. زمانی که روش های دقیق برای جستجوی راه حل بهینه مصرف می کنند، به طور تصاعدی افزایش می یابد. روش های دقیق مانند جستجوی کامل یا شاخه و محدود، منابع محاسباتی فوق العاده ای را از نظر مکان و زمان. به ویژه برای کوله پشتی های مقیاس بزرگ، مصرف می کنند. از این رو، نیاز به یافتن یک راه حل تقریباً بهینه در یک زمان قابل قبول روندی است که بسیاری از محققان برای حل کوله پشتی دنبال می کنند.

مسئله کوله پشتی ۰-۱:

در مسئله کوله پشتی ۰-۱، فرض کنید مجموعه ای از n مورد به گونه ای آورده شده است. که هر یک دارای یک وزن خصوصی و Wi و مزیت Pi باشد. از بین n مورد ارائه شده، تصمیم گیرندگان به زیر مجموعه ای از آنها احتیاج دارند. که با حداکثر جمع کردن وزن خود از ظرفیت کوله پشتی، مزیت را به حداکثر برسانند. برای یافتن زیر مجموعه های این موارد، کوله پشتی ایجاد شده است. تا شامل آیتم انتخابی i با مقداری باشد که در حالی سایر موارد دارای مقداری هستند که در کوله پشتی xi = 1 xi = 0 انتخاب نشده است.