الگوریتم های ژنتیکی
الگوریتم های ژنتیکی (GA) الگوریتم های جستجوی اکتشافی تطبیقی هستند که متعلق به بخش بزرگتر الگوریتم های تکاملی هستند. الگوریتم های ژنتیکی مبتنی بر ایده های انتخاب طبیعی و ژنتیک است. اینها بهره برداری هوشمندانه از جستجوی تصادفی است که با داده های تاریخی تهیه شده است تا بتواند جستجوی منطقه را به سمت عملکرد بهتر در فضای راه حل هدایت کند. آنها معمولاً برای تولید راه حلهای با کیفیت بالا برای مشکلات بهینه سازی و مشکلات جستجو استفاده می شوند.
الگوریتم های ژنتیکی روند انتخاب طبیعی را شبیه سازی می کنند و این بدان معنی است که گونه هایی که می توانند با تغییرات در محیط خود سازگار شوند قادر به زنده ماندن و تولید مثل و رفتن به نسل بعدی هستند. به عبارت ساده تر ، آنها “بقای اصلح” را در بین افراد نسل متوالی برای حل مسئله شبیه سازی می کنند. هر نسل متشکل از جمعیتی از افراد است و هر فرد نقطه ای از فضای جستجو و راه حل ممکن را نشان می دهد. هر فرد به عنوان رشته ای از کاراکتر / عدد صحیح / شناور / بیت نمایش داده می شود. این رشته مشابه Chromosome است.
بنیاد الگوریتم های ژنتیکی
الگوریتم های ژنتیکی مبتنی بر قیاس با ساختار ژنتیکی و رفتار کروموزوم جمعیت است. در زیر پایه GAs مبتنی بر این قیاس- افراد در جمع برای منابع و همسران رقابت می کنند
آن دسته از افرادی که موفق هستند (صالح ترین) پس از آن جفت گیری می کنند تا فرزندان بیشتری را نسبت به دیگران ایجاد کنند
ژنهای والدین “مناسب ترین” در سراسر نسل تبلیغ می شوند ، یعنی بعضی اوقات والدین فرزندان به وجود می آورند که بهتر از والدین است.
بنابراین هر نسل موفق برای محیط خود مناسب تر است.
فضای جستجو
جمعیت افراد در فضای جستجو حفظ می شود. هر یک از افراد برای حل مسئله ، راه حل در فضای جستجو را نشان می دهند. هر فرد به عنوان یک وکتور طول محدود (شبیه به کروموزوم) از اجزای کدگذاری می شود. این مؤلفه های متغیر شبیه Genes هستند. بنابراین یک کروموزوم (فردی) از چندین ژن (اجزای متغیر) تشکیل شده است.
نمره تناسب اندام
تناسب اندام به هر فرد داده می شود که توانایی یک فرد در “رقابت” را نشان می دهد. فرد دارای نمره تناسب اندام مطلوب (یا نزدیک به مطلوب) مورد جستجو قرار می گیرد.
افراد دارای مدرک دانشگاهی ، تعداد n افراد (کروموزوم / راه حل ها) را به همراه نمرات تناسب اندام خود حفظ می کنند. به افراد دارای نمرات تناسب اندام بهتر فرصت بیشتری برای تولید مثل از دیگران می دهند. افراد با نمرات تناسب اندام بهتری انتخاب می شوند که با ترکیب کروموزوم والدین فرزندان بهتری حاصل می شوند. اندازه جمعیت ایستا است بنابراین باید اتاق برای ورودهای جدید ایجاد شود. بنابراین ، برخی از افراد می میرند و با ورود جدید جایگزین می شوند و سرانجام هنگامی که تمام فرصت جفت گیری از جمعیت قدیمی خسته می شود ، نسل جدیدی ایجاد می شوند. امید است که در طول نسل های بعدی ، راه حل های بهتری حاصل شود ، در حالی که حداقل مناسب می میرند.
هر نسل جدید به طور متوسط ”ژنهای بهتری” از نسلهای قبل دارند. بنابراین ، هر نسل جدید “راه حلهای جزئی” بهتری نسبت به نسلهای گذشته دارند. هنگامی که فرزندان تولید شده هیچ تفاوت معنی داری با فرزندان حاصل از جمعیت قبلی ندارند ، جمعیت همگرا می شود. گفته می شود که این الگوریتم به مجموعه ای از راه حل های مسئله همگرا شده است.
عملگرهای الگوریتم های ژنتیک
پس از ایجاد نسل اولیه ، الگوریتم با استفاده از عملگرهای زیر ، نسل را تکامل می بخشد –
1) عملگر انتخاب: ایده این است كه به افراد دارای نمرات تناسب اندام مناسب ترجیح داده و به آنها اجازه دهیم كه ژن ها را در آنجا به نسل های متوالی منتقل كنند.
2) اپراتور متقاطع: این نشان دهنده جفت گیری بین افراد است. دو نفر با استفاده از اپراتور انتخاب و سایت های متقاطع به طور تصادفی انتخاب می شوند. سپس ژنهای موجود در این سایتهای متقاطع رد و بدل می شوند و بدین ترتیب فرد کاملاً جدیدی (فرزندان) ایجاد می شوند. مثلا –
3) عملگر جهش: ایده اصلی درج ژن های تصادفی در فرزندان برای حفظ تنوع در جمعیت برای جلوگیری از همگرایی زودرس است. مثلا –
کل الگوریتم را می توان به صورت خلاصه کرد –
1) به طور تصادفی جمعیت های اولیه را ص
2) تناسب اندام جمعیت را تعیین کنید
3) تکرار همگرایی تا زمانی که تکرار شود:
الف) والدین را از جمعیت انتخاب کنید
ب) متقاطع و ایجاد جمعیت جدید
ج) جهش روی جمعیت جدید را انجام دهید
د) تناسب اندام برای جمعیت جدید
مشکل و راه حل مثال با استفاده از الگوریتم های ژنتیک
با توجه به یک رشته هدف ، هدف تولید رشته هدف با شروع از یک رشته تصادفی با همان طول است. در اجرای زیر ، قیاس های زیر ساخته شده است –
شخصیت های A-Z ، a-z ، 0-9 و سایر نمادهای ویژه به عنوان ژن در نظر گرفته می شوند
رشته ایجاد شده توسط این شخصیت ها به عنوان کروموزوم / راه حل / فردی در نظر گرفته می شود
تناسب اندام تعداد کاراکترهایی است که در یک شاخص خاص با کاراکترهای رشته هدف متفاوت است. بنابراین به فردی که از ارزش آمادگی کمتری برخوردار باشد ، اولویت بیشتری دارد.