آموزش الگوریتم ژنتیک – آموزش رایگان و جامع از ۰ تا ۱۰۰ الگوریتم ژنتیک

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

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

الگوریتم ژنتیک (GA) یک روش بهینه سازی مبتنی بر جستجو بر اساس اصول ژنتیک و انتخاب طبیعی است. این الگوریتم برای یافتن راه‌حل‌های بهینه یا تقریباً بهینه برای مسائل سخت “NP-Hard” طراحی شده است. مسائل سخت جزو مسائلی هستند که حل آن‌ها به‌صورت سنتی، یک عمر زمان می‌برد.

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

بهینه سازی به یافتن مقادیر ورودی‌ها به گونه‌ای اشاره دارد که «بهترین» مقادیر خروجی بدست آید. تعریف «بهترین» از مسئله‌ای به مسئله دیگر متفاوت است، اما در اصطلاح ریاضی، به حداکثر کردن «Maximizing» یا کمینه کردن «Minimizing» یک یا چند تابع هدف «Cost Function» با تغییر پارامترهای ورودی اشاره دارد.

مجموعه‌ای از تمام راه حل‌ها یا مقادیر ممکن که ورودی‌ها می‌توانند بگیرند فضای جستجو «Search Space» را تشکیل می‌دهند. در این فضای جستجو، یک نقطه یا مجموعه‌ای از نقاط نهفته است که راه حل بهینه را ارائه می‌دهند. هدف از بهینه سازی یافتن آن نقطه یا مجموعه‌ای از نقاط در فضای جستجو یا فضای حالت است.

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

طبیعت همواره منبع بزرگ الهام برای بشریت بوده است. الگوریتم ژنتیک جزو الگوریتم‌های مبتنی بر جستجو هستند که بر اساس مفاهیم انتخاب طبیعی و ژنتیک هستند. الگوریتم ژنتیک زیرمجموعه‌ای از شاخه بسیار بزرگ‌تری از محاسبات هستند که به عنوان محاسبات تکاملی «Evolutionary Computation» شناخته می‌شوند.

• پاورپوینت آماده محاسبات تکاملی (Evolutionary Computation) — ویژه ارائه کلاسی

در ادامه آموزش الگوریتم ژنتیک بهتر است با ابداع کنندگان این الگوریتم آشنا شویم. الگوریتم ژنتیک توسط جان هالند «John Holland» و دانشجویان و همکارانش در دانشگاه میشیگان «University of Michigan» ابداع و توسعه یافت و از آن زمان بر روی مسائل مختلف بهینه سازی با درجه موفقیت بالایی آزمایش شده است. برای اطلاعات بیشتر در مورد تاریخچه این الگوریتم می‌توانید مقاله کامل تاریخچه الگوریتم ژنتیک را مطالعه کنید.

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

به این ترتیب اعضا یا راه‌حل‌های بهتر در طول نسل‌ها به «تکامل» می‌رسند تا زمانی که به یک معیار توقف برسیم. الگوریتم‌ ژنتیک از نظر ماهیت تاحدودی تصادفی است، همان چیزی که باعث پیدایش آفرینش شده است. الگوریتم GA عملکرد بهتری نسبت به جستجوی تصادفی (که در آن ما فقط راه‌حل‌های تصادفی مختلفی را امتحان می‌کنیم)، دارد، چون از اطلاعات گذشته یا «Historical» نیز بهره می برد.

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

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

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

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

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

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

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

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

۱- حل مسائل سخت

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

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

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

۳- دریافت سریع راه حل خوب

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

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

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

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

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

• جمعیت Population: زیر مجموعه‌ای از همه راه‌حل‌های ممکن (کدگذاری شده) برای یک مسئله است. جمعیت برای یک GA مشابه جمعیت برای انسان است با این تفاوت که به جای انسان، ما راه حل‌های نامزدی داریم که نماینده انسان‌ها هستند.
• کروموزوم Chromosome: کروموزوم یکی از راه حل‌های مسئله در بین جمعیت است.
• ژن Gene: ژن موقعیت یک عنصر از کروموزوم است.
• Allele: مقداری است که یک ژن برای یک کروموزوم خاص می‌گیرد.

