معرفی ساده و مختصری از الگوریتم ژنتیک – علیرضا محمودی فرد

به گزارش کلام ماندگار، از سال ۱۹۶۰ تقلید از موجودات زنده برای استفاده در الگوریتم‌های قدرتمند برای مسائل بهینه‌سازی، مورد توجه محققان قرار گرفت که تکنیک‌های محاسبات تکاملی نام گرفتند. الگوریتم ژنتیک، اولین بار توسط جان هالند و همکارانش در دانشگاه میشیگان در سال ۱۹۶۵-۱۹۶۲ ضمن درسی که تحت‌عنوان سیستم‌های تطبیقی ارائه می‌داد، مطرح شد؛ آنان در تحقیقات خود به فرآیند سازگاری در سیستم‌های طبیعی توجه نمودند و برای مدل‌سازی آن در سیستم‌های مصنوعی، که باید دارای توانایی‌های سیستم‌های طبیعی باشند، تلاش کردند؛ نتیجه‌ی این تلاش‌ها، پیدایش الگوریتم ژنتیک بود؛ سپس در سال ۱۹۷۵ مبانی ریاضی آن در کتاب سازگاری در سیستم طبیعی و مصنوعی توسط هالند منتشر شد؛ در ادامه، گولدبرگ در سال ۱۹۸۶ آن را توسعه داد.

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

الگوریتم‌ ژنتیک، در واقع خانواده‌ای از «مدل‌های محاسباتی» است که از مفهوم «تکامل» الهام گرفته‌ شده‌اند؛ این دسته از الگوریتم‌ها، «جواب‌های محتمل» یا «جواب‌های کاندیدا» و یا «فرضیه‌های محتمل»  برای یک مسأله خاص را در یک ساختار داده‌ای «کروموزوم مانند» کدبندی می‌کنند. الگوریتم ژنتیک از طریق اعمال «عملگرهای بازترکیب» روی ساختارهای داده‌ای کروموزوم مانند، اطلاعات حیاتی ذخیره شده در این ساختارهای داده‌ای را حفظ می‌کند؛ همچنین با جهش ژنتیکی روی کروموزوم‌ها، امکان فرار از نقاط بهینه محلی ایجاد خواهد شد. انتخاب، بازترکیب و جهش، مهم‌ترین عملگرهایی هستند که می‌توانند تفاوت‌ها را ایجاد کنند.

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

پیاده‌سازی الگوریتم ژنتیک، معمولا با تولید جمعیتی از کروموزوم‌ها آغاز می‌شود؛ جمعیت اولیه از کروموزوم‌ها در الگوریتم‌های ژنتیک، معمولا به‌صورت تصادفی تولید می‌شود و مقید به حد بالا و پایین متغیرهای مسأله هستند؛ در مرحله بعد، ساختارهای داده‌ای تولید شده (کروموزوم‌ها) «ارزیابی» می‌شوند و کروموزوم‌هایی که به‌شکل بهتری می‌توانند «جواب بهینه» مسأله مورد نظر (هدف) را نمایش دهند، شانس بیشتری برای «تولید مثل» نسبت به جواب‌های ضعیف‌تر پیدا می‌کنند؛ یعنی فرصت‌های تولید مثل بیشتری به این دسته از کروموزوم‌ها اختصاص داده می‌شود. میزان «خوب بودن» یک جواب، معمولا نسبت به جمعیت جواب‌های کاندید فعلی سنجیده می‌شود.

علیرضا محمودی‌فرد – محققِ حوزه بهینه‌سازی