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

از ویکی‌پدیا، دانشنامهٔ آزاد.

الگوریتم ژنتیک (Genetic Algorithm - GA) تکنیک جستجویی در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیکهای زیست‌شناسی فرگشتی مانند وراثت و جهش استفاده می‌کند.


فهرست مندرجات

[ویرایش] تاریخچه

از سال 1960 علاقه زیادی برای توسعه دادن الگوریتم های قدرتمند برای حل مسائل بهینه سازی مشکل بوجود آمد.

واژه ای که به طور معمول برای اشاره به چنین روشهایی مورد استفاده قرار گرفت، واژه محاسبات تحولی (1) می باشد. بهترین الگوریتم های معرف در این گروه شامل الگوریتم ژنتیک (توسعه داده شده توسط هلند) ، استراتژی های تحول (توسعه داده شده توسط رچنبرگ)، برنامه ریزی تحولی (توسعه داده شده توسط فوگل)، برنامه ریزی ژنتیک (توسعه داده شده توسط کزا) می باشند.

الگوریتم های ژنتیک به عنوان روشهای بهینه سازی و جستجوی احتمالی با کاربرد بسیار وسیع و قوی، امروزه به عنوان وسیعترین روشهای محاسبات تحولی می باشند.

الگوریتم ژنتیک از اوایل سال 1970 با تلاش های بسیار آقای جان هلند و شاگردانش پا به عرصه وجود گذاشت.

[ویرایش] الگوریتم ژنتیک در علوم رایانه ای

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

[ویرایش] عملگرهای یک الگوریتم ژنتیک

در هر مسئله قبل از آنکه بتوان الگوریتم ژنتیک را برای یافتن یک پاسخ به کار برد به دو عنصر نیاز است:در ابتدا روشی برای ارائه یک جواب به شکلی که الگوریتم ژنتیک بتواند روی آن عمل کند لازم است. در روش سنتی یک جواب به صورت یک رشته از بیتها، اعداد یا نویسهها نمایش داده می‌شود.دومین جزء اساسی الگوریتم ژنتیک روشی است که بتواند کیفیت هر جواب پیشنهاد شده را با استفاده از توابع تناسب محاسبه نماید. مثلاً اگر مسئله هر مقدار وزن ممکن را برای یک کوله پشتی مناسب بداند بدون اینکه کوله پشتی پاره شود، (مسئله کوله پشتی را ببینید) یک روش برای ارائه پاسخ می‌تواند به شکل رشته ای از بیتهای ۰ و۱ در نظر گرفته شود, که ۱ یا ۰ بودن نشانه اضافه شدن یا نشدن وزن به کوله پشتی است.تناسب پاسخ، با تعیین وزن کل برای جواب پیشنهاد شده اندازه گیری می‌شود.


[ویرایش] اجزائ الگوریتم ژنتیک

روال بهینه یابی در الگوریتم ژنتیک براساس یک روند تصادفی- هدایت شده استوار می‌باشد. این روش , بر مبنای نظریه تکامل تدریجی و ایده‌های بنیادین داروین پایه گذاری شده‌است.در این روش , ابتدا برای تعدادی ثابت که جمعیت نامیده می‌شود مجموعه‌ای از پارامترهای هدف بصورت اتفاقی تولید می‌شود , پس از اجرای برنامه شبیه ساز عددی را که معرف انحراف معیار و یا برازش آن مجموعه از اطلاعات است را به آن عضو از جمعیت مذکور نسبت می‌دهیم. این عمل را برای تک تک اعضای ایجاد شده تکرار می‌کنیم , سپس با فراخوانی عملگرهای الگوریتم ژنتیک از جمله لقاح , جهش و انتخاب نسل بعد را شکل می‌دهیم و این روال تا ارضای معیار همگرایی ادامه داده خواهد شد.

به طور کلی، یک الگوریتم ژنتیک دارای پنج قسمت اصلی می باشد:

1- نمایش اعضاء در الگوریتم ژنتیک

2- روش ایجاد یک جمعیت اولیه

3- تابع ارزیابی برای محاسبه نرخ شایستگی هر عضو

4- عملگرهای ژنتیک که باعث ترکیب ساخت ژنتیکی فرزندان در طول تولید مثل می شوند.

5- مقادیر مربوط به پارامتر های الگوریتم ژنتیک


[ویرایش] کاربردهای الگوریتم ژنتیک

  • روندیابی هیدرولوژیکی روان آب جاری در شبکه رودخانه خشک
  • کمک در حل مسایل تصمیم گیری چند معیاره
  • بهینه سازی چند هدفه در مدیریت منابع آبی
  • بهینه سازی و بارآرایی شبکه های توزیع نیروی برق

و...


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