• ژنوتایپ Genotype: ژنوتایپ جمعیت در فضای محاسباتی است. در فضای محاسباتی، راه‌حل‌ها به گونه‌ای نمایش داده می‌شوند که به راحتی قابل درک و دستکاری با استفاده از یک سیستم محاسباتی باشد.
• فنوتایپ Phenotype: فنوتایپ جمعیتی در فضای واقعی راه حل دنیای واقعی است که در آن راه حل‌ها به گونه‌ای نشان داده می‌شوند که در موقعیت‌های دنیای واقعی نشان داده می‌شوند.
• کدگذاری Encoding و کدکشایی Decoding: برای مسائل ساده، فضاهای فنوتایپ و ژنوتایپ یکسان هستند. اما در بیشتر موارد فضاهای فنوتایپ و ژنوتایپ متفاوت است. کدگشایی فرآیند تبدیل راه‌حل از ژنوتایپ به فضای فنوتایپ است، کدگذاری یعنی فرآیند تبدیل از فنوتایپ به فضای ژنوتایپ و باید سریع باشد زیرا در طول اجرای الگوریتم، بارها و بارها ارزش تابع تناسب، محاسبه می‌شود.

• تابع تناسب Fitness Function: تابع تناسب تعریف شده تابعی است که راه حل را به عنوان ورودی می‌گیرد و مناسب بودن راه حل را به عنوان خروجی تولید می‌کند. در برخی موارد، تابع تناسب و تابع هدف ممکن است یکسان باشد، در حالی که در برخی مسائل دیگر ممکن است بر اساس شکل مسئله متفاوت باشد.
• عملگرهای ژنتیک Genetic Operators: عملگرهای ژنتیک، ترکیب ژنتیکی فرزندان را تغییر می‌دهند که عبارتند از متقاطع، جهش، انتخاب و غیره.

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

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

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

GA()
   initialize population
   find fitness of population
   
   while (termination criteria is reached) do
      parent selection
      crossover with probability pc
      mutation with probability pm
      decode and fitness calculation
      survivor selection
      find best
   return best

نمایش راه‌حل

یکی از مهم‌ترین تصمیماتی که باید در حین اجرای الگوریتم ژنتیک اتخاذ کرد، تصمیم گیری در مورد نمایش راه‌حل است. اثبات شده که نمایش نامناسب می‌تواند منجر به عملکرد ضعیف الگوریتم GA شود؛ بنابراین، انتخاب یک نمایش مناسب، داشتن تعریف مناسب از نگاشت بین فضاهای فنوتایپ و ژنوتایپ است.

۱- نمایش باینری

نمایش باینری «Binary Representation» یکی از ساده‌ترین و پرکاربردترین نمایش‌ها در الگوریتم ژنتیک است. در این نوع نمایش، ژنوتایپ از رشته‌های بیتی تشکیل شده است.

برای برخی از مسائل زمانی که فضای راه‌حل متشکل از متغیرهای تصمیم بولی است (بله یا خیر)، نمایش باینری طبیعی است. برای مثال مسئله کوله پشتی را در نظر بگیرید. اگر n مورد وجود داشته باشد، می‌توانیم یک راه حل را با یک رشته باینری از n عنصر نشان دهیم، جایی که عنصر X می گوید که آیا آیتم X انتخاب شده (۱) یا نه (۰).

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

۲- نمایش با ارزش واقعی

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

۳- نمایش عدد صحیح

برای ژن‌های با ارزش گسسته، همیشه نمی‌توانیم فضای حل مسئله را به «بله» یا «خیر» باینری محدود کنیم. به عنوان مثال، اگر بخواهیم چهار فاصله شمالی، جنوبی، شرقی و غربی را کدگذاری کنیم، می‌توانیم آن‌ها را به صورت {۰،۱،۲،۳} رمزگذاری کنیم. در چنین مواردی، نمایش اعداد صحیح مطلوب است.

۴- نمایش جایگشتی

در بسیاری از مسائل، راه حل با ترتیبی از عناصر نشان داده می‌شود. در چنین مواردی نمایش جایگشتی مناسب‌ترین است. یک مثال کلاسیک از این نمایش، مسئله فروشنده دوره گرد (TSP) است. در این مسئله، فروشنده باید در تمام شهرها گشت بزند و دقیقاً یک بار از هر شهر بازدید کند و به شهر شروع بازگردد و مسافت کل تور باید به حداقل برسد. راه حل TSP طبیعتاً ترتیب یا جایگشت همه شهرها است و بنابراین استفاده از نمایش جایگشت برای این مسئله منطقی است.

