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

نظریه تکامل چارلز داروین که در سال ۱۸۵۹ ارائه گردید، جایگاه ویژه­ای را در مسائل بهینه­سازی به خود اختصاص داد. این نظریه بر اساس تکامل بهترین­ها ارائه گردید و آن را می­توان به عنوان نقطه شروعی برای محاسبات تکاملی دانست. ایده محاسبات تکاملی اولین بار در سال ۱۹۶۰ توسط رچنبرگ که در زمینه استراتژی­های تکاملی تحقیق می­کرد به وجود آمد. در سال ۱۹۷۵ پروفسور هلند این ایده را در کتاب خود با نام ” انطباق بین طبیعت و سیستم­های هوشمند” ارائه کرد (فتاحی، ۱۳۹۰). او ایده استفاده از تکامل طبیعی در حل مسائل بهینه­سازی را شرح داد که پایه­ای برای الگوریتم ژنتیک محسوب می­گردید. مشهورترین تکنیک در تحقیقات محاسبات تکاملی، الگوریتم ژنتیک است. در این الگوریتم فرض می­گردد که هر موقعیت (نقطه) در رشته معرف یک ویژگی خاص از یک فرد(جواب) است و مقدار مشخص شده برای آن موقعیت، نشان­دهنده نحوه بیان آن ویژگی در جواب است. این الگوریتم، یک تکنیک جستجو را برای یافتن راه­حل­های نزدیک بهینه برای مسائل بهینه­سازی ارائه می­نماید.

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

 

جدول ۲-۱- مقایسه الگوریتم ژنتیک با سیستم­های طبیعی (مسعودیان و استکی، ۱۳۸۸)

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

 

 

 

رویه انتخاب، برای رقابت افراد در داخل جمعیت به کار می­رود که بر اساس یک تابع شایستگی[۱] عمل می­نماید. برای هر کروموزوم، یک مقدار مرتبط با شایستگی جوابی که نمایش می­دهد، وجود دارد. الگوریتم ژنتیک به دنبال حداکثر کردن مقدار تابع شایستگی است. بعد از اینکه تولید مثل و تابع برازندگی به خوبی تعریف شدند، یک الگوریتم ژنتیک بر اساس یک ساختار مشابه و پایه طراحی می­گردد. این ساختار ساده با تولید یک جمعیت اولیه از کروموزوم­ها شروع می­گردد. جمعیت اولیه باید به حدی بزرگ باشد که توانایی تولید تمامی راه­حل­های فضای جواب را داشته باشد. معمولاً جمعیت اولیه به صورت تصادفی تولید می­گردد.  سپس الگوریتم ژنتیک یک رویه تکراری را به منظور تکامل جمعیت انجام می­دهد. هر تکرار شامل مراحل زیر است:

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

روش­های مختلفی برای انتخاب وجود دارد که از آن جمله می­توان به موارد زیر اشاره کرد:

• انتخاب مرتبه­ای

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

• انتخاب تصادفی

در این روش والدین بر اساس یک روش کاملاً تصادفی از جمعیت انتخاب می­شوند. این روش با توجه به عدم اهمیت به شانس بیش­تر بهترین­ها برای تولید مثل، از کیفیت پایینی نیز برخوردار است.

• انتخاب رقابتی

 

 

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

• انتخاب بولتزمن

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

• انتخاب چرخ رولت

روشی که غالباً در انتخاب والدین مورد استفاده می­گیرد، همانطور که در شکل ۲-۱ می بینید، سطح چرخ رولت به بخش هایی تقسیم می­شود که تعداد آن­ها برابر تعداد اعضای جمعیت و سطح هر بخش متناسب با مقدار برازندگی هر کروموزوم می­باشد. سپس چرخ رولت به گردش در می­آید تا در نقطه­ای به تصادف متوقف شود. این نقطه، کروموزوم انتخاب شده را مشخص می­سازد. کروموزوم­هایی انتخاب می­شوند که سطح بیش تر(شایستگی بالاتری) را دارا می­باشند. این شیوه انتخاب سبب می­شود که با گذشت زمان، تعداد کروموزوم­های مطلوب در جمعیت افزایش یابد به طوریکه میانگین مقدار برازندگی جمعیت در مقایسه با جمعیت مرحله قبل بیش­تر شود.

 

