الگوریتم جستجوی فراکتال تصادفی — Stochastic Fractal Search
در این بخش به توضیح و تشریح یکی از الگوریتم های فراابتکاری یا متاهیوریستیک (Metaheuristic Algorithm) قدرتمند و اثربخش با نام الگوریتم جستجوی فراکتال تصادفی (Stochastic Fractal Search) خواهیم پرداخت. شاید این الگوریتم بیشتر با نام الگوریتم SFS نیز شناخته شده باشد. در این مقاله سعی خواهیم کرد آموزش این الگوریتم را برای شما عزیزان داشته باشیم تا با جزئیات کامل و بهتری بتوانید این الگوریتم را درک کنید.
الگوریتم جستجوی فرکتال در سال 2014 توسط آقای 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) است.
در طول دهههای 50 و 60 میلادی، مفهوم تکامل (Evolution) توسط محققان علوم کامپیوتر به عنوان ابزاری بهینهسازی برای حل مسائل مهندسی مورد بررسی قرار گرفت و پس از آن روشی فنی به نام الگوریتمهای تقریبی را پایهگذاری کردند. الگوریتم های تقریبی را می توان به دو دسته ابتکاری (heuristic) و فراابتکاری (metaheuristic) تقسیم بندی کرد. اصطلاح «heuristic» در اصل از زبان یونانی گرفته شده است و به معنای «کشف» و «راهنمایی تحقیق» است. هیوریستیک ها روش ها و تکنیک هایی هستند که به دنبال راه حل های خوب (نزدیک به بهینه) با هزینه محاسباتی معقول هستند، بدون اینکه قادر به تضمین امکان سنجی یا بهینه بودن باشند، یا حتی در بسیاری از موارد بیان کنند که یک راه حل عملی خاص چقدر به بهینه نزدیک است. الگوریتم های ابتکاری برای مسائل خاص طراحی شده اند، در حالی که الگوریتم های فراابتکاری ها برای طیف وسیعی از مسائل بهینه سازی قابل استفاده است و برای حل هر مسئله بهینه سازی می توان از آن ها استفاده کرد. این نوع از الگوریتم ها اغلب برای حل مسائل سخت NP-Hard به کار می رود
الگوریتم های فرا ابتکاری اغلب برای حل مسائل سختی که نیاز به جستجو در فضای بزرگتر دارند، استفاده می شود. مزیت الگوریتم های فراابتکاری مربوط به جستجو کارآمد فضا، بدون حساسیت به اندازه فضای جستجو است. به طور معمول، الگوریتم های فراابتکاری بر سه هدف اصلی استوار است:
- حل سریعتر مسائل
- حل مسائل بزرگ
- به دست آوردن الگوریتم های قوی
علاوه بر موارد ذکر شده، سهولت در طراحی و پیاده سازی در کنار انعطاف پذیری باید از دیگر ویژگی های این الگوریتم ها باشد. دو ویژگی مهم الگوریتم های فراابتکاری عبارتند از:
- تنوع یا اکتشاف (Exploration)
- تشدید یا بهره برداری (Exploitation)
جستجو در اطراف بهترین راه حل های فعلی و انتخاب بهترین نامزدها یا راه حل ها از ویژگی های تشدید یا بهره برداری است هستند، در حالی که تنوع یا اکتشاف، کارایی الگوریتم را در جستجو بررسی می کند.
در دو دهه اخیر، استفاده از فراابتکاری در بسیاری از زمینههای علمی از جمله هوش مصنوعی، هوش محاسباتی، محاسبات نرم، برنامهریزی ریاضی و تحقیقات عملیاتی، توسعه عظیمی داشته است. بیشتر الگوریتم های فراابتکاری از رفتارهای پدیده های طبیعی الهام گرفته شده اند. در میان آن ها، الگوریتم ژنتیک (GA) نظریه داروین را به عنوان یکی از الگوریتم های محبوبی که فرآیند تکامل طبیعی را تقلید می کند، تثبیت کرد. بهینهسازی ازدحام ذرات (PSO) پیشنهاد شده توسط ابرهارت و کندی، از رفتار اجتماعی دستههایی از پرندگان الهام گرفته شده است که در جستجوی غذای خود هستند. الگوریتم کلونی زنبورهای مصنوعی (ABC) که توسط Karaboga توسعه یافته است، رفتار جستجوی غذا یک دسته زنبور را شبیه سازی می کند]. الگوریتم کلونی مورچگان مورچه ها (ACO) الگوریتم بهینه سازی دیگری است که از رفتار جستجوی کلونی مورچه ها در یافتن کوتاهترین مسیر برای جمع آوری غذا الهام گرفته شده است. “هر ذره در جهان هر ذره دیگر را جذب می کند”، این قانون گرانش نیوتنی است که الگوریتم جستجوی گرانشی (GSA) بر اساس آن استوار است. الگوریتم جستجوی فاخته (CS) یکی دیگر از روش های فراابتکاری موفق است که استراتژی بازتولید رفتار فاخته را تقلید می کند. این الگوریتم ها برای حل مسائل پیچیده بهینه سازی محاسباتی استفاده می شوند، با این حال، همگرایی سریع همراه با دقت تضمین نمی شود.
الگوریتم جستجوی فراکتال تصادفی (SFS) نیز یک الگوریتم بهینه سازی است. این الگوریتم فراابتکاری مبتنی بر خواص فراکتال است که با یک بینش متفاوت در حل مسائل بهینهسازی بر اساس خاصیت انتشار است که در در دنیای واقعی در فراکتالها مشاهده می شود. در ادامه خلاصه ای از فراکتال ها و ویژگی های فراکتال را ارائه خواهد شد. جستجوی فراکتال و جستجوی فراکتال تصادفی نیز به طور کامل در بخش های بعدی تشریح خواهد شد.
فراکتال چیست؟
خاصیت یک شیء یا کمیتی که تشابه خود را در تمام مقیاس ها، به معنایی فنی، توضیح می دهد، فراکتال نامیده می شود. اصطلاح “فراکتال” از کلمه لاتین fractus به معنای “شکسته” گرفته شده است و اولین بار توسط Benoit Mandelbrot در سال 1975 استفاده شد. نظریه های فراکتال برای توصیف الگوهای هندسی در طبیعت است. در شکل زیر نمونه ای از فراکتال را مشاهده می کنید.
نمونه ای از فراکتال ها شامل ساختارهایی از دانه های میکروسکوپی تا خوشه کهکشان ها وجود دارد. برخی از مثالها برای چنین فرآیندهایی عبارتند از انجماد دندریتی (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) از سه قانون ساده برای یافتن راه حل استفاده می کند:
- هر ذره دارای یک انرژی پتانسیل الکتریکی است.
- هر ذره منتشر می شود و باعث ایجاد ذرات تصادفی دیگر می شود و انرژی ذره دانه بین ذرات تولید شده تقسیم می شود.
- تنها تعداد کمی از بهترین ذرات در هر نسل باقی می مانند و بقیه ذرات نادیده گرفته می شوند.
فرض کنید P ذره برای یافتن راه حل یک مسئله در نظر گرفته شده است. در ابتدا، هر ذره Pi به طور تصادفی در فضای جستجو با انرژی برابر Ei به دست آمده از معادله 1 قابل محاسبه است.
که در آن E، حداکثر انرژی پتانسیل الکتریکی در نظر گرفته شده برای حل یک مسئله است. برای اجرای بهینه ساز فراکتال، هر ذره در هر نسل پخش می شود و بر اساس پرواز لوی، ذرات دیگری را ایجاد می کند. پرواز لِوی نوع خاصی از حرکت براونی است که شامل چند سطحی از مراحل تصادفی است که در آن، هر چند وقت یکبار، جسم متحیرکننده تصادفی یک جهش پرنده به ناحیه دیگری از فضا انجام می دهد. در این مدل، پرواز لوی را برای مدل رشد DLA اعمال می کنیم. معادله زیر توزیع لوی را توصیف می کند:
در شکل زیر نشان داده شده است، انتشار ذرات باعث ایجاد ذرات جدید با موقعیت های مختلف تصادفی در اطراف ذره می شود.
در نتیجه انتشار، برخی ذرات دیگر ایجاد می شوند. برای ایجاد هر نقطه در فرآیند انتشار، هر دو توزیع Levy و Gaussian بر اساس معادلات اعمال میشوند. (3) و (4) به ترتیب به صورت زیر خواهند بود.
که در آن q تعداد ذرات به دست آمده از انتشار ذره اصلی است. حاصل ضرب به معنای ضرب های ورودی است. β در معادله (4) برابر با log(g)/g است که g تعداد تکرارها در نظر گرفته می شود. (Pi,BP)Gaussian توزیع گاوسی است که در آن میانگین و انحراف معیار به ترتیب Pi و BP هستند. BP به عنوان موقعیت بهترین نقطه ذکر شده است. علاوه بر این، γ و ‘γ پارامترهای تصادفی بین 0 و 1 هستند. برای استفاده از مزیت هر دو راه رفتن لوی و گاوسی، الگوریتم جستجوی فراکتال به طور تصادفی بین آنها مبادله می شود. به این معنی که توزیع لوی معمولاً برای تضمین یک الگوریتم همگرا سریع استفاده میشود در حالی که پیادهروی گاوسی برای بهرهبرداری از تخمین بهتر نتیجه نهایی استفاده میشود.
از آنجایی که رویکرد جستجو کاملاً بر پیادهرویهای تصادفی متکی است، نمیتوان همگرایی سریع را تضمین کرد. بنابراین، پارامتر a نقش مهمی از نظر همگرایی سریع دارد. دو معادله برای α در نظر گرفته می شود که یکی از آنها برای جستجو در فضای وسیع تری استفاده می شود و دیگری برای یافتن راه حلی با دقت بالاتر استفاده می شود. دو معادله مورد استفاده برای a به شرح زیر است:
که در آن (E)min حداقل انرژی است که یک ذره در کل سیستم دارد. U و D کران بالا و پایین فضای جستجو هستند. g شماره نسل است. Ei انرژی ذرات P است و E به عنوان توانی در نظر گرفته می شود.
پس از انتشار ذره، مشکل اصلی نحوه توزیع انرژی ذره بین سایر ذرات ایجاد شده است. یک ایده ساده برای توزیع انرژی ارائه شده است و آن این است: هر چه ذره تناسب به دست آمده بهتر باشد، انرژی بیشتر است. فرض کنید q تعداد ذرات تولید شده با انتشار ذره Pi با انرژی Ei باشد. هر ذره منتشر شده دارای مقدار تناسب fj است که در آن j = 1، 2، . . . ، . معادله توزیع انرژی را می توان به صورت زیر تعریف کرد:
که در آن fi مقدار تناسب ذره اصلی قبل از انتشار است. اگرچه این مدل در هر دو جستجوی محلی و سراسری عملکرد خوبی درارد، در طول تکرار پیچیدگی جستجو به دلیل ایجاد ذرات جدید بر اساس انتشار افزایش یافت. برای مقابله با این مشکل، تنها تعدادی از بهترین ذرات به نسل بعدی منتقل می شوند (کمتر از 10٪ از کل ذرات در هر نسل). انرژی حاصل از دور ریختن ذرات برای باقی مانده ذرات و ایجاد ذرات جدید مصرف می شود.
فرض کنید Ø مجموع تمام انرژی حاصل از حذف ذرات است. فرض کنید μ نرخ توزیع انرژی بین ذرات باقیمانده و ذرات جدید ایجاد شده باشد. معادله توزیع انرژی برای ذرات باقی مانده به شرح زیر است:
که در آن Et new و Et old انرژی ذره t بعد و قبل از توزیع انرژی هستند. از طرف دیگر، ς تعداد تمام ذرات در تکرار است. برای هر ذره ای که قرار است منتشر شود، تعداد ذرات در نظر گرفته شده ایجاد شده و به صورت تصادفی در فضای جستجو قرار می گیرد طبق رابطه زیر محاسبه می شود:
انرژی توزیع شده برای ایجاد هر ذره برابر با انرژی ذرات دیگر است و به شرح زیر است:
الگوریتم استاندارد بهینه سازی جستجوی فراکتال را می توان به صورت شبه کد زیر توصیف کرد:
جستجوی فراکتال تصادفی Stochastic Fractal Search
اگرچه جستجوی فراکتال در یافتن راه حل خوب عمل می کند، اما این رویکرد از معایبی رنج می برد. یکی از اصلی ترین آنها داشتن پارامترهای زیادی است که باید به خوبی به آنها پرداخته شود، و دیگری این که تبادل اطلاعات بین ذرات رخ نمی دهد. تبادل اطلاعات بین تمام نقاط شرکت کننده در گروه تلاشی برای سرعت بخشیدن به همگرایی به حداقل است. در FS، هیچ تبادل اطلاعاتی بین ذرات انجام نشده است، و ضروری است که جستجو به طور مستقل انجام شود، بنابراین، این وضعیت در الگوریتم SFS با افزودن فازی به نام فرآیند بهروزرسانی اصلاح میشود. از طرف دیگر، از آنجایی که جستجوی فراکتال یک الگوریتم پویا است به این معنا که تعداد عوامل در الگوریتم اصلاح شده است، ما با یک مبادله بین دقت و زمان مصرف مواجه شده ایم. بنابراین، برای رفع مشکلات ذکر شده، نسخه دیگری از جستجوی فراکتال را به نام جستجوی فراکتال تصادفی (SFS) معرفی شده است.
دو فرآیند اصلی در الگوریتم SFS عبارتند از: فرآیند انتشار و فرآیند بهروزرسانی. در فرآیند اول، مشابه جستجوی فراکتال، هر ذره در اطراف موقعیت فعلی خود منتشر می شود تا خاصیت تشدید (بهره برداری) را برآورده کند. این فرآیند شانس یافتن حداقل های سراسری را افزایش می دهد و همچنین از گیر افتادن در حداقل های محلی جلوگیری می کند. در فرآیند دوم، الگوریتم شبیهسازی میکند که چگونه یک نقطه در گروه موقعیت خود را بر اساس موقعیت سایر نقاط گروه بهروزرسانی میکند. برخلاف فاز انتشار در FS که باعث افزایش چشمگیر تعداد نقاط شرکت کننده می شود، یک فرآیند انتشار استاتیک برای SFS در نظر گرفته شده است. به این معنی که بهترین ذره تولید شده از فرآیند انتشار تنها ذره ای است که در نظر گرفته می شود و بقیه ذرات دور ریخته می شوند. علاوه بر کاوش کارآمد فضای مسئله، SFS از برخی روش های تصادفی به عنوان فرآیندهای به روز رسانی استفاده می کند. به عبارت دیگر، بهروزرسانی فرآیند در SFS ما را به ویژگیهای متنوعسازی (اکتشاف) در الگوریتمهای فراابتکاری هدایت میکند.
برای ایجاد ذرات جدید از روش انتشار، دو روش آماری به نامهای پرواز Levy و Gaussian بررسی میشوند. با این حال، مطالعات اولیه در مورد استفاده از توزیع لوی و گاوسی به طور جداگانه نشان می دهد که اگرچه پرواز لوی در چند نسل سریعتر از پیاده روی گاوسی همگرا می شود. پیاده روی گاوسی از پرواز لوی در یافتن حداقل های سراسری امیدوارکننده تر است. بنابراین، برخلاف جستجوی فراکتال که از توزیع پرواز Levy استفاده می کند، توزیع گاوسی تنها راهپیمایی تصادفی است که در فرآیند رشد DLA SFS استفاده می شود. به طور کلی، یک سری از پیاده روی گاوسی شرکت کننده در فرآیند انتشار در معادلات زیر فهرست شده است:
که در آن ε و ‘ε اعداد تصادفی توزیع شده یکنواخت و محدود به [0، 1] هستند. BP و Pi به ترتیب به عنوان موقعیت بهترین نقطه و نقطه i ام در گروه مشخص می شوند. دو پارامتر گاوسی اول μBP و σ هستند که در آن μBP دقیقاً برابر با BP است. دو پارامتر دوم μP و σ هستند که μP برابر با Pi است. با در نظر گرفتن پارامترهای گاوسی، انحراف معیار با معادله محاسبه می شود:
برای تشویق به جستجوی محلیتر و نزدیکتر شدن به راهحل، اصطلاح log(g)/g به منظور کاهش اندازه پرشهای گاوسی، با افزایش تعداد نسلها استفاده میشود.
فرض کنید یک مسئله بهینه سازی سراسری با بعد D در دسترس است. بنابراین، هر ذره ای که برای حل مسئله در نظر گرفته شده است، بر اساس یک بردار بعدی D ساخته شده است. در طول فرآیند مقداردهی اولیه، هر نقطه به طور تصادفی بر اساس محدودیت های مسئله با تجویز کران های پایین و بالا مقداردهی اولیه می شود. معادله اولیه نقطه Pj، به شرح زیر است:
که در آن LB و UB به ترتیب بردارهای محدود مسئله پایین و بالایی هستند. همانطور که در معادلات قبلی بیان شد، ε یک عدد تصادفی توزیع شده یکنواخت است که به ناحیه پیوسته [0، 1] محدود می شود. پس از مقداردهی اولیه همه نقاط، تابع تناسب هر نقطه برای دستیابی به بهترین نقطه (BP) در بین تمام نقاط محاسبه می شود. با توجه به ویژگی بهره برداری در روش انتشار، همه نقاط در اطراف موقعیت فعلی خود برای بهره برداری از فضای جستجوی مشکل پرسه می زنند. از سوی دیگر، دو روش آماری با هدف افزایش اکتشافات فضایی بهتر به دلیل خاصیت اکتشاف در نظر گرفته شده است. روش آماری اول بر روی هر شاخص برداری منفرد انجام می شود و روش آماری دوم سپس برای همه نقاط اعمال می شود.
برای اولین روش آماری، ابتدا همه امتیازها بر اساس مقدار تابع تناسب رتبه بندی می شوند. سپس به هر نقطه i در گروه یک مقدار احتمال داده می شود که از توزیع یکنواخت ساده به صورت معادله زیر تبعیت می کند:
که در آن رتبه (Pi) به عنوان رتبه نقطه Pi در بین سایر نقاط گروه در نظر گرفته می شود و N به عنوان تعداد تمام نقاط گروه استفاده می شود. در واقع معادله (15) می خواهد بیان کند که هر چه نقطه بهتر باشد، احتمال آن بیشتر است. این معادله برای افزایش شانس تغییر موقعیت نقاطی که جواب خوبی به دست نیاورده اند استفاده می شود. از طرفی شانس گذراندن راه حل های خوب در نسل آینده افزایش می یابد. برای هر نقطه Pi در گروه، بر اساس اینکه آیا شرط Pai < ε برآورده شده است یا نه، و جایی که ε یک عدد تصادفی یکنواخت متعلق به [0، 1] است، مولفه j از Pi مطابق معادله 16 بهروزرسانی میشود در غیر این صورت بدون تغییر باقی می ماند.
با توجه به روش آماری اول که بر روی اجزای نقاط انجام می شود، تغییر آماری دوم با هدف تغییر موقعیت یک نقطه با توجه به موقعیت سایر نقاط گروه است. این ویژگی کیفیت اکتشاف را بهبود می بخشد و ویژگی تنوع را برآورده می کند. قبل از شروع روش دوم، یک بار دیگر، کلیه امتیازات به دست آمده از روش آماری اول بر اساس معادله رتبه بندی می شوند. مشابه اولین فرآیند آماری، اگر شرطPai < ε برای یک نقطه جدید حفظ شود، موقعیت فعلی Pi مطابق معادلات اصلاح میشود. (17) و (18)، در غیر این صورت هیچ به روز رسانی رخ نمی دهد. معادله (17) و (18) به شرح زیر ارائه می شود:
شبه کد الگوریتم جستجوی فراکتال تصادفی استاندارد را می توان به صورت زیر توصیف کرد:
فلوچارت الگوریتم جستجوی فراکتال تصادفی
سخن آخر
در این پست سعی شد الگوریتم جستجوی فراکتال تصادفی Stochastic Fractal Search تشریح شود. در مقاله اصلی این الگوریتم دو الگوریتم جستجی فراکتال FS و جستجوی فراکتال تصادفی SFS ارائه شده است. در الگوریتم اول، هر ذره در سیستم سعی می کند خاصیت انشعاب شکست دی الکتریک را شبیه سازی کند، بنابراین جستجو را برای حل مسائل بهینه سازی سراسری آماده می کند. الگوریتم دوم نسخه توسعه یافته الگوریتم اول است که می تواند تمام معایب الگوریتم اول را پوشش دهد. تمامی رویه ها در الگوریتم دوم را می توان به دو فرآیند به نام فرآیندهای انتشار و به روز رسانی تقسیم کرد. در فرآیند اول، برای افزایش شانس یافتن حداقل سراسری مشابه الگوریتم اول، هر ذره در اطراف موقعیت فعلی خود پخش می شود. در فرآیند دوم، برای بررسی کارآمد فضای مسئله، الگوریتم دوم از برخی روشهای تصادفی به عنوان فرآیندهای بهروزرسانی استفاده میکند. الگوریتم دوم یعنی SFS امیدوارکنندهتر از الگوریتم اول است.
درباره امین جلیل زاده رزین
پایه گذار و موسس وب سایت آموزشی پی استور، مدرس دانشگاه فنی و حرفه ای، برنامه نویس و تحلیل گر سیستم، پژوهشگر در حوزه الگوریتم های ابتکاری، فرا ابتکاری، یادگیری ماشین، شبکه و پایگاه داده. ایشان در زبان های برنامه نویسی متعدد، نظیر ++C، سی شارپ، PHP ،Java، متلب MATLAB و Python تسلط و سابقه تدریس فعال دارند.
خیلی جامع و کامل بود. ممنون از شما