• دوره جامع آموزش الگوریتم ژنتیک و حل مسئله فروشنده دوره گرد با آن (متلب) — کلیک کنید
• آموزش الگوریتم ژنتیک و حل مسئله فروشنده دوره گرد با آن (پایتون) — کلیک کنید

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

همانطور که در بخش تعاریف آموزش الگوریتم ژنتیک اشاره شد جمعیت «Population» زیر مجموعه‌ای از راه حل‌ها در نسل کنونی است. جمعیت را می‌توان به عنوان مجموعه‌ای از کروموزوم‌ها تعریف کرد. موارد مهمی وجود دارد که باید در هنگام برخورد با جمعیت در الگوریتم ژنتیک در نظر داشت:

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

جمعیت اولیه Population Initialization

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

• مقداردهی اولیه تصادفی «Random Initialization»: جمعیت اولیه با راه‌حل‌های کاملاً تصادفی ایجاد می‌شود.
• مقدار‌دهی اولیه اکتشافی «Heuristic initialization»: جمعیت اولیه را با استفاده از یک روش اکتشافی شناخته شده برای مسئله ایجاد می‌شود.

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

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

مدل‌های جمعیت

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

• حالت پایدار Steady State

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

• نسلی Generational

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

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

در این بخش از آموزش الگوریتم ژنتیک به تابع تناسب می رسیم. تابع تناسب «Fitness Function» تابعی است که یک راه‌حل کاندید برای مسئله را به عنوان ورودی می‌گیرد و نشان می‌دهد که راه‌حل ما چقدر «خوب» است. محاسبه ارزش تابع تناسب به طور مکرر درالگوریتم ژنتیک انجام می‌شود و بنابراین باید به اندازه کافی سریع و بدور از محاسبت پیچیده باشد. محاسبه آهسته مقدار تابع تناسب می‌تواند بر عملکرد الگوریتم ژنتیک تأثیر منفی بگذارد و آن را بسیار کند یا ناکارآمد کند.

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

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

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

تصویر زیر محاسبه تابع تناسب برای حل کوله پشتی ۰/۱ را نشان می دهد. مثال زیر یک تابع تناسب ساده را نشان می‌دهد که فقط مقادیر سود اقلام انتخاب شده (که ۱ دارند) را جمع می‌کند، عناصر را از چپ به راست اسکن می‌کند تا زمانی که کوله پشتی پر شود.

• حل مسئله کوله پشتی با الگوریتم ژنتیک GA در متلب — کلیک کنید

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

در ادامه آموزش الگوریتم ژنتیک به بخش انتخاب والدین در الگوریتم ژنتیک می‌رسیم. انتخاب والدین یا «Parent Selection» فرآیندی است که در آن والدینی برای جفت‌گیری و ترکیب انتخاب می‌شوند تا برای نسل بعدی فرزندانی ایجاد کنند. انتخاب والدین برای نرخ همگرایی GA بسیار مهم است زیرا والدین خوب، جواب‌ها را به سمت راه‌حل‌های بهتر و مناسب‌تر سوق می‌دهند.

با این حال، باید مراقب بود که در چند نسل از یک راه حل بسیار مناسب برای انتخاب والدین جلوگیری شود، زیرا این امر منجر به نزدیکی راه حل‌ها به یکدیگر در فضای جستجو می‌شود و در نتیجه منجر به از دست دادن تنوع «Variety» می‌شود. حفظ تنوع خوب در جمعیت برای موفقیت در الگوریتم ژنتیک بسیار مهم است.

۱- انتخاب والدین بر اساس تابع تناسب مناسب

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

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

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

• انتخاب چرخ رولت Roulette Wheel Selection

در انتخاب چرخ رولت «Roulette Wheel Selection»، چرخ دایره‌ای مانند قبل تقسیم می‌شود. همانطور که نشان داده شده است یک نقطه ثابت روی دور چرخ انتخاب می‌شود و چرخ می‌چرخد. ناحیه‌ای از چرخ که جلوی نقطه ثابت می‌آید به عنوان والد انتخاب می‌شود. برای والد دوم نیز همین روند تکرار می‌شود. شکل زیر نمونه‌ای از انتخاب والدین با چرخه رولت را نشان می‌دهد.

