الگوریتم فرگشت

الگوریتم فرگشت

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

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

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

  1. آغاز

  2. انتخاب

  3. عملگر های ژنتیک

  4. پایان

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

01-الگوریتم فرگشت

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

 

آغاز

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

انتخاب

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

توابع هدف چندگانه

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

02-الگوریتم فرگشت

عملگر های ژنتیک

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

 

 پایان

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

 

پیشنهاد

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

دیدگاهتان را بنویسید

مقالات مرتبط

X