الگوریتم های تکاملی
ES یکی از روش های تکاملی می باشد. که با یک جمعیت اولیه شروع می شود در این روش بعد از انتخاب والدین از روش های تکثیر برای تولید نسل جدید استفاده میشود.
الگوریتمهای فرگشت یا تکامل که بر اساس فرگشت طراحی شدهاند امروزه در علوم مختلف بسیار پرکاربرد هستند. در نتیجه میتوان گفت که فرگشت در مورد کلیه موجودات هستی لااقل به لحاظ تئوری کاملاً امکانپذیر است.
نظریه داروین یکی از جنجالیترین نظریات علمی است. یکی از دلایل جنجالی بودن این نظریه ناهمخوانی آن با داستان خلقت در برخی ادیان است، هرچند موارد مشابهی مانند سخنان گالیله و نیوتن در باب جهان-مرکزی نبودن زمین یا گرانش (با وجود آنکه با آموزه های کتابهای مقدس در تضاد است) امروزه کاملا پذیرفته شده هستند. اما چه چیزی باعث شده هنوز نظریه داروین مورد حمله قرار بگیرد؟ یکی از مهمترین دلایل پیچیدگی این نظریه و ارتباط آن با شاخه های دیگر دانش است که فهم درست از آن ها به چند دهه اخیر بر میگردد. در این جا سعی می کنیم نشان دهیم که چگونه میتوان عجیب بودن فرگشت را درک کرد. باید توجه کرد که نظریه فرگشت (تکامل) در مورد پیچیدگی، تغییرات ژنتیکی و تولید نسل نوین با خواص متفاوت حرف میزند و از پیدایش اولین موجود زنده و منشاء حیات سخنی به میان نمیآورد، گرچه برای آن هم نظریات و تئوریهای متفاوتی در میان دانشمندان وجود دارد.
الگوریتمهای فرگشتی :
زیر مجموعهای از محاسبات فرگشتی است و در شاخه هوش مصنوعی قرار میگیرد و شامل الگوریتمهایی جهت جستجو است که در آنها عمل جستجو از چندین نقطه در فضای جواب آغاز میشود.
الگوریتمهای فرگشتی بهطور اساسی با دیگر روشهای بهینهسازی و جستجوی مرسوم قدیمی تفاوت دارند. برخی از این تفاوتها عبارتند از:
الگوریتمهای فرگشتپذیر تنها یک تک نقطه را جستجو نمیکنند بلکه جمعیتی از نقاط را به صورت موازی بررسی مینمایند.
الگوریتمهای فرگشتپذیر نیاز به اطلاعاتی ضمنی و دیگر دانشهای مکمل ندارند؛ تنها تابع هدف و شایستگی مربوط در جهتهای جستجو تأثیر گذارند.
الگوریتمهای فرگشتپذیر از قوانین در حال تغییر احتمالی بهره میبرند و نه موارد مشخص و معین.
استفاده از الگوریتمهای فرگشتپذیر بهطور کلی خیلی سر راست است، زیرا هیچگونه محدودیتهایی برای تعریف تابع هدف وجود ندارد.
الگوریتمهای فرگشتپذیر تعداد زیادی از پاسخهای قابل قبول را بدست میدهند و انتخاب پایانی بر عهده کاربر است؛ لذا در مواردی که مسئله مورد نظر شامل یک پاسخ مفرد نمیباشد، مثلاً خانوادهای از پاسخهای بهینه-پَرِتو، مشابه آنچه در بهینهسازی چند هدفه و مسائل زمانبندی وجود دارد. الگوریتمهای فرگشتی برای شناسایی این پاسخهای چندگانه بهطور همزمان ذاتاً کارآمدند.
الگوریتمهای فرگشتی عبارتند از:
الگوریتم ژنتیک
الگوریتم کلونی زنبور عسل
روش بهینهسازی گروه مورچهها
راهبرد فرگشتی
الگوریتم رقابت استعماری
انواع مختلف الگوریتم های تکاملی :
رشته دودویی : الگوریتم های ژنتیک
بردارهایی از اعداد حقیقی: استراتژی های تکامل
ماشین های متناهی الحالت: برنامه نویسی تکاملی
درخت ها: برنامه نویسی ژنتیک
شرح الگوریتم ES
تعیین جمعیت اولیه :
ابتدا یک جمعیت اولیه در بازه مورد نظر تعیین می کنیم. این جمعیت به صورت یک ماتریس با تعداد سطر برابر با تعداد جمعیت، و تعداد ستون برابر با تعداد متغیرهای مساله می باشد.
تولید مثل Recombination :
در اینجا از روش Discrete Recombination استفاده شده است.
در این روش ابتدا دو والد را برای آمیزش در نظر می گیریم که این کار از طریق انتخاب دو عدد رندوم و در نظر گرفتن یک میزان احتمال برای انجام آمیزش صورت می گیرد.
در انتها از روش (µ+λ) یعنی افزودن تعداد فرزندان تولیدی به نسل قبل و انتخاب بهترین آنها برای نسل بعد استفاده شده است.
جهش (mutation) :
انجام این عمل ما را در رسیدن به نقطه جدید کمک می کند. اصولا جهش با اضافه نمودن یک عدد گوسی به جمعیت مورد نظر صورت می گیرد.
را می توان در هر مرحله آبدیت نمود. بدین منظور در این برنامه از روش Additive استفاده شده است که روابط آن به صورت زیر می باشد.
σij(t + 1) = σij(t) + ησij(t)Nij(0, 1)
و در نهایت جهش به صورت زیر انجام می گیرد:
انتخاب (selection) :
حال مجموعه ای از والدین و فرزندان را داریم که بهترین آنها را با توجه به مساله مورد بررسی برای تولید نسل بعد انتخاب می کنیم.
حوزههای کاربردی
هوش مصنوعی
دانشهای کاربردی: برق، مکانیک، صنایع، شیمی، زیستشناسی و غیره
سنتز و آزمونهای سختافزاری
طراحی و بهینهسازی فیلترهای دیجیتال و آنالوگ
استفاده در سیستمهای چند پردازندهای
کنترل رباتها
جانمایی سلولهای منطقی