الگوریتم جستجوی فراکتال تصادفی — Stochastic Fractal Search

الگوریتم جستجوی فرکتال در سال ۲۰۱۴ توسط آقای Hamid Salimi در ژورنال معتبر Knowledge-Based Systems از انتشارات الزویر Elsevier معرفی شد. عنوان مقاله ارائه شده Stochastic Fractal Search: A powerful metaheuristic algorithm می‌باشد که در این لینک (+) قابل مشاهده است. در این مقاله با الهام از پدیده طبیعی رشد (growth)، الگوریتم فراابتکاری جدیدی ارائه شده است که از مفهومی ریاضی به نام فراکتال استفاده می‌کند. با استفاده از ویژگی انتشار (Diffusion) که به‌طور منظم در فراکتال‌های تصادفی دیده می‌شود، ذرات در الگوریتم ارائه شده، فضای جستجو را کارآمدتر جستجو  می‌کنند.

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

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

در دنیای واقعی برای به حداقل رساندن زمان، هزینه یا ریسک و به حداکثر رساندن سود، کیفیت یا کارایی به بهینه سازی نیاز داریم. بسیاری از مسائل بهینه‌سازی واقعی پیچیده در بسیاری از زمینه‌های علمی مانند مهندسی، اقتصاد و تجارت پدیدار شده‌اند که نمی‌توانند در مدت زمان معقولی حل شوند و در عین حال پاسخ دقیقی برای حل آن‌ها وجود ندارد. در واقع، چنین مسائلی اغلب غیرخطی هستند. علاوه بر این، برخی از این مسائل شامل بسیاری از متغیرهای مختلف هستند و تحت محدودیت‌های پیچیده عمل می‌کنند.

این محدودیت‌ها یا به صورت مرزهای ساده مانند محدوده خواص مواد هستند یا به صورت روابط غیر خطی مانند حداکثر تنش (maximum stress)، حداکثر انحراف (maximum deflection)، حداقل ظرفیت بار (minimum load capacity) یا پیکربندی هندسی (geometrical configuration) هستند.

از سوی دیگر، از آن‌جایی که اندازه فضای جستجو (search space) در حین حل مسائل بهینه سازی با ابعاد بالا به طور چشمگیری افزایش می‌یابد بنابراین الگوریتم های بهینه سازی کلاسیک راه حل مناسبی برای حل اینگونه مسائل ارائه نمی‌دهند. در واقع، جایگزین اصلی برای حل این نوع مسائل، استفاده از الگوریتم های تقریبی (approximate algorithms) است.

در طول دهه‌های ۵۰ و ۶۰ میلادی، مفهوم تکامل (Evolution) توسط محققان علوم کامپیوتر به عنوان ابزاری بهینه‌سازی برای حل مسائل مهندسی مورد بررسی قرار گرفت و پس از آن روشی فنی به نام الگوریتم‌های تقریبی را پایه‌گذاری کردند. الگوریتم‌های تقریبی را می‌توان به دو دسته ابتکاری (heuristic) و فراابتکاری (metaheuristic) تقسیم بندی کرد. اصطلاح «heuristic» در اصل از زبان یونانی گرفته شده است و به معنای «کشف» و «راهنمایی تحقیق» است.

هیوریستیک‌ها روش‌ها و تکنیک‌هایی هستند که به دنبال راه حل‌های خوب (نزدیک به بهینه) با هزینه محاسباتی معقول هستند، بدون اینکه قادر به تضمین امکان سنجی یا بهینه بودن باشند، یا حتی در بسیاری از موارد بیان کنند که یک راه حل عملی خاص چقدر به بهینه نزدیک است.

الگوریتم های ابتکاری برای مسائل خاص طراحی شده‌اند، در حالی که الگوریتم های فراابتکاری‌ها برای طیف وسیعی از مسائل بهینه سازی قابل استفاده است و برای حل هر مسئله بهینه سازی می‌توان از آن‌ها استفاده کرد. این نوع از الگوریتم‌ها اغلب برای حل مسائل سخت NP-Hard به کار می‌رود.

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

