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

الگوریتم‌ ژنتیک (GA | Genetic Algorithms)، خانواده‌ای از «مدل‌های محاسباتی» (Computational Models) است که از مفهوم «تکامل» (Evolution) الهام گرفته‌ شده‌اند. این دسته از الگوریتم‌ها، «جواب‌های محتمل» (Potential Solutions) یا «جواب‌های کاندید» (Candidate Solutions) و یا «فرضیه‌های محتمل» (Possible Hypothesis) برای یک مسأله خاص را در یک ساختار داده‌ای «کروموزوم مانند» (Chromosome-like) کدبندی می‌کنند. الگوریتم ژنتیک از طریق اعمال «عملگرهای بازترکیب» (Recombination Operators) روی ساختارهای داده‌ای کروموزوم مانند، اطلاعات حیاتی ذخیره شده در این ساختارهای داده‌ای را حفظ می‌کند.

در بسیاری از موارد، از الگوریتم‌های ژنتیک به عنوان الگوریتم‌های «بهینه‌ساز تابع» (Function Optimizer) یاد می‌شود؛ یعنی، الگوریتم‌هایی که برای بهینه‌سازی «توابع هدف» (Objective Functions) مسائل مختلف به کار می‌روند. البته، گستره کاربردهایی که از الگوریتم ژنتیک، برای حل مسئله در دامنه کاربردی خود استفاده می‌کنند، بسیار وسیع است.

پیاده‌سازی الگوریتم ژنتیک، معمولا با تولید جمعیتی از کروموزوم‌ها (جمعیت اولیه از کروموزوم‌ها در الگوریتم‌های ژنتیک، معمولا تصادفی تولید می‌شود و مقید به حد بالا و پایین متغیرهای مسأله هستند) آغاز می‌شود. در مرحله بعد، ساختارهای داده‌ای تولید شده (کروموزوم‌ها) «ارزیابی» (Evaluate) می‌شوند و کروموزوم‌هایی که به شکل بهتری می‌توانند «جواب بهینه» (Optimal Solution) مسأله مورد نظر (هدف) را نمایش دهند، شانس بیشتری برای «تولید مثل» (Reproduction) نسبت به جواب‌های ضعیف‌تر پیدا می‌کنند. به عبارت دیگر، فرصت‌های تولید مثل بیشتری به این دسته از کروموزوم‌ها اختصاص داده می‌شود. میزان «خوب بودن» (Goodness) یک جواب، معمولا نسبت به جمعیت جواب‌های کاندید فعلی سنجیده می‌شود.

بسیاری از اختراعات بشری از طبیعت الهام گرفته شده‌اند. «شبکه‌های عصبی مصنوعی» (ANN | Artificial Neural Network) نمونه بارز چنین ابداعاتی هستند. یکی دیگر از چنین ابداعاتی، توسعه ایده الگوریتم ژنتیک است. الگوریتم‌های ژنتیک، با «شبیه‌سازی» (Simulating) فرایند تکامل در طبیعت، با هدف یافتن بهترین جواب ممکن برای یک مسأله، به جستجو در «فضای جواب‌های کاندید» (Candidate Solution Space) می‌پردازند. در فرایند جستجو برای یافتن جواب بهینه، ابتدا مجموعه یا جمعیتی از جواب‌های ابتدایی تولید می‌شود. سپس، در «نسل‌های» (Generations) متوالی، مجموعه‌ای از جواب‌های تغییر یافته تولید می‌شوند (در هر نسل از الگوریتم ژنتیک، تغییرات خاصی در ژن‌های کروموزوم‌های تشکیل دهنده جمعیت ایجاد می‌شود). جواب‌های اولیه معمولا به شکلی تغییر می‌کنند که در هر نسل، جمعیت جواب‌ها به سمت جواب بهینه «همگرا» (Converge) می‌شوند.

این شاخه از حوزه «هوش مصنوعی» (Artificial Intelligence)، بر پایه مکانیزم تکامل موجودات زنده و تولید گونه‌های موفق‌تر و برازنده‌تر در طبیعت الهام گرفته شده است. به عبارت دیگر، ایده اصلی الگوریتم‌های ژنتیک، «بقای برازنده‌ترین‌ها» (Survival of the Fittest) است.

