الگوریتم تکاملی

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

الگوریتم‌های تکاملی(به انگلیسی: 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.