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

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


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

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

طبیعت همواره منبع عظیمی از دانش برای انسان بوده است. الگوریتم‌های ژنتیک (GAها)، الگوریتم‌های مبتنی بر جستجو هستند که بر اساس مفاهیم انتخاب طبیعی و علم ژنتیک کار می‌کنند. GAها زیر مجموعه‌ای از روش‌ محاسباتی دیگری هستند که محاسبات تکاملی نامیده می‌شود.
GA توسط John Holland و دانشجویان و همکاران او، به ویژه David E. Goldberg در دانشگاه میشیگان طراحی شده است؛ از آن زمان تا کنون این الگوریتم برای مسائل بهینه‌سازی مختلف بکار رفته است و به میزان موفقیت قابل توجهی دست یافته است.
در الگوریتم ژنتیک، مخزن یا جمعیتی از پاسخ‌های احتمالی برای یک مسئله‌ی مشخص داریم. این پاسخ‌ها سپس تحت فرآیند باز ترکیب {recombination} و جهش {mutation} (همچون علم ژنتیک) قرار می‌گیرند و فرزندان جدیدی تولید می‌کنند؛ این فرآیند بر روی نسل‌های مختلف تکرار می‌شود. به هر فرد (یا پاسخ‌ کاندیدا) یک مقدار صلاحیت (بر اساس مقدار تابع هدف) تخصیص داده می‌شود و به افراد شایسته‌تر شانس بالاتری جهت جفت‌گیری داده می‌شود، و در نتیجه افراد «شایسته‌تری» به وجود می‌آیند. این امر با نظریه‌ی داروین مبنی بر «بقای شایسته‌ترین» سازگار است.
بدین ترتیب، افراد یا پاسخ‌های شایسته‌تر «تکامل» در نسل‌های مختلف پیدا می‌کنند تا زمانی که ضابطه‌ی توقف برآورده شود.
الگوریتم‌های ژنتیک دارای ماهیت به اندازه‌ی کافی تصادفی هستند، اما بسیار بهتر از جستجوی محلی تصادفی کار می‌کنند (در جستجوی محلی تصادفی تنها پاسخ‌های تصادفی مختلف آزمایش می‌شوند، و بهترین پاسخ در نظر گرفته می‌شود)، زیرا در الگوریتم ژنتیک از اطلاعات تاریخی {سابقه} نیز استفاده می‌شود.

مزایای GA

الگوریتم ژنتیک مزایای مختلفی دارند که آنها را بسیار محبوب کرده است. این مزایا عبارتند از:
• به هیچ گونه اطلاعات مشتقه‌ای نیاز ندارند (چنین اطلاعاتی در بسیاری موارد در مسائل واقعی موجود نیست).
• الگوریتم ژنتیک در مقایسه با روش‌های سنتی‌تر سریع‌تر و کارامدتر هستند.
• آنها قابلیت‌های موازی‌کاری بسیاری خوبی دارند.
• الگوریتم ژنتیک توابع پیوسته و توابع گسسته، و همچنین مسائل چند هدفی را بهینه‌ می‌کند.
• بجای تنها یک پاسخ، لیستی از پاسخ‌های «مناسب» ارائه می‌دهد.
• همواره یک پاسخ برای مسئله پیدا می‌کند؛ این پاسخ با گذشت زمان بهتر می‌شود.
• وقتی فضای جستجو بسیار بزرگ است و تعداد زیادی پارامتر درگیر هستند، الگوریتم ژنتیک بسیار کارامد است.

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

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

ترجمه  itrans.ir 

نظرات

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

بیشتر بخوانید