یک کروموزوم، رشته‌ای بلند و پیچیده از «اسید دی‌اکسی ریبونوکلئیک» (Deoxyribonucleic Acid) یا DNA است. عوامل ارثی که ویژگی‌ها یا خصیصه‌های یک «فرد» (Individual) را مشخص می‌کنند، در طول این کروموزوم‌ها نقش یافته‌اند. هر یک از خصیصه‌های موجود در افراد، به وسیله ترکیبی از DNA، در ژن‌های انسان کدبندی می‌شوند. در بدن موجودات زنده، معمولا چهار «پایه» (Base) برای تولید کروموزوم‌ها از روی DNA وجود دارد:

  • پایه A یا Adenine
  • پایه C یا Cytosine
  • پایه G یا Thymine
  • پایه T یا Guanine
    همانطور که الفبا، واحدهای سازنده یک «زبان» (Language) را تعریف می‌کند، ترکیب با معنی از کروموزوم‌ها (و پایه‌های آن‌ها)، دستورالعمل‌های خاصی را برای سلول‌ها تولید می‌کند. تغییرات در کوروموزوم‌ها، طی فرایند تولید مثل اتفاق می‌افتد. کروموزوم‌های «والدین» (Parents) از طریق فرایند خاصی به نام «ترکیب یا آمیزش» (Crossover)، به طور تصادفی با یکدیگر مبادله می‌شوند. بنابراین، فرزندان برخی از ویژگی‌ها یا خصیصه‌های پدر و برخی از ویژگی یا خصیصه‌های مادر را به ارث می‌برند و از خود به نمایش می‌گذارند.

فرایند نادری به نام «جهش» (Mutation) نیز سبب ایجاد تغییراتی در ویژگی‌ها یا خصیصه‌های موجودات زنده می‌شود. برخی از مواقع، ممکن است خطایی در فرایند کپی کردن کروموزوم‌ها رخ دهد که به آن «میتوز» (Mitosis) نیز گفته می‌شود. غالب جهش‌هایی که در موجودات زنده اتفاق می‌افتد، منجر به از بین رفتن موجودات خواهد شد؛ با این حال، در یک دوره چند میلیون ساله از تکامل، جهش ممکن است منجر به ایجاد گونه‌های جدید و برازنده‌تر از موجودات زنده شود.

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

در طبیعت، موجوداتی که ویژگی‌های برازنده‌تری نسبت به دیگر گونه‌ها دارند، برای مدت بیشتری به بقاء در طبیعت ادامه می‌دهند. چنین ویژگی‌ای، این امکان را در اختیار برازنده‌ترین موجودات زنده قرار می‌دهد تا بر اساس مواد ژنتیکی خود، اقدام به تولید مثل کنند. بنابراین، پس از یک دوره زمانی بلند مدت، جمعیت موجودات زنده به سمتی تکامل پیدا خواهد کرد که در آن، غالب موجودات بسیاری از ویژگی‌های ارثی خود را از «ژن‌های» (Genes) موجودات برتر و تعداد کمی از ویژگی‌های خود را از ژن‌های موجودات «رده پایین» (Inferior) با ژن‌ها یا ویژگی‌های نامرغوب به ارث خواهند برد.

به بیان ساده‌تر، موجودات برازنده‌تر زنده می‌مانند و موجودات نامناسب از بین می‌روند. به این فرایند و نیروی شگفت‌انگیز طبیعی، «انتخاب طبیعی» (Natural Selection) گفته می‌شود. نکته مهم در مورد انتخاب طبیعی و اثبات درست بودن این اصل این است که تحقیقات دانشمندان در مورد «توضیحات مولکولی از تکامل» (Molecular Explanation of Evolution) نشان داده است که گونه‌های مختلف موجودات زنده، خود را با شرایط محیطی تطبیق نمی‌دهند، بلکه صرفا موجودات برازنده‌تر به بقاء خود ادامه می‌دهند.

