در هوش مصنوعی ،الگوریتم تکاملی یک زیرمجموعه از محاسبه تکاملی است ، الگوریتم بهینه سازی فوق ابتکاری اجماع مدار جنسی .یک الگوریتم تکاملی برخی مکانیسم هایی را که توسط سیر تکاملی بیولوزیکی الهام می شوند را استفاده می کند :تولید دوباره ، جهش ،ترکیب دوباره ،گزینش طبیعی وبقای انسب .راه حل های کاندید در مسئله بهینه سازی نقش منفرد ها را در اجتماع بازی می کنند ، وتابع هزینه محیط را در جایی که راه حل ها زنده اند را مشخص می سازد .سیر تکاملی اجتماع بعد اتفاق می افتد سپس کاربرد تکرار شده اپراتورهای فوق .سیر تکاملی مصنوعی یک پروسه که شامل الگوریتم های تکاملی می شود را تشریح می کند .الگوریتم های تکاملی اعضا منفردی هستند که در سیر تکاملی شرکت می کنند .
الگوریتم های تکاملی به طور ثابت راه حل های مشابه خوبی را به همه انواع مسائل انجام می دهند چرا که آنها هیچ فرضیه ای راجع به حوزه موردنظر سازگاری ارایه نمی دهند.این کلیت توسط موفقیت های در زمینه های معکوس با مهندسی ،هنر ،بیولوزی ،اقتصاد ،زنتیک ،عملیات های جستجو ،روبات ،علوم اجتماعی ،فیزیک ،و شیمی نشان می دهند.جدا از استفاده آنها به عنوان بهینه گرهای ریاضیا تی ،محاسبات تکاملی والگوریتم ها همچنین به عنوان یک قالب کاری آزمایشی برای اعتبار بخشیدن به تئوری های سیر تکاملی بیولزیکی و مجموعه طبیعی استفاده می شوند ،فقط از طریق کار در زندگی مصنوعی .تکنیک های ناشی از الگوریتم های تکاملی به کار رفته در مدلینگ سیر تکاملی بیولزیکی به طور کلی به کشفیات پروسه های میکرو تحولی محدود می شوند.اگر چه برخی مشابهات کامپیوتر ها ،مانند تیرا و آویدا تلاش می کنند تا سیر تکاملی دینامیک را مدل سازی کنند.یک محدودیت الگوریتم های تکاملی فقدان تفاوت موخود بین زنوتیپ و
فنوتیپ می باشد.در طبیعت سلول بارور شده تخم مرغ متحمل یک پروسه پیچیده به نام پیدایش جنین می شود تا یک فنوتیپ رسیده وبالغ شود.این کدگذاری غیر مستقیم باور شده که جستجوی زنتیک را قوی تر می کند ، وهمچنین ممکن است گشایش اورگانیسم را اصلاح کند.کارهای اخیر در زمینه پیدایش جنین یا سیستم های توسعه مصنوعی این توجهات را نشان می دهند.
تکنیک های الگوریتم تکاملی
تکنیک های مشابه در جزئیات اجرایی و مسئله به کار گرفته شده متفاوت هستند .
الگوریت مزنتیک –این معروفترین نوع الگوریتم تکاملی است .یکی که به دنبال راه حل یک مسئله در فرم رشته هایی از اعداد می گردد ،واقعا همیشه به کارگیری اپراتورهای ترکیب دوباره به علاوه مجموعه و جهش .این نوع الگوریتم تکاملی اغلب در مسائل بهینه سازی استفاده می شود.
برنامه نویسی تکاملی –مانند برنامه نویسی زنتیک ،فقط ساختار برنامه ثابت شده و پارامترهای عددی اجازه گشایش دارند.
استراتزی سیر تکاملی –کار با بردارهایی از اعداد حقیقی به عنوان ارایه دهندگان راه حل ها ،به طور نمومه نسبت های جهش خود سازگارپذیر را استفاده می کند
برنامه نویسی زنتیک –اینجا راه حل ها در فرم برنامه های کامپیوتری هستند ،و سازگاری آنها توسط قابلیت حل مسئله محاسباتی مشخص میشود.
سیستم طبقه بندی یادگیری –به جای استفاده از تابع سازگاری ،منفعت قانون توسط یک تکنیک قوی ساز یادگیری انتخاب می شود.
تکنیک های مرتبط
سیر تکاملی افتراقی-بر پایه تفاوتهای برداری و بنابراین در ابتدا برای مسائل بهینه سازی عددی مناسب است
بهینه سازی انبوه ذرات –برپایه نظرات غارت مورچه ای توسط ارتباط فرمونی برای ایجاد مسیر .در ابتدا برای مسائل بهینه سازی ترکیبی مناسب است .
الگوریتم بهینه سازی هجوم علف هرزه –بر پایه نظرات رفتارکلنی علف هرزه در جستجو و یافتن یک مکان مناسب برای رشد و تولید دوباره.
جستجوی هارمونیک –بر پایه نظرات رفتار موسیقیدانان در جستجوی هارمونی بهتر .این الگوریتم برای بهینه سازی ترکیبی مانند بهینه سازی پارامتری مناسب است
انطباق حیوان با محیط گاوس –برپایه تئوری اطلاعات ،برای بیشینه کردن بازده تولید استفاده می شود ،به معنای سازگاری یا میانگین اطلاعات است .برای مثال انتروپی را در ترمودینامیک وتئوری اطلاعات ببینید.
استراتزی سیر تکاملی
در علوم کامپیوتر استراتزی سیر تکاملی یک تکنیک بهینه سازی بر پایه نظرات سازگاری وسیر تکاملی می باشد.در سال 1960،70 توسط اینگو رشنبرگ و همکارانش خلق شد ،و به کلاس جامع تری از محاسبات تکاملی یا سیر تکاملی مصنوعی متعلق است .استراتزی های سیر تکاملی از بردارهای حقیقی به عنوان ارایه کنندگان کدها استفاده کرده ،ودر ابتدا جهش و مجموعه مانند اپراتورهای جستجو استفاده شوند.به سادگی الگوریتم های تکاملی اپراتورها در چرخه ای به کار گرفته می شوند.یک تکرار از چرخه یک تولید نامیده می شود.مراحل پشت سر هم تولید تا زمانی که یک معیار پایان داده شده انجام شود ادامه می یابد.جهش به سادگی توسط اضافه کردن یک ارزش اتفاقی توزیع شده به هر یک از اعضا بردار انجام می شود.اندازه مرحله یا قدرت جهش اغلب توسط خود سازگاری کنترل می شود .اندازه های مرحله انفرادی برای هماهنگی وهمبستگی بین مختصات حال یا خود سازگارند یا توسط CMA کنترل می شوند.
برنامه نویسی سیر تکاملی
برنامه نویسی سیر تکاملی یکی از 4 الگوریتم اصلی تکاملی می باشد.در ابتدا توسط لارنس به سال 1960 برای استفاده سیر تکاملی شبیه سازی شده به عنوان پروسه یادگیری با هدف خلق کردن هوش مصنوعی .
فوگل از ماشین های با حالت متناهی به جای پیش بینی کننده ها استفاده کرد و آنها را گشایش کرد .اخیرا برنامه نویسی تکاملی یک لهجه محاسبه ای تکاملی بدون ساختار ثابت یا در تضاد با برخی دیگر لهجه ها می باشد.و تشخیص آنها زا استراتزی های تکاملی سختر می شود.برخی از متغیرهای اصلی تقریبا شبیه به برنامه نویسی زنتیکی آخری هستند ، به جز آن ساختار برنامه که ثابت شده است پارامتر های عددی آن اجازه دارند تا گشایش پیدا کنند.نوسان اصلی اپراتور آن جهش است .اعضا اجتماع مانند جزئی از ذرات خاص نسبت به اعضا ذرات مشابه نمایش داده می شوند پس هر اولیایی یک نوزاد با استفاده از (µ+µ) مجموعه زنده ماندن تولید می کند .
الگوریتم زنتیک
یک الگوریتم زنتیک یک تکنیک جستجو مورد استفاده در محاسبه برای یافتن راه حل های دقیق یا شبیه سازی شده برای بهینه سازی و مسائل جستجو می باشد .الگوریتم های زنتیکی با عنوان ابتکارات جستجوی جهانی طبقه بندی می شوند.الگوریتم های زنتیک کلاس خاصی از الگوریتم های تکاملی هستند که از تکنیک های الهام گرفته از بیولوزی تکاملی مانند ارث بردن ،جهش ، مجموعه ،ترکیب وتقاطع دوباره استفاده می کند.الگوریتم های زنتیکی به عنوان یک شبیه ساز کامپیوتری کار می کند که در آن اجتماع یک ارایه مطلق راه حل های کاندید در یک مسئله بهینه سازی را در دستیابی به راه حل های بهتر یاری می دهد.راه حل ها
دودوئی ارائه می شوندمانند رشته های 0و1 اما دیگر رمزگزاری ها نیز ممکن است .سیر تکاملی معمولا از
اجتماعی آغاز می شود که منفرد های آنها به صورت اتفاقی تولید شده اند ودر نسل ها اتفاق می افتد. در هر نسل ،سازگاری هر منفردی در اجتماع ارزشیابی می شود ،چندین منفرد به صورت اتفاقی از اجتماع اخیر انتخاب می شوند ،وشناسایی می شوند تا یک اجتماع جدید را شکل دهند.اجتماع جدید سپس در تکرار بعدی الگوریتم استفاده می شود.معمولا ،الگوریتم به پایان می رساندوقتی بیشترین تعداد نسل ها را تولید کرده است ،
یا یک سطح سازگاری رضایت مند شده برای اجتماع می رسد.اگر الگوریتم به پایان رسیده باشد با توجه به بیشترین تعداد نسل ها ،یک راه حل راضی شده ممکن است برسد یا نرسد.الگوریتم های زنتیکی کاربرد در بیوزنتیک ،علوم کامپیوتر،مهندسی ،اقتصاد ،شیمی ،تولید ،ریاضیات ،فیزیک و دیگر زمینه پیدا میکنند.
یک الگوریتم معمولی به 2 چیز برای مشخص شدن نیاز دازد :
یک ارایه زنتیکی از دامنه راه حل
یک تابع سازگاری برای ارزیابی دامنه راه حل
یک ارائه استاندارد از راه حل رشته ای از ذره ها می باشد.رشته های دیگر انواع و ساختارها می توانند رد راه مشابهی استفاده شوند.متعلقه اصلی که این ارائه های زنتیکی را مناسب می سازد آن است که قسمت های آنها با توجه به اندازه ثابت شده تنظیم شده اند ، که عملیات تقاطع ساده عملی می کند. ارایه طول متغیر ممکن است استفاده شود ، اما تقاطع اجرائیات در این مورد بسیار پیچیده تر است .ارائه های دختی در برنامه نویسی زنتیکی یافت می شوند و ارائی های گراف مانند در برنامه نویسی تکاملی یافت می شوند.تابع سازگاری در ارائه زنتیکی تشریح می شود و کیفیت راه حل ارائه شده را اندازه گیری می کند.تابع سازگاری همیشه وابسته به مسئله می باشد .در برخی مسائل ،معمولا سخت یا حتی غیرممکن است تا اصطلاح سازگاری تشریح کنیم .در این موارد ، الگوریتم های تقابلی زنتیکی استفاده می شوند.وقتی ما ارائه زنتیکی را داریم و تابع سازگاری تشریح می شود ، GA به آغاز یک اجتماع از راه حل های اتفاقی ادامه می دهد،بعد آنرا از طریق کاربرد تکرار جهش ،تقابل ،وارونگی واپراتورهای انتخابی اصلاح می کند.
ارزش دهی آغازی
در ابتدا بسیاری از راه حل های منفرد به طور اتفاقی تولید می شوند تا یک اجتماع اولیه را فرم دهند.اندازه اجتماع بستگی به طبیعت مسئله دارد ، اما به طور نمونه شامل بسیار صدها یا هزاران راه حل ممکن می باشد. اجتماع به صورت اتفاقی تولید می شود ،و همه حوزه راه حل های ممکن را می پوشاند.گاهی ،راه حل ها ممکن است در حوزه ها سابقه دار باشند در جاهایی که راه حل های بهینه به نظر پیدا شده اند.
بهگزینگی
در طی هر بار تولید موفق ،نسبتی از اجتماع موجود انتخاب می شوند تا نسل جدید را غذا بدهند .راه خل های منفرد از طریق یک پروسه مبنی بر سازگاری انتخاب می شوند ، درجایی که راه حل های بهتر به طور نمونه بیشتر انتخاب می شوند .روش های بهگزینگی معینی سازگاری هر راه حل را می سنجند و ترجیحا بهترین راه حل را انتخاب می کنند .روش های دیگر فقط یک نمونه اتفاقی اجتماع را می سنجند ،و این پروسه ممکن است بسیار زمان بر باشد .بسیاری توابع اتفاقی هستند وطراحی شده اند تا نسبت کمی از راه حل های سازگار را انتخاب کنند.این تضاد باعث حفظ بزرگی اجتماع می شود ،و از انحرافات نابالغ در راه حل های ضعیف جلوگیری می کند .روش های بهگزینگی معروف .خوب مطالعه شده شامل مجموعه چرخ رولتی و مجموعه تورنومنتی می شود.
تولید دوباره
مرحله بعدی تولید نسل دوم از راه حل ها از آنهایی است که از طریق اپراتورهای زنتیک "تقابل ، جهش " انتخاب شده اند .برای تولید هر راه حل جدید ،یک خفت از راه حل های اولیایی انتخاب می شوند تا از استخر انتخاب شده های قبلی غذا بدهند.با تولید یک راه حل کودک از طریق روش های تقابل و جهش ،یک راه حل جدید ایجاد می شود که به طور نمونه بسیاری از خصوصیات اولیا خویش را دارد.اولیا جدید برای فرزند جدید
انتخاب می شوند ،و پروسه تا زما نیکه یک اجتماع جدید از راه خل ها در اندازه های مقتضی تولید شود ،ادامه خواهد داشت .این پروسه بلافاصله منجر به خلق اجتماع نسل بعدی کروموزوم ها می شوند که با نسل اولی متفاوت هستند . رد کل سازگاری مینگین توسط این پروزه برای اجتماع افزایش می یابد،از آن جایی که بهترین اورگانیسم ها از نسل اولیه برای غذا دهی انتخاب می شوند ،در کنار تعداد کمی از راه حل های سازگار برای دلایل که در بالا ذکر شده اند .
پایان دهی
این پروسه کلی تا وقتی که حالت پایان دهی برسد ادامه پیدا میکند.حالات پایان دهی معمول هستند :
یک راه حل پیدا شده است که کمترین محدوده را راضی میکند
تعداد ثابت شده نسل ها رسیده است
بودجه تعیین شده رسیده است
بالاترین سطح رضایت مندی رسیده است یا به کفی رسیده است که تکرر های پی در پی
دیگر راه حل های بهتری ایجاد نمی کنند
نظارت دستی
ترکیب موارد بالا
مشاهدات
تعداد بسیاری مشاهدات کلی راجع به نسل راه حل ها از طریق الگوریتم زنتیک وجود دارد:
دربسیاری مسائل ،GA ممکن است تمایل به انحراف از مقابل بهینه محلی یا حتی نقاط قراردادی نسبت به بهینه جهانی مسئله داشته باشد .این بدان معنی است که نمی داند که چگونه رضایت مندی دوره کوتاه را برای به دست آوردن رضایت مندی بلند مدت قربانی کنیم.احتمال کلی این رخداد بستگی به شکل رضایت مندی زمینه دارد.مسائل خاص ممکن است سربالایی راحتی را در مقابل یک بهبنه جهانی ایجادکنند ،بقیه ممکن است آنرا برای تابع تا یافتن بهینه جهانی آسانتر کنند.این مسئله ممکن است با استفاده از تابع رضایت متفاوتی آرام گیرد ،افزایش نسبت جهش ،یا با استفاده از تکنیک های بهگزینگی که اجتماعی از راه حل های وارونه را نگهداری کند.اگرچه No FREE LUNCH theorem ثابت کرده است که هیچ راه حل گلی برای این مسئله وجود ندارد .یک تکنیک معمول برای نگهداری عکس این است که یک گود رفتگی را به آن تحمیل کنیم .در جایی که هر گروهی از منفردها با شباهت کافی دارای یک هدف اضافه شده هستند ،که ارائه آن تیم را در نسل های بعدی کاهش می دهد.و به بقیه منفرد ها اجازه می دهد تا در نسل باقی بمانند .این حیله ، اگرچه ممکن است موثر نباشد ،بستگی داشته باشد به حوزه فعالیت مسئله.وارونگی در الگوریتم های زنتیکی مهم است چرا که گذشتن از کنار یک اجتماع هم جنس راه حل های جدیدی ارایه نمی کند.در استراتزی های تکاملی و برنامه نویسی تکاملی ،وارونگی لازم نیست چراکه وابستگی بیشتر روی جهش است.
عمل کردن روی سری های دینامیک اطلاعات مشکل است ،همان گونه زن ها می بایست زود از مقابل راه حل هایی که ممکن است دیگر برای اطلاعات بعدی معتبر نباشند منحرف شوند.روش های بسیاری برای آن چاره ای اندیشیده اند تا با افزایش وارونگی زنتیکی به گونه ای و از انحراف زود جلوگیری کنند یا اینکه با افزایش احتمال جهش وقتی که کیفیت راه حل افت می کند یا با معرفی همه جدید ها به صورت اتفاقی المان های تولید شده را به داخل استخر زن وارد میکنندوتحقیق اخیر نیز نشان داده است تطبیق بیولوزیکی اولیه در حل این مسئله مفید است.دوباره استراتزی های تکاملی و برنامه نویسی تکاملی می توانند با استراتزی کاما اجرا شوند در جایی که اولیا نگهداری میشوند و اولیا جدید فقط از نوزادان انتخاب می شوند.این می تواند در مسائل دینامیک موثرتر باشد.
GA نمی تواند به طور موثر مسائل را در جایی که تنها معیار رضایت مندی درست/غلط باشد .همان گونه هیچ راهی برای انحراف در راه حل وجود ندارد.دراین موارد یک جستجوی اتفاقی ممکن است یک راه حل را به سرعت GA بیابد.