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

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

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

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

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

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

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

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

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

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

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

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

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

این سورس کد از ۹ فایل تشکیل شده است که فایل 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 در متلب

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

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