الگوریتم فرگشتی

از ویکی‌پدیا، دانشنامهٔ آزاد
(تغییرمسیر از الگوریتم تکاملی)
پرش به: ناوبری، جستجو

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

الگوریتم‌های فرگشتی به طور اساسی با دیگر روش‌های بهینه‌سازی و جستجوی مرسوم قدیمی تفاوت دارند. برخی از این تفاوت‌ها عبارتند از:

  • الگوریتم‌های فرگشت‌پذیر تنها یک تک نقطه را جستجو نمی‌کنند بلکه جمعیتی از نقاط را به صورت موازی بررسی می‌نمایند.
  • الگوریتم‌های فرگشت‌پذیر نیاز به اطلاعاتی ضمنی و دیگر دانش‌های مکمل ندارند؛ تنها تابع هدف و شایستگی مربوطه در جهت‌های جستجو تأثیر گذارند.
  • الگوریتم‌های فرگشت‌پذیر از قوانین در حال تغییر احتمالی بهره می‌برند و نه موارد مشخص و معین.
  • استفاده از الگوریتم‌های فرگشت‌پذیر به طور کلی خیلی سر راست است، زیرا هیچگونه محدودیت‌هایی برای تعریف تابع هدف وجود ندارد.
  • الگوریتم‌های فرگشت‌پذیر تعداد زیادی از پاسخ‌های قابل قبول را بدست می‌دهند و انتخاب پایانی بر عهده کاربر است؛ لذا در مواردی که مسئله مورد نظر شامل یک پاسخ مفرد نمی‌باشد، مثلاً خانواده‌ای از پاسخ‌های بهینه-پَرِتو، مشابه آنچه در بهینه‌سازی چند هدفه و مسائل زمان‌بندی وجود دارد. الگوریتم‌های فرگشتی برای شناسایی این پاسخ‌های چندگانه به طور همزمان ذاتاً کارآمدند.

الگوریتم‌های فرگشتی عبارتند از:

روش[ویرایش]

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

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

حوزه‌های کاربردی[ویرایش]

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

منابع[ویرایش]

  • Ashlock، D. (۲۰۰۶)، Evolutionary Computation for Modeling and Optimization، Springer، ISBN

۰-۳۸۷-۲۲۱۹۶-۴.

  • Bäck، T. (۱۹۹۶)، Evolutionary Algorithms in Theory and Practice: Evolution Strategies، Evolutionary Programming، Genetic Algorithms، Oxford Univ. Press.