الگوریتم های ژنتیک موازی

الگوریتم های ژنتیک موازی

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

فهرست :

مقدمه

پیدایش الگوریتم ژنتیک و روند اجرای آن

نحوه ی نمایش

گام ارزیابی و گام انتخاب

عملگرهای ژنتیک

سایز جمعیت

پارامترهای crossover 11

Exploration & Exploitation 13

چالشهایی که GA با آن رودررو است

فاکتورهای موثر در PGA 11

یادداشت های تاریخی روی PGA 11

نحوه ی کنترل در سیستمهای موازی

چگونه GA را موازی کنیم

طبقه بندی PGA 16

معیار ارزیابی کارآیی در الگوریتم ژنتیک موازی

نتیجه گیری

منابع و مراجع