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

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

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

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

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

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

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

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

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

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

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

مسئله فروشنده دوره گرد یا TSP قابل حل با الگوریتم‌های فرا ابتکاری می‌باشد که یکی از آن‌ها الگوریتم جستجوی فراکتال تصادفی می‌باشد. این سورس کد دارای ۷ فایل اصلی می‌باشد که مهم‌ترین فایل 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 برنامه نویسی و اجرا شده است و قابل اجرا با نسخه‌های بالاتر متلب نیز هست. این سورس کد توسط تیم پشتیبانی پی استور تست و اجرا شده است. کیفیت اثر توسط پی استور تضمین می‌شود و دارای نشان تضمین کیفیت پی استور است. برای دانلود اثر مذکور آن را خریداری فرمایید به محض خرید لینک دانلود در دسترس خواهد بود.