اگر شما با بهینه سازی سروکار داشته باشید، مثلا دانشجوی رشته کامپیوتر یا تحقیق در عملیات یا بهینه سازی باشید ، حتما یکی از مواردی که در خصوصش بحث میشود مسئله کوله پشتی یا Knapsak Problem هست. از انجا که من خودم ارشد هوش مصنوعی هستم ، با این مسئله زیاد سرو کار داشتم. برای همین ترجیح دادم که اینجا هم یک گریزی به کوله پشتی و روشهای حل آن بزنم.
مسئله کوله پشتی یا knapsack Problem را اگر بخواهیم خیلی ساده توضیح بدهیم ، باید با یک مثال ساده این کار رو انجام بدیم.
بله یک دزد رو در نظر بگیرید که یک کیسه دست گرفته است و وارد خانه ای شده است ، حالا میخواهد کیسه خود را از اشیا و لوازم قیمتی پر کند و پا به فرار بگذارد.
کیسه همراه اقای دزد، یک وزن مشخص را میتواند تحمل کند مثلا 50 کیلو، و خب وسایلی که در خانه هست هم وزن های مختلفی دارند. قیمت هر کدوم هم متفاوت هست
دزد قصه ما دنبال این هست که وسایلی رو برداره که وزنشون کمتر و قیمتشون بیشتر باشه تا بتواند سود بیشتری از این دزدی برده باشد.
خب مثال رو به صورت زیر توصیف میکنیم تا بتوانیم به یک مدل ریاضی برسیم
خب مسئله کوله پشتی 0 و 1 را میتوانیم بصورت زیر فرموله کنیم:
در مسئله کوله پشتی 0 و 1 ، یک شی یا داخل کیسه قرار میگیرد یا قرار نمیگیرد. و فرومول فوق به بیان ساده میگوید که دنبال بیشینه کردن ارزش اشیای انتخابی هستیم با این شرط که مجموع وزن اشیای انتخاب شده بیشتر از W (وزن قابل تحمل توسط کیسه) نباشد.
سوالی که ممکن هست برای خیلی ها بوجود بیاد این هست که چرا مسئله کوله پشتی و حل آن مهم است؟
مسائل مختلفی در دنیای واقعی هستند که به نوعی مشابه مسئله کوله پشتی هستند و یافتن روش بهینه برای حل مسئله کوله پشتی، منجر به یافتن پاسخ بهینه برای آنها نیز میشود بعنوان مثال مسئله تخصیص منابع در شبکه ابری، انتخاب سهام در بورس، رمزنگاری در امنیت و مسائل مختلف دیگر از این دست مسائلی هستند که در کلاس مسئله کوله پشتی قرار میگیرند.
در طی سالهای اخیر، افراد زیادی برای حل بهینه مسئله کوله پشتی تلاش کرده اند ، و روشهای مختلفی نیز ابداع شده است ، از روش جستجوی عقبگرد گرفته ، تا روش جستجوی حریصانه و روش برنامه نویسی پویا، تا اخیرا که با معرفی الگوریتم های فراابتکاری و بهینه سازی ، استفاده از این روشها برای حل کوله پشتی همه گیر شده است . روشهایی مانند الگورتیم ژنتیک ، الگوریتم pso ، تا الگوریتم های جدید تر مانند الگوریتم ملخ، الگوریتم گرگ خاکستری ، الگوریتم شاهین هریس و غیره.
سعی کردم بصورت ساده ، مسئله کوله پشتی را تشریح کنم ، اگر شما نیز بر روی این مسئله کار میکنید و نیاز به برنامه نویس دست به کد در متلب دارید تا کوله پشتی را با الگوریتم های مختلف برای شما حل کند با من در تماس باشید. فراموش نکنید که من کارشناس ارشد هوش مصنوعی هستم و 10 سال هست که کدنویسی متلب بصورت حرفه ای انجام میدهم.
