مقایسه الگوریتم های حل مسئله TSP

در این پست سورس کد مقایسه الگوریتم های حل مسئله TSP قرار داده شده است. برای حل مسئله TSP یا همان فروشنده دوره گرد Traveling Salesman Problem می‌توان از الگوریتم های بهینه سازی یا فراابتکاری (Metaheuristic) استفاده کرد. هدف از الگوریتم‌های بهینه سازی یافتن یک جواب قابل قبول، با توجه به محدودیت‌ و نیاز مسئله است. در ادامه توضیحات کامل‌تری ارائه می‌شود.

مقایسه الگوریتم های حل مسئله فروشنده دوره گرد TSP

در سورس کدی که در متلب برای شما آماده شده است به مقایسه ۱۲ الگوریتم بهینه سازی برای حل مسئله TSP و نتایج حاصل از آن‌ها پرداخته شده است. این الگوریتم‌ها مبتنی بر جمعیت یا population based بوده که با الهام گیری از طبیعت و محیط پیرامون ما اقدام به حل مسئله می‌کنند. این الگوریتم‌ها عبارتند از:

• الگوریتم ژنتیک GA
• الگوریتم ازدحام ذرات PSO
• الگوریتم کلونی مورچگان ACO
• الگوریتم زنبور عسل مصنوعی BEE
• الگوریتم استراتژی تکاملی انطباق ماتریس کوواریانس CMA-ES
• الگوریتم تفاضل تکاملی DE
• الگوریتم کرم شب تاب FA
• الگوریتم جهش قورباغه SFLA
• الگوریتم رقابت استعماری ICA
• الگوریتم گرگ خاکستری GWO
• الگوریتم وال یا نهنگ WOA
• الگوریتم شمع و پروانه MFO

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

مسئله فروشنده دورگرد TSP

مساله فروشنده دوره گرد Travelling salesman problem یا به اختصار TSP مساله‌ای است که شرح آن خیلی آسان می‌باشد. تعریف آن بدین صورت است که تعداد متناهی شهر با هزینه پیمایش بین هر جفت از آن‌ها داده می‌شود و هدف مساله این است که یک فروشنده دوره گرد تمامی این شهرها را به گونه‌ای ملاقات کند که هر یک از این شهرها را فقط یک بارملاقات کرده و دوباره به شهر آغازین برگردد با این شرط که با کم‌ترین هزینه پیمایش این کار را انجام دهد.

به طور کلی هدف پیدا کردن کم هزینه‌ترین تور برای پیمایش همه شهرها و بازگشت به شهر آغازین حرکت است. مساله فروشنده دوره گرد در شکل ساده و اختصاری با نام TSP شناخته می‌شود. شکل زیر یک نمونه جواب از مساله فروشنده دوره گرد که در سال ۱۵۹۱ برای ۱۵ شهر از کشور آمریکا مطرح شد را نشان می‌دهد که با روش شاخه و حد حل شد.

قسمتی از سورس کد مقایسه الگوریتم های حل مسئله 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;
fobj=@(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;

تصاویر خروجی پروژه

درباره سورس کد مقایسه الگوریتم های حل مسئله TSP

سورس کد مقایسه الگوریتم های حل مسئله TSP برای حل مسئله فروشنده دوره گرد TSP با الگوریتم های بهینه سازی یا فرا ابتکاری در متلب عنوان اثری است که در این پست به آن پرداخته شده است. این سورس کد در نرم افزار متلب ۲۰۱۷ نوشته شده و بصورت کامل توسط گروه پشتیبانی پی استور تست و اجرا شده است. اثر مذکور دارای نشان تضمین کیفیت پی استور می باشد. برای دانلود اثر آن را خریداری کنید.