برای شبیه‌سازی فرایند انتخاب طبیعی توسط سیستم‌های کامپیوتری و حل مسأله با استفاده از الگوریتم‌های الهام گرفته شده از انتخاب طبیعی، ابتدا باید مدل‌های نمایشی جهت مدل‌سازی متغیرهای مسأله تعریف شوند:

نمایشی از یک «موجودیت» (Individual) در هر نقطه از فضای جستجوی مسأله در طول فرایند جستجو برای یافتن جواب بهینه: برای چنین کاری، مفهوم «نسل‌های» (Generation) متوالی از موجودیت‌ها مطرح می‌شود. هر موجودیت یک ساختار داده‌ای خواهد بود که «ساختار ژنتیکی» (Genetic Structure) یک جواب یا فرضیه محتمل/کاندید را نمایش می‌دهد. همانند یک کروموزوم، ساختار ژنتیکی یک موجودیت توسط الفبایی ثابت و محدود توصیف خواهد شد. به عنوان نمونه، الگوریتم ژنتیک از الفبای مبتنی بر رشته‌های «باینری» (Binary)، «مقادیر صحیح» (Integer Values) یا «مقادیر حقیقی» (Real Values) به عنوان تفسیری از جواب‌های محتمل برای یک مسأله خاص استفاده می‌کند.

به عنوان نمونه، مسأله «فروشنده دوره‌‌گرد» (Travelling Salesman) یا TSP را در نظر بگیرید. مسأله فروشنده دور‌گرد، مسأله پیدا کردن مسیر بهینه برای پیمایش مثلا 10 شهر است. فروشنده می‌تواند مسیر پیمایشی خود را از هر شهری شروع کند. بنابراین، جواب‌های این مسأله «جایگشتی» (Permutation) از شهرهای پیمایش شده خواهد بود: 1-3-2-5-4-8-10-9-7-8-6.

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

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

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

در ادامه، با مؤلفه‌های اساسی الگوریتم‌های ژنتیک و نحوه عملکرد آن‌ها در پیدا کردن جواب بهینه یک مسأله خاص مورد بررسی قرار می‌گیرد.

الگوریتم‌های ژنتیک، الگوریتم‌های جستجو هستند که بر پایه مفاهیم انتخاب طبیعی و ژنتیک موجودات زنده بنا نهاده شده‌اند. الگوریتم‌های ژنتیک پدیده آمده‌اند تا برخی از فرایندهای مشاهده شده در «تکامل طبیعی» (Natural Evolution) را از طریق الگوریتم‌های کامپیوتری شبیه‌سازی کنند. فرایندهایی که بر اساس انجام عملیات روی کروموزوم‌ها (سیستم‌های ارگانیک جهت کدبندی کردن ساختار ژنتیکی موجودات زنده) شکل گرفته‌اند.

همانطور که پیش از این نیز اشاره شد، الگوریتم‌های ژنتیک در زیر مجموعه الگوریتم‌های جستجو قرار می‌‌گیرند. با این حال، تفاوت‌های بسیار اساسی با دیگر الگوریتم‌های جستجو دارند. الگوریتم‌های ژنتیک به جای اینکه به طور مستقیم با مقادیر پارامترهای مسأله سروکار داشته باشند، با نمایشی کدبندی شده از مجموعه پارامترهای مسأله کار می‌کنند و جمعیتی متشکل از نقاط در یک فضای جستجو را برای یافتن جواب‌های مسأله جستجو می‌کنند. همچنین، بدون اینکه از اطلاعات «گرادیان» (Gradient) مرتبط با «تابع هدف» (Objective Function) مسأله اطلاعی داشته باشند، تابع هدف مسأله را بهینه‌سازی می‌کنند.