واضح است که یک عضو مناسب، قسمت بیشتری روی چرخ دارد و بنابراین هنگام چرخاندن چرخ، شانس بیشتری برای فرود آمدن در مقابل نقطه ثابت «Fixed Point» دارد. بنابراین، احتمال انتخاب یک عضو مستقیماً به تابع تناسب آن بستگی دارد.

• نمونه برداری سراسری تصادفی Stochastic Universal Sampling

نمونه برداری سراسری تصادفی «Stochastic Universal Sampling» کاملاً شبیه به انتخاب چرخ رولت است، اما به جای داشتن یک نقطه ثابت، چندین نقطه ثابت مانند تصویر زیر داریم. بنابراین، تمام والدین تنها در یک چرخش چرخ انتخاب می‌شوند. همچنین، چنین تنظیمی اعضای بسیار مناسب را تشویق می‌کند که حداقل یک بار انتخاب شوند.

۲- انتخاب تورنومنتی Tournament Selection

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

۳- انتخاب بر اساس رتبه Rank Selection

انتخاب رتبه «Rank Selection» با مقادیر تناسب تناسب منفی کار می‌کند و بیشتر زمانی استفاده می‌شود که افراد در جمعیت دارای مقادیر تناسب بسیار نزدیک باشند (این کار معمولاً در پایان اجرا اتفاق می‌افتد). این کار منجر به این می‌شود که هر فرد سهم تقریباً مساوی از قسمت‌ها (مانند انتخاب متناسب تناسب) را همانطور که در تصویر زیر نشان داده شده است داشته باشد و از این رو هر فرد صرف نظر از اینکه چقدر نسبت به یکدیگر تناسب داشته باشد، احتمال تقریباً یکسانی برای انتخاب شدن دارد. این کار به نوبه خود منجر به از دست دادن فشار انتخاب نسبت به افراد مناسب‌تر می‌شود، و باعث می‌شود GA در چنین شرایطی انتخاب‌های ضعیفی برای والدین انجام دهد.

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

۴- انتخاب تصادفی Random Selection

در این استراتژی به طور تصادفی والدین را از بین جمعیت موجود انتخاب می‌کنیم. هیچ فشار انتخابی نسبت به افراد مناسب‌تر وجود ندارد و بنابراین معمولاً از این استراتژی اجتناب می‌شود.

عملگر متقاطع Crossover در الگوریتم ژنتیک

در این بخش از آموزش الگوریتم ژنتیک، در مورد عملگر متقاطع «Crossover» و کاربردها و مزایای آن صحبت خواهیم کرد. عملگر Crossover مشابه تولید مثل و کراس اور بیولوژیکی است. در این روش بیش از یک والد انتخاب می‌شود و یک یا چند فرزند با استفاده از مواد ژنتیکی والدین تولید می‌شود. Crossover معمولاً در الگوریتم ژنتیک با احتمال p_c زیاد استفاده می‌شود.

۱- متقاطع تک نقطه ای One Point Crossover

در متقاطع یک نقطه‌ای یا One Point Crossover، یک نقطه متقاطع تصادفی انتخاب می‌شود و دو قسمت از والدین آن‌ها برای به دست آوردن فرزندهای جدید تعویض یا جابجا می‌شوند.

۲- متقاطع چند نقطه ای Multi Point Crossover

متقاطع چند نقطه‌ای Multi Point Crossover تعمیم متقاطع یک نقطه‌ای است که در آن بخش های متناوب برای دریافت فرزندهای جدید تعویض می‌شوند.

۳- متقاطع یکنواخت Uniform Crossover

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

۴- متقاطع Whole Arithmetic Recombination

این نوع از کراس اور، معمولاً برای نمایش اعداد صحیح استفاده می‌شود و با گرفتن میانگین وزنی دو والد با استفاده از فرمول‌های زیر کار می‌کند:

• Child1 = α.x + (1-α).y
• Child2 = α.x + (1-α).y

بدیهی است که اگر α = 0.۵ باشد، هر دو فرزند همانند تصویر زیر خواهند بود.

۵- متقاطع Davis’ Order

کراس اوور Davis’ Order یا OX1 برای کراس اوورهای مبتنی بر جایگشت با هدف انتقال اطلاعات در مورد سفارش نسبی به فرزندها استفاده می‌شود و به صورت زیر کار می‌کند:

