الگوریتم فرگشت و 4 سطح آن
در مقالهی پیشین از سری مقالات مرتبط با بهینه‌یابی به شرح و بررسی «الگوریتم تبرید شبیه‌سازی شده» پرداختیم در این مقاله به شرح و بررسی «الگوریتم فرگشت» می‌پردازیم.
– – –
منطق جهان مادی ما به گونه‌ای ساختار یافته که برای حل هر مشکل یا چالشی با محدودیت‌هایی روبرو هستیم، این محدودیت ها شامل محدودیت هزینه، محدودیت زمان، محدودیت منابع و … می‌شوند. با در نظر گرفتن این فرض و ورود به جهان الگوریتم‌ها متوجه خواهیم شد که الگوریتم‌ها همیشه کارآمد نیستند ما در این جهان پیوسته با نوعی تعادل سروکار داریم تعادلی میان صرفه ی زمان ، هزینه و دقت در به دست آوردن پاسخ مطلوب.
به بیان ساده تر در طول راه با الگوریتم‌هایی مواجه خواهیم شد که دارای دقتی بالا در به دست آوردن پاسخ مطلوب هستند اما باید توجه داشت که منابع زمانی و محاسباتی قال توجهی را نیز مورد استفاده قرار می‌دهند از طرف دیگر الگوریتم‌هایی وجود دارند که از نظر زمانی بسیار به صرفه‌تر هستند اما تضمینی وجود ندارد که پاسخ ارائه شده توسط این الگوریتم‌ها، مشخصا پاسخی که ما به دنبال آن هستیم باشد.
در چنین شرایطی با مفهومی به نام الگوریتم‌های فرگشتی یا تکاملی مواجه خواهیم شد الگوریتم‌هایی که راه حلی قابل اعتماد برای صرفه‌جویی در زمان و یافتن پاسخ‌هایی نزدیک به پاسخ مطلوب هستند.
فهم پروسه عملکرد یک الگوریتم فرگشتی کار سختی نیست با توجه به اینکه بسیاری از ما با مفهوم انتخاب طبیعی آشنایی داریم . عملکرد یک الگوریتم فرگشتی را می‌توان به چهار سطح اساسی تقسیم کرد:
- آغاز
- انتخاب
- عملگر های ژنتیک
- پایان
کمی جلوتر به مفهوم هر یک از این سطوح خواهیم پرداخت هر یک از چهار موردی که مشاهده کردید در واقع به مرحله ای از مراحل فرآیند انتخاب طبیعی اشاره دارد و استفاده از این مراحل به کار بردن و فهم یک الگوریتم فرگشتی به طور قابل توجه ای آسان‌تر خواهد شد.
برای اینکه کل عملکرد را در یک بیان منطقی خلاصه کرده باشیم می‌توان گفت پاسخ هایی که توانایی بیشتری برای تطبیق با معیار ما دارند باقی مانده و به نسل‌های بعد منتقل می‌شوند در مقابل پاسخ‌های نامطلوب حذف شده و از بین خواهند رفت درست مانند پروسه‌ای که در انتخاب طبیعی شاهد آن هستیم.
در ادامه این مقاله بر طبق آموزش بهینه‌یابی، شیوه عملکرد و کاربرد یک الگوریتم فرگشتی را توضیح خواهیم داد مسئله‌ای که با آن سروکار داریم به بررسی مجموعه‌ای از حالات می‌پردازد که آن‌هارا با معیار بیشینه کردن مقدار یک تابع برازش با یکدیگر مقایسه خواهیم کرد. لازم است بدانید که پاسخ ما بر دو طریق به دست خواهد آمد: اول آنکه الگوریتم ما به اندازه تعداد از پیش مشخص شده تکرار شود و یا آنکه به سنجه‌ای از معیار مورد نظر خود دست پیدا کنیم. برای دریافت پاسخ از یک الگوریتم فرگشتی راه‌های دیگری نیز وجود دارید اما به طور معمول این دو حالت مورد استفاده قرار خواهند گرفت.
آغاز
در آغاز برای استفاده از الگوریتم باید مجموعه‌ای از پاسخ‌ها داشته باشیم یا به طور دقیق‌تر مجموعه‌ای از پاسخ‌های احتمالی برای مسئله، به هر یک از این پاسخ‌ها Member عضو گفته می‌شود. این مجموعه معمولا به طور رندوم و تصادفی یا با دانش قبلی از حدودی که ممکن است شامل جواب باشد انتخاب می‌شود. شاید مهم‌ترین نکته در مورد این مجموعه اولیه از پاسخ‌های احتمالی گوناگونی آن است که بر کیفیت عملکرد الگوریتم ما تاثیر بالایی خواهد داشت.
انتخاب
پس از آنکه مجموعه اولیه ساخته شد حال باید هر یک از اعضا بر اساس تابع هدف سنجیده شوند این تابع هدف خصوصیات و ویژگی‌های هر یک از اعضا را به صورت ورودی دریافت کرده و نهایتا با یک خروجی عددی میزان مطلوبیت و کارآیی عضو و ویژگی‌هایش را بر اساس ساختار تابع هدف مشخص می‌کند.
ساخت یک تابع برازش با کیفیت کار بسیار دشواری است چرا که این تابع باید به طور درستی ویژگی‌های مورد انتظار ما از پاسخ مطلوب را منعکس را کند و طراحی و ساختار آن کاملا وابسته به مشکلی است که برای حل آن مورد استفاده قرار می‌گیرد.
توابع هدف چندگانه
الگوریتم‌های فرگشتی می‌توانند با توابع برازش چندگانه نیز مورد استفاده قرار بگیرند این کار پروسه را کمی پیچیده‌تر خواهد کرد به این معنی که در نهایت مجموعه‌ای از پاسخ‌ها به جای یک پاسخ منفرد در اختیار ما قرار خواهد گرفت. این مجموعه از پاسخ‌های بهینه را Preto Frontier یا آنگونه که در فارسی ترجمه کرده اند جبهه پارتو می‌خوانیم. این مجموعه شامل پاسخ‌های برتری است که هیچکدام بر دیگری مسلط نمیشوند در نهایت نوعی انتخاب‌گر طراحی شده براساس ذات مسئله یک پاسخ بهینه را از بین این مجموعه انتخاب خواهد کرد.
عملگرهای ژنتیک
این مرحله به دو زیر مجموعه تقیسم می‌شود. :
- ترکیب
- جهش
پس از انتخاب مطلوب‌ترین پاسخ‌های هر نسل براساس تابع برازش، ویژگی‌های آن‌ها برای ساخت نسل بعدی در الگوریتم مورد استفاده قرار می‌دهیم. با استفاده از ویژگی‌های مطلوب اصطلاحا این والدین فرزندانی تولید خواهند شد که دارای ترکیبی از ویژگی‌های والدین هستند. پس از این اتفاق نوبت به مرحله ضروری «جهش» می‌رسد بدون اجرای این مرحله احتمال گیر افتادن در یک اپتیموم محلی بسیار بالاست. این اتفاق به سادگی با تغییر بخشی از ویژگی‌های بچه‌ها صورت می‌گیرد به طوری که دیگر به طور کامل ویژگی‌های والدین را منعکس نکنند.
معمولا جهش‌ها بر اساس نوعی توزیع احتمال صورت می‌پذیرند که از قبل بر اساس داده‌ها طراحی شده است.
پایان
نهایتا همانطور که بالاتر گفته شده الگوریتم با رسیدن به حداکثر تعداد تکرار از پیش مشخص شده و یا معیار مشخصی از عملکرد متوقف شده و ما پاسخ نهایی را در دست خواهیم داشت.
– – –
در مقالهی بعدی به بررسی مفهوم دیگری از مفاهیم مربوط به بهینه یابی می‌پردازیم.
دیدگاهتان را بنویسید
برای نوشتن دیدگاه باید وارد بشوید.