الگوریتم ژنتیک چیست؟ کاربردها و چند مثال

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

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

الگوریتم ژنتیک دارای یک‌سری ویژگی‌هایی است که نسبت به باقی روش‌ها و الگوریتم‌های قدیمی ریاضی، به عنوان یک روش دارای مزیت خود را معرفی می‌کند که به چند مورد آن اشاره می‌کنیم.

• الگوریتم ژنتیک به جای یک پاسخ مجموعی‌ای از پاسخ‌ها را می‌دهد.
• الگوریتم ژنتیک به جای قوانین قطعی، از قوانین احتمالی استفاده می‌کند و بر پایه احتمالات فعالیت می‌کند.
• این الگوریتم برخلاف تابع‌های کلاسیک ریاضی، برای بهینه‌سازی نیازی به مشتق تابع هدف ندارد.

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

الگوریتم ژنتیک خود به دو حالت باینری و پیوسته قابل پیاده سازی است.

تابع شایستگی در الگوریتم ژنتیک

در ابتدا گفته شد که برای بررسی کروموزوم‌ها یا همان راه‌حل‌های تصادفی ایجاد شده، از تابع شایستگی استفاده می‌شود. این تابع با نام تابع برازش نیز شناخته می‌شود. برای حل هر مسئله بهینه‌سازی باید در ابتدا یک تابع ساخته شود. در حقیقت این تابع در برابر بررسی هر راه‌حل ایجاد شده، یک عدد غیر منفی جواب می‌دهد که به ما میزان توانایی راه‌حل ایجاد شده در بهینه‌سازی مسئله را نشان می‌دهد.

در اینجا سوال پیش میاید که آیا تابع شایستگی همان تابع هدف است؟ در بسیاری از مسائل این دو مورد یکی هستند، اما در برخی موارد نیز نیاز است تا در ابتدا یک تابع شایستگی تعریف شود.

آشنایی با مفاهیم مورد نیاز در الگوریتم ژنتیک

قبل از آشنایی با روند پیاده‌سازی و فرآیند الگوریتم ژنتیک بهتر است با چند مفهوم ساده در این مسیر آشنا شویم.

کروموزوم

در الگوریتم ژنتیک هر کروموزوم نشان‌دهنده یک جواب برای مسئله مورد نظر است.

ژن

هر ژن بیانگر یک متغیر و پارامتر در مسئله است. هر کروموزوم از تعداد زیادی ژن تشکیل شده است.

تولید مثل

در الگوریتم ژنتیک برای ایجاد نسل بعد و جدید از تولید مثل استفاده می‌شود. در این مرحله تعدادی از کروموزوم‌ها انتخاب می‌شوند تا با ترکیب نسل جدید را ایجاد کنند. به کروموزوم‌‌‌‌‌‌های انتخاب شده والد می‌گویند. برای ترکیب از ۳ عملگر زیر استفاده می‌شود. که جلوتر با این موارد بیشتر آشنا می‌شویم.

• انتخاب
• ترکیب
• جهش

عملگر انتخاب

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

عملگرهای انتخاب مختلفی وجود دارد که در این قسمت به چند عدد از آن‌ها اشاره می‌شود.

• انتخاب تورنومنت
• انتخاب رتبه‌ای
• روش مقیاس کردن شایستگی
• انتخاب رولت

عملگر ترکیب

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

• ترکیب چند والدی
• ترکیب مخلوط
• ترکیب جهت‌دار
• ترکیب یک نقطه‌ای
• ترکیب دو نقطه‌ای
• ترکیب چند نقطه‌ای

عملگر جهش

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

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

الگوریتم ژنتیک از مراحل زیر تشکیل شده است:

• START 
• Generate the initial population
• Compute fitness
• REPEAT
• Selection
• Crossover
• Mutation
• Compute fitness
• UNTIL population has converged
• STOP

اگر بخواهیم به زبان فارسی این مراحل را خلاصه کنیم به شکل زیر خواهد بود.

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

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

الگوریتم ژنتیک در محدوده بسیار بزرگ و متنوعی استفاده می‌شوند. در این قسمت به چند نمونه از آن اشاره می‌کنیم.

یادگیری ماشین

الگوریتم‌های ژنتیک به ویژه در بهینه‌سازی پارامترهای مدل در ماشین لرنینگ کاربرد زیادی دارند. همچنین از این الگوریتم، در بهینه‌سازی هایپر پارامترها مانند نرخ یادگیری، پارامترهای منظم سازی و معماری شبکه در شبکه های عصبی استفاده می‌شود. 

پردازش تصویر و سیگنال

در پردازش تصویر و سیگنال و همچنین کارهایی مانند حذف نویز، بازسازی تصویر و یا تشخیص الگو از از الگوریتم‌های ژنتیک استفاده می‌شود.

بیشتر بدانید: تشخیص چهره با متلب

مدل‌سازی‌های مالی

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

مثال‌هایی از الگوریتم ژنتیک در شرکت‌های بزرگ

امروزه در بسیاری از شرکت‌های دنیا در حوزه‌های متفاوت در فرآیند تولید محصول و یا خدمت‌رسانی، از الگوریتم‌های ژنتیک استفاده می‌شود. تعدادی از معروف‌ترین‌ها در این قسمت ذکر شده‌اند:

برنامه خودران تسلا

تسلا؛ شرکت ساخت و تولید خودروهای برقی و الکتریک با استفاده از الگوریتم ژنتیک توانسته است به این امکان دست پیدا کند که به وسیله بهینه‌سازی شبکه عصبی بتواند خودروهایی را تولید کند که به صورت خودران در شهر تردد کنند.

زنجیره تامین تویوتا

کمپانی بزرگ خودروسازی تویوتا با استفاده از الگوریتم ژنتیک، زنجیره تامین خود در سراسر جهان را بهینه‌سازی می‌کند و با استفاده از آن به مدیریت موجودی و بهینه‌سازی برنامه فروش خود می‌پردازد.

جمع‌بندی

الگوریتم‌های مختلفی برای بهینه‌سازی وجود دارد، از الگوریتم بهینه‌سازی فاخته گرفته تاالگوریتم ژنتیک. الگوریتم ژنتیک یکی از بهترین راه‌ها برای بهینه‌سازی پاسخ و پیدا کردن مجموعه‌ای از جواب‌ها برای مسائل مختلف است. این الگوریتم می‌تواند در حوزه‌های مختلف استفاده شود و به ما در پیشبرد مسائل کمک کند.