
در این پست سورس کد مقایسه الگوریتم های حل مسئله TSP قرار داده شده است. برای حل مسئله TSP یا همان فروشنده دوره گرد Traveling Salesman Problem می توان از الگوریتم های بهینه سازی یا فراابتکاری (Metaheuristic) استفاده کرد. هدف از الگوریتم های بهینه سازی يافتن یک جواب قابل قبول، با توجه به محدوديت و نياز مسئله است. در ادامه توضیحات کامل تری ارائه می شود.
برنامه نویس: امین جلیل زاده رزین
کارشناس ارشد رشته مهندسی کامپیوتر — نرم افزار
امین جلیل زاده رزین از بنیانگذاران مجموعه آموزشی پی استور و مدرس دانشگاه فنی و حرفه ای هستند. ایشان علاوه بر پژوهش در حوزه های الگوریتم های ابتکاری، فرا ابتکاری، یادگیری ماشین، شبکه و پایگاه داده در زبان های برنامه نویسی متعدد، نظیر ++C، سی شارپ، PHP ،Java، متلب MATLAB و Python تسلط و سابقه تدریس فعال دارند.
مقایسه الگوریتم های حل مسئله فروشنده دوره گرد TSP
در سورس کدی که در متلب برای شما آماده شده است به مقایسه 12 الگوریتم بهینه سازی برای حل مسئله TSP و نتایج حاصل از آنها پرداخته شده است. این الگوریتم ها مبتنی بر جمعیت یا population based بوده که با الهام گیری از طبیعت و محیط پیرامون ما اقدام به حل مسئله می کنند. این الگوریتم ها عبارتند از:
- الگوریتم ژنتیک GA
- الگوریتم ازدحام ذرات PSO
- الگوریتم کلونی مورچگان ACO
- الگوریتم زنبور عسل مصنوعی BEE
- الگوریتم استراتژی تکاملی انطباق ماتریس کوواریانس CMA-ES
- الگوریتم تفاضل تکاملی DE
- الگوریتم کرم شب تاب FA
- الگوریتم جهش قورباغه SFLA
- الگوریتم رقابت استعماری ICA
- الگوریتم گرگ خاکستری GWO
- الگوریتم وال یا نهنگ WOA
- الگوریتم شمع و پروانه MFO
برای مقایسه عملکرد الگوریتم های فوق بر روی مسئله TSP از یک مدل سازی پیوسته برای جایگشت های شهر ها استفاده شده است. با اجرای سورس کد 2 خروجی خواهیم داشت یکی موقعیت شهرها و نحوه حرکت فروشنده دوره گرد و دیگری نمودار همگرایی.
مسئله فروشنده دورگرد TSP
مساله فروشنده دوره گرد Travelling salesman problem یا به اختصار TSP مساله ای است که شرح آن خیلی آسان می باشد. تعریف آن بدین صورت است که تعداد متناهی شهر با هزینه پیمایش بین هر جفت از آنها داده می شود و هدف مساله این است که یک فروشنده دوره گرد تمامی این شهرها را به گونه ای ملاقات کند که هر یک از این شهرها را فقط یک بارملاقات کرده و دوباره به شهر آغازین برگردد با این شرط که با کمترین هزینه پیمایش این کار را انجام دهد.
به طور کلی هدف پیدا کردن کم هزینه ترین تور برای پیمایش همه شهرها و بازگشت به شهر آغازین حرکت است. مساله فروشنده دوره گرد در شکل ساده و اختصاری با نام TSP شناخته می شود. شکل زیر یک نمونه جواب از مساله فروشنده دوره گرد که در سال 1591 برای 15 شهر از کشور آمریکا مطرح شد را نشان می دهد که با روش شاخه و حد حل شد.
قسمتی از سورس کد مقایسه الگوریتم های حل مسئله TSP
clc close all clear addpath('GA'); addpath('PSO'); addpath('ACO'); addpath('BEE'); addpath('CMA-ES'); addpath('DE'); addpath('FA'); addpath('GWO'); addpath('ICA'); addpath('SFLA'); addpath('WOA'); addpath('MFO'); model=CreateModel(); dim=model.n; lb=0; ub=1; [email protected](tour) TourLength(tour,model); SearchAgents_no=50; % Number of search agents Max_iteration=1000; % Maximum numbef of iterations Positions=initialization(SearchAgents_no,dim,ub,lb); [Best_SolGA,GA_cg_curve]=GA(SearchAgents_no,Max_iteration,lb,ub,dim,fobj,Positions); [Best_SolPSO,PSO_cg_curve]=PSO(SearchAgents_no,Max_iteration,lb,ub,dim,fobj,Positions); [Best_SolACO,ACO_cg_curve]=ACO(SearchAgents_no,Max_iteration,lb,ub,dim,fobj,Positions); [Best_SolBEE,BEE_cg_curve]=BEE(SearchAgents_no,Max_iteration,lb,ub,dim,fobj,Positions); [Best_Solcmaes,cmaes_cg_curve]=cmaes(SearchAgents_no,Max_iteration,lb,ub,dim,fobj,Positions); [Best_SolDE,DE_cg_curve]=DE(SearchAgents_no,Max_iteration,lb,ub,dim,fobj,Positions); [Best_SolFA,FA_cg_curve]=FA(SearchAgents_no,Max_iteration,lb,ub,dim,fobj,Positions); [Best_SolICA,ICA_cg_curve]=ICA(SearchAgents_no,Max_iteration,lb,ub,dim,fobj,Positions); [Best_SolSFLA,SFLA_cg_curve]=SFLA(SearchAgents_no,Max_iteration,lb,ub,dim,fobj,Positions); [Best_scoreGWO,Best_posGWO,GWO_cg_curve]=GWO(SearchAgents_no,Max_iteration,lb,ub,dim,fobj,Positions); [Best_scoreWOA,Best_posWOA,WOA_cg_curve]=WOA(SearchAgents_no,Max_iteration,lb,ub,dim,fobj,Positions); [Best_scoreMFO,Best_posMFO,MFO_cg_curve]=MFO(SearchAgents_no,Max_iteration,lb,ub,dim,fobj,Positions); figure(1); %Draw objective space semilogy(GA_cg_curve,'Color','[0 0 0]','LineWidth',2) hold on; semilogy(PSO_cg_curve,'Color','[0 0 1]','LineWidth',2) semilogy(ACO_cg_curve,'Color','[0 1 0]','LineWidth',2) semilogy(BEE_cg_curve,'Color','[0 1 1]','LineWidth',2) semilogy(cmaes_cg_curve,'Color','[1 0 0]','LineWidth',2) semilogy(DE_cg_curve,'Color','[1 0 1]','LineWidth',2) semilogy(FA_cg_curve,'Color','[1 1 0]','LineWidth',2) semilogy(ICA_cg_curve,'--','Color','[0 0 1]','LineWidth',2) semilogy(SFLA_cg_curve,'--','Color','[0 1 0]','LineWidth',2) semilogy(GWO_cg_curve,'--','Color','[0 1 1]','LineWidth',2) semilogy(WOA_cg_curve,'--','Color','[1 0 0]','LineWidth',2) semilogy(MFO_cg_curve,'--','Color','[1 0 1]','LineWidth',2) xlabel('Iteration'); ylabel('Best score obtained so far'); grid on legend('GA','PSO','ACO','BEE','CMA-ES','DE','FA','ICA','SFLA','GWO','WOA','MFO','Location','bestoutside') test;
تصاویر خروجی پروژه
ویدئوی معرفی پروژه
توجه: این ویدئو نسخه کامل و 13 دقیقه ای از نحوه اجرای پروژه به همراه برخی توضیحات تکمیلی می باشد.
درباره سورس کد مقایسه الگوریتم های حل مسئله TSP
سورس کد مقایسه الگوریتم های حل مسئله TSP برای حل مسئله فروشنده دوره گرد TSP با الگوریتم های بهینه سازی یا فرا ابتکاری در متلب عنوان محصولی است که در این پست به آن پرداخته شده است. محصول در نرم افزار متلب 2017 نوشته شده و بصورت کامل توسط گروه پشتیبانی پی استور تست و اجرا شده است. محصول دارای نشان تضمین کیفیت پی استور می باشد. برای دانلود محصول آن را خریداری کنید.
مباحث مرتبط با این موضوع
تاریخ انتشار: | 7 اسفند 1398 |
---|---|
تاریخ بروزرسانی: | 15 خرداد 1399 |
حجم فایل: | 25 کیلوبایت |
فرمت فایل | m. در قالب متلب |
نسخه: | 1.0 |
لایسنس: | ندارد |
هماهنگی با: | Matlab 2009 و بالاتر |
تاکنون 156 نفر این محصول را تهیه کرده اند و 3 نظر برای آن ثبت شده است.
نظرات و دیدگاه ها
قوانین ثبت دیدگاه
- لطفاً دیدگاه های خود را فارسی تایپ کنید.
- دیدگاه های نامرتبط به مطلب تایید نخواهد شد.
- از درج دیدگاه های تکراری پرهیز نمایید.
- سوالات تخصصی خودتان را از طریق تیکت پشتیبانی مطرح کنید.
قیمت 79,000 تومان
این فایل به زبان Matlab و بصورت zip شده قابل دانلود است. بلافاصله پس از خرید، لینک دانلود محصول در اختیار شما قرار خواهد گرفت.
با خرید این محصول از مزایای زیر بهرهمند میشوید:
- دسترسی به فایل محصول به صورت مادامالعمر
- ۶ ماه پشتیبانی کاملا رایگان و تضمین شده
تاریخ انتشار: | 7 اسفند 1398 |
---|---|
تاریخ بروزرسانی: | 15 خرداد 1399 |
حجم فایل: | 25 کیلوبایت |
فرمت فایل | m. در قالب متلب |
نسخه: | 1.0 |
لایسنس: | ندارد |
هماهنگی با: | Matlab 2009 و بالاتر |
قیمت: 79,000 تومان
امین جلیل زاده
نظرات و پیشنهادات خود را با ما در میان بگذارید.
عباس شعبانی
عرض سلام وادب-می خواستم بدونم این سورس کد در پایتون قابل اجرا هست؟میشه سورس الگوریتم های دیگه ای همچون TA ویا عملگرهای 2-OPT و3-OPTرو هم به این اضافه نمود؟
امین جلیل زاده رزین
سلام و عرض ادب
این کد فقط در متلب قابل اجرا هست و بله میشه هر الگوریتم دیگه ای رو بهش اضافه کرد
نجار
با سلام
ببخشید من در ارن کردن کدها در متلب مشکل دارم و وقتی ران را میزنم ارور میدهد. ممنون میشم راهنمایی بفرمایید
امین جلیل زاده رزین
سلام از طریق تیکت پشتیبانی در حساب کاربری تان مشکل رو مطرح کنید و تصویر خطا رو پیوست کنید تا رسیدگی بشه.