الگوریتم های تکاملی

مقدمه

در میان مجموعه ای از تکنیک های جستجو و بهینه سازی، توسعه Evolutionary Algorithms یا الگوریتم های تکاملی  (EA) در دهه گذشته بسیار مهم بوده است. الگوریتم های تکاملی مجموعه ای از اکتشافات مدرن متشکل از موفقیت در بسیاری از برنامه های کاربردی با پیچیدگی های زیادی است. این موفقیت در حل مشکلات دشوار موتور محرک شناخته شده و به عنوان  Evolutionary Computation محاسبات تکاملی (EC) بوده است.

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

   اکثر پیاده سازی های فعلی EA از هر کدام از این سه نوع اساسی (به شدت مرتبط است هر چند به طور مستقل توسعه یافته): الگوریتم های ژنتیک (GA)، برنامه ریزی تکاملی (EP) و استراتژی های تکاملی (ES). دو گروه از EA بسیار مهم بوده اند: برنامه ریزی ژنتیک (GP) با بسیاری از مشکلات واقعی و سیستم های طبقه بندی (CS) مورد استفاده برای یادگیری ماشین و برای کشف قوانین در سیستم های مبتنی بر قوانین (RBS)

الگوریتم‌های تکاملی

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

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

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