حل مسئله فروشنده دوره گرد TSP با الگوریتم گرگ خاکستری GWO در متلب

الگوریتم گرگ خاکستری

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

در هر گله از گرگ‌ها برای شکار کردن ۴ درجه وجود دارد که مانند شکل زیر به صورت یک ساختار هرمی مدل می‌شود.

• گرگ‌های رهبر گروه alpha نامیده می‌شوند که می‌توانند مذکر یا مونث باشند. این گرگ‌ها بر گله تسلط دارند.
• گرگ‌های beta: کمک به گرگ‌های alpha در فرایند تصمیم گیری بوده و همچنین مستعد انتخاب شدن به جای آن‌ها هستند.
• گرگ‌های delta: پایین‌تر از گرگ‌های beta و شامل گرگ‌های پیر، شکارچی‌ها و گرگ‌های مراقبت کننده از نوزادان.
• گرگ‌های omega: پایین‌ترین مرتبه در هرم سلسله مراتب که کم‌ترین حق را نسبت به بقیه اعضای گروه دارند. بعد از همه غذا می‌خورند و در فرآیند تصمیم گیری مشارکتی ندارند.

ترتیب الگوریتم

• برازندگی کلیه جواب‌ها محاسبه شده و سه جواب برتر به عنوان alpha, beta, deltaتا پایان الگوریتم انتخاب می‌شوند.
• در هر تکرار سه جواب برتر (گرگ‌های alpha, beta, delta) قابلیت تخمین موقعیت شکار را داشته و این کار را در هر iteration با استفاده از رابطه زیر انجام می‌دهند:
• در هر تکرار بعد از تعیین موقعیت گرگ‌های alpha, beta, delta، آپدیت موقعیت بقیه جواب‌ها با تبعیت از آن‌ها انجام می‌شود.
• در هر تکرار بردار a (و به تبع آن A) و C آپدیت می‌شوند.
• در پایان تکرارها موقعیت گرگ alpha به عنوان نقطه بهینه معرفی می‌شود.

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

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

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

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

در این قسمت سورس برنامه حل مسئله فروشنده دوره گرد TSP با الگوریتم گرگ خاکستری GWO در متلب آماده شده است این سورس کد شامل ۵ فایل می‎باشد که عبارتند از:

• TSPGWO.m: فایل اصلی برنامه است و فراخوانی دیگر توابع و مقادیر پارامترها و الگوریتم GWO در داخل این فایل قرار دارد.
• CreateModel.m: برای ایجاد شهرهای فاصله و مختصات هر یک از شهرها از این تابع استفاده می‌شود.

function model=CreateModel()

    x=[82 91 12 92 63 9 28 55 96 97 15 98 96 49 12 92 63 9 28 55 96 97 15 98 80 14 42 92 80 96];
    
    y=[12 92 63 9 28 55 96 97 15 98 66 3 85 94 68 76 75 39 66 17 71 3 27 4 9 83 70 32 95 3];
    
    n=numel(x);
    
    D=zeros(n,n);
    
    for i=1:n-1
        for j=i+1:n
            
            D(i,j)=sqrt((x(i)-x(j))^2+(y(i)-y(j))^2);
            
            D(j,i)=D(i,j);
            
        end
    end
    
    model.n=n;
    model.x=x;
    model.y=y;
    model.D=D;

end

• PlotSolution.m: برای رسم مسیر های بین شهرها از این تابع استفاده می شود.

function PlotSolution(tour,model)

    tour=[tour tour(1)];
    
    plot(model.x(tour),model.y(tour),'k-s',...
        'MarkerSize',12,...
        'MarkerFaceColor','y',...
        'LineWidth',2);

end

• TourLength.m: این تابع برای محاسبه طول مسیرهای یک تور یا یک پیمایش کامل شهرها بکار می‌رود.

function [z sol]=MyCost(s,model) 
 
    d=model.d; 
 
    [~, tour]=sort(s); 
    sol.tour=tour; 
     
    n=numel(tour); 
     
    tour=[tour tour(1)]; 
     
    L=0; 
    for i=1:n 
        L=L+d(tour(i),tour(i+1)); 
    end 
     
    sol.L=L; 
     
    z=L; 
 
end

• initialization.m: این تابع برای محاسبه مقدار اولیه جواب‌های ممکن برای الگوریتم بکار می‌رود.

function Positions=initialization(SearchAgents_no,dim,ub,lb)

Boundary_no= size(ub,2); % numnber of boundaries

% If the boundaries of all variables are equal and user enter a signle
% number for both ub and lb
if Boundary_no==1
    Positions=rand(SearchAgents_no,dim).*(ub-lb)+lb;
end

% If each variable has a different lb and ub
if Boundary_no>1
    for i=1:dim
        ub_i=ub(i);
        lb_i=lb(i);
        Positions(:,i)=rand(SearchAgents_no,1).*(ub_i-lb_i)+lb_i;
    end
end

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

تصاویر خروجی فروشنده دوره گرد TSP با الگوریتم گرگ خاکستری

درباره فروشنده دوره گرد TSP با الگوریتم گرگ خاکستری

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