الگوریتم ژنتیک چیست ✔️ آموزش کامل صفر تا 100 + فلوچارت ، عملگرها

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

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

الگوریتم ژنتیک اولین بار توسط جان هلند (Jan Holand) در سال 1970 میلادی یعنی سال 1349 شمسی معرفی شد.

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

ما در ادامه به سوال پرتکرار الگوریتم ژنتیک چیست؟ پاسخ خواهیم داد و صفر تا 100 این الگوریتم را بررسی خواهیم کرد.

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

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

دانشمندی بنام جان هنلد با تکیه بر نظریه تکامل وراتثی ، نظریه انتخاب طبیعی و نحوه انتقال خصوصیات از والدین به فرزندان ،

در انسان، و فرموله کردن این رفتارها ، به یک الگوریتم برای حل مسئله رسید که نام آن را Genetic Algorithm گذاشت.

الگوریتم وراثتی (الگوریتم ژنتیک) در سال 1962 توسط جان هلند ارائه شد و در دهه 60 و 70 میلادی با تلاش وی و شاگردانش، در دانشگاه میشیگان آمریکا توسعه پیدا کرد.

کتاب جان هلند با نام “سازش در سیستم های طبیعی و مصنوعی” در سال 1975 منتشر شد و یکی از مراجع اصلی در مبحث الگوریتم وراثتی یا ژنتیک می باشد.

در سال 1992 مقاله ای توسط دی جانگ، با عنوان “الگوریتم وراثتی بهینه ساز تابع نیست ” ارائه شد. که بیان میکرد که الگوریتم ژنتیک فقط یک بهینه ساز برا حل توابع ریاضی نیست بلکه توانایی بسیاری برای حل مسائل مختلف دنیای واقعی دارد.

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

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

• الگوریتم ژنتیک ، یک جستجوگر موازی است و جستجو را با مجموعه ای از راه حل ها شروع میکند.
• الگوریتم وراثتی ، بر پایه احتمالات عمل میکند و برای تولید نسل بعدی از توانین اتفاقی به جای قوانین قطعی استفاده میکند.
• الگوریتم GA به مشتق تابع هدف نیازی ندارد. (بر خلاف روشهای کلاسیک ریاضی ، برای بهینه سازی تابع ).
• الگوریتم ژنتیک قادر است که پاسخ بهینه را برای بسیاری از مسائل Np-Hard را بیابد.
• این الگوریتم ، قابلیت پیاده سازی با سخت افزارهای موازی را دارد.
• الگوریتم وراثتی یا ژنتیک ، قادر به ارائه مجموعه ای از جواب های خوب است (به جای یک جواب).

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

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

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

بعد از اینکه یک جمعیت بصورت تصادفی ساخته شد، الگوریتم ژنتیک میزان خوب بودن هر یک از کروموزوهای جمعیت را بررسی میکند (با تابع شایستگی) و سپس سعی میکند طی سه مرحله بنام های “انتخاب” ، “ترکیب” و “جهش” راه حل ها را بهبود دهد و راه حل های جدیدی را تولید کند.

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

در واقع روال کار الگوریتم ژنتیک به بیان ساده بصورت زیر می باشد:

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

در الگوریتم ژنتیک با اصطلاحات زیر باید آشنا باشیم:

• کروموزوم (Chromosome)
• ژن (Gene)
• آلل (Allele)
• جمعیت (Population)
• تابع شایستگی یا تابع برازش (Fitness Function)
• تولید مثل یا Reproduction
• عملگر انتخاب یا Selection
• عملگر ترکیب یا Crossover
• عملگر جهش یا Mutation
• همگرایی یا Convergence

 

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

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

کروموزوم

در الگوریتم ژنتیک هر کروموزوم بیانگر یک جواب برای مسئله مورد نظر به صورت رمز شده می باشد ، و یک نقطه در فضای جستجو را نشان میدهد.   (هر راه حل = یک کروموزوم)

ژن

هر کروموزم از تعداد مشخصی ژن تشکیل شده است که هر ژن نشان دهنده یک متغیر در مسئله مورد نظر است (هر متغیر = یک ژن)

آلل

