الگوریتم ژنتیک
از ویکیپدیا، دانشنامهٔ آزاد.
الگوریتم ژنتیک (Genetic Algorithm - GA) تکنیک جستجویی در علم رایانه برای یافتن راهحل تقریبی برای بهینهسازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیکهای زیستشناسی فرگشتی مانند وراثت و جهش استفاده میکند.
الگوریتمهای ژنتیک معمولاً به عنوان یک شبیهساز کامپیوتر که در آن جمعیت یک نمونهٔ انتزاعی (کروموزومها) از نامزدهای راهحل یک مسأله بهینهسازی به راه حل بهتری منجر شود، پیادهسازی میشوند. به طور سنتی راهحلها به شکل رشتههایی از ۰ و ۱ بودند، اما امروزه به گونههای دیگری هم پیادهسازی شدهاند. فرضیه با جمعیتی کاملاً تصادفی منحصر بفرد آغاز میشود و در نسلها ادامه مییابد. در هر نسل گنجایش تمام جمعیت ارزیابی میشود، چندین فرد منحصر در فرایندی تصادفی از نسل جاری انتخاب میشوند (بر اساس شایستگیها) و برای شکل دادن نسل جدید، اصلاح میشوند (کسر یا دوباره ترکیب میشوند) و در تکرار بعدی الگوریتم به نسل جاری تبدیل میشود.
[ویرایش] عملگرهای یک الگوریتم ژنتیک
در هر مسئله قبل از آنکه بتوان الگوریتم ژنتیک را برای یافتن یک پاسخ به کار برد به دو عنصر نیاز است: اول روشی برای ارائه یک جواب به شکلی که الگوریتم ژنتیک بتواند روی آن عمل کند لازم است. به شکل سنتی یک جواب به صورت یک رشته از بیتها، اعداد یا نویسهها.نمایش داده میشود.دوم روشی لازم است که بتواند کیفیت هر جواب پیشنهاد شده را با استفاده از توابع تناسب محاسبه نماید. مثلاً اگر مسئله هر مقدار وزن ممکن را برای یک کوله پشتی مناسب بداند بدون اینکه کوله پشتی پاره شود، (مسئله کوله پشتی را ببینید) یک روش برای ارائه پاسخ میتواند به شکل رشته ای از بیتهای ۰ و۱ در نظر گرفته شود, که ۱ یا ۰ بودن نشانه اضافه شدن یا نشدن وزن به کوله پشتی است.تناسب پاسخ، با تعیین وزن کل برای جواب پیشنهاد شده اندازه گیری میشود.
الگوریتم ژنتیک : الگوریتم ژنتیک که بهعنوان یکی از روشهای تصادفی بهینه یابی شناخته شده, توسط جان هالند در سال ۱۹۶۷ ابداع شدهاست. بعدها این روش با تلاشهای گلدبرگ ۱۹۸۹, مکان خویش را یافته و امروزه نیز بواسطه تواناییهای خویش , جای مناسبی در میان دیگر روشها دارد. روال بهینه یابی در الگوریتم ژنتیک براساس یک روند تصادفی- هدایت شده استوار میباشد. این روش , بر مبنای نظریه تکامل تدریجی و ایدههای بنیادین داروین پایه گذاری شدهاست.در این روش , ابتدا برای تعدادی ثابت که جمعیت نامیده میشود مجموعهای از پارامترهای هدف بصورت اتفاقی تولید میشود , پس از اجرای برنامه شبیه ساز عددی را که معرف انحراف معیار و یا برازش آن مجموعه از اطلاعات است را به آن عضو از جمعیت مذکور نسبت میدهیم. این عمل را برای تک تک اعضای ایجاد شده تکرار میکنیم , سپس با فراخوانی عملگرهای الگوریتم ژنتیک از جمله لقاح , جهش و انتخاب نسل بعد را شکل میدهیم و این روال تا ارضای معیار همگرایی ادامه داده خواهد شد.
بصورت متداول سه معیار بهعنوان معیار توقف شمرده میشود: I. زمان اجرای الگوریتم II. تعداد نسلهایی که ایجاد میشوند III. همگرایی معیار خطا
کاربردهای الگوریتم ژنتیک :
- روندیابی هیدرولوژیکی رواناب جاری در شبکه رودخانه خشک
- کمک در حل مسایل تصمیم گیری چند معیاره
- بهینه سازی چند هدفه در مدیریت منابع آبی
[ویرایش] مراجع
- J. H. Holland, Adoption in Natural and Artificial Systems, University of Michigan, Ann Arbor, 1975.
- D. T. Pham and D. Karaboga, Intelligent Optimization Techniques, Springer, 2000.
پیوند به بیرون هوش مصنوعی و سیستمهای هوشمند ایران