1. حل سریع‌تر مسائل
2. حل مسائل بزرگ
3. به دست آوردن الگوریتم‌های قوی

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

• تنوع یا اکتشاف (Exploration)
• تشدید یا بهره برداری (Exploitation)

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

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

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

“هر ذره در جهان هر ذره دیگر را جذب می‌کند”، این قانون گرانش نیوتنی است که الگوریتم جستجوی گرانشی (GSA) بر اساس آن استوار است. الگوریتم جستجوی فاخته (CS) یکی دیگر از روش‌های فراابتکاری موفق است که استراتژی بازتولید رفتار فاخته را تقلید می‌کند. این الگوریتم‌ها برای حل مسائل پیچیده بهینه سازی محاسباتی استفاده می‌شوند، با این حال، همگرایی سریع همراه با دقت تضمین نمی‌شود.

• آموزش الگوریتم PSO در پایتون — کلیک کنید

الگوریتم جستجوی فراکتال تصادفی (SFS) نیز یک الگوریتم بهینه سازی است. این الگوریتم فراابتکاری مبتنی بر خواص فراکتال است که با یک بینش متفاوت در حل مسائل بهینه‌سازی بر اساس خاصیت انتشار است که در در دنیای واقعی در فراکتال‌ها مشاهده می‌شود. در ادامه خلاصه‌ای از فراکتال‌ها و ویژگی‌های فراکتال را ارائه خواهد شد. جستجوی فراکتال و جستجوی فراکتال تصادفی نیز به طور کامل در بخش‌های بعدی تشریح خواهد شد.

فراکتال چیست؟

خاصیت یک شیء یا کمیتی که تشابه خود را در تمام مقیاس‌ها، به معنایی فنی، توضیح می‌دهد، فراکتال نامیده می‌شود. اصطلاح “فراکتال” از کلمه لاتین fractus به معنای “شکسته” گرفته شده است و اولین بار توسط Benoit Mandelbrot در سال ۱۹۷۵ استفاده شد. نظریه‌های فراکتال برای توصیف الگوهای هندسی در طبیعت است. در شکل زیر نمونه‌ای از فراکتال را مشاهده می‌کنید.

نمونه‌ای از فراکتال‌ها شامل ساختارهایی از دانه‌های میکروسکوپی تا خوشه کهکشان‌ها وجود دارد. برخی از مثال‌ها برای چنین فرآیندهایی عبارتند از انجماد دندریتی (dendritic solidification) در محیطی که سرد نشده، انگشت‌گذاری چسبناکی (viscous fingering) که هنگامی که یک سیال چسبناک به مایع چسبناک‌تر تزریق می‌شود یا رسوب الکتریکی یون‌ها روی الکترود (electrodepositing of ions).

به طور معمول، برای تولید یک شکل فراکتال، از برخی روش‌های رایج مانند: سیستم‌های تابع تکراری (Iterated function systems)، جاذبه‌های عجیب (Strange attractors)، سیستم‌های Lsystems، قوانین تقسیم‌بندی محدود (Finite subdivision rules) و فرکتال‌های تصادفی (Random fractals) استفاده می‌شود. بر اساس ویژگی‌های فراکتال، الگوریتم فرااکتالی الهام‌بخش فرکتال‌های تصادفی است که با مفهوم روش تجمع محدود انتشار (DLA – Diffusion Limited Aggregation ) به عنوان یک الگوریتم جستجوی عمل می‌کند.

• پاورپوینت های آماده ویژه ارائه کلاسی با موضوع الگوریتم بهینه سازی — کلیک کنید

فراکتال های تصادفی

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

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

خرابی دی الکتریک Dielectric breakdown

انشعاب‌های تخلیه باریک که اغلب در طبیعت دیده می‌شوند، شکست دی الکتریک نامیده می‌شوند. مطالعه بر روی خواص شکست دی الکتریک نشان می‌دهد که تمایل به انشعاب را می‌توان به الگوهای تصادفی پیچیده مدل کرد. به عنوان مثال می‌توان به رعد و برق، تخلیه سطحی (شکل‌های لیختنبرگ) و درختکاری در پلیمرها اشاره کرد.

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