هر ژن مقادیر مختلفی میتواند داشته باشد، یعنی هر متغیر از مسئله مورد نظر یک بازه مقادیر دارد که این مقادیر آلل های ژن نامیده میشوند (آلل = بازه متغیر)

جمعیت یا Population 

مجموعه ای از کروموزم ها ، جمعیت را می سازند ، جمعیت در جین اجرای الگوریتم ، با اعمال عملگرهای خاص ، جمعیت جدید یا نسل بعدی را می سازند.

تابع شایستگی یا تابع برازش (Fitness Funcion)

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

در بسیاری از مسائل بهینه سازی ، تابع شایستگی همان تابع هدف (Objective Function) است، اما مسائل متعددی نیز وجود دارند که با مشخص بودن تابع هدف ، نیاز به تعریف و طراحی یک تابع شایستگی وجود دارد.

تولید مثل یا Reproduction

در الگوریتم وراثتی (ژنتیک) برای ساختن نسل بعد، از تولید مثل استفاده میشود.

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

برای تولید مثل و ساخت نسل جدید از عملگرهای وراثتی استفاده میشود که عبارتند از : انتخاب ، ترکیب و جهش.

عملگر انتخاب یا Selection

با استفاده از این عملگر ، از بین کروموزوم های موجود در جمعیت فعلی ، تعدادی برای تولید مثل انتخاب میشوند و به حوضچه ازدواج (Mating Pool) منتقل میشوند.

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

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

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

• روش انتخاب چرخ گردان یا Roulette Wheel Selection
• روش نمونه برداری عمومی اتفاقی یا Stochastic Universal Sampling یا به اختصار روش SUS
• روش مقیاس کردن شایستگی یا Fitness Scaling
• روش انتخاب رتبه ای یا Rank base selection
• روش انتخاب تورنومنت یا Tournament selection

عملگر ترکیب یا همبری (Crossover)

این عملگر ، مهم ترین عملگر در الگوریتم وراثتی است ، این عملگر بر روی دو (چند) کروموزوم والد عمل ترکیب را انجام میدهد و دو فرزند برای نسل بعد تولید میکند.

در حالت کلی دو دسته عملگر ترکیب یا همبری داریم:

1. عملگر ترکیب برای نسخه باینری یا دودویی
2. عملگر ترکیب برای نسخه حقیقی یا پیوسته

در حین فرایند ترکیب یا همبری ، برخی از کروموزوهای والدین با هم ترکیب میشوند یا کروموزوم های فرزند را شکل دهند.

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

• عملگر ترکیب یک نقطه ای  (Single-point Crossover)
• عملگر ترکیب دو نقطه ای (Two-point Crossover)
• عملگر ترکیب چند نقطه ای (Multi-point Crossover)
• عملگر ترکیب یکنواخت (Uniform Crossover)
• همبری مبتنی بر شایستگی (Fitness based Crossover)
• همبری نایکنواخت مبتنی بر ماسک الگو
• همبری چندوالدی (Multi-parent Crossover)
• همبری حسابی (Arithmetic Crossover)
• همبری خط (Line Crossover)
• همبری جهت دار (Direction-base Crossover)
• همبری مخلوط (Blend Crossover)
• همبری باینری شبیه سازی شده (Simulated binary Crossover)

عملگر جهش یا Mutation

در فرایند جهش، هر کروموزم میتواند جهش کوچکی داشته باشد به این شکل که یک یک ژن از یک کروموزوم به صورت تصادفی انتخاب میشود و مقدار محتوای آن ژن کمی تغییر میکند.

در الگوریتم ژنتیک حقیقی ، روش های جهش مختلفی معرفی شده است مانند:

• جهش یکنواخت
• جهش غیریکنواخت

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

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

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

یک جمعیت زمانی همگرا نامیده میشود که همه ژن های آن همگرا شده باشند.

و ژنی همگرا گفته میشود که 95 درصد افراد جمعیت مقدار یکسانی در آن ژن داشته باشند.

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

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

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

جمع بندی

در این مقاله به معرفی الگوریتم ژنتیک و اصطلاحات و عملگرهای آن پرداختیم. همچنین فلوچارت الگوریتم GA را ارائه کردیم.