الگوریتم ژنتیک – از صفر تا صد

۲۰۳۴۷ بازدید
آخرین به‌روزرسانی: ۰۱ اسفند ۱۴۰۲
زمان مطالعه: ۴۳ دقیقه
الگوریتم ژنتیک – از صفر تا صد

الگوریتم‌ ژنتیک (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 یا Guanine
  • پایه T یا Thymine

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

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

رشته DNA

انتخاب طبیعی

در طبیعت، موجوداتی که ویژگی‌های برازنده‌تری نسبت به دیگر گونه‌ها دارند، برای مدت بیشتری به بقاء در طبیعت ادامه می‌دهند. چنین ویژگی‌ای، این امکان را در اختیار برازنده‌ترین موجودات زنده قرار می‌دهد تا بر اساس مواد ژنتیکی خود، اقدام به تولید مثل کنند. بنابراین، پس از یک دوره زمانی بلند مدت، جمعیت موجودات زنده به سمتی تکامل پیدا خواهد کرد که در آن، غالب موجودات بسیاری از ویژگی‌های ارثی خود را  از «ژن‌های» (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.

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

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

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

الگوریتم ژنتیکتوضیح
کروموزوم (رشته، موجودیت)جواب مسأله
ژن‌ها (بیت‌ها)بخشی از جواب مسأله
مکان (Locus)مکان ژن‌ها
آلل‌ها (Alleles)مقادیر ژن‌ها
فنوتایپ (Phenotype)جواب کدگشایی شده مسأله
ژنوتایپ (Genotype)جواب کدبندی شده مسأله

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

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

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

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

الگوریتم‌های ژنتیک، الگوریتم‌های جستجو هستند که بر پایه مفاهیم انتخاب طبیعی و ژنتیک موجودات زنده بنا نهاده شده‌اند. الگوریتم‌های ژنتیک پدیده آمده‌اند تا برخی از فرایندهای مشاهده شده در «تکامل طبیعی» (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) هر یک از اعضای جمعیت اولیه مشخص می‌شود. پس از مشخص شدن مقدار برازندگی جواب‌های کاندید، از عملگرهای الگوریتم ژنتیک جهت انجام تغییرات روی جواب‌های کاندید استفاده می‌شود.

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

برای نمایش اصول کاری الگوریتم ژنتیک، یک مسأله بهینه‌سازی نامقید در نظر گرفته می‌شود. فرض کنید که مسأله بهینه‌سازی زیر داده شده است و هدف الگوریتم ژنتیک، «بیشینه‌سازی» (Maximizing) تابع زیر باشد:

$$maximize \; f ( x ) , \; \; x _ i ^ l \leq x _ { i } \leq x _ i ^ u , i = 1 , 2 , . . . . , N ,$$

در این رابطه، $$x _ i ^ l$$ و $$x _ i ^ u$$ حد بالا و حد پایین تعیین شده برای مقادیر متغیر $$x _ { i }$$ است. اگر چه در اینجا از یک مسأله بیشینه‌سازی برای نمایش اصول کاری الگوریتم ژنتیک استفاده است، با این حال، الگوریتم ژنتیک به راحتی قادر به کمینه‌سازی مسائل مختلف نیز خواهد بود. برای پیاده‌سازی الگوریتم‌های ژنتیک، وظایف خاصی باید تعریف و توسط این الگوریتم، جهت بهینه‌سازی توابع مختلف، اجرا شوند.

کدبندی متغیرهای مسأله

برای اینکه الگوریتم ژنتیک قادر باشد تا تابع بالا را بیشینه کند، متغیرهای $$x _ { i }$$ باید توسط یک ساختار رشته‌ای کدبندی شوند. شایان توجه است که کدبندی متغیرهای مسأله، کاملا ضروری نیست. در تحقیقات انجام شده توسط محققان این حوزه، الگوریتم‌های ژنتیکی پیاده‌سازی شده‌اند که به جای کدبندی متغیرهای مسأله، به طور مستقیم روی خود متغیرها عمل می‌کنند. با این حال، این دسته از الگوریتم‌ها به نوعی استثناء محسوب می‌شوند و در این مطلب، کدبندی متغیرهای مسأله به عنوان یکی از وظایف اصلی الگوریتم‌های ژنتیک مرسوم لحاظ شده است.

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

از کدبندی مبتنی بر رشته‌های باینری، برای کدبندی متغیرهای مسأله استفاده می‌شود. در الگوریتم ژنتیک، طول رشته باینری معمولا بر حسب دقت مطلوب و مورد انتظار از مسأله بهینه‌سازی تعیین می‌شود. به عنوان نمونه، اگر از چهار بیت برای کدبندی یک مسأله بهینه‌سازی دو متغیره استفاده شود، رشته‌های (0000 0000) و (1111 1111) به ترتیب متناظر با دو نقطه $$( x _ 1 ^ l , x _ 2 ^ l ) ^ { T }$$ و $$( x _ 1 ^ u , x _ 2 ^ u ) ^ { T } $$ در فضای جواب مسأله خواهند بود؛ زیرا، زیررشته‌های (0000) و (1111) حد بالا و پایین یک نقطه در فضای جستجوی مسأله را نمایش خواهند داد.

در کدبندی متغیرهای مسأله، با استفاده از یک «قانون نگاشت» (Mapping Rule) ثابت، هر رشته هشت بیتی را می‌توان به یک نقطه در فضای جستجوی مسأله نگاشت کرد. معمولا از قانون نگاشت خطی زیر، برای نگاشت یک رشته هشت بیتی به یک نقطه در فضای جستجوی مسأله استفاده می‌شود:

$$x _ { i } = x _ i ^ l + \frac { x _ i ^ u - x _ i ^ l } { 2 ^ { \beta } - 1 } \Large { \sum } _ { j = 0 } ^ \beta \gamma _ { j } 2 ^ { j }$$

در این رابطه، متغیر $$x _ { i }$$ به وسیله زیر رشته $$s _ { i }$$ با طول $$\beta$$ کدبندی شده است. مقدار کدگشایی شده زیر رشته $$s _ { i }$$، از طریق عبارت $$ \sum _ { j = 0 } ^ \beta \gamma _ { j } 2 ^ { j }$$ محاسبه می‌شود. همچنین، $$s _ { i }$$ به وسیله مقادیر (0 ، 1) و رشته $$s$$، در قالب $$( s _ { \beta - 1 } , s _ { \beta - 1 } , . . . . , s _ { 1 } , s _ { 0 } )$$ نمایش داده می‌شوند. به عنوان نمونه، با استفاده از رابطه $$ \sum _ { j = 0 } ^ \beta \gamma _ { j } 2 ^ { j }$$، مقدار کدگشایی شده برای رشته چهار بیتی (0111)، برابر با مقدار 7 محاسبه خواهد شد.

شایان توجه است که برای یک رشته 4 بیتی، از آنجایی که هر بیت تنها می‌تواند مقادیر 0 یا 1 به خود اختیار کند، تنها 16 زیر رشته متمایز قابل تعریف خواهد بود. دقت قابل استحصال توسط کدبندی چهار بیتی، تقریبا برابر با یک شانزدهم (1/16) فضای جستجوی مسأله است. اما اگر طول رشته به 5 افزایش پیدا کند، دقت قابل استحصال توسط کدبندی پنج بیتی، تقریبا برابر با یک سی و دوم (1/32) فضای جستجوی مسأله خواهد شد.

بنابراین، طول زیر رشته‌های نمایش دهنده مقادیر متغیرها، وابستگی مستقیم به دقت مطلوب و مورد انتظار از متغیرها دارد. طول زیر رشته‌ها، بسته به دقت مطلوب و مورد انتظار از نتایج الگوریتم، متغیر است؛ هر چقدر طول رشته‌ها بیشتر باشد، دقت نتایج خروجی بیشتر می‌شود. رابطه میان طول رشته $$ \beta$$ و دقت نتایج تولید شده $$\alpha$$ از طریق رابطه زیر به دست می‌آید:

$$( { x _ i ^ u - x _ i ^ l } ) \; 10 ^ { \alpha } \leq ( { 2 ^ { \beta } - 1 } )$$

به محض اینکه فرایند کدبندی متغیرهای مسأله به پایان رسید، هر کدام از نقاط متناظر با مقادیر متغیرهای مسأله، $$x = ( x _ { 1 } , x _ { 2 } , . . . . . , x _ { N } ) ^ { T }$$، تولید و در فضای جستجوی مسأله قرار داده خواهند شد. پس از تولید نقاط متناظر با مقادیر متغیرهای مسأله در فضای جستجو، مقدار تابع در نقطه $$x$$، از طریق جایگذاری $$x$$ در یک تابع هدف داده شده یا همان $$f(x)$$، محاسبه خواهد شد.

تابع برازندگی

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

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

در الگوریتم ژنتیک، کروموزوم‌ها یا موجودیت‌هایی که بیشترین برازندگی را دارند، نسبت به دیگر کروموزوم‌های موجود در جمعیت، شانس بیشتری برای ترکیب و جهش (عملگرهای ژنتیکی) خواهند داشت. عملکرد صحیح برخی از عملگرهای ژنتیکی منوط به تعریف توابع برازندگی «نامنفی» (Non-Negative) است؛ با این حال، دیگر عملگرهای ژنتیکی، پیش‌شرط نامنفی بودن تابع برازندگی را برای انجام عملیات خود تعریف نمی‌کنند. در مسائل بیشینه‌سازی، می‌توان تابع برازندگی را معادل تابع هدف در گرفت. به عبارت دیگر:

$$F ( i ) = O ( i ) \; \; \rightarrow \; \; Objective \; function \; ( i ) = Fitness \; function \; ( i )$$

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

$$F ( x ) = \frac { 1 } { 1 + f ( x ) }$$

در این رابطه، $$F ( x )$$ تابع برازندگی و $$f ( x )$$ تابع هدف مسأله کمینه‌سازی تعریف شده است. این تبدیل، مکان جواب کمینه در فضای جواب‌های مسأله را تغییر نمی‌دهد ولی یک مسأله کمینه‌سازی را به یک مسأله بیشینه‌سازی معادل آن تبدیل می‌کند. تابع جایگزین دیگری که جهت تبدیل تابع هدف به مقدار برازندگی کروموزوم $$i$$،  یا $$F ( i )$$، مورد استفاده قرار می‌گیرد، به شکل زیر تعریف می‌شود.

$$F ( i ) = V - \frac { O ( i ) P } { \sum _ { i = 1 } ^ P O ( i ) }$$

در این رابطه، $$O ( i )$$ مقدار تابع هدف موجودیت یا کروموزوم $$i$$اُم، $$P$$ اندازه جمعیت و $$V$$ یک مقدار بزرگ است که نا‌منفی شدن مقادیر برازندگی را تضمین می‌کند. مقدار $$V$$ در این تبدیل، معمولا برابر مقدار بیشینه عبارت $$\frac { O ( i ) P } { \sum _ { i = 1 } ^ P O ( i ) }$$ در نظر گرفته می‌شود؛ در چنین حالتی، مقدار برازندگی متناظر با مقدار بیشینه تابع هدف، برابر با صفر می‌شود. این تبدیل نیز مکان جواب کمینه را در فضای جواب‌های مسأله تغییر نمی‌دهد ولی یک مسأله کمینه‌سازی را به یک مسأله بیشینه‌سازی معادل آن تبدیل می‌کند. به مقدار تابع برازندگی یک رشته، «برازندگی رشته» (String Fitness) نیز گفته می‌شود.

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

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

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

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

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

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

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

عملگر تولید مثل

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

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

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

عملگر انتخاب مبتنی بر چرخ رولت

یکی از عملگرهای شایع و پرکاربرد برای تولید مثل در الگوریتم ژنتیک، روش «انتخاب چرخ رولت» (Roulette-Wheel Selection) نام دارد. در این عملگر، احتمال انتخاب یک رشته یا کروموزوم برای قرار گرفتن در مخزن Mating Pool، متناسب با برازندگی آن رشته یا کروموزم محاسبه می‌شود. بنابراین، احتمال قرار گرفتن رشته $$i$$اُم در مخزن Mating Pool، متناسب یا برازندگی آن یا $$F _ { i }$$ خواهد بود.

از آنجایی در الگوریتم ژنتیک اندازه جمعیت ثابت است، حاصل جمع تمامی احتمالات محاسبه شده برای انتخاب و قرار گرفتن کروموزوم‌ها یا رشته‌ها در مخزن Mating Pool، برابر با 1 خواهد بود. بنابراین، احتمال انتخاب و قرار گرفتن رشته $$i$$اُم در مخزن Mating Pool، برابر است با:

$$p _ { i } = \frac { F _ { i } } { \sum _ { i = 1 } ^ n F _ { i } }$$

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

از آنجایی که محیط چرخ رولت، متناسب با برازندگی هر یک از رشته‌ها یا کروموزوم‌ها نشانه‌گذاری شده است، انتظار می‌رود که $$F _ { i } / \overline { F }$$ کپی از رشته $$i$$اُم توسط این عملگر، در مخزن Mating Pool تولید شود. برازندگی میانگین جمعیت کروموزوم‌ها نیز به شکل زیر محاسبه می‌شود.

$$ \overline { F } = \sum_ { i = 1 } ^ n F _ { i }$$

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

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

$$ p _ { i } = \frac { F _ { i }}{ \sum_ { i = 1 } ^ n F _ { i } } $$

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

جمعیتبرازندگیاحتمال انتخاباحتمال تجمعی
1250٫250٫25
250٫050٫30
3400٫400٫70
4100٫100٫80
5200٫201

به عنوان نمونه، به مثال جمعیت بالا توجه کنید. برای انتخاب $$n$$ موجودیت یا کروموزوم از بین جمعیت نسل فعلی، تعداد $$n$$ عدد تصادفی بین صفر و یک تولید خواهد شد. سپس، به ازاء هر کدام از مقادیر تصادفی تولید شده، شرط‌های زیر به ترتیب چک می‌شوند:

  • در صورتی که مقدار تصادفی تولید شده کوچکتر از احتمال تجمعی کروموزوم اول (0٫25) باشد، کروموزوم 1 انتخاب می‌شود. در غیر این صورت، شرط بعدی چک می‌شود.
  • در صورتی که مقدار تصادفی تولید شده کوچکتر از احتمال تجمعی کروموزوم دوم (0٫30) باشد، کروموزوم 2 انتخاب می‌شود. در غیر این صورت، شرط بعدی چک می‌شود
  • در صورتی که مقدار تصادفی تولید شده کوچکتر از احتمال تجمعی کروموزوم سوم (0٫70) باشد، کروموزوم 3 انتخاب می‌شود. در غیر این صورت، شرط بعدی چک می‌شود.
  • در صورتی که مقدار تصادفی تولید شده کوچکتر از احتمال تجمعی کروموزوم چهارم (0٫80) باشد، کروموزوم 4 انتخاب می‌شود. در غیر این صورت، شرط بعدی چک می‌شود.
  • در نهایت، در صورتی هیچ یک از شرط‌های بالا صحیح نباشند، کروموزوم 5 انتخاب می‌شود.

عملگر انتخاب باقی مانده تصادفی (بدون جایگذاری)

 این عملگر، روش بهتری برای انتخاب رشته‌ها یا کروموزوم‌ها است. ایده اصلی این روش این است که رشته‌ها یا کروموزوم‌ها، بر اساس تعداد دفعات تولید مثل از آن‌ها، از جمعیت جدید حذف و یا در جمعیت جدید تکثیر می‌شوند. برای چنین کاری، پارامتر تعداد «دفعات تولید مثل» (Reproduction Count) به ازاء هر کدام از رشته‌ها یا کروموزوم‌ها محاسبه می‌شود.

پارامتر تعداد دفعات تولید مثل متناظر با هر یک از رشته‌ها یا کروموزوم‌ها، بر اساس مقدار برازندگی (هر کدام از رشته‌ها) و بدون جایگذاری محاسبه خواهد شد. این روش، نسبت به دیگر عملگرهای انتخاب برتر است و برای استفاده در الگوریتم ژنتیک پیشنهاد می‌شود. در این عملگر، ابتدا احتمال انتخاب یا $$ p _ { s }$$ به شکل زیر محاسبه می‌شود:

$$ p _ { s } = \frac { F ( i ) } { \sum F ( i ) }$$

بنابراین، تعداد دفعات تولید مثل‌ مورد انتظار به ازاء هر رشته یا کروموزوم، از طریق رابطه زیر محاسبه می‌شود:

$$ e _ { i }= p _ { s } \times P$$

در این رابطه، $$P$$ برابر با اندازه جمعیت است. از قسمت کسری مقادیر $$e _ { i }$$ تولید شده به ازاء هر رشته یا کروموزوم، به عنوان احتمالات انتخاب آن کروموزوم‌ها استفاده می‌‌شود. به عنوان نمونه، در صورتی که پارامتر تعداد دفعات تولید مثل‌ مورد انتظار یک رشته یا کروموزوم، برابر با $$e _ { i }= 1.5$$ باشد، حتما یک کپی از این رشته در جمعیت جدید وجود خواهد داشت. همچنین، یک کپی دیگر با احتمال 0٫50، برای قرار گرفتن در جمعیت جدید انتخاب خواهد شد.

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

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

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

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

عملگر ترکیب یا آمیزش

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

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

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

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

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

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

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

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

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

وقتی که در الگوریتم ژنتیک، پارامتر احتمال ترکیب تعریف می‌شود، یعنی تنها $$p _ { c }$$ درصد از رشته‌ها یا کروموزوم‌های موجود در جمعیت، توسط عملگر ترکیب دستکاری می‌شوند. به عبارت دیگر، $$(1 - p _ { c })$$ درصد از رشته‌ها یا کروموزوم‌های موجود در جمعیت، به همان شکل اصلی خودشان در جمعیت نسل فعلی باقی خواهند ماند.

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

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

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

عملیات ترکیب تک نقطه‌ای

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

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

عملیات ترکیب دو نقطه‌ای

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

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

عملگر جهش

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

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

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

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

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

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

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

01101011
00111101
00010110
01111100

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

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

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

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

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

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

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

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

برای اینکه با عملکرد الگوریتم ژنتیک در همگرایی به جواب بهینه بهتر آشنا شویم، یک تابع دو متغیری ساده با استفاده از الگوریتم ژنتیک حل خواهد شد. گام‌های تفصیلی و جواب‌های حاصل شده در ادامه نمایش داده شده‌اند. مسأله کمینه‌سازی زیر را در بازه $$0 \leq x _ { 1 } , x _ { 2 } \leq 6$$ در نظر بگیرید:

$$f ( x _ { 1 } , x _ { 2 } ) = ( x _ { 1 } ^ 2 + x _ { 2 } - 11 ) + ( x _ { 1 } + x _ { 2 } ^ 2 - 7 ) ^ 2$$

جواب بهینه سراسری برای مسأله بهینه‌سازی فوق در نقطه $$( 3 , 2 ) ^ T$$ حاصل می‌شود. در این نقطه، مقدار تابع هدف نمایش داده شده برابر با صفر خواهد بود.

مرحله اول

برای حل این مسأله توسط الگوریتم ژنتیک، از کدبندی باینری برای نمایش متغیرهای $$x _ { 1 }$$ و $$x _ { 2 }$$ استفاده می‌شود. در این مسأله، از 10 بیت برای نمایش هر متغیر استفاده شده است؛ در نتیجه، از آنجایی که مسأله دو متغیری است، طول رشته یا کروموزوم برابر با 20 خواهد بود.

با انتخاب ده بیت برای نمایش متغیرهای مسأله، الگوریتم ژنتیک به دقتی برابر با $$(6 - 0 ) ( 2 ^ { 1 0 } -1 )$$ یا ۰٫۰۰۶ در بازه (6 ، 0) دست خواهد یافت. احتمال ترکیب ($$p _ { c }$$) و احتمال جهش ($$p _ { m }$$) به ترتیب برابر با 0٫۸ و ۰٫05 در نظر گرفته شده است.

اندازه جمعیت برابر با 20 و تعداد نسل‌ها نیز برابر با 30 خواهد بود. از یک مولد تصادفی تعبیه شده برای تولید مقادیر تصادفی و از یک «نمونه‌گیری تصادفی بدون جای‌گذاری» (Stochastic Sampling Without Replacement) به عنوان عملگر انتخاب یا تولید مثل استفاده می‌شود. در مرحله بعد، برازندگی تمامی رشته‌ها یا کروموزوم‌های موجود در جمعیت سنجیده می‌شود. در این مثال کاربردی، تنها برازندگی رشته یا کروموزوم اول محاسبه می‌شود.

مرحله دوم

در این مرحله، برازندگی تمامی رشته‌ها یا کروموزوم‌های موجود در جمعیت سنجیده می‌شود. این کار از طریق کد گشایی رشته‌ها یا کروموزوم‌ها انجام می‌شود. زیر رشته اول (1000001110) با استفاده از تابع زیر به مقداری برابر با $$( 2 ^ 9 + 2 ^ 3 + 2 ^ 2 + 2 ^ 1 )$$ یا 525 کد گشایی می‌شود.

$$ \sum _ { j = 0 } ^ \beta \gamma _ { j } 2 ^ { j }$$

بنابراین، با استفاده از تابع زیر، مقدار پارامتر متناظر، برابر با $$0 + ( 6 - 0 ) \star \frac { 525 } { 1023 }$$  یا 3٫۰۹ خواهد بود.

$$x _ { i } = x _ i ^ l + \frac { x _ i ^ u - x _ i ^ l } { 2 ^ { \beta } - 1 } \Large { \sum } _ { j = 0 } ^ \beta \gamma _ { j } 2 ^ { j }$$

همچنین، فرض کنید که زیر رشته دوم (0001110000) به مقداری برابر با 12 کد گشایی می‌شود. مقدار پارامتر متناظر با این زیر رشته، $$0 + ( 6 - 0 ) \star \frac { 112 } { 1023 }$$ یا 0٫۶۶ خواهد شد. بنابراین اولین زیر رشته، برابر با نقطه $$x ^ 0 = ( 3.09 , 0.66 ) ^ T$$ در فضای جستجوی مسأله خواهد بود. با جای‌گذاری این مقادیر در تابع هدف، مقدار تابع هدف برابر با ۱۲٫۸۱۶ برای رشته اول در نقطه $$x ^ 0 = ( 3.09 , 0.66 ) ^ T$$ تولید خواهد شد.

با توجه به اینکه مسأله بهینه‌سازی تعریف شده در اصل یک مسأله کمینه‌سازی است، مقدار برازندگی رشته اول به شکل $$F ( x ^ { ( 1 ) } ) = \frac { 1.0 } { ( 1.0 + 12.816 ) } = 0.072$$ محاسبه می‌شود. از مقدار برازندگی محاسبه شده، در عملیات تولید مثل (عملگر انتخاب یا تولید مثل) استفاده می‌شود. جدول زیر، جزئیات مرتبط با رشته‌ها یا کروموزوم‌های دوم تا دهم جمعیت را نشان می‌دهد.

جزئیات مربوط به رشته‌های دوم (شماره 1) تا دهم (شماره 9) تا مرحله انتخاب یا تولید مثل کروموزوم‌ها

شمارهزیر رشته اولزیر رشته دومپارامتر اولپارامتر دوممقدار تابع هدفمقدار تابع برازندگیتعداد کپی‌ها در نسل بعد
1110011000001011111104.72.2207.90.0051
2001011011000001100001.00.2126.00.0081
3010000100110000110111.53.150.00.0202
4101100110101001110104.21.873.00.0141
5100111100101111000113.72.853.90.0181
6100011101111011111113.35.2601.20.0020
7001110011110011101001.33.692.70.0111
8011000110110111111112.34.5243.40.0041
9001010101110001100001.03.267.90.0141

مرحله سوم

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

مرحله چهارم

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

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

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

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

جزئیات مربوط به رشته‌های دوم (شماره 1) تا دهم (شماره 9) پس از عملیات ترکیب و جهش روی جمعیت

شمارهزیر رشته اولزیر رشته دومپارامتر اولپارامتر دوممقدار تابع هدفمقدار تابع برازندگی
1011010000000011111102.40.734.60.028
2001011011110011100000.51.0122.50.008
3010000100100000110011.03.694.00.011
4101000111110101111101.50.1100.60.010
5100111101101111000113.84.1252.20.004
6001110101110010000113.72.855.00.018
711001000011000101101001.33.467.40.015
8111000110101101111015.32.6427.70.002
9001110111001010100001.41.953.00.018

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

موقعیت جواب‌های کاندید (جمعیت اولیه) در فضای جستجوی مسأله
همگرایی سریع جواب‌های کاندید به جواب بهینه در الگوریتم ژنتیک پس از 30 نسل

تفاوت الگوریتم ژنتیک و الگوریتم‌های بهینه‌سازی و جستجوی سنتی

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

  • الگوریتم ژنتیک از طریق کدبندی مجموعه جواب‌های کاندید، توابع را بهینه و مسائل بهینه‌سازی را حل می‌کند. در حالی که الگوریتم‌های ‌بهینه‌سازی و جستجوی سنتی، از مجموعه جواب‌های کاندید برای بهینه‌سازی استفاده می‌کنند.
  • الگوریتم ژنتیک، مجموعه‌ای از جواب‌های کاندید را برای یافتن جواب بهینه جستجو می‌کند. در حالی که الگوریتم‌های بهینه‌سازی و جستجوی سنتی، از همان ابتدا به دنبال یک جواب واحد هستند.
  • الگوریتم ژنتیک، از اطلاعات مرتبط با تابع برازندگی برای حل مسائل بهینه‌سازی بهره می‌برد. در حالی که الگوریتم‌های بهینه‌سازی و جستجوی سنتی، از مشتق تابع هدف و دیگر اطلاعات کمکی استفاده می‌کنند.
  • الگوریتم ژنتیک از قوانین گذار «احتمالی» (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) در طول فرایند تکامل.
  • مدل‌های اقتصادی: مدل‌سازی فرایند نوآوری، توسعه استراتژی‌های مناقصه و ظهور بازارهای اقتصادی.
الگوریتم ژنتیک
طراحی خودکار آنتن استفاده شده در ماموریت‌های فضایی ناسا (NASA's Space Technology) توسط الگوریتم‌های تکاملی

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

در این بخش، کدهای پیاده‌سازی الگوریتم ژنتیک برای مدل‌سازی و حل «الگوریتم راسو» (Weasel algorithm) [+] نمایش داده شده است. هدف این الگوریتم این است که نشان دهد تغییرات تصادفی در ژ‌ن‌ها و ترکیب آن‌ها با یک مکانیزم انتخاب غیر تصادفی، منجر به تولید نتایجی متفاوت و بهتر از شانس خالص در فرایندهای تکاملی خواهد شد. مشخصات این مسأله به شکل زیر است:

  • جمعیت اولیه: یک آرایه 28 عنصری متشکل از الفبای ABCDEFGHIJKLMNOPQRSTUVWXYZ.
  • هدف نهایی: تبدیل رشته ورودی یا جمعیت اولیه به رشته METHINKS IT IS LIKE A WEASEL.
  • تابع برازندگی: تابعی که شباهت آرگومان ورودی را به رشته نهایی یا هدف نهایی مشخص می‌کند.
  • عملگرهای تکاملی (پیاده‌سازی عملگر انتخاب و جهش ضروری است، ولی پیاده‌سازی عملگر ترکیب اختیاری است)

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

1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4 
5const char target[] = "METHINKS IT IS LIKE A WEASEL";
6const char tbl[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ ";
7 
8#define CHOICE (sizeof(tbl) - 1)
9#define MUTATE 15
10#define COPIES 30
11 
12/* returns random integer from 0 to n - 1 */
13int irand(int n)
14{
15	int r, rand_max = RAND_MAX - (RAND_MAX % n);
16	while((r = rand()) >= rand_max);
17	return r / (rand_max / n);
18}
19 
20/* number of different chars between a and b */
21int unfitness(const char *a, const char *b)
22{
23	int i, sum = 0;
24	for (i = 0; a[i]; i++)
25		sum += (a[i] != b[i]);
26	return sum;
27}
28 
29/* each char of b has 1/MUTATE chance of differing from a */
30void mutate(const char *a, char *b)
31{
32	int i;
33	for (i = 0; a[i]; i++)
34		b[i] = irand(MUTATE) ? a[i] : tbl[irand(CHOICE)];
35 
36	b[i] = '\0';
37}
38 
39int main()
40{
41	int i, best_i, unfit, best, iters = 0;
42	char specimen[COPIES][sizeof(target) / sizeof(char)];
43 
44	/* init rand string */
45	for (i = 0; target[i]; i++)
46		specimen[0][i] = tbl[irand(CHOICE)];
47	specimen[0][i] = 0;
48 
49	do {
50		for (i = 1; i < COPIES; i++)
51			mutate(specimen[0], specimen[i]);
52 
53		/* find best fitting string */
54		for (best_i = i = 0; i < COPIES; i++) {
55			unfit = unfitness(target, specimen[i]);
56			if(unfit < best || !i) {
57				best = unfit;
58				best_i = i;
59			}
60		}
61 
62		if (best_i) strcpy(specimen[0], specimen[best_i]);
63		printf("iter %d, score %d: %s\n", iters++, best, specimen[0]);
64	} while (best);
65 
66	return 0;
67}

خروجی:

1iter 0, score 26: WKVVYFJUHOMQJNZYRTEQAGDVXKYC
2iter 1, score 25: WKVVTFJUHOMQJN YRTEQAGDVSKXC
3iter 2, score 25: WKVVTFJUHOMQJN YRTEQAGDVSKXC
4iter 3, score 24: WKVVTFJUHOMQJN YRTEQAGDVAKFC
5...
6iter 221, score 1: METHINKSHIT IS LIKE A WEASEL
7iter 222, score 1: METHINKSHIT IS LIKE A WEASEL
8iter 223, score 0: METHINKS IT IS LIKE A WEASEL

پیاده‌سازی الگوریتم ژنتیک با C#‎‏

1using System;
2using System.Collections.Generic;
3using System.Linq;
4 
5static class Program {
6    static Random Rng = new Random((int)DateTime.Now.Ticks);
7 
8    static char NextCharacter(this Random self) {
9        const string AllowedChars = " ABCDEFGHIJKLMNOPQRSTUVWXYZ";
10        return AllowedChars[self.Next() % AllowedChars.Length];
11    }
12 
13    static string NextString(this Random self, int length) {
14        return String.Join("", Enumerable.Repeat(' ', length)
15            .Select(c => Rng.NextCharacter()));
16    }
17 
18    static int Fitness(string target, string current) {
19        return target.Zip(current, (a, b) => a == b ? 1 : 0).Sum();
20    }
21 
22    static string Mutate(string current, double rate) {
23        return String.Join("", from c in current
24               select Rng.NextDouble() <= rate ? Rng.NextCharacter() : c);
25    }
26 
27    static void Main(string[] args) {
28        const string target = "METHINKS IT IS LIKE A WEASEL";
29        const int C = 100;
30        const double P = 0.05;
31 
32        // Start with a random string the same length as the target.
33        string parent = Rng.NextString(target.Length);
34 
35        Console.WriteLine("START:       {0,20} fitness: {1}", 
36            parent, Fitness(target, parent));
37        int i = 0;
38 
39        while (parent != target) {
40            // Create C mutated strings + the current parent.
41            var candidates = Enumerable.Range(0, C + 1)
42                .Select(n => n > 0 ? Mutate(parent, P) : parent);
43 
44            // select the fittest
45            parent = candidates.OrderByDescending(c => Fitness(target, c)).First();
46 
47            ++i;
48            Console.WriteLine("     #{0,6} {1,20} fitness: {2}", 
49                i, parent, Fitness(target, parent));
50        }
51 
52        Console.WriteLine("END: #{0,6} {1,20}", i, parent);
53    }
54}

خروجی:

1START:       PACQXJB CQPWEYKSVDCIOUPKUOJY fitness: 0
2     #     1 PALQXJB CQPWEYKSVDCIOUPEUOJY fitness: 1
3     #     2 PALQXJB CQPWEYKSVDEIOUPEUOJY fitness: 2
4     #     3 PALQXJB CQPWEYKSVDE OUPEUOJY fitness: 3
5     #     4 MALQOJB CQPWEYKSVDE OUPEUOJY fitness: 4
6     #     5 MALQOJB CQPWEYKSVKE OUPEUOJY fitness: 5
7     #     6 MALQOJB CQPWEYKLVKE OUPEUOES fitness: 7
8     #     7 MALQOJB CQPWEYKLVKE OUPEAOES fitness: 8
9     #     8 M LQOJB CQPWEYKLVKE OUPEAOES fitness: 8
10..............
11     #    60 METHINBS IT IS LIKE A WEASEL fitness: 27
12     #    61 METHINBS IT IS LIKE A WEASEL fitness: 27
13     #    62 METHINKS IT IS LIKE A WEASEL fitness: 28
14END: #    62 METHINKS IT IS LIKE A WEASEL

پیاده‌سازی الگوریتم ژنتیک با C++‎‏

1#include <string>
2#include <cstdlib>
3#include <iostream>
4#include <cassert>
5#include <algorithm>
6#include <vector>
7#include <ctime>
8 
9std::string allowed_chars = " ABCDEFGHIJKLMNOPQRSTUVWXYZ";
10 
11// class selection contains the fitness function, encapsulates the
12// target string and allows access to it's length. The class is only
13// there for access control, therefore everything is static. The
14// string target isn't defined in the function because that way the
15// length couldn't be accessed outside.
16class selection
17{
18public:
19  // this function returns 0 for the destination string, and a
20  // negative fitness for a non-matching string. The fitness is
21  // calculated as the negated sum of the circular distances of the
22  // string letters with the destination letters.
23  static int fitness(std::string candidate)
24  {
25    assert(target.length() == candidate.length());
26 
27    int fitness_so_far = 0;
28 
29    for (int i = 0; i < target.length(); ++i)
30    {
31      int target_pos = allowed_chars.find(target[i]);
32      int candidate_pos = allowed_chars.find(candidate[i]);
33      int diff = std::abs(target_pos - candidate_pos);
34      fitness_so_far -= std::min(diff, int(allowed_chars.length()) - diff);
35    }
36 
37    return fitness_so_far;
38  }
39 
40  // get the target string length
41  static int target_length() { return target.length(); }
42private:
43  static std::string target;
44};
45 
46std::string selection::target = "METHINKS IT IS LIKE A WEASEL";
47 
48// helper function: cyclically move a character through allowed_chars
49void move_char(char& c, int distance)
50{
51  while (distance < 0)
52    distance += allowed_chars.length();
53  int char_pos = allowed_chars.find(c);
54  c = allowed_chars[(char_pos + distance) % allowed_chars.length()];
55}
56 
57// mutate the string by moving the characters by a small random
58// distance with the given probability
59std::string mutate(std::string parent, double mutation_rate)
60{
61  for (int i = 0; i < parent.length(); ++i)
62    if (std::rand()/(RAND_MAX + 1.0) < mutation_rate)
63    {
64      int distance = std::rand() % 3 + 1;
65      if(std::rand()%2 == 0)
66        move_char(parent[i], distance);
67      else
68        move_char(parent[i], -distance);
69    }
70  return parent;
71}
72 
73// helper function: tell if the first argument is less fit than the
74// second
75bool less_fit(std::string const& s1, std::string const& s2)
76{
77  return selection::fitness(s1) < selection::fitness(s2);
78}
79 
80int main()
81{
82  int const C = 100;
83 
84  std::srand(time(0));
85 
86  std::string parent;
87  for (int i = 0; i < selection::target_length(); ++i)
88  {
89    parent += allowed_chars[std::rand() % allowed_chars.length()];
90  }
91 
92  int const initial_fitness = selection::fitness(parent);
93 
94  for(int fitness = initial_fitness;
95      fitness < 0;
96      fitness = selection::fitness(parent))
97  {
98    std::cout << parent << ": " << fitness << "\n";
99    double const mutation_rate = 0.02 + (0.9*fitness)/initial_fitness;
100    std::vector<std::string> childs;
101    childs.reserve(C+1);
102 
103    childs.push_back(parent);
104    for (int i = 0; i < C; ++i)
105      childs.push_back(mutate(parent, mutation_rate));
106 
107    parent = *std::max_element(childs.begin(), childs.end(), less_fit);
108  }
109  std::cout << "final string: " << parent << "\n";
110}

خروجی:

BBQYCNLDIHG   RWEXN PNGFTCMS: -203
ECPZEOLCHFJBCXTXFYLZQPDDQ KP: -177
HBSBGMKEEIM BUTUGWKWNRCGSZNN: -150
EEUCGNKDCHN  RSSITKZPRBESYQK: -134
GBRFGNKDAINX TVRITIZPSBERXTH: -129
JEUFILLDDGNZCWYRIWFWSUAERZUI: -120
JESGILIGDJOZCWXRIWFVSXZESXXI: -109
JCSHILIIDIOZCTZOIUIVVXZEUVXI: -93
...........
NETHINKS IT JS LHKE A WEASEL: -3
NETHINKS IT JS LIKE A WEASEL: -2
NETHINKS IT JS LIKE A WEASEL: -2
NETHINKS IT JS LIKE A WEASEL: -2
NETHINKS IT JS LIKE A WEASEL: -2
NETHINKS IT JS LIKE A WEASEL: -2
NETHINKS IT JS LIKE A WEASEL: -2
METHINKS IT JS LIKE A WEASEL: -1
METHINKS IT JS LIKE A WEASEL: -1
METHINKS IT JS LIKE A WEASEL: -1
final string: METHINKS IT IS LIKE A WEASEL

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

1import java.util.Random;
2 
3public class EvoAlgo {
4  static final String target = "METHINKS IT IS LIKE A WEASEL";
5  static final char[] possibilities = "ABCDEFGHIJKLMNOPQRSTUVWXYZ ".toCharArray();
6  static int C = 100; //number of spawn per generation
7  static double minMutateRate = 0.09;
8  static int perfectFitness = target.length();
9  private static String parent;
10  static Random rand = new Random();
11 
12  private static int fitness(String trial){
13    int retVal = 0;
14    for(int i = 0;i < trial.length(); i++){
15      if (trial.charAt(i) == target.charAt(i)) retVal++;
16    }
17    return retVal;
18  }
19 
20  private static double newMutateRate(){
21    return (((double)perfectFitness - fitness(parent)) / perfectFitness * (1 - minMutateRate));
22  }
23 
24  private static String mutate(String parent, double rate){
25    String retVal = "";
26    for(int i = 0;i < parent.length(); i++){
27      retVal += (rand.nextDouble() <= rate) ?
28        possibilities[rand.nextInt(possibilities.length)]:
29        parent.charAt(i);
30    }
31    return retVal;
32  }
33 
34  public static void main(String[] args){
35    parent = mutate(target, 1);
36    int iter = 0;
37    while(!target.equals(parent)){
38      double rate = newMutateRate();
39      iter++;
40      if(iter % 100 == 0){
41        System.out.println(iter +": "+parent+ ", fitness: "+fitness(parent)+", rate: "+rate);
42      }
43      String bestSpawn = null;
44      int bestFit = 0;
45      for(int i = 0; i < C; i++){
46        String spawn = mutate(parent, rate);
47        int fitness = fitness(spawn);
48        if(fitness > bestFit){
49          bestSpawn = spawn;
50          bestFit = fitness;
51        }
52      }
53      parent = bestFit > fitness(parent) ? bestSpawn : parent;
54    }
55    System.out.println(parent+", "+iter);
56  }
57 
58}

خروجی:

100: MEVHIBXSCG TP QIK FZGJ SEL, fitness: 13, rate: 0.4875
200: MEBHINMSVI IHTQIKW FTDEZSWL, fitness: 15, rate: 0.42250000000000004
300: METHINMSMIA IHUFIKA F WEYSEL, fitness: 19, rate: 0.29250000000000004
400: METHINSS IT IQULIKA F WEGSEL, fitness: 22, rate: 0.195
METHINKS IT IS LIKE A WEASEL, 492

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

1%This class impliments a string that mutates to a target
2classdef EvolutionaryAlgorithm
3 
4    properties
5 
6        target;
7        parent;
8        children = {};
9        validAlphabet;
10 
11        %Constants
12        numChildrenPerIteration;
13        maxIterations;
14        mutationRate;
15 
16    end
17 
18    methods
19 
20        %Class constructor
21        function family = EvolutionaryAlgorithm(target,mutationRate,numChildren,maxIterations)
22 
23            family.validAlphabet = char([32 (65:90)]); %Space char and A-Z
24            family.target = target;
25            family.children = cell(numChildren,1);
26            family.numChildrenPerIteration = numChildren;
27            family.maxIterations = maxIterations;
28            family.mutationRate = mutationRate;
29            initialize(family);
30 
31        end %class constructor
32 
33        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
34        %Helper functions and class get/set functions
35        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
36 
37        %setAlphabet() - sets the valid alphabet for the current instance
38        %of the EvolutionaryAlgorithm class.
39        function setAlphabet(family,alphabet)
40 
41            if(ischar(alphabet))
42                family.validAlphabet = alphabet;
43 
44                %Makes change permanent
45                assignin('caller',inputname(1),family); 
46            else
47                error 'New alphabet must be a string or character array';
48            end            
49 
50        end
51 
52        %setTarget() - sets the target for the current instance
53        %of the EvolutionaryAlgorithm class.
54        function setTarget(family,target)
55 
56            if(ischar(target))
57                family.target = target;
58 
59                %Makes change permanent
60                assignin('caller',inputname(1),family); 
61            else
62                error 'New target must be a string or character array';
63            end            
64 
65        end
66 
67        %setMutationRate() - sets the mutation rate for the current instance
68        %of the EvolutionaryAlgorithm class.
69        function setMutationRate(family,mutationRate)
70 
71            if(isnumeric(mutationRate))
72                family.mutationRate = mutationRate;
73 
74                %Makes change permanent
75                assignin('caller',inputname(1),family); 
76            else
77                error 'New mutation rate must be a double precision number';
78            end            
79 
80        end
81 
82        %setMaxIterations() - sets the maximum number of iterations during
83        %evolution for the current instance of the EvolutionaryAlgorithm class.
84        function setMaxIterations(family,maxIterations)
85 
86            if(isnumeric(maxIterations))
87                family.maxIterations = maxIterations;
88 
89                %Makes change permanent
90                assignin('caller',inputname(1),family); 
91            else
92                error 'New maximum amount of iterations must be a double precision number';
93            end            
94 
95        end
96 
97        %display() - overrides the built-in MATLAB display() function, to
98        %display the important class variables
99        function display(family)
100            disp([sprintf('Target: %s\n',family.target)...
101                  sprintf('Parent: %s\n',family.parent)...
102                  sprintf('Valid Alphabet: %s\n',family.validAlphabet)...
103                  sprintf('Number of Children: %d\n',family.numChildrenPerIteration)...
104                  sprintf('Mutation Rate [0,1]: %d\n',family.mutationRate)...
105                  sprintf('Maximum Iterations: %d\n',family.maxIterations)]);                 
106        end
107 
108        %disp() - overrides the built-in MATLAB disp() function, to
109        %display the important class variables
110        function disp(family)
111            display(family);
112        end
113 
114        %randAlphabetElement() - Generates a random character from the
115        %valid alphabet for the current instance of the class.
116        function elements = randAlphabetElements(family,numChars)
117 
118            %Sample the valid alphabet randomly from the uniform
119            %distribution
120            N = length(family.validAlphabet);
121            choices = ceil(N*rand(1,numChars));
122 
123            elements = family.validAlphabet(choices);
124 
125        end
126 
127        %initialize() - Sets the parent to a random string of length equal
128        %to the length of the target
129        function parent = initialize(family)
130 
131            family.parent = randAlphabetElements(family,length(family.target));
132            parent = family.parent;
133 
134            %Makes changes to the instance of EvolutionaryAlgorithm permanent
135            assignin('caller',inputname(1),family); 
136 
137        end %initialize
138 
139        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
140        %Functions required by task specification
141        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
142 
143        %mutate() - generates children from the parent and mutates them
144        function mutate(family)
145 
146            sizeParent = length(family.parent);
147 
148            %Generate mutatant children sequentially
149            for child = (1:family.numChildrenPerIteration)
150 
151                parentCopy = family.parent;
152 
153                for charIndex = (1:sizeParent) 
154                    if (rand(1) < family.mutationRate)
155                        parentCopy(charIndex) = randAlphabetElements(family,1);
156                    end
157                end
158 
159                family.children{child} = parentCopy;
160 
161            end
162 
163            %Makes changes to the instance of EvolutionaryAlgorithm permanent
164            assignin('caller',inputname(1),family);  
165 
166        end %mutate
167 
168        %fitness() - Computes the Hamming distance between the target
169        %string and the string input as the familyMember argument
170        function theFitness = fitness(family,familyMember)
171 
172            if not(ischar(familyMember))
173                error 'The second argument must be a string';
174            end
175 
176            theFitness = sum(family.target == familyMember);
177        end
178 
179        %evolve() - evolves the family until the target is reached or it 
180        %exceeds the maximum amount of iterations        
181        function [iteration,mostFitFitness] = evolve(family)
182 
183            iteration = 0;
184            mostFitFitness = 0;
185            targetFitness = fitness(family,family.target);
186 
187            disp(['Target fitness is ' num2str(targetFitness)]);
188 
189            while (mostFitFitness < targetFitness) && (iteration < family.maxIterations)
190 
191                iteration = iteration + 1;
192 
193                mutate(family);
194 
195                parentFitness = fitness(family,family.parent);                
196                mostFit = family.parent;
197                mostFitFitness = parentFitness;
198 
199                for child = (1:family.numChildrenPerIteration)
200 
201                    childFitness = fitness(family,family.children{child});
202                    if childFitness > mostFitFitness
203                        mostFit = family.children{child};
204                        mostFitFitness = childFitness;
205                    end
206 
207                end               
208 
209                family.parent = mostFit;
210                disp([num2str(iteration) ': ' mostFit ' - Fitness: ' num2str(mostFitFitness)]);
211 
212            end
213 
214            %Makes changes to the instance of EvolutionaryAlgorithm permanent
215            assignin('caller',inputname(1),family);
216 
217        end %evolve
218 
219    end %methods
220end %classdef

اجرا:

1>> instance = EvolutionaryAlgorithm('METHINKS IT IS LIKE A WEASEL',.08,50,1000)
2Target: METHINKS IT IS LIKE A WEASEL
3Parent: UVEOCXXFBGDCSFNMJQNWTPJ PCVA
4Valid Alphabet:  ABCDEFGHIJKLMNOPQRSTUVWXYZ
5Number of Children: 50
6Mutation Rate [0,1]: 8.000000e-002
7Maximum Iterations: 1000
8 
9>> evolve(instance);

خروجی:

Target fitness is 28
1: MVEOCXXFBYD SFCMJQNWTPM PCVA - Fitness: 2
2: MEEOCXXFBYD SFCMJQNWTPM PCVA - Fitness: 3
3: MEEHCXXFBYD SFCMJXNWTPM ECVA - Fitness: 4
4: MEEHCXXFBYD SFCMJXNWTPM ECVA - Fitness: 4
5: METHCXAFBYD SFCMJXNWXPMARPVA - Fitness: 5
6: METHCXAFBYDFSFCMJXNWX MARSVA - Fitness: 6
7: METHCXKFBYDFBFCQJXNWX MATSVA - Fitness: 7
8: METHCXKFBYDFBF QJXNWX MATSVA - Fitness: 8
9: METHCXKFBYDFBF QJXNWX MATSVA - Fitness: 8
10: METHCXKFUYDFBF QJXNWX MITSEA - Fitness: 9
20: METHIXKF YTBOF LIKN G MIOSEI - Fitness: 16
30: METHIXKS YTCOF LIKN A MIOSEL - Fitness: 19
40: METHIXKS YTCIF LIKN A MEUSEL - Fitness: 21
50: METHIXKS YT IS LIKE A PEUSEL - Fitness: 24
100: METHIXKS YT IS LIKE A WEASEL - Fitness: 26
150: METHINKS YT IS LIKE A WEASEL - Fitness: 27
195: METHINKS IT IS LIKE A WEASEL - Fitness: 28

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

1from string import letters
2from random import choice, random
3 
4target  = list("METHINKS IT IS LIKE A WEASEL")
5charset = letters + ' '
6parent  = [choice(charset) for _ in range(len(target))]
7minmutaterate  = .09
8C = range(100)
9 
10perfectfitness = float(len(target))
11 
12def fitness(trial):
13    'Sum of matching chars by position'
14    return sum(t==h for t,h in zip(trial, target))
15 
16def mutaterate():
17    'Less mutation the closer the fit of the parent'
18    return 1-((perfectfitness - fitness(parent)) / perfectfitness * (1 - minmutaterate))
19 
20def mutate(parent, rate):
21    return [(ch if random() <= rate else choice(charset)) for ch in parent]
22 
23def que():
24    '(from the favourite saying of Manuel in Fawlty Towers)'
25    print ("#%-4i, fitness: %4.1f%%, '%s'" %
26           (iterations, fitness(parent)*100./perfectfitness, ''.join(parent)))
27 
28def mate(a, b):
29    place = 0
30    if choice(xrange(10)) < 7:
31        place = choice(xrange(len(target)))
32    else:
33        return a, b
34 
35    return a, b, a[:place] + b[place:], b[:place] + a[place:]
36 
37iterations = 0
38center = len(C)/2
39while parent != target:
40    rate = mutaterate()
41    iterations += 1
42    if iterations % 100 == 0: que()
43    copies = [ mutate(parent, rate) for _ in C ]  + [parent]
44    parent1 = max(copies[:center], key=fitness)
45    parent2 = max(copies[center:], key=fitness)
46    parent = max(mate(parent1, parent2), key=fitness)
47que()

خروجی:

#100 , fitness: 50.0%, 'DVTAIKKS OZ IAPYIKWXALWE CEL'
#200 , fitness: 60.7%, 'MHUBINKMEIG IS LIZEVA WEOPOL'
#300 , fitness: 71.4%, 'MEYHINKS ID SS LIJF A KEKUEL'

#378 , fitness: 100.0%, 'METHINKS IT IS LIKE A WEASEL'

فیلم آموزش تئوری و عملی الگوریتم ژنتیک و پیاده سازی آن در MATLAB

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

جمع‌بندی

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

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

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

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

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۷۰ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
DATAJOBS
۱۷ دیدگاه برای «الگوریتم ژنتیک – از صفر تا صد»

الگوریتم بهینه سازی NSGA ii رو شرحش رو میگذارید لطفا؟

در بیان پایه‌های تولثد کروموزوم از دی ان آ که چهذ مورد هست یک اشتباه صورت گرفته و جای T و G اشتباه نوشته شده است.

سلام
یعنی هر چی زمان میگذره انسان های بهتری متولد میشن؟

با سلام و احترام؛

صمیمانه از همراهی شما با مجله فرادرس و ارائه بازخورد سپاس‌گزاریم.

این مورد اصلاح شد.

برای شما آرزوی سلامتی و موفقیت داریم.

سلام
فوق العاده بود.

سلام
من یه سوال داشتم اینکه روشهای انتخاب جمعیت جدید تو این الگوریتم ژنتیک به چه صورتی هست اگه میشه لطفا توضیح بدید ممنون میشم؟

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

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

سلام سوالی داشتم از محضرتون چرا در الگوریتم ژنتیک چند هدفه با تغییر تعداد اعضای جمعیت تعداد نقاط پارتو تغییر میکنه؟

سلام در مسئله مطرح شده متغیر ها بین 0 تا 6 تغییر میکنند که به اشتباه در صورت سوال بین 0 تا 0 ذکر شده

با سلام و احترام؛

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

برای شما آرزوی سلامتی و موفقیت داریم.

در انتهای جمله “اما اگر طول رشته به 5 افزایش پیدا کند، دقت قابل استحصال توسط کدبندی پنج بیتی، تقریبا برابر با یک شانزدهم (1/32) فضای جستجوی مسأله خواهد شد.” باید یک سی و دوم قید شود که اشتباه تایپی دارد.

با سلام؛

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

پیروز، شاد و تندرست باشید.

با سلام و احترام .
ممنون از مطلب عالی تون .
فقط من نیاز دارم که منابع این مطلب شمارو مطالعه کنم . میشه منابعش رو معرفی کنید ؟

سلام، وقت شما بخیر؛

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

از اینکه با مجله فرادرس همراه هستید از شما بسیار سپاسگزاریم.

خیلی عالی بود و همچنین کامل.

خیلی عالی و کامل بود، ممنون.

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *