در دانشگاه که بودم برای درس طراحی الگوریتم باید در مورد الگوریتم جهش قورباغه ارائه ای آماده میکردم. خیلی در اینترنت گشتم و مطلبی که در سطح یک ارائه دانشگاهی باشه پیدا نکردم. بیشتر مطالبی که پیدا میکردم سطح بالاتری نسبت به نیاز من داشت و بعضی از مطالب هم حالتی تجاری از پیاده سازی آن بود که طبیعتا خارج از خواست کلاس و ارائه ی من بود.
در نتیجه آستین بالا زدم و یک تحقیق بسیار اساسی کردم و چندین مقاله به زبان انگلیسی و چند مورد هم فارسی خواندم و درنهایت یک جمع بندی از آن کردم و برای ارائه هم پاورپوینت درست کردم. در آخر ارائه تمام کلاس و استاد بسیار خوششان آمده بود و استاد ازم خواست اسکریپت و پاورپوینت ارائه رو براش بفرستم. ولی ضمن حمایتم از منطق Copyleft براش نفرستادم. چند روز پیش در محیط کار درباره ی این موضوع با یکی از همکارانم صحبت کردم و دوباره یاد اون ارائه افتادم. و حالا برای کاهش عذاب وجدانم میخواهم در اینجا اون یک پست مختصری در اینباره بنویسم.
در این مطلبی که منتشر میکنم قصدم تمرکز برروی معرفی این الگوریتم هست. و وارد مرحله ی پیاده سازی آن نمی شوم.
Shuffled Frog Leaping Algorithm (SFLA)
اسم اصلی این الگوریتم "الگوریتم جهش قورباغه مخلوط شده" است که در مورد تک تک کلمات استفاده شده در این اسم جلوتر صحبت خواهیم کرد.
در تعریف این الگوریتم یک حمله هست که در زیر میخوانیم:
A memetic meta-heuristic for discrete optimization
تعریف کلمات استفاده شده در این عبارت
الگورتیم ها از دنیای واقعی ایده میگیرند و ما دونوع الگوریتم اصلی داریم که عبارتند از :
برای مثال انسانها فقط خصوصیات ظاهریشان را از پدران و مادرانشان به ارث نمی برند بلکه بسیاری از رفتارهایشان را از آنها تقلید میکنند. و البته ما بسیاری از رفتارهایی که تقلید میکنیم را با سطح درک خودمان بهبود میبخشیم تا به نتایج بهتری برسیم.
در علوم کامپیوتر یک مسئله ی بهینه سازی، مسئله ی یافتن بهترین راه حل از میان همه ی راه حل های عملی میباشد.
این کلمه به معنای ابتکاری است و پیشوند meta در تعریف معنای این کلمه را به فرا ابتکاری ارتقا داده. در علوم کامیپوتر به راه حل های یک مسئله که بسیار سریع تر از راه حل های کلاسیک آن است گفته میشود.
در این تعریف به معنای گسسته است که بهینه سازی برروی متغیر های گسسته میباشد. که به این گونه بهینه سازی ها هم در واقع مسائل بهینه سازی ترکیبی گفته میشود.
الگوریتم جهش قورباغه با بهینه سازی بخشی از الگوریتم دیگر با نام SCE یا به عبارت علمی تر SCE-UA درست شده است که مخفف Shuffled Complex Evolution و پسوند UA به خاطر تولید این الگوریتم در دانشگاه آریزونا به انتهای آن اضافه شده است.
عملکرد این الگوریتم به این صورت است که مجموعه اصلی را به تعدادی مجموعه کوچکتر تبدیل میکند و سپس آنها را با الگوریتم CCE که مخفف شده ی عبارت Competitive Complex Evolution است مرتب کرده و دوباره با ادغام زیر مجموعه های مرتب شده مجموعه ی اصلی ای را که یک مرحله مرتب تر شده است را تشکیل میدهد و این کار را بارها و بارها انجام میدهد تا بهینه ترین پاسخ ها حاصل شود.
الگوریتم جهش قورباغه دقیقا با بهبود همین الگوریتم CCE بدست آمده است و بقیه بخش های آن با الگورتیم پدرش یعنی SCE برابر است.
در الگوریتم SFLA الگوریتمی که این مرتب سازی را روی زیرمجموعه ها انجام میدهد FLA نام دارد که همان الگوریتم بهینه شده و کامل تر شده ی CCE است. در CCE مرتب سازی در یک Complex از زیر مجموعه های جمعیت اصلی انجام میشد ولی در FLA این کار ابتدا روی یک Memplex و سپس برروی تمام Memplex ها انجام میشود تا همیشه بهترین پاسخ ها از میان تمام پاسخ های ممکن بدست بیاید.
ممکن است بعضی از بخش های این مطلب برای فردی که آشنایی مقدماتی با مفاهیم اصلی طراحی الگوریتم ندارد سخت و یا غیرقابل فهم باشد. و این به دو دلیل است اول اینکه این یک مطلب مختصر شده است طبیعتا برای تدریس فهمیدن عمیق کاربرد ندارد و تنها معرفی الگوریتم است. درصورت تمایل به یادگیری عمیق آن میتوانید به منابع اصلی (که مقالاتی عموما 50 تا 100 صفحه هستند) مراجعه نمایید. و دوم اینکه دانش تا قبل از این مطلب برای فهم بهتر آن لازم است.
اما همین قدر هم میتواند باعث ایجاد یک ارائه خوب ، شروع یک تحقیق ، بهینه سازی برروی کدهای شما و یا داشتن ایده ای برای حل مسئله ای در حال و یا آینده ی کار شما باشد.
موفق باشید