در الگوریتم‌های ژنتیک برای «گذار» (Transition) از یک حالت در فضای مسأله به حالت دیگر، از مکانیزم‌های «احتمالی» (Probabilistic) استفاده می‌شود؛ در حالی که در الگوریتم‌های جستجوی مرسوم، از اطلاعات گرادیان مرتبط با تابع هدف مسأله برای چنین کاری استفاده می‌شود. چنین ویژگی مهمی در الگوریتم‌های ژنتیک، آن‌ها را تبدیل به الگوریتم‌های جستجوی «همه منظوره» (General purpose) کرده است. همچنین، از الگوریتم‌های ژنتیک برای جستجوی فضاهای جستجوی نامنظم و بی‌قاعده استفاده می‌شود. به طور کلی، از الگوریتم‌های ژنتیک برای حل مسأله در کاربردهایی نظیر بهینه‌سازی توابع، «تخمین پارامتر» (Parameter Estimation) و «یادگیری ماشین» (Machine Learning) استفاده می‌شود.

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

اصول کاری الگوریتم ژنتیک، در ساختار الگوریتمی زیر نمایش داده شده است. مهم‌ترین گام لازم برای پیاده‌سازی الگوریتم ژنتیک و انواع مختلف آن عبارتند از: تولید جمعیت (اولیه) از جواب‌های یک مسأله، مشخص کردن تابع هدف، تابع «برازندگی» (Fitness) و به کار گرفتن «عملگرهای ژنتیک» (Genetic Operators) جهت ایجاد تغییرات در جمعیت جواب‌های مسأله. عملگرهای ژنتیک قابل تعریف در الگوریتم ژنتیک، در ادامه معرفی خواهند شد. اصول کاری الگوریتم ژنتیک عبارتست از:

  • فرموله کردن جمعیت ابتدایی متشکل از جواب‌های مسأله
  • مقدار‌دهی اولیه و تصادفی جمعیت ابتدایی متشکل از جواب‌های مسأله
  • حلقه تکرار:

– ارزیابی تابع هدف مسأله
– پیدا کردن تابع برازندگی مناسب
– انجام عملیات روی جمعیت متشکل از جواب‌های مسأله با استفاده از عملگرهای ژنتیک
– عملگر «تولید مثل» (Reproduction)
–  عملگر «ترکیب یا آمیزش» (Crossover)
– عملگر «جهش» (Mutation)

  • تا زمانی که: شرط توقف ارضا شود.

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

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

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

اگر مسأله‌ای که قرار است جواب‌های بهینه آن مشخص شود بیش از یک متغیر داشته باشد، به تعداد متغیرهای آن مسأله، «کدبندی‌های تک متغیره» (Single-Variable Coding) متناظر با تک تک آن‌ها ایجاد و با یکدیگر ادغام می‌شوند. در چنین حالتی، یک «کدبندی چند متغیره» (Multi-Variable Coding) از مسأله مورد نظر شکل خواهد گرفت. یکی از مهم‌ترین ویژگی‌های الگوریتم‌های ژنتیک، پردازش هم‌زمان چندین جواب کاندید تولید شده برای مسأله تعریف شده است.

بنابراین، در مرحله اول از پیاده‌سازی الگوریتم ژنتیک، مجموعه‌ای متشکل از P موجودیت یا کروموزوم توسط «مولدهای شبه تصادفی» (Pseudo Random Generators) تشکیل می‌شود. هر کدام از موجودیت‌ها با کروموزوم‌های موجود در این جمعیت، یک جواب کاندید و امکان‌پذیر برای مسأله را نمایش می‌دهند. هر کدام از این موجودیت‌ها، یک نمایش برداری از جواب مسأله در یک «فضای جواب» (Solution Space) هستند که به آن‌ها «جواب اولیه» (Initial Solution) نیز گفته می‌شود.

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

در این مرحله، معمولا یک «تابع جریمه خارجی» (Exterior Penalty Function) به کار گرفته می‌شود تا «مسأله بهینه‌سازی مقید» (Constrained Optimization Problem) به یک مسأله بهینه‌سازی «نامقید» (Unconstrained) تبدیل شود. چنین تبدیلی، بسته به مسائل بهینه‌سازی مختلف (مسائلی که قرار است جواب‌های بهینه آن‌ها تولید شود)، متفاوت خواهد بود.

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

