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

در این بخش حل مسئله کوله پشتی با الگوریتم ژنتیک GA در متلب قرار داده شده است. مسئله کوله پشتی و حل آن یکی از مواردی است که می توان در آن از الگوریتم های فرا ابتکاری یا متاهیورستیک استفاده نمود. حل مسئله کوله پشتی برای بهینه سازی مسائل مختلف NP-Hard مورد استفاده قرار می گیرد. برای استفاده از سورس کد در سایر مسائل بهینه سازی می توان مدل و تابع هزینه آن را منطبق بر مسئله کرد و از آن سود برد.

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

برای توضیح این مسئله به زبان ساده می توان از یک سری مثال های واقعی استفاده کرد، چرا که این مسئله در زندگی روزمره هم می تواند کاربرد داشته باشد. اگر دانشجوی رشته کامپیوتر باشید و یا با مسائل بهینه سازی سر و کار دارید، حتماً با مسئله کوله پشتی یا 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 در متلب عنوان محصولی است که در این پست به آن پرداخته شده است. محصول در نرم افزار متلب نوشته شده و بصورت کامل توسط گروه پشتیبانی پی استور تست و اجرا شده است. محصول دارای نشان تضمین کیفیت پی استور می باشد. برای دانلود محصول آن را خریداری کنید.

مباحث مرتبط با الگوریتم ژنتیک

سورس کدهای آماده حل مسئله کوله پشتی