• سورس کد الگوریتم جستجوی فراکتال تصادفی در متلب — کلیک کنید

جستجوی فراکتال Fractal Search

با توجه به توضیحات مقدماتی در مورد الگوریتم جستجوی فراکتال تصادفی، می‌توان از رشد فراکتال (روش DLA) و نظریه پتانسیل برای طراحی الگوریتم فراکتال استفاده کرده است. به زبان ساده، جستجوی فراکتال (FS) از سه قانون ساده برای یافتن راه حل استفاده می‌کند:

1. هر ذره دارای یک انرژی پتانسیل الکتریکی است.
2. هر ذره منتشر می‌شود و باعث ایجاد ذرات تصادفی دیگر می‌شود و انرژی ذره دانه بین ذرات تولید شده تقسیم می‌شود.
3. تنها تعداد کمی از بهترین ذرات در هر نسل باقی می‌مانند و بقیه ذرات نادیده گرفته می‌شوند.

فرض کنید P ذره برای یافتن راه حل یک مسئله در نظر گرفته شده است. در ابتدا، هر ذره Pi به طور تصادفی در فضای جستجو با انرژی برابر Ei به دست آمده از معادله ۱ قابل محاسبه است.

که در آن E، حداکثر انرژی پتانسیل الکتریکی در نظر گرفته شده برای حل یک مسئله است. برای اجرای بهینه ساز فراکتال، هر ذره در هر نسل پخش می‌شود و بر اساس پرواز لوی، ذرات دیگری را ایجاد می‌کند. پرواز لِوی نوع خاصی از حرکت براونی است که شامل چند سطحی از مراحل تصادفی است که در آن، هر چند وقت یکبار، جسم متحیرکننده تصادفی یک جهش پرنده به ناحیه دیگری از فضا انجام می‌دهد. در این مدل، پرواز لوی را برای مدل رشد DLA اعمال می‌کنیم. معادله زیر توزیع لوی را توصیف می‌کند:

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

در نتیجه انتشار، برخی ذرات دیگر ایجاد می‌شوند. برای ایجاد هر نقطه در فرآیند انتشار، هر دو توزیع Levy و Gaussian بر اساس معادلات اعمال می‌شوند. (۳) و (۴) به ترتیب به صورت زیر خواهند بود.

که در آن q تعداد ذرات به دست آمده از انتشار ذره اصلی است. حاصل ضرب به معنای ضرب‌های ورودی است. β در معادله (۴) برابر با log(g)/g است که g تعداد تکرارها در نظر گرفته می‌شود. (P_i,BP)Gaussian توزیع گاوسی است که در آن میانگین و انحراف معیار به ترتیب Pi و BP هستند. BP به عنوان موقعیت بهترین نقطه ذکر شده است.

علاوه بر این، γ و ‘γ پارامترهای تصادفی بین ۰ و ۱ هستند. برای استفاده از مزیت هر دو راه رفتن لوی و گاوسی، الگوریتم جستجوی فراکتال به طور تصادفی بین آن‌ها مبادله می‌شود. به این معنی که توزیع لوی معمولاً برای تضمین یک الگوریتم همگرا سریع استفاده می‌شود در حالی که پیاده‌روی گاوسی برای بهره‌برداری از تخمین بهتر نتیجه نهایی استفاده می‌شود.

از آن‌جایی که رویکرد جستجو کاملاً بر پیاده‌روی‌های تصادفی متکی است، نمی‌توان همگرایی سریع را تضمین کرد. بنابراین، پارامتر a نقش مهمی از نظر همگرایی سریع دارد. دو معادله برای α در نظر گرفته می‌شود که یکی از آن‌ها برای جستجو در فضای وسیع تری استفاده می‌شود و دیگری برای یافتن راه حلی با دقت بالاتر استفاده می‌شود. دو معادله مورد استفاده برای a به شرح زیر است:

که در آن (E)min حداقل انرژی است که یک ذره در کل سیستم دارد. U و D کران بالا و پایین فضای جستجو هستند. g شماره نسل است. Ei انرژی ذرات P است و E به عنوان توانی در نظر گرفته می‌‎شود.

