حل مسئله کوله پشتی با الگوریتم ژنتیک GA در متلب

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

قبل از مطالعه حل مسئله کوله پشتی با الگوریتم ژنتیک GA در متلب پیشنهاد می‌کنیم با مسئله کوله پشتی آشنا شوید. برای توضیح این مسئله به زبان ساده می‌توان از یک سری مثال‌های واقعی استفاده کرد، چرا که این مسئله در زندگی روزمره هم می‌تواند کاربرد داشته باشد. اگر دانشجوی رشته کامپیوتر باشید و یا با مسائل بهینه سازی سر و کار دارید، حتماً با مسئله کوله پشتی یا Knapsak Problem آشنایی خواهید داشت.

موارد استفاده از این مسئله در زندگی روزمره بسیار است، مانند برش پارچه با الگو به طوری که کمترین هدرروی انجام شود. اما توضیح این مسئله با مدل سازی ریاضی کمی ممکن است کاربران را سردرگم سازد، بنابراین با معروف ترین مثال این مسئله را برای ما توضیح می دهیم.

فرض کنید یک دزد وجود دارد که قصد دزدی از خانه دارای وسایل گران قیمت بیشماری است. این دزد یک کیف یا کیسه به همراه دارد که تنها وزن مشخصی را می‌تواند تحمل کند. برای مثال اگر میزان تحمل این کیسه 30 کیلو باشد، امکان اینکه وسایلی با حجم بیشتر از 30 کیلو یا مجموع حجم بیشتر را نخواهد داشت.

مسئله بدین صورت است که دزد بایستی وسایلی را بدزدد که وزنشان کمتر و در عین حال ارزش یا قیمتشان بیشتر باشد. برای این کار نیازمند تفکر و انتخاب بهینه خواهد بود. مسئله دیگر اینجاست که در صورت بیشتر بودن تعداد وسایل امکان انتخاب آن‌ها با بهترین نتیجه کمی سخت خواهد بود. به همین دلیل برای حل کردن این مسئله از الگوریتم‌های فرا ابتکاری یا متاهیورستیک مانند الگوریتم ساخت اهرام جیزه استفاده می‌شود.

این مثالی از مسئله کوله پشتی می‌باشد که قابل حل با الگوریتم Genetic Algorithm می‌باشد. در ادامه درمورد سورس کد حل مسئله کوله پشتی با الگوریتم ژنتیک بیشتر صحبت شده است.

الگوریتم ژنتیک GA

الگوریتم ژنتیک (GA) یک روش بهینه سازی مبتنی بر جستجو بر اساس اصول ژنتیک و انتخاب طبیعی است. این الگوریتم برای یافتن راه‌حل‌های بهینه یا تقریباً بهینه برای مسائل سخت “NP-Hard” طراحی شده است. مسائل سخت جزو مسائلی هستند که حل آنها به‌صورت سنتی، یک عمر زمان می‌برد.

برای آموزش الگوریتم ژنتیک بهتر است با تعریف بهینه سازی شروع کنیم. بهینه سازی روند بهتر کردن چیزی است. در هر فرآیندی، مجموعه ای از ورودی‌ها و خروجی‌ها را داریم.

طبیعت همیشه منبع بزرگ الهام برای بشریت بوده است. الگوریتم ژنتیک “GA” جزو الگوریتم‌های مبتنی بر جستجو هستند که بر اساس مفاهیم انتخاب طبیعی و ژنتیک هستند. الگوریتم ژنتیک زیرمجموعه‌ای از شاخه بسیار بزرگ‌تری از محاسبات هستند که به عنوان محاسبات تکاملی “Evolutionary Computation” شناخته می‌شوند.

حل مسئله کوله پشتی با الگوریتم ژنتیک GA در متلب

این سورس کد از 10 فایل تشکیل شده است که فایل GA.m فایل اصلی برنامه است و فراخوانی دیگر توابع و مقادیر پارامترها و الگوریتم ژنتیک در داخل این فایل قرار دارد. فایل CreateModel.m فایلی است که از آن برای ایجاد وزن و ارزش کالاها از این تابع استفاده شده است؛ و در نهایت فایل MyCost.m می‌باشد که تابع هزینه را دربر گرفته است. بخشی از سورس کد تابع هزینه در زیر آورده شده است.

function [z, sol]=MyCost(pos,model)

    x=round(pos);
    v=model.v;
    w=model.w;

    V1=sum(v.*x);   % Sum of the selected values
    W1=sum(w.*x);   % Sum of selected weight

برای دریافت سورس کامل محصول لطفا آن را خریداری کنید.

تصویر خروجی حل مسئله

درباره سورس کد

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