Skip to content
بازگشت به نتایج جست‌وجو

الگوریتم ژنتیک — بهینه‌سازی تکاملی

معرفی‌شده توسط
John Henry Holland
سال
1975
نوع
Population-based metaheuristic

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

الگوریتم ژنتیک (GA) یک روش بهینه‌سازی فراابتکاری مبتنی بر جمعیت است که توسط جان هنری هالند (۱۹۷۵) معرفی شد و اصول انتخاب طبیعی را تقلید می‌کند. این الگوریتم جمعیتی از راه‌حل‌های کاندید را حفظ کرده و آن‌ها را به طور تکراری از طریق عملگرهای انتخاب، تقاطع (crossover) و جهش بهبود می‌بخشد، که آن را به ویژه در فضاهای جستجوی ناپیوسته، غیرمحدب و چندوجهی که روش‌های کلاسیک مبتنی بر گرادیان شکست می‌خورند، قدرتمند می‌سازد.

شهود پشت روش

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

تاریخ

الگوریتم ژنتیک توسط جان هنری هالند در کتاب خود در سال ۱۹۷۵ با عنوان «سازگاری در سیستم‌های طبیعی و مصنوعی» معرفی شد که مفهوم شماتیک (بلوک سازنده) را فرموله کرد و تحلیل نظری بنیادی را در مورد اینکه چرا تقاطع و انتخاب، جستجو را به سمت مناطق برازنده‌تر هدایت می‌کنند، ارائه داد. دانشجویان هالند — به ویژه دیوید گلدبرگ — GAها را در دهه ۱۹۸۰ از طریق کاربردهای مهندسی محبوب کردند. کالیانموی دب بعداً چارچوب را به تنظیمات چندهدفه گسترش داد و به الگوریتم NSGA-II که به طور گسترده‌ای پذیرفته شده است (۲۰۰۲) رسید. امروزه GAها ابزار استانداردی در محاسبات تکاملی باقی مانده‌اند و تحقیقات فعالی در روش‌های ترکیبی که جستجوی تکاملی را با پالایش محلی ترکیب می‌کنند، در جریان است.

چه زمانی استفاده شود

الگوریتم‌های ژنتیک زمانی مناسب هستند که فضای جستجو بزرگ، ناپیوسته، غیرقابل تفکیک، یا به شدت چندوجهی باشد — شرایطی که حل‌کننده‌های مبتنی بر گرادیان نمی‌توانند عمل کنند یا در بهینه‌های محلی گیر می‌کنند. آن‌ها برای انواع متغیرهای پیوسته، دسته‌ای، دودویی و ترتیبی اعمال می‌شوند و هیچ فرض نرمال بودن یا توزیعی را تحمیل نمی‌کنند. تنها الزام، یک تابع برازندگی قابل محاسبه است. برای مسائلی که فرمول‌بندی تحلیلی یا محدب وجود دارد، روش‌های کلاسیک (برنامه‌ریزی خطی، نزول گرادیان) سریع‌تر هستند و باید ترجیح داده شوند. تکرارهای کافی (معمولاً بسیار بیشتر از ۱۰۰۰ نسل) برای همگرایی معنی‌دار لازم است؛ اجرای نسل‌های کم، رایج‌ترین حالت شکست است.

محدودیت‌ها و ملاحظات

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

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • کار بر روی چشم‌اندازهای هدف ناپیوسته، غیرقابل تفکیک و چندوجهی که در آن‌ها روش‌های مبتنی بر گرادیان شکست می‌خورند.
  • هیچ فرض توزیعی را تحمیل نمی‌کند — تنها ورودی مورد نیاز یک تابع برازندگی قابل محاسبه است.
  • به طور طبیعی طیف گسترده‌ای از انواع متغیرها را مدیریت می‌کند: پیوسته، دودویی، دسته‌ای و ترتیبی.
  • تنوع جمعیت امکان کاوش همزمان مناطق متعدد فضای جستجو را فراهم می‌کند و خطر به دام افتادن زودرس در بهینه محلی را کاهش می‌دهد.
  • بسیار قابل گسترش: عملگرهای تقاطع و جهش خاص دامنه، مدیریت محدودیت‌ها، و انواع چندهدفه (مانند NSGA-II) در ادبیات به خوبی تثبیت شده‌اند.

کاربردها

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

چگونه کار می‌کند

چگونه کار می‌کند

1

جمعیتی از راه‌حل‌های کاندید (افراد) ایجاد می‌شود که معمولاً به صورت تصادفی در فضای جستجو قرار دارند. هر فرد یک راه‌حل بالقوه را رمزگذاری می‌کند — به عنوان مثال به صورت رشته دودویی، بردار مقادیر حقیقی، یا جایگشت — و اندازه جمعیت پارامتر کلیدی است که تعیین می‌کند فضای جستجو از ابتدا تا چه حد به طور گسترده نمونه‌برداری می‌شود.

2

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

3

افرادی با برازندگی بالاتر به طور ترجیحی برای تبدیل شدن به والدین نسل بعدی انتخاب می‌شوند. مکانیسم‌های رایج انتخاب شامل انتخاب تورنمنت، انتخاب چرخ رولت (متناسب با برازندگی) و انتخاب مبتنی بر رتبه است. فشار انتخاب، تعادل بین بهره‌برداری از راه‌حل‌های با کیفیت بالا و حفظ تنوع جمعیت را کنترل می‌کند.

4

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

5

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

دام‌های رایج

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

پرسش‌های متداول

الگوریتم ژنتیک چگونه با نزول گرادیان متفاوت است؟

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

به چند نسل و چه اندازه جمعیت نیاز دارم؟

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

آیا الگوریتم ژنتیک تضمین می‌کند که بهینه سراسری را پیدا کند؟

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

چه زمانی باید GA را به جای تبرید شبیه‌سازی شده یا بهینه‌سازی ازدحام ذرات انتخاب کنم؟

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

روش‌های مرتبط

منابع

  1. Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.

    باز کردن مرجع انتشار
    کپی شد.
  2. Deb, K. (2001). Multi-Objective Optimization using Evolutionary Algorithms. Wiley.

    شابک: 9780471873396
    کپی شد.