پس از انتشار ذره، مشکل اصلی نحوه توزیع انرژی ذره بین سایر ذرات ایجاد شده است. یک ایده ساده برای توزیع انرژی ارائه شده است و آن این است: هر چه ذره تناسب به دست آمده بهتر باشد، انرژی بیشتر است. فرض کنید q تعداد ذرات تولید شده با انتشار ذره Pi با انرژی Ei باشد. هر ذره منتشر شده دارای مقدار تناسب fj است که در آن j = 1، ۲، . . . ، . معادله توزیع انرژی را می توان به صورت زیر تعریف کرد:

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

فرض کنید Ø مجموع تمام انرژی حاصل از حذف ذرات است. فرض کنید μ نرخ توزیع انرژی بین ذرات باقیمانده و ذرات جدید ایجاد شده باشد. معادله توزیع انرژی برای ذرات باقی مانده به شرح زیر است:

که در آن E^t new و  E^t old انرژی ذره t بعد و قبل از توزیع انرژی هستند. از طرف دیگر، ς تعداد تمام ذرات در تکرار است. برای هر ذره‌ای که قرار است منتشر شود، تعداد ذرات در نظر گرفته شده ایجاد شده و به صورت تصادفی در فضای جستجو قرار می‌گیرد طبق رابطه زیر محاسبه می‌شود:

انرژی توزیع شده برای ایجاد هر ذره برابر با انرژی ذرات دیگر است و به شرح زیر است:

الگوریتم استاندارد بهینه سازی جستجوی فراکتال را می‌توان به صورت شبه کد زیر توصیف کرد:

جستجوی فراکتال تصادفی Stochastic Fractal Search

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

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

• حل مسئله ۸ وزیر با الگوریتم SFS جستجوی فراکتال تصادفی در متلب — کلیک کنید

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

برخلاف فاز انتشار در FS که باعث افزایش چشمگیر تعداد نقاط شرکت کننده می‌شود، یک فرآیند انتشار استاتیک برای SFS در نظر گرفته شده است. به این معنی که بهترین ذره تولید شده از فرآیند انتشار تنها ذره‌ای است که در نظر گرفته می‌شود و بقیه ذرات دور ریخته می‌شوند. علاوه بر کاوش کارآمد فضای مسئله، SFS از برخی روش‌های تصادفی به عنوان فرآیندهای به روز رسانی استفاده می‌کند. به عبارت دیگر، به‌روزرسانی فرآیند در SFS ما را به ویژگی‌های متنوع‌سازی (اکتشاف) در الگوریتم‌های فراابتکاری هدایت می‌کند.

برای ایجاد ذرات جدید از روش انتشار، دو روش آماری به نام‌های پرواز Levy و Gaussian بررسی می‌شوند. با این حال، مطالعات اولیه در مورد استفاده از توزیع لوی و گاوسی به طور جداگانه نشان می‌دهد که اگرچه پرواز لوی در چند نسل سریع‌تر از پیاده روی گاوسی همگرا می‌شود. پیاده روی گاوسی از پرواز لوی در یافتن حداقل‌های سراسری امیدوارکننده‌تر است.

بنابراین، برخلاف جستجوی فراکتال که از توزیع پرواز Levy استفاده می‌کند، توزیع گاوسی تنها راهپیمایی تصادفی است که در فرآیند رشد DLA SFS استفاده می‌شود. به طور کلی، یک سری از پیاده روی گاوسی شرکت کننده در فرآیند انتشار در معادلات زیر فهرست شده است:

که در آن ε و ‘ε اعداد تصادفی توزیع شده یکنواخت و محدود به [۰، ۱] هستند. BP و Pi به ترتیب به عنوان موقعیت بهترین نقطه و نقطه i ام در گروه مشخص می‌شوند. دو پارامتر گاوسی اول μ_BP و σ هستند که در آن μ_BP دقیقاً برابر با BP است. دو پارامتر دوم μ_P و σ هستند که μ_P برابر با P_i است. با در نظر گرفتن پارامترهای گاوسی، انحراف معیار با معادله محاسبه می‌شود:

