ایمیل خود را وارد و بر روی بچرخون کلیک کنید. (کد تخفیف دریافتی را هنگام ثبت سفارش وارد کنید)
قوانین بازی:
برنامهنویس:
هزینه سفارش:
۱۹۹,۰۰۰ تومان قیمت اصلی: ۱۹۹,۰۰۰ تومان بود.۷۹,۶۰۰ تومانقیمت فعلی: ۷۹,۶۰۰ تومان.
تخصصی و منحصر به فرد بودن این اثر، تضمین کننده بهای محصول نسبت به آثار مشابه است.
در این پست پیاده سازی الگوریتم جستجوی ممنوعه TS برای حل مسئله فروشنده دوره گرد TSP در متلب قرار داده شده است. واژهٔ ممنوعه یا تابو از تُنگان زبان مردم جزایر پلینزی در اقیانوس آرام گرفته شدهاست. این واژه به معنای شیء مقدسی است که به دلیل قداست نباید آن را لمس کرد. بر اساس واژهنامهٔ وِبستر، امروزه این واژه در معنای «ممنوعیت ایجاد شده به دلیل فرهنگ اجتماعی برای ایجاد اقدام حفاظتی» یا «ممنوعیت چیزی که دارای ریسک است»، به کار میرود.
معنای اخیر واژهٔ تابو، با تکنیک جستجوی ممنوعه کاملاً سازگار است. ریسکی که در الگوریتم جستجوی ممنوعه از آن اجتناب میشود، خطر مسیرهای نامناسب است. در ادامه به توضیح این الگوریتم و سورس کد آن پرداخته می شود.
الگوریتم جستجوی ممنوعه (Tabu Search) (TS) یک استراتژی جستجوی حافظه ای می باشد که برای اولین بار توسط گلوور در سال ۱۹۸۶ مطرح شده است. این الگوریتم تقریبا مانند الگوریتم های جستجوی محلی کار می کند، با این تفاوت که برای جلوگیری از دور و تسلسل در جواب ها و افتادن در دام جوا ب های بهینه محلی، از مفهومی به نام فهرست ممنوع استفاده می کند.
جابه جایی از جواب جاری به جواب همسایه امکان پذیر زمانی انجام می شود که در فهرست تابو قرار نداشته باشد. در غیر اینصورت، جواب همسایه دیگری که در ارزیابی جواب های همسایه در رده بعدی قرار گرفته است، انتخاب شده و جابه جایی به آن صورت می گیرد. هرگاه ساختار همسایگی متقارن باشد، خطر افتادن در دور وجود دارد. نمودار جریان الگوریتم جستجوی ممنوعه بصورت زیر است.
حافظه الگوریتم میتواند از دو نوع recency و یا frequency باشد
حافظه کوتاه مدت در روش جستجوی ممنوع نوعی از جستجوی فعال را جهت یافتن بهترین جواب ها تشکیل می دهد و می توان اینگونه بیان نمود که هسته اصلی جستجوی ممنوع، در فرایند کوتاه مدت مجسم می شود. این حافظه لیستی با ابعاد N رکورد می باشد که N تا از آخرین حرکاتی را که الگوریتم با آن مواجه بوده است را به عنوان tabu نگهداری میکند.
حافظه frequency که به عنوان حافظه بلندمدت شناخته می شود با اضافه نمودن اطلاعات تکمیلی دیگری از قبیل اینکه چند بار یک حرکت و یا جواب ممنوع جستجو شده است، مکمل حافظه recency می باشد. در حالت کلی جستجوی ممنوع با در نظر گرفتن حافظه بلند مدت و استراتژی های مرتبط با آن قوی تر میشود.
این لیست که دارای ابعادی ثابت یا متغیر می باشد، جابه جایی های منع شده را نگهداری می کند و کاربرد اصلی آن، پرهیز از همگرا شدن به جواب های بهینه محلی است. به عبارت دیگر، به کمک فهرست tabu جابه جایی به جوا بهایی که اخیراً جستجو شده اند، ممنوع خواهد شد و فقط بخش هایی از مجموعه جواب که پیش از این مورد بررسی قرار نگرفته، مد نظر خواهند بود. نحوه ورود و خروج جواب ها به فهرست ممنوع به صورت FIFO است.
مساله فروشنده دوره گرد Travelling salesman problem یا به اختصار TSP مساله ای است که شرح آن خیلی آسان می باشد. تعریف آن بدین صورت است که تعداد متناهی شهر با هزینه پیمایش بین هر جفت از آنها داده می شود و هدف مساله این است که یک فروشنده دوره گرد تمامی این شهرها را به گونه ای ملاقات کند که هر یک از این شهرها را فقط یک بارملاقات کرده و دوباره به شهر آغازین برگردد با این شرط که با کمترین هزینه پیمایش این کار را انجام دهد.
به طور کلی هدف پیدا کردن کم هزینه ترین تور برای ملاقات همه شهرها و بازگشت به شهر آغازین حرکت است. مساله فروشنده دوره گرد در شکل ساده و اختصاری با نام TSP شناخته می شود. شکل زیر یک نمونه جواب از مساله فروشنده دوره گرد که در سال ۱۵۹۱ برای ۱۵ شهر از کشور آمریکا مطرح شد را نشان می دهد که با روش شاخه وحد حل شد.
در این بخش قسمتی از سورس برنامه حل مسئله فروشنده دوره گرد TSP با الگوریتم TS در متلب آماده شده است این سورس کد شامل ۱۰ فایل می باشد که عبارتند از:
قسمتی از کد TabuSearch به صورت زیر است:
model = CreateModel(); CostFunction=@(tour) TourLength(tour, model); ActionList=CreatePermActionList(model.n); nAction=numel(ActionList); %% Parameters MaxIt=100; TL=round(0.5*nAction); %% Initialization empty_individual.Position=[]; empty_individual.Cost=[]; % Create Initial Solution sol=empty_individual; sol.Position=randperm(model.n); sol.Cost=CostFunction(sol.Position); % Initialize Best Solution Ever Found BestSol=sol; % Array to Hold Best Costs BestCost=zeros(MaxIt,1); % Initialize Action Tabu Counters TC=zeros(nAction,1); %% Main Loop for it=1:MaxIt bestnewsol.Cost=inf; % Apply Actions for i=1:nAction if TC(i)==0 newsol.Position=Action(sol.Position,ActionList{i}); newsol.Cost=CostFunction(newsol.Position); newsol.ActionIndex=i; if newsol.Cost<=bestnewsol.Cost bestnewsol=newsol; end end end % Update Current Solution sol=bestnewsol; % Update Tabu List for i=1:nAction if i==bestnewsol.ActionIndex TC(i)=TL; % Add To Tabu List else TC(i)=max(TC(i)-1,0); % Reduce Tabu Counter end end % Update Best Solution Ever Found if sol.Cost<=BestSol.Cost BestSol=sol; end % Save Best Cost Ever Found BestCost(it)=BestSol.Cost; % Show Iteration Information disp(['Iteration ' num2str(it) ': Best Cost = ' num2str(BestCost(it))]); % Plot Best Solution figure(1); PlotSolution(BestSol, model); pause(0.01); % If Global Minimum is Reached if BestCost(it)==0 break; end end BestCost=BestCost(1:it);
برای دانلود مجموعه کامل و قابل اجرا در متلب الگوریتم جستجو ممنوع محصول را خریداری نمایید.
سورس برنامه حل مسئله فروشنده دوره گرد TSP با الگوریتم جستجوی ممنوعه TS در متلب عنوان محصولی است که در این پست به آن پرداخته شده است. محصول در نرم افزار متلب نوشته شده و بصورت کامل توسط گروه پشتیبانی پی استور تست و اجرا شده است. محصول دارای نشان تضمین کیفیت پی استور می باشد. برای دانلود محصول آن را خریداری کنید. به محض خرید لینک دانلود در دسترس خواهد بود.
نام اثر: | الگوریتم جستجوی ممنوعه TS برای حل مسئله فروشنده دوره گرد TSP در متلب |
نوع اثر: | پاورپوینت |
تهیهکننده: | تیم برنامهنویسی پیاستور |
تیم برنامه نویسی پی استور یکی از اولین گروههای تشکیل شده در مجموعه آموزشی پی استور میباشد. این تیم از اساتید مجرب و فارغ التحصیلان رشتههای فنی و مهندسی تشکیل شده که در زمینههای مختلف برنامهنویسی و تهیه سورس کد فعال هستند.
هزینه سفارش:
۱۹۹,۰۰۰ تومان قیمت اصلی: ۱۹۹,۰۰۰ تومان بود.۷۹,۶۰۰ تومانقیمت فعلی: ۷۹,۶۰۰ تومان.
نظرات
علیرضا سلطانی
ممنون از این کد متلب که آماده کردید. واقعاً بهترین جوابی که تا حالا گرفتم برای حل مسئله فروشنده دوره گرد یا همون TSP با الگوریتم جستجوی ممنوعه بوده اکثراً در تکرار کمتر از ۵۰ جواب مسئله رو پیدا می کنه. من با الگوریتم های زیادی مسئله TSP رو آزمایش کردم (ژنتیک، PSO، الگوریتم مورچگان، زنبور، گرگ خاکستری، وال، پروانه، شمع و پروانه، فاخته، قورباغه، ملخ و …) ولی بهترین جواب برای حل مسئله TSP همین الگوریتم TS هست. فقط از ادمین محترم خواهشمندم فیلم آموزش کد نویسی رو هم در کنار کد متلب قرار بدن چون من خیلی زحمت کشیدم تا از کد سر در بیارم.
از دوستان عزیر که در مورد حل مسئله با الگوریتم های فرا اکتشافی کار می کنن خواهش دارم اگه نتایجی بهتر برای حل مسئله TSP دارن بفرمایند تا استفاده کنیم. ممنون از مدیریت محترم.
مدیریت و پشتیبانی
ممنون از اینکه نتایج خودتون رو مورد نقد و بررسی قرار دادید. ایشالا نظرات شما رو به برنامه نویسان و مدرسان مجموعه انعکاس می دیم.