الگوریتم ژنتیک (GA) یک روش بهینه سازی مبتنی بر جستجو بر اساس اصول ژنتیک و انتخاب طبیعی است. این الگوریتم اغلب برای یافتن راه حل های بهینه یا نزدیک به مطلوب برای مسائل دشوار استفاده می شود که در غیر این صورت برای حل آن زمان بسیاری لازم است. الگوریتم ژنتیک معمولا برای حل مسائل بهینه سازی و یادگیری ماشین استفاده می شود.

مقدمه ای بر بهینه سازی

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

الگوریتم ژنتیک چیست؟

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

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

    GA دارای مزایای مختلف است که آن را بسیار محبوب ساخته است، از آن جمله می توان به موارد زیر اشاره نمود:

  • به هیچ اطلاعات فرعی یا مشتق شده ای نیاز ندارد (که ممکن است برای بسیاری از مشکلات دنیای واقعی در دسترس نباشد).
  • در مقایسه با روش های سنتی سریع تر و کارآمدتر است.
  • قابلیت های موازی بسیار خوبی دارد.
  • در بهینه سازی توابع گسسته و پیوسته و همچنین چند هدفه کاربرد دارد.
  • لیستی از راه حل های “خوب” را ارائه می دهد و نه فقط یک راه حل واحد.
  • همیشه پاسخی برای مساله ارائه می دهد که در طول زمان بهتر می شود.
  • زمانی مفید است که فضای جستجو بسیار بزرگ است و تعداد پارامترهای درگیر زیاد است.

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

    مانند هر تکنیک، GA ها نیز از چند محدودیت رنج می برند که شامل موارد زیر می شود:

  • GA ها برای همه مسائل، مخصوصا مسائل ساده و مسائلی که برای آنها اطلاعات مشتق شده در دسترس هستند مناسب نیستند.
  • مقدار تابع تناسب به طور مکرر محاسبه می شود که این محاسبه ممکن است برای برخی از مسائل هزینه بالایی داشته باشد.
  • به دلیل تصادفي بودن، هيچ تضميني براي بهينه سازي يا کيفيت راه حل وجود ندارد.
  • اگر به درستی اجرا نشود، GA ممکن است به راه حل بهینه همگرا نباشد.

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

الگوریتم های ژنتیک توانایی ارائه راه حل به اندازه کافی خوب را دارند و این باعث جذابیت این الگوریتم ها برای استفاده در حل مسائل بهینه سازی می شود. دلایل اینکه GA ها مورد نیاز هستند عبارتند از:

حل مسائل پیچیده

در علوم کامپیوتر، مسائل بسیاری وجود دارد که NP-Hard هستند. این اساسا بدان معناست که حتی با بهره گیری از سیستم های قدرتمند محاسباتی، زمان بسیار زیادی (حتی سال ها!) برای حل این مسائل موردنیاز است. در چنین سناریویی، GA ها یک ابزار کارآمد برای ارائه راه حل های نزدیک به مطلوب و قابل استفاده در یک زمان کوتاه است.

شکست روش های مبتنی بر گرادینت

روشهای مبتنی بر محسبات سنتی با شروع در یک نقطه تصادفی و با حرکت در جهت گرادیان، تا زمانی که به بالای تپه برسند، کار می کنند. این تکنیک کارآمد است و به خوبی برای توابع هدف تک منظوره مانند تابع هزینه در رگرسیون خطی کار می کند. اما در بیشتر موقعیتهای واقعی دنیا، مسائل بسیار پیچیده وجود دارد که از تعداد بسیاری قله و دره ساخته شده است و باعث می شود که چنین روش هایی شکست بخورند، زیرا آنها از یک گرایش ذاتی به توقف در نقاط بهینه محلی، همانطور که در شکل زیر نشان داده شده است، رنج می برند:
GA Motivation

بدست آوردن سریع راه حل مناسب

بعضی از مسائل دشوار مانند فروشنده دوره گرد (TSP)، دارای کاربردهای بسیاری در دنیای واقعی مانند مسیریابی و طراحی VLSI دارند. در حال حاضر تصور کنید که شما از سیستم ناوبری GPS خود استفاده می کنید و چند دقیقه (یا حتی چند ساعت) طول می کشد تا مسیر «مطلوب» را از منبع به مقصد محاسبه کنید. تاخیر در چنین برنامه های کاربردی دنیای واقعی قابل قبول نیست و بنابراین یک راه حل «خوب و کافی» که «سریع» تحویل داده می شود، چیزی است که مورد نیاز است.

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *