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

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

معرفی‌شده توسط
Holland, J. H.
سال
1975
نوع
Stochastic evolutionary metaheuristic
خانواده
Simulation / optimization

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

اندازه قلم

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

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

شهود پشت روش

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

تاریخ

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

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

هنگامی از الگوریتم ژنتیک تصادفی استفاده کنید که: (۱) فضای جستجو بزرگ، چندوجهی، یا ناپیوسته باشد و روش‌های مبتنی بر گرادیان شکست بخورند یا قابل‌اجرا نباشند؛ (۲) تابع هدف جعبه سیاه، نویزی، یا ارزیابی آن پرهزینه باشد اما برای نمونه‌برداری در سطح جمعیت قابل‌مدیریت باشد؛ (۳) مسائل ترکیبی یا مختلط صحیح، حل‌کننده‌های دقیق کارآمدی نداشته باشند؛ (۴) یک راه‌حل نزدیک به بهینه که در تعداد معقولی از ارزیابی‌ها یافت می‌شود، قابل‌قبول باشد. از SGA استفاده نکنید زمانی که: مسئله محدب باشد یا گرادیان در دسترس و ارزان باشد — بهینه‌سازی کلاسیک سریع‌تر همگرا می‌شود؛ زمانی که ارزیابی تابع فوق‌العاده پرهزینه است (ده‌ها یا صدها)، روش‌های مبتنی بر جمعیت ممکن است بودجه را تمام کنند؛ یا زمانی که یک راه‌حل بهینه قابل‌اثبات مورد نیاز است، زیرا الگوریتم‌های ژنتیک هیچ تضمینی برای بهینگی ارائه نمی‌دهند.

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

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

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

نقاط قوت

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

کاربردها

  • زمان‌بندی شغل-کارگاه و جریان-کارگاه در تولید و لجستیک
  • انتخاب ویژگی و تنظیم ابرپارامترها در خطوط لوله یادگیری ماشین
  • بهینه‌سازی سازه و توپولوژی در مهندسی مکانیک و عمران
  • مسائل فروشنده دوره‌گرد و مسیریابی وسایل نقلیه در تحقیق در عملیات
  • پیش‌بینی ساختار پروتئین و کشف دارو در بیوانفورماتیک
  • جستجوی معماری شبکه عصبی و بهینه‌سازی وزن

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

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

1

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

2

براى هر فرد در جمعیت، با استفاده از تابع هدف (یا یک جایگزین)، برازش f(x_i) را محاسبه کنید. برازش کیفیت راه‌حل را کمی می‌کند؛ برازش بالاتر به معنای راه‌حل بهتر است. برای مسائل کمینه‌سازی، برازش اغلب به‌عنوان معکوس یا تبدیل تابع هزینه تعریف می‌شود.

فرمول
f(x_i), \quad i = 1, \ldots, N
3

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

فرمول
P(\text{select } x_i) = \frac{f(x_i)}{\sum_{j=1}^{N} f(x_j)}
4

با احتمال p_c (معمولاً 0.6–0.9)، جفت‌های والدین انتخاب‌شده را برای تولید فرزندان ترکیب کنید. تقاطع تک‌نقطه‌ای، دو‌نقطه‌ای یا یکنواخت، مواد ژنتیکی را بین کروموزوم‌های والدین مبادله کرده و فرزندانی ایجاد می‌کند که صفات را از هر دو به ارث می‌برند. این عملگر، بهره‌برداری از بلوک‌های سازنده خوب را هدایت می‌کند.

5

با احتمال کم p_m (معمولاً 0.001–0.05 در هر ژن)، به‌طور تصادفی ژن‌های منفرد را در هر کروموزوم فرزند تغییر دهید. جهش تنوع ژنتیکی را حفظ می‌کند، از همگرایی زودهنگام جلوگیری می‌کند و تضمین می‌کند که الگوریتم می‌تواند از بهینه‌های محلی فرار کند. نرخ جهش یک پارامتر حیاتی است که برای مسئله تنظیم می‌شود.

6

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

دام‌های رایج

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

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

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

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

اندازه جمعیت چقدر باید باشد؟

یک نقطه شروع رایج ۵۰–۲۰۰ فرد برای مسائل با ابعاد متوسط است. جمعیت‌های بزرگتر تنوع را بهبود می‌بخشند و همگرایی زودهنگام را کاهش می‌دهند اما هزینه محاسباتی در هر نسل را افزایش می‌دهند. قوانین سرانگشتی مبتنی بر طول کروموزوم (مانند ۱۰ برابر تعداد ژن‌ها) وجود دارد، اما تنظیم تجربی یا فرا-بهینه‌سازی اغلب ضروری است.

چه زمانی باید بهینه‌سازی ازدحام ذرات یا تبرید شبیه‌سازی شده را به الگوریتم ژنتیک ترجیح دهم؟

بهینه‌سازی ازدحام ذرات (PSO) اغلب در مسائل پیوسته با مقادیر حقیقی سریع‌تر است زیرا از اطلاعات سرعت بهره می‌برد. تبرید شبیه‌سازی شده (SA) پیاده‌سازی ساده‌تری دارد و می‌تواند برای جستجوی مسیر تک‌راه‌حل مؤثر باشد. الگوریتم‌های ژنتیک زمانی ترجیح داده می‌شوند که فضای جستجو ترکیبی باشد، زمانی که تقاطع به‌طور معنی‌داری ساختارهای راه‌حل را ترکیب می‌کند، یا زمانی که تنوع جمعیت برای چشم‌اندازهای چندوجهی ارزشمند است.

آیا الگوریتم ژنتیک تصادفی به مسائل با ابعاد بالا مقیاس‌پذیر است؟

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

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

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

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

منابع

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

    شابک: 978-0262581110
    کپی شد.
  2. Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA.

    شابک: 978-0201157673
    کپی شد.