الگوریتم جهش قورباغه یا SFLA : الگوریتم قورباغه متحرک چیست؟

الگوریتم جهش قورباغه یا الگوریتم SFLA یک الگوریتم بهینه سازی و فراابتکاری الهام گرفته شده از طبیعت است که در سال 2006 در مقاله ای با نام Shuffled frog-leaping algorithm: a memetic metaheuristic for discrete optimization معرفی شد.

الگوریتم جهش قورباغه مخلوط شده یا Shuffled Frog Leaping Algorithm (به اختصار SFLA)، یکی از الگوریتم های بهینه سازی فرا ابتکاری است که از رفتار اجتماعی قورباغه ها الهام گرفته شده است، و از نظر طبقه بندی، در میان الگوریتم های رفتاری یا الگوریتم های ممتیک (Memetic Algorithms) قرار می گیرد.

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

اگر دوست دارید که مقاله اصلی الگوریتم SFLA را داشته باشید بر روی لینک زیر کلیک کنید:

دانلود مقاله لاتین الگوریتم جهش قورباغه یا SFLA

آشنایی با الگوریتم جهش قورباغه SFLA

الگوریتم SFLA از نحوه جستجوی غذای گروههای قورباغه سرچشمه می گیرد.

این الگوریتم برای جستجوی محلی میان زیر گروههای قورباغه از روش نموممتیک استفاده می کند.

الگوريتم جهش ترکیبی قورباغه از استراتژی ترکیب استفاده می کند و امکان مبادله پیام در جستجوی محلی را فراهم می سازد.

این الگوریتم مزایای الگوریتم نموممتیک و بهینه سازی گروه ذرات را ترکیب می کند.

در الگوریتم جهش ترکیبی قورباغه نه تنها در جستجوی محلی بلکه در جستجوی سراسری نیز پیامها مبادله می شوند.

بدین ترتیب جستجوی محلی و سراسری به خوبی در این الگوریتم ترکیب می شوند.

جستجوی محلی امکان انتقام مم را میان افراد ممکن می سازد و استراتژی ترکیب امکان انتقال مم را میان كل جمعیت ممکن می سازد.

مانند الگوریتم ژنتیک و بهینه سازی گروه ذرات الگوریتم جهش ترکیبی قورباغه یک الگوریتم بهینه سازی مبتنی بر کلونی است.

الگوریتم جهش ترکیبی قورباغه قابلیت بالایی برای جستجوی سراسری دارد و پیاده سازی آن آسان است.

الگوريتم جهش ترکیبی قورباغه می تواند بسیاری از مسائل غیر خطی، غیرقابل تشخیص و چند حالته را حل کند.

در این الگوریتم جمعیت شامل یک دسته از قورباغه ها (جواب ها) می شود،

کل جمعیت قورباغه ها در دسته های کوچکتری تقسیم بندی می شوند،

هر دسته نماینده انواع مختلفی از قورباغه ها هستند که در محل های مختلفی از فضای جوابها گسترده شده اند.

سپس هر دسته از این قورباغه ها شروع به یک جستجوی محلی دقیق در اطراف محل استقرار خود می کنند.

هر قورباغه در هر دسته هم تحت تأثیر دیگر اعضای گروه خود قرار می گیرد و هم از گروه های دیگر متاثر می شود.

بعد از چند مرحله بعد آمیزش انجام می گیرد و اطلاعات بین تمامی گروه ها پخش میشود تا شرط همگرایی برقرار شود.

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

تشکیل جمعیت اولیه در الگوریتم جهش قورباغه

ابتدا تعداد دسته های موردنظر و تعداد قورباغه هایی که می بایست در هر دسته قرار گیرند مشخص می شوند.

اگر تعداد دسته ها m عدد و تعداد قورباغه های موجود در هر دسته k عدد در نظر گرفته شود، در این صورت تعداد کل قورباغه ها برابر N = mk خواهد بود.

سپس تابع هزینه برای تمام نمونه های تولیدشده محاسبه می گردد.

مرتب سازی و توزیع قورباغه ها در دسته ها یا ممپلکس ها

کل قورباغه های انتخابی بر اساس تابع هزینه محاسبه شده، مرتب می شوند به گونه ای که نمونه با کمترین تابع هزینه و بهترین موقعیت در اولین مکان قرار گیرد. موقعیت بهترین قورباغه در کل جمعیت ذخیره می گردد.

سپس کل قورباغه ها در بین m دسته انتخابی تقسیم می شوند به قسمتی که در هر دسته k قورباغه قرار گیرد،

نحوه تقسیم بدین صورت می باشد که در جمعیت مرتب شده اولین عضو در اولین دسته قرار می گیرد،

دومین عضو در دومین دسته و به همین ترتیب ادامه می یابد تا امین عضو انتخاب شده و در mامین دسته قرار گیرد،

سپس عضو 1+m ام در اولین دسته قرار خواهد گرفت و به همین ترتیب روند تقسیم قورباغه ها ادامه می یابد.

تکامل دسته ها از تقسیم قورباغه ها در بین دسته های مختلف هر دسته به تعداد از قبل تعیین شده مراحل تکامل را تکرار می کند. پس از این مرحله، تمام قورباغه ها ترکیب شده و مرحله جستجوی سراسری دوباره تکرار می شود.

تاریخچه الگوریتم جهش قورباغه :

الگوریتم جهش قورباغه، نسخه توسعه یافته الگوریتم تکامل مجتمع های مخلوط شده یا Shuffled Complex Evolution (به اختصار SCE و یا SCE-UA) است، که یکی از الگوریتم نسبتا با سابقه در حوزه بهینه سازی هوشمند است.

الگوریتم SCE-UA در واقع از ترکیب قابلیت های تکاملی الگوریتم ژنتیک و قابلیت جستجوی تصادفی الگوریتم جستجوی تصادفی کنترل شده یا CRS ایجاد شده است و می توان آن را نیز، تا حدودی در دسته الگوریتم های ممتیک (Memetic Algorithms) طبقه بندی کرد.

با افزوده شدن قابلیت های نخبه گرایی (Elitism) و هوش جمعی (Swarm Intelligence) به الگوریتم SCE، الگوریتم جهش قورباغه به دست آمده است که از نظر ساختاری، اشتراکات بسیار زیادی را با الگوریتم SCE دارد.

این شباهت و ارتباط به اندازه ای است، که در هنگام پیاده سازی هر یک از این دو الگوریتم، با تغییراتی که چند دقیقه بیشتر زمان نمی برد، می توان برنامه کامپیوتری و پیاده سازی یک الگوریتم را به دیگری تبدیل نمود.

الگوریتم SFLA یک الگوریتم ممتیک است!

همان طور که گفته شد، الگوریتم جهش قورباغه یا SFLA، از جمله الگوریتم های رفتاری یا ممتیک (Memetic Algorithms) است.

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

یعنی، علاوه بر تکامل در جمعیت، تکامل به صورت فردی نیز به پیش می رود. به همین دلیل، بعضا الگوریتم های ممتیک، به عنوان الگوریتم های ترکیبی (Hybrid Algorithms) و یا الگوریتم های ژنتیک محلی (Local Genetic Algorithms) نیز شناخته می شوند.