الگوریتم ژنتیک در متلب

الگوریتم ژنتیک در متلب

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

الگوریتم های بهینه سازی در متلب

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

انواع الگوریتم های بهینه سازی عبارتند از:

  • الگوریتم الهام
  • الگوریتم پراش (دیفرانسیلی)
  • الگوریتم تکاملی
  • آزادسازی پویا (کنش رهش یا Dynamic RELAXATION)
  • الگوریتم ژنتیک
  • الگوریتم تپه نوردی با شروع تصادفی
  • الگوریتم نلدر-مید
  • الگوریتم بهینه سازی ازدحام ذرات
  • الگوریتم لانه زنبوری
  • شبیه سازی حرارتی
  • تونل زنی کاتوره ای

مثالی از الگوریتم شبیه سازی حرارتی که در مهندسی مکانیک کاربرد بسیاری دارد.

الگوریتم های بهینه سازی در متلب و شبیه سازی حرارتی

پیشینه الگوریتم ژنتیک

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

حتما بخوانید:  الگوریتم ازدحام ذرات PSO : از صفر تا صد!

الگوریتم ژنتیک در متلب

الگوریتم ژنتیک در متلب

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

الگوریتم ژنتیک به عنوان یکی از الگوریتم های بهینه سازی در متلب

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

الگوریتم های بهینه سازی متلب در ریاضیات، با الهام از انتخاب طبیعی

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

الگوریتم ژنتیک در متلب و بهینه سازی

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

حتما بخوانید:  روش های بهینه سازی در متلب

پارادوکس مندل

اساس کار الگوریتم ژنتیک به عنوان اساس الگوریتم های بهینه سازی در متلب

به منظور پاسخ دادن به این سوالات، الگورریتم ژنتیک در متلب پدید آمد. الگوریتم ژنتیک در متلب در عین حفظ تنوع و فعالیت در سرتاسر دامنه تنوع، پاسخ های بهینه را به صورت چندتایی (و نه تکی) پیدا می کند.

نسل یک یا Initial Population

در سرتاسر فضای تعریف شدن یک تابع، پاسخ هایی تصادفی و به صورت کاتوره ای پخش می شوند. بدیهی است که برخی از این پاسخ های کاتوره ای نسبت به دیگر پاسخ ها مینیمم تر هستند. مینیمم تر بودن را در الگوریتم ژنتیک در متلب با شاخص سازگاری یا fitness function عنوان می کنیم. درواقع برخی پاسخ ها سازگاری بیشتری نسبت به بقیه دارند. بقیه پاسخ ها حذف می شوند و بهترین ها باقی می مانند.

زاد و ولد یا Reproduction

پاسخ های باقی مانده در گذر از نسلی به نسل بعدی دچار تغییراتی می شوند.

  • در بازه های قبلی و در اطراف همان سازگاری، تکثیر می شوند. این کار از طریق ترکیب پاسخ های نسل قبل با یکدیگر انجام می شود. به این روش CrossOver گفته می شود. آمیختگی جمعیت ها سبب بروز افراد (در اینجا پاسخ) های جدیدی می شود که ممکن است صفات بهتر و نزدیکی بیشتری به پاسخ داشته باشند.
  • برخی (درصد بسیار کمی) از این نقاط تکثیر شده چهش پیدا می کنند و ممکن است به هر نقطه ای از فضای تعریف تابع پرتاب شوند. این عمل در الگوریتم ژنتیک به جهش یا Mutation معروف است .
حتما بخوانید:  روش های بهینه سازی در متلب

نسل دو

الگوریتم از ابتدا مجددا تکرار می شود.

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

الگوریتم ازدحام ذرات به عنوان حالت پیوسته الگوریتم ژنتیک در متلب

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

تصویر زیر پخش کاتوره ای ذرات را در ابتدای الگوریتم نشان می دهد.

ازدحام ذرات به عنوان یکی از الگوریتم های بهینه سازی در متلب

تصویر زیر نیز نشان دهنده نتیجه بهینه سازی با ازدحام ذرات به عنوان یکی از دگرشکل های الگوریتم ژنتیک می باشد.

نتیجه ازدحام ذرات به عنوان یکی از الگوریتم های بهینه سازی در متلب

الگوریتم لانه زنبوری به عنوان روش گسسته الگوریتم ژنتیک در متلب

الگوریتم لانه زنبوری یکی از الگوریتم های بهینه سازی در متلب

شاید نام الگوریتم لانه زنبوری به علت مشابهت با لانه کبوتری به گوش شما آشنا باشد. درست حدس زدید! الگوریتم لانه زنبوری (یا Artificial Bee Colony) کاملا بر اساس اصل لانه کبوتری عمل می کند. به ازای هر لانه، تنها یک کبوتر قرار می گیرد. و به ازای هر غذا یک زنبور کارگر به دنبال آن می رود. کبوتر و زنبوری که به پاسخ نزدیکترند، با برداشتن غذا یا ورود به خانه به نسل بعد منتقل می شوند و سایر گونه ها که دورترند حذف می شوند. الگوریتم لانه زنبوری بهترین روش برای مسائل ابعاد بالاتر می باشد.

 

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

این سایت از اکیسمت برای کاهش هرزنامه استفاده می کند. بیاموزید که چگونه اطلاعات دیدگاه های شما پردازش می‌شوند.