حل مسئله کوله پشتی با الگوریتم جستجوی ممنوعه TS در متلب

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

الگوریتم جستجوی ممنوعه – Tabu search

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

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

برای جلوگیری از چرخه، TSبا استفاده از حافظه ای که فهرست tabu (ممنوعه) نامیده می شود، راه حل قبلی را که قبلاً بازدید شده است، دور می اندازد. طول حافظه لیست tabu روند جستجو را کنترل می کند. طول بالای لیست تابو زیاد است، جستجو در مناطق بزرگتر کاوش می کند و مانع بازدید مجدد تعداد زیادی از راه حل ها می شود. طول کم لیست tabuجستجو را در قسمت کوچکی از فضای جستجو متمرکز می کند.

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

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

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

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

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

این مثالی از مسئله کوله پشتی می باشد که قابل حل با الگوریتم Tabu search می باشد. در ادامه درمورد سورس کد حل مسئله کوله پشتی با الگوریتم جستجوی ممنوعه بیشتر صحبت شده است.

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

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

function [z, sol]=MyCost(x,model)
    v=model.v;
    w=model.w;
    W=model.W;
    V1=sum(v.*x);   % Sum of the selected values
    W1=sum(w.*x);   % Sum of selected weight
    V0=sum(v.*(1-x)); % Sum of the unselected values
    W0=sum(w.*(1-x)); % Sum Of unselected weight
    Violation=max((W1/W)-1,0); % Violation from total weight Knapsack

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

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

ویدئوی معرفی

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

سورس کد حل مسئله کوله پشتی با الگوریتم TS در متلب در محیط Matlab 2017 برنامه نویسی و اجرا شده است و قابل اجرا با نسخه های بالاتر متلب نیز هست. این سورس کد توسط تیم پشتیبانی پی استور تست و اجرا شده است. کیفیت محصول توسط پی استور تضمین می شود و محصول دارای نشان تضمین کیفیت پی استور است. برای دانلود محصول آن را خریداری فرمایید به محض خرید لینک دانلود در دسترس خواهد بود.

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