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