شکل ۲-۱-  نمایش انتخاب چرخ رولت در الگوریتم ژنتیک (فتاحی، ۱۳۹۱)

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

الف) اپراتور تولید مثل یک زوج والد را از حوضچه تولید مثل انتخاب می­نماید.

ب) یک نقطه تقاطع به طور تصادفی در طول رشته انتخاب می­شود.

ج) مقادیر رشته­ها با توجه به نقطه تقاطع تعویض می­گردند.

عملگر تقاطعی با یک احتمال از قبل تعیین شده، بر روی کروموزوم­های والد عمل می­ کند. اگر هیچ تقاطعی صورت نگیرد، فرزندان دقیقأ مشابه والدین خواهند بود.

روش­های مختلفی برای عملگر تقاطع وجود دارد و بخشی از این روش­ها به شرح زیر هستند:

• تقاطع دو نقطه­ای

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

• تقاطع چند­نقطه­ای

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

• تقاطع یکنواخت

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

• تقاطع از سه والد

در این روش، ۳ والد به صورت تصادفی انتخاب می­شود. هر ژن از والد اول با همان ژن از والد دوم مقایسه می­شود. در صورتی که مشابه باشند، همان ژن به فرزند منتقل می­شود و در غیر این صورت با والد سوم مقایسه می­شود. این روش بر این پایه استوار است که شباهت­های والدین کشف شده و بر اساس آن­ها فرزندانی تولید می­گردد.

• تقاطع مرتب

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

• تقاطع تک نقطه­ای

عملگر تقاطعی تک نقطه­ای معمول­ترین نوع عملگرهای تقاطع محسوب می­شود که در مدل ارائه شده در این تحقیق هم از آن بهره گرفته شده است. در این عملگر دو کروموزوم به صورت تصادفی از یک نقطه شکسته می­شوند و بخش­های شکسته شده دو کروموزوم با هم جابه­جا می­گردند. بدین ترتیب، دو کروموزوم جدید بدست می­آید. به کروموزوم­های اولیه، کروموزوم­های والد و به کروموزوم­های حاصل شده از عمل جا به ­جایی، فرزند می­گویند (فتاحی، ۱۳۹۰). یک مثال از عملگر تقاطع تک­نقطه­ای در شکل ۲-۲ نشان داده شده است.

شکل۲-۲-  نمایش عملگر تقاطع تک­نقطه­ای در الگوریتم ژنتیک (فتاحی، ۱۳۹۰)

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

شکل­های مختلفی برای جهش به شرح زیر موجود است:

• معکوس کردن
• تعویض

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

 

شکل۲-۳-  نمایش عملگر جهش تک نقطه­ای در الگوریتم ژنتیک (فتاحی، ۱۳۹۰)

 

 

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

ارزیابی: در این مرحله، میزان برازندگی فرزندان جدید تولید شده، ارزیابی می­گردد.

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

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

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

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

• حداکثر تولید نسل. در این حالت الگوریتم زمانی متوقف می­شود که تعداد مشخصی از تولید نسل اتفاق افتاده باشد.
• زمان سپری­شده: زمانی که فرآیند الگوریتم ژنتیک زمان خاصی را سپری کرد، الگوریتم متوقف می­شود.
• عدم بهبود در برازندگی: در این حالت، در صورتی­که هیچ تغییری در بهترین برازندگی جمعیت بعد از تعداد مشخصی تولید نسل به وجود نیاید، الگوریتم ژنتیک متوقف می­شود (فتاحی، ۱۳۹۰).

 

 

 

تولید جمعیت اولیه به طور تصادفی

ارزیابی جمعیت

ارضای شرط پایان؟

ترکیب با احتمال ۶۰%

جهش با احتمال کمتر از ۱%

جمعیت جدید

انتخاب

خروجی بهترین جدول

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

شکل ۲-۴- فلوچارت الگوریتم ژنتیکی عادی و استاندارد (منجمی و نعیمی، ۱۳۸۸)

 

 

[۱] -Fitness function

[۲]- Crossover