عملیات بهینه‌سازی در الگوریتم ژنتیک، با یک تولید جمعیت اولیه از «رشته‌های تصادفی» (Random Strings) آغاز می‌شود (این رشته‌ها معادل کروموزوم‌ها یا موجودیت‌ها یا جواب‌های کاندید مسأله هستند). رشته‌های تصادفی، طراحی مسأله یا به عبارت دیگر، «متغیرهای تصمیم» (Decision Variables) مرتبط با یک مسأله را نمایش می‌دهند.

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

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

جمعیت جدید تولید شده نیز مورد ارزیابی بیشتر قرار می‌گیرد و اینکار تا «خاتمه یافتن» (Termination) فرایندهای عملیاتی در الگوریتم ژنتیک ادامه پیدا می‌کند. تا زمانی که شرط توقف الگوریتم ژنتیک ارضا نشود، جمعیت کروموزوم‌ها یا بردارهای جواب، به وسیله عملگرهای تولید مثل، ترکیب و جهش دستکاری و ارزیابی می‌شوند. این رویه تا زمانی که معیار توقف الگوریتم ژنتیک ارضا شود، ادامه پیدا می‌کند.

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

عملگر تولید مثل یا «انتخاب» (Selection)، عملگری است که بهترین «رشته‌ها» (Strings) در یک جمعیت جدید را کپی می‌کند (منظور، بهترین کروموزوم‌ها یا بردارهای جواب کاندید در یک نسل است). عملگر تولیدِ مثل، معمولا اولین عملگری است که برای دستکاری جمعیت مورد استفاده قرار می‌گیرد و روی کروموزوم‌ها اعمال می‌شود. این عملگر، رشته‌ها یا کروموزوم‌های خوب جمعیت را انتخاب می‌کند و آن‌ها را در مخزنی که در اصطلاح به آن Mating Pool گفته می‌شود، قرار می‌دهد؛ به همین دلیل است که به عملگر تولید مثل، عملگر انتخاب نیز گفته می‌شود.

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

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

از عملگر «ترکیب یا آمیزش» (Crossover)، برای «باز‌ترکیب» (Recombine) دو رشته یا کروموزوم استفاده می‌شود. این کار، با هدف تولید رشته‌ها یا کروموزوم‌های بهتر انجام می‌شود. در عملیات ترکیب در الگوریتم ژنتیک، طریق ترکیب کردن مواد ژنتیکی دو کروموزوم موجود در جمعیت نسل قبل، کروموزوم‌های جدیدی در نسل‌های فعلی می‌شود. به عبارت دیگر، فرایند بازترکیب، ژن‌های موجود در دو کروموزوم را ترکیب و از این طریق، کروموزوم‌های جدیدی در جمعیت فعلی تولید می‌کند.

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

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

به دو کروموزوم یا رشته‌ای که در عملیات ترکیب یا آمیزش مشارکت می‌کنند، کروموزوم‌های «والد» (Parents) گفته می‌شود. همچنین، کروموزوم‌هایی که در اثر فرایند ترکیب یا آمیزش تولید می‌شوند، کروموزوم‌های «فرزند» (Children) نامیده می‌شوند.

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

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

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

با این حال، طبیعت تصادفی عملگرهای ژنتیک (نظیر عملگر ترکیب) ممکن است اثر «مخرب» (Detrimental) یا «سودمند» (Beneficial) در کیفیت کروموزوم‌ها یا همان جواب‌های مسأله داشته باشد. در صورتی که کروموزوم‌های فرزند خوبی در نتیجه ترکیب تولید شوند، در جمعیت نسل‌های بعدی، کروموزوم‌های خوبی مشارکت خواهند کرد و برعکس.

بنابراین، برای حفظ برخی از رشته‌ها یا کروموزوم‌های خوبی که در مخزن Mating Pool وجود دارند، تمامی رشته‌ها یا کروموزوم‌های موجود در مخزن Mating Pool، توسط عملگر ترکیب دستکاری نخواهند شد. برای چنین کاری، از مفهومی به نام «احتمال ترکیب» (Crossover Probability) یا pcاستفاده می‌شود.

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

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

