آشنایی با الگوریتم های ژنتیک (GA : Genetic algorithm )

نگاه به طبیعت همواره الهام بخش بشر برای حل مسائلی که با آن مواجه می‌شود، بوده است. یکی از روش‌ های حل مسائل بدون اینکه درگیر پیچیدگی ذات مسائل شد، استفاده از الگوریتم ژنتیک است. الگوریتم ژنتیک یکی از الگوریتم‌های پرکاربرد و شناخته شده در عمل بهینه‌سازی است. این الگوریتم بر گرفته از نظریه تکامل داروین می‌باشد، که در آن افراد قوی تر و برازنده تر شانس بیشتری برای تولید و گسترش نسل خود دارند. بر همین اساس آقای جان هنری هلند در سال ۱۹۷۵ میلادی الگوریتمی نوین ارائه داد، که تحت عنوان الگوریتم ژنتیک شناخته شد. گرچه این الگوریتم در ابتدای کار صرفا برای بهینه سازی های باینری بوده است، اما بعدها شکل بهبود یافته آن برای حل مسائل گسترده ای به کار رفت. و هم چنان یکی از الگوریتم‌ های بهینه سازی پرطرفدار بین محققان می‌باشد. الگوریتم ژنتیک با توجه به عملگرهایی که دارد، به خوبی می‌تواند برای مسائل بهینه‌ سازی پیوسته و گسسته به کار رود.

روند اجرای GA که پایه الگوریتم‌ های تکاملی است به صورت شکل ۱ زیر است:

اجزای اصلی Genetic algorithm به صورت زیر است

_ بازنمایی محیط
_ تابع ارزیابی
_ جمعیت (مجموعه‌ای از جواب‌ها)
_ فرآیند انتخاب والدین
_ عملگرهای ایجاد تنوع (تولید نسل)
_ فرآیند انتخاب زنده‌ها (انتخاب افراد بهتر جهت ساخت نسل بعد)
_ شرط توقف

سازماندهی ژنتیک

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

برخی از روش هایی معمول مورد استفاده در سازماندهی ژنتیک عبارتند از:

• آرایه ها دودویی
• درخت ژنتیک
• درخت تجزیه
• درخت دودویی
• زبان طبیعی

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

• الگوریتم های ژنتیک ترکیبی
• الگوریتم های ژنتیک موازی
• الگوریتم های ژنتیک هیبرید
• الگوریتم های ژنتیک خودسازمان
• الگوریتم های ژنتیک خودسازمان یکپارچه شده (Integrated Adaptive GA)
• الگوریتم های ژنتیک آشفته
• الگوریتم های ژنتیک زایشی (GGA)
• الگوریتم های ژنتیک حالت دائمی (SSGA)

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

برخی از مزایای GA عبارتند از:

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

برخی از کاربردهای GA ( Genetic algorithm ) :

_ حل مساله ۸ وزیر
_ انتخاب ویژگی برای طبقه بندی و رگرسیون
_ بهینه‌ سازی توابع مهندسی
_ بهینه سازی مسائل گسترده ریاضی و مهندسی
_ بهینه سازی شبکه‌ های عصبی
_ کاهش ابعاد مجموعه داده ها
_ بهینه سازی توابع بنچمارک (پایه) cec 2013
_ بهینه سازی توابع بنچمارک (پایه) cec 2012
_ بهینه سازی توابع بنچمارک (پایه) cec 2014
_ بهینه سازی توابع بنچمارک (پایه) cec 2015
_ حل مسائل زمانبندی با استفاده از الگوریتم‌های تکاملی
_ مسئله فروشنده دوره گرد با الگوریتم ژنتیک
_ پیدا کردن مینیمم تابع اکلی (Ackley)
_ حل مربع جادویی
_ محاسبه ی مینیمم تابع
_ حل مسئله Maze

وب سایت مطلب دی ال با انجام پروژه های ژنتیک در خدمت کاربران عزیز می باشد .