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

الگوریتم جستجوی فراکتال تصادفی

الگوریتم جستجوی فراکتال تصادفی Stochastic Fractal Search که به اختصار SFS نیز نامیده می شود یکی از الگوریتم های فرا ابتکاری مهم است که با الهام از پدیده طبیعی رشد (growth) به وجود آمده است. این الگوریتم فراابتکاری جدید ارائه شده است که از مفهومی ریاضی به نام فراکتال استفاده می کند. با استفاده از ویژگی انتشار (Diffusion) که به طور منظم در فراکتال‌های تصادفی دیده می‌شود، ذرات در الگوریتم ارائه شده، فضای جستجو را کارآمدتر جستجو می‌کنند.

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

فرکتال‌های تصادفی را می‌توان با اصلاح فرآیند تکرار از طریق قوانین تصادفی مانند خوشه‌های نفوذی (percolation clusters)، پیاده‌روی‌های خود اجتنابی (self-avoiding walks)، مناظر فراکتال (fractal landscapes)، مسیر حرکت براونی (trajectories of Brownian motion) و درخت براونی (Brownian tree) تولید کرد (دندریتی که با مدل‌سازی فراکتال‌های دندریتی تولید می‌شود).

درنهایت از رشد فراکتال (روش DLA) و نظریه پتانسیل برای طراحی الگوریتم فراکتال استفاده شده است. اگرچه جستجوی فراکتال در یافتن راه حل خوب عمل می کند، اما این رویکرد از معایبی رنج می برد. یکی از اصلی ترین آنها داشتن پارامترهای زیادی است که باید به خوبی به آنها پرداخته شود، و دیگری این که تبادل اطلاعات بین ذرات رخ نمی دهد.

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

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

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

در عین حال فروشنده دوره گرد باید یک بار از هر شهر عبور کند و همزمان با کمترین هزینه، کمترین مسافت را نیز طی کند.

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

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

یکی دیگر از مهم ترین فایل های موجود در این سورس کد فایل Stochastic_Fractal_Search.m است که سورس کد اصلی الگوریتم جستجوی فراکتال تصادفی در این فایل قرار می گیرد و توسط فایل اصلی فراخوانی می شود. فایل TourLength.m توابع مسئله فروشنده دوره گرد در این فایل قرار گرفته است. دو فایل مهم دیگر CreateModel.m و PlotSolution.m می باشد.

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

% Initializing Problem******************************************************
 S.Function_Name = @(tour,model) TourLength(tour,model);
 S.Ndim = S.model.n;
 lb = 0;
 ub = 1;
 S.Lband = ones(1, S.Ndim)*(lb);
 S.Uband = ones(1, S.Ndim)*(ub);
[pbest, fbest, F] = Stochastic_Fractal_Search(S);

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

تصاویر خروجی حل مسئله

ویدئوی معرفی

درباره سورس کد

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