تاکنون، عملگرهای ترکیب متعددی برای الگوریتم ژنتیک توسعه داده شده‌اند. روش‌های «تک نقطه‌ای» (Single Point) و «دو نقطه‌ای» (Two point)، از جمله مهم‌ترین عملگرهای ترکیب در الگوریتم ژنتیک محسوب می‌شوند. در غالب عملگرهای ترکیب توسعه داده شده برای الگوریتم ژنتیک، دو رشته یا کروموزوم به طور تصادفی از مخزن Mating Pool انتخاب می‌شوند و بخش‌هایی از رشته‌های این دو کروموزوم با یکدیگر ترکیب می‌شوند تا رشته‌ها یا کروموزوم‌های جدیدی پدید آیند.

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

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

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

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

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

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

زمانی که در نسل‌های متوالی، از عملیات ترکیب و تولید مثل به دفعات روی رشته‌ها یا کروموزوم‌ها استفاده می‌شود، جمعیت کروموزوم‌ها یا جواب‌های کاندید به «همگن» (Homogeneous) شدن گرایش پیدا می‌کند. عملگر جهش به الگوریتم ژنتیک کمک می‌کند تا «تنوع» (Diversity) در جمعیت کروموزوم‌ها یا جواب‌های کاندید افزایش پیدا کند.

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

به بیان ساده‌تر، عملگر جهش، فرایندی تصادفی برای به هم ریختن و ایجاد اختلال در اطلاعات ژنتیکی محسوب می‌شود. بر خلاف عملگر ترکیب، عملگر جهش در سطح ژن کار می‌کند؛ یعنی، زمانی که ژن‌ها از رشته یا کروموزوم فعلی در رشته یا کروموزوم جدید کپی می‌شوند، این احتمال وجود دارد که هر کدام از این ژن‌ها جهش پیدا کنند. این احتمال معمولا مقدار بسیار کوچکی است که به آن «احتمال جهش» (Mutation Probability) یاpmگفته می‌شود.

در صورتی که از نمایش بیتی (صفر و یک) برای مشخص کردن مقادیر متغیرهای مسأله یا ژن‌ها استفاده شود، جهت انجام عملیات جهش، از مکانیزم «پرتاب سکه» (Coin Toss) در الگوریتم ژنتیک استفاده می‌شود؛ یعنی، در صورتی که مقدار تصادفی (بین صفر و یک) از احتمال جهش کمتر باشد، مقدار ژن یا همان بیت ژن معکوس می‌شود. به عبارت دیگر، مقادیر ژنی برابر با یک تبدیل به صفر و مقادیر ژنی برابر با صفر، تبدیل به یک خواهند شد.

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

عملگر جهش مکانیزم هوشمندانه‌ای برای جستجوی محلی در فضای جستجوی جواب‌های مسأله به شمار می‌آید. با استفاده از عملگر جهش در الگوریتم ژنتیک، رشته‌ها یا کروموزوم‌های جدیدی در همسایگی رشته یا کروموزوم فعلی ایجاد می‌شوند. در نتیجه، عملگر جهش سبب ایجاد مکانیزم جستجوی محلی اطراف کروموزوم‌های فعلی می‌شود. همچنین، عملگر جهش سبب حفظ تنوع در جمعیت کروموزوم‌ها یا جواب‌های کاندید می‌شود. به عنوان نمونه، به جمعیت زیر توجه کنید. این جمعیت، از 4 کروموزم تشکیل شده است که هر کدام از آن‌ها، یک رشته 8 بیتی هستند:

01101011
00111101
00010110
01111100

با دقت به جمعیت کروموزومی نمایش داده شده می‌توان دریافت که اولین ژن تمامی رشته‌ها از سمت چپ، صفر (0) است. در صورتی که ابتدایی‌ترین ژن رشته متناظر با جواب بهینه سراسری برابر با (1) باشد، هیچ کدام از عملگرهای تولید مثل (انتخاب) و ترکیب قادر به تولید مقدار یک (1) در این مکان ( اولین ژن رشته از سمت چپ) نخواهند بود. استفاده از عملگر جهش در الگوریتم ژنتیک سبب می‌شود تا مقدار اولین ژن این رشته‌ها، با احتمال pm از صفر (0) به یک (1) تغییر پیدا کند.

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