• دو نقطه متقاطع تصادفی در والد ایجاد می‌شود و بخش بین آن‌ها را از والد اول تا اولین فرزند کپی می‌کند.
• از نقطه متقاطع دوم در والد دوم شروع شده، اعداد استفاده نشده باقیمانده را از والد دوم به فرزند اول کپی می‌‎شود.
• این کار برای فرزند دوم با تغییر نقش والدین تکرار می‌شود.

عملگر جهش Mutation

به زبان ساده، جهش یا Mutation ممکن است به عنوان یک تغییر تصادفی کوچک در کروموزوم برای به دست آوردن یک راه حل جدید تعریف شود. جهش برای حفظ و معرفی تنوع در جمعیت استفاده می شود و معمولاً با احتمال  p_m  کم استفاده می‌شود. اگر احتمال بسیار زیاد باشد، الگوریتم ژنتیک به یک الگوریتم جستجوی تصادفی تبدیل می‌شود.

عملگرهای جهش

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

۱- جهش Bit Flip

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

۲- جهش تنظیم مجدد تصادفی Random Resetting

جهش تنظیم مجدد تصادفی یا Random Resetting یک بسط از جهش Bit Flip برای نمایش عدد صحیح است. در این نوع از جهش، یک مقدار تصادفی از مجموعه مقادیر مجاز به یک ژن به طور تصادفی انتخاب شده اختصاص داده می‌یابد.

۳- جهش تعویض Swap Mutation

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

۴- جهش Scramble Mutation

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

۵- جهش وارونگی Inversion Mutation

در جهش Inversion، ما زیرمجموعه‌ای از ژن‌ها را مانند جهش Scramble انتخاب می‌کنیم، اما به جای اینکه زیرمجموعه را به هم بزنیم، فقط کل رشته زیر مجموعه را معکوس می‌کنیم.

به طور کلی در اکثر پیاده سازی‌ها با استفاده از یک چرخه رولت و به صورت تصادفی در هر مرحله از جهش یک نمونه از جهش انتخاب می‌شود. به عنوان مثال در یک تکرار از الگوریتم Swap Mutation و در تکرار بعدی Random Resetting و الی آخر انتخاب می‌شود.

انتخاب بازمانده Survivor Selection

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

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

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

۱- انتخاب بر اساس سن Age Based Selection

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

به عنوان مثال، در مثال زیر، سن تعداد نسل‌هایی است که فرد در آن جمعیت بوده است. مسن‌ترین اعضای جمعیت یعنی P4 و P7 از جمعیت اخراج می‌شوند و سن بقیه اعضا یک نفر افزایش می‌یابد.

۲- انتخاب بر اساس تابع تناسب Fitness Based Selection

در انتخاب مبتنی بر تابع تناسب، فرزندان جدید جایگزین اعضایی می‌شوند که از لحاظ شایستگی در جمعیت ارزش یا مقدار کم‌تری دارند. انتخاب اعضا با کم‌ترین شایستگی ممکن است با استفاده از تغییری از هر یک از سیاست‌های انتخابی که قبلاً توضیح داده شد (انتخاب تورنومنت، انتخاب متناسب با تابع تناسب و غیره) انجام شود.

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

شرایط خاتمه یا توقف الگوریتم ژنتیک

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

معمولاً یکی از شرایط پایان یا شرایط توقف زیر را برای الگوریتم ژنتیک در نظر می‌گیریم:

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

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

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

سخن آخر در مورد آموزش الگوریتم ژنتیک

در آموزش الگوریتم ژنتیک سعی شد مفاهیم و اصطلاحات رایج این الگوریتم تشریح شوند تا الگویی کامل در ذهن فراگیر از الگوریم ژنتیک شکل بگیرد. در مورد عملگرهای اصلی Crossover، جهش و غیره توضیحات کاملی ارائه شد و در مورد شرط یا شرایط پایانی الگوریتم نیز مطالبی بیان شد. هر چند که این مقاله آموزشی منتشر شده از سایت پی استور بسیار پرمحتوا و کامل است ولی آموزش‌های تکمیلی زیادی نیز می‌تواند برای آموزش وجود داشته باشد. یکی از جدیدترین فیلم های آموزشی سایت پی استور در زمینه حل مسئله TSP با الگوریتم ژنتیک است که می‌تواند برای فراگیران عزیز مفید باشد. امیدواریم مطالب فوق برای شما عزیزان مفید بوده باشد. موفق و پیروز باشید.