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

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

اساس الگوریتم های ژنتیک چیست؟

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

الگوریتم ژنتیک چگونه کار می کند؟

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

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

پنج مرحله وجود دارد که کل فرآیند نحوه عملکرد این الگوریتم را نشان می دهد.

۱. مقداردهی اولیه

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

۲. تابع فیتنس

تابع فیتنس الگوریتم ژنتیک توانایی فرد را برای رقابت با افراد دیگر تعیین می کند. امتیازی را برای هر فردی فراهم می کند که احتمال انتخاب شدن او برای فرآیند تولید مثل را تعیین می کند.
هر چه نمره تابع فیتنس بالاتر باشد، شانس انتخاب فرد برای تولید مثل بیشتر است.

۳. انتخاب

در این مرحله، از بین تمامی مراحل الگوریتم ژنتیک، افراد با چیدمان دوتایی برای تولید نسل انتخاب می شوند. سه نوع روش انتخاب در این فرآیند مورد استفاده قرار می گیرد که در زیر ذکر شده است.

Rank based selection
Tournament selection
Roulette wheel selection

۴. تولید مثل

در مرحله بازتولید، الگوریتم ژنتیک از دو عملگر تغییر استفاده می کند. اینها برای جمعیت والدین اعمال می شود. این دو عملگر عبارتند از:

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

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

۵. Termination

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

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

۱. شبکه های عصبی

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

۲. داده کاوی و خوشه بندی

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

۳. پردازش تصویر

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

۴. شبکه حسگر بی سیم

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

۵. مسئله فروشنده دوره گرد (TSP)

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

منبع

مقالات بیشتر