با اینکه هیچ‌گونه تضمینی برای ایجاد جواب‌ها یا رشته‌ها یا کروموزوم‌های خوب در نتیجه عملیات این عملگرها وجود ندارد، با این حال می‌توان از دو مورد زیر تا حد زیادی مطمئن بود:

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

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

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

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

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

در صورتی که بتوانید جواب‌های کاندید یک مسأله را در قالب کروموزوم‌ها کدبندی کنید، به راحتی خواهید توانست از الگوریتم ژنتیک برای حل مسأله و مقایسه عملکرد (برازندگی) نسبی جواب‌های بهینه حاصل شده استفاده کنید. نمایش دقیق و مؤثر از متغیرهای مسأله و پیاده‌سازی ساز و کارهای با معنی برای ارزیابی برازندگی جواب‌های کاندید، مهم‌ترین عوامل در موفقیت در کاربردهای تولید شده از الگوریتم ژنتیک است.

نقطه قوت الگوریتم ژنتیک، در سادگی و ظرافت آن‌ها به عنوان یک الگوریتم جستجوی قدرتمند و قدرت آن‌‌ها در کشف سریع جواب‌های خوب برای مسائل سخت و «با ابعاد بالا» (High Dimensional) نهفته است. الگوریتم ژنتیک زمانی می‌توانند مفید و مؤثر واقع شود که:

  1. فضای جستجوی مسأله بزرگ، پیچیده و دارای ساختار بندی ضعیف باشد.
  2. دانش دامنه نایاب باشد و یا دانش خبره، جهت محدود کردن فضای جستجو، به سختی کدبندی شود.
  3. هیچ‌گونه تحلیل ریاضی در دسترس نباشد.
  4. روش‌های جستجوی سنتی با شکست مواجه شوند.

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

  • بهینه‌سازی: دامنه وسیعی از مسائل بهینه‌سازی نظیر «بهینه‌سازی عددی» (Numerical Optimization) و «بهینه‌سازی ترکیبیاتی» (Combinatorial Optimization).
  • «برنامه‌نویسی خودکار» (Automatic Programming): برنامه‌نویسی سیستم‌های کامپیوتری برای انجام وظایف خاص و طراحی ساختارهای محاسباتی نظیر «اتوماتای سلولی» (Cellular Automata) و «شبکه‌های مرتب‌سازی» (Sorting Networks).
  • «یادگیری ماشین» (Machine Learning): «دسته‌بندی» (Classification)، «پیش‌بینی» (Prediction)، طراحی «شبکه‌های عصبی مصنوعی» (Artificial Neural Networks) و سایر موارد.
  • مدل‌های «سیستم ایمنی» (Immune Systems): برای مدل‌سازی جنبه‌های مختلف سیستم ایمنی طبیعی، از جمله برخی جهش‌ها در طول دوره حیات موجودات و اکتشاف خانواده‌های «چندژنی» (Multi-Genes) در طول فرایند تکامل.
  • مدل‌های اقتصادی: مدل‌سازی فرایند نوآوری، توسعه استراتژی‌های مناقصه و ظهور بازارهای اقتصادی.

الگوریتم‌های ژنتیک، به راحتی در دامنه وسیعی از مسائل، از جمله مسائل بهینه‌سازی نظیر «مسأله فروشنده دوره‌گرد» (Travelling Salesman Problem) و مسائل مرتبط با «برنامه‌ریزی» (Scheduling)، می‌توانند مورد استفاده قرار بگیرند. نتایج حاصل از الگوریتم ژنتیک برای برخی از مسائل ممکن است بسیار خوب و برای برخی دیگر از مسائل، ممکن است بسیار ضعیف باشد. اگر تنها از عملگر جهش در الگوریتم ژنتیک استفاده شود، الگوریتم بسیار کند می‌شود. استفاده از عملگر ترکیب، سبب سرعت بخشیدن به فرایند همگرایی در الگوریتم ژنتیک خواهد شد.

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

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