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

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 ها انجام میشود تا همیشه بهترین پاسخ ها از میان تمام پاسخ های ممکن بدست بیاید. منبع: ویرگول