برای تشویق به جستجوی محلی‌تر و نزدیک‌تر شدن به راه‌حل، اصطلاح log(g)/g به منظور کاهش اندازه پرش‌های گاوسی، با افزایش تعداد نسل‌ها استفاده می‌شود.

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

که در آن LB و UB به ترتیب بردارهای محدود مسئله پایین و بالایی هستند. همانطور که در معادلات قبلی بیان شد، ε یک عدد تصادفی توزیع شده یکنواخت است که به ناحیه پیوسته [۰، ۱] محدود می‌شود. پس از مقداردهی اولیه همه نقاط، تابع تناسب هر نقطه برای دستیابی به بهترین نقطه (BP) در بین تمام نقاط محاسبه می‌شود.

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

برای اولین روش آماری، ابتدا همه امتیازها بر اساس مقدار تابع تناسب رتبه بندی می‌شوند. سپس به هر نقطه i در گروه یک مقدار احتمال داده می‌شود که از توزیع یکنواخت ساده به صورت معادله زیر تبعیت می‌کند:

که در آن رتبه (P_i) به عنوان رتبه نقطه P_i در بین سایر نقاط گروه در نظر گرفته می‌شود و N به عنوان تعداد تمام نقاط گروه استفاده می‌شود. در واقع معادله (۱۵) می‌خواهد بیان کند که هر چه نقطه بهتر باشد، احتمال آن بیشتر است. این معادله برای افزایش شانس تغییر موقعیت نقاطی که جواب خوبی به دست نیاورده‌اند استفاده می‌شود.

از طرفی شانس گذراندن راه حل‌های خوب در نسل آینده افزایش می‌یابد. برای هر نقطه P_i در گروه، بر اساس اینکه آیا شرط Pa_i < ε برآورده شده است یا نه و جایی که ε یک عدد تصادفی یکنواخت متعلق به [۰، ۱] است، مولفه j از P_i مطابق معادله ۱۶ به‌روزرسانی می‌شود در غیر این صورت بدون تغییر باقی می‌ماند.

با توجه به روش آماری اول که بر روی اجزای نقاط انجام می‌شود، تغییر آماری دوم با هدف تغییر موقعیت یک نقطه با توجه به موقعیت سایر نقاط گروه است. این ویژگی کیفیت اکتشاف را بهبود می‌بخشد و ویژگی تنوع را برآورده می‌کند. قبل از شروع روش دوم، یک بار دیگر، کلیه امتیازات به دست آمده از روش آماری اول بر اساس معادله رتبه بندی می‌شوند. مشابه اولین فرآیند آماری، اگر شرطPa_i < ε برای یک نقطه جدید حفظ شود، موقعیت فعلی Pi مطابق معادلات اصلاح می‌شود. (۱۷) و (۱۸)، در غیر این صورت هیچ به روز رسانی رخ نمی‌دهد. معادله (۱۷) و (۱۸) به شرح زیر ارائه می‌شود:

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

شبه کد الگوریتم جستجوی فراکتال تصادفی استاندارد را می‌توان به صورت زیر توصیف کرد:

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

• مجموعه آموزش های الگوریتم های متاهیوریستیک — کلیک کنید

سخن آخر در مقاله الگوریتم جستجوی فراکتال تصادفی

در این پست سعی شد الگوریتم جستجوی فراکتال تصادفی Stochastic Fractal Search تشریح شود. در مقاله اصلی این الگوریتم دو الگوریتم جستجی فراکتال FS و جستجوی فراکتال تصادفی SFS ارائه شده است. در الگوریتم اول، هر ذره در سیستم سعی می‌کند خاصیت انشعاب شکست دی الکتریک را شبیه سازی کند، بنابراین جستجو را برای حل مسائل بهینه سازی سراسری آماده می‌کند. الگوریتم دوم نسخه توسعه یافته الگوریتم اول است که می‌تواند تمام معایب الگوریتم اول را پوشش دهد.

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