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

مقدمه

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

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

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


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

اصل مطلب

Shuffled Frog Leaping Algorithm (SFLA)

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

در تعریف این الگوریتم یک حمله هست که در زیر میخوانیم:

A memetic meta-heuristic for discrete optimization

تعریف کلمات استفاده شده در این عبارت

Memetic

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

  • در Memetic ها رفتارها و فرهنگ منتقل میشود و واحد سازنده ی آن MEME (میم) است.
  • در مقابل Genetic ها هستند که خصوصیت ها را منتقل میکنند و واحد سازنده شان GENE (ژن یا جین) است.

برای مثال انسانها فقط خصوصیات ظاهریشان را از پدران و مادرانشان به ارث نمی برند بلکه بسیاری از رفتارهایشان را از آنها تقلید میکنند. و البته ما بسیاری از رفتارهایی که تقلید میکنیم را با سطح درک خودمان بهبود میبخشیم تا به نتایج بهتری برسیم.

Optimization

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

Heuristic

این کلمه به معنای ابتکاری است و پیشوند meta در تعریف معنای این کلمه را به فرا ابتکاری ارتقا داده. در علوم کامیپوتر به راه حل های یک مسئله که بسیار سریع تر از راه حل های کلاسیک آن است گفته میشود.

Descrete

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

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

الگوریتم جهش قورباغه با بهینه سازی بخشی از الگوریتم دیگر با نام SCE یا به عبارت علمی تر SCE-UA درست شده است که مخفف Shuffled Complex Evolution و پسوند UA به خاطر تولید این الگوریتم در دانشگاه آریزونا به انتهای آن اضافه شده است.

عملکرد این الگوریتم به این صورت است که مجموعه اصلی را به تعدادی مجموعه کوچکتر تبدیل میکند و سپس آنها را با الگوریتم CCE که مخفف شده ی عبارت Competitive Complex Evolution است مرتب کرده و دوباره با ادغام زیر مجموعه های مرتب شده مجموعه ی اصلی ای را که یک مرحله مرتب تر شده است را تشکیل میدهد و این کار را بارها و بارها انجام میدهد تا بهینه ترین پاسخ ها حاصل شود.

الگوریتم جهش قورباغه دقیقا با بهبود همین الگوریتم CCE بدست آمده است و بقیه بخش های آن با الگورتیم پدرش یعنی SCE برابر است.

در الگوریتم SFLA الگوریتمی که این مرتب سازی را روی زیرمجموعه ها انجام میدهد FLA نام دارد که همان الگوریتم بهینه شده و کامل تر شده ی CCE است. در CCE مرتب سازی در یک Complex از زیر مجموعه های جمعیت اصلی انجام میشد ولی در FLA این کار ابتدا روی یک Memplex و سپس برروی تمام Memplex ها انجام میشود تا همیشه بهترین پاسخ ها از میان تمام پاسخ های ممکن بدست بیاید.



خاتمه

ممکن است بعضی از بخش های این مطلب برای فردی که آشنایی مقدماتی با مفاهیم اصلی طراحی الگوریتم ندارد سخت و یا غیرقابل فهم باشد. و این به دو دلیل است اول اینکه این یک مطلب مختصر شده است طبیعتا برای تدریس فهمیدن عمیق کاربرد ندارد و تنها معرفی الگوریتم است. درصورت تمایل به یادگیری عمیق آن میتوانید به منابع اصلی (که مقالاتی عموما 50 تا 100 صفحه هستند) مراجعه نمایید. و دوم اینکه دانش تا قبل از این مطلب برای فهم بهتر آن لازم است.

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


موفق باشید