معرفی الگوریتم ژنتیک
نظریه تکامل چارلز داروین که در سال ۱۸۵۹ ارائه گردید، جایگاه ویژهای را در مسائل بهینهسازی به خود اختصاص داد. این نظریه بر اساس تکامل بهترینها ارائه گردید و آن را میتوان به عنوان نقطه شروعی برای محاسبات تکاملی دانست. ایده محاسبات تکاملی اولین بار در سال ۱۹۶۰ توسط رچنبرگ که در زمینه استراتژی های تکاملی تحقیق میکرد به وجود آمد. در سال ۱۹۷۵ پروفسور هلند این ایده را در کتاب خود با نام ” انطباق بین طبیعت و سیستمهای هوشمند” ارائه کرد (فتاحی، ۱۳۹۰). او ایده استفاده از تکامل طبیعی در حل مسائل بهینهسازی را شرح داد که پایهای برای الگوریتم ژنتیک محسوب میگردید. مشهورترین تکنیک در تحقیقات محاسبات تکاملی، الگوریتم ژنتیک است. در این الگوریتم فرض میگردد که هر موقعیت (نقطه) در رشته معرف یک ویژگی خاص از یک فرد(جواب) است و مقدار مشخص شده برای آن موقعیت، نشاندهنده نحوه بیان آن ویژگی در جواب است. این الگوریتم، یک تکنیک جستجو را برای یافتن راهحلهای نزدیک بهینه برای مسائل بهینهسازی ارائه مینماید.
الگوریتم ژنتیک با یک جمعیت اولیه از راهحلها شروع میگردد. هر راهحل از طریق یک کروموزوم که رشتهای از بیتها است و در واقع شکل کدشده یک جواب ممکن از مسئله مورد نظر میباشد، نمایش داده می شود. تمامی راهحلهای ممکن باید با بهره گرفتن از یک سیستم کدگذاری، تبدیل به کد شوند. سپس مجموعه ای از اپراتورهای تولید مثل، باید تعیین گردند. اپراتورهای تولید مثل، مستقیماً روی کروموزومها عمل نموده و سپس کروموزومها تحت اپراتور جهش و رویه ترکیب قرار میگیرند. طراحی ساختار کدگذاری تأثیر زیادی روی عملکرد الگوریتم ژنتیک خواهد داشت.
جدول ۲-۱- مقایسه الگوریتم ژنتیک با سیستمهای طبیعی (مسعودیان و استکی، ۱۳۸۸)
سیستمهای طبیعی | الگوریتم ژنتیک |
کروموزوم: بستههای ژنی هستند که اطلاعات وراثتی را از نسلی به نسل دیگر انتقال می دهند. | کروموزوم: پاسخهای ممکن مسئله که به صورت رشتههای عددی رمزگذاری شده اند. |
محیط: شرایط محیطی که جمعیت در آن قرار دارد و دیکته کننده نحوه تحول است. | تابع برازش: محک کیفیت یک کروموزوم که به صورت یک رابطه ریاضی درآمده که آن را تابع برازش مینامند. |
اصل انتخاب طبیعی: معیار بقای موجود زنده و تکثیر آن، سازش با محیط است. | تکثیر: هر رشته جمعیت را به عنوان متغیر تابع برازش در نظر گرفته و مقدار تابع برازش هر رشته محاسبه می شود. متناسب با مقدار تابع برازش، رشتههای والدین برای تولید جمعیت جدید انتخاب می شود. |
تقاطع: در نتیجه تقاطع یا تبادل قسمتی از کروموزومها، مبادله ژنهای پیوسته صورت میگیرد. | ادغام: رشتههای جمعیت به صورت دو به دو مزدوج میشوند. زوج رشتهها از یک نقطه قطع میشوند. نیم بخشهای بین دو رشته تعویض میشوند. |
جهش: جانشین شدن ژنی به جای ژن دیگر یا در تغییرات ایجاد شده در DNA طول زنجیره ژن. گاهی قسمتی از یک ژن جانشین ژن دیگری می شود. | جهش: یک بیت از رشته عددی به صورت تصادفی انتخاب می شود و دچارتغییر میگردد. |
تجدید نسل: ایجاد نسلهای جدید و تکامل موجودات | تجدید نسل: تکرار مراحل الگوریتم بعد از مرحله تکثیرتا حصول پاسخ بهینه یا رسیدن به حد توقف. |
رویه انتخاب، برای رقابت افراد در داخل جمعیت به کار میرود که بر اساس یک تابع شایستگی[۱] عمل مینماید. برای هر کروموزوم، یک مقدار مرتبط با شایستگی جوابی که نمایش میدهد، وجود دارد. الگوریتم ژنتیک به دنبال حداکثر کردن مقدار تابع شایستگی است. بعد از اینکه تولید مثل و تابع برازندگی به خوبی تعریف شدند، یک الگوریتم ژنتیک بر اساس یک ساختار مشابه و پایه طراحی میگردد. این ساختار ساده با تولید یک جمعیت اولیه از کروموزومها شروع میگردد. جمعیت اولیه باید به حدی بزرگ باشد که توانایی تولید تمامی راهحلهای فضای جواب را داشته باشد. معمولاً جمعیت اولیه به صورت تصادفی تولید میگردد. سپس الگوریتم ژنتیک یک رویه تکراری را به منظور تکامل جمعیت انجام میدهد. هر تکرار شامل مراحل زیر است:
انتخاب: اولین قدم شامل انتخاب افرادی از جمعیت برای تولید مثل است. این انتخاب به صورت تصادفی، با بهره گرفتن از یک احتمال متناسب با تابع برازندگی افراد انجام میگردد. در این مرحله، باید در ارتباط با نحوه انتخاب والدین برای عمل تقاطع (باز ترکیب)[۲]، نحوه تولید فرزندان و تعداد فرزندان تصمیم گیری گردد. هدف این است که والدین شایستهتر انتخابشده که منجر به تولید فرزندانی با برازندگی بالا گردد. کروموزومهایی که از جمعیت اولیه برای تولید مثل انتخاب میشوند، والدین نام دارند. همگرایی الگوریتم ژنتیک وابستگی بالایی به دامنه و شدت فشار رویه انتخاب برای گزینش افراد شایستهتر دارد.
روشهای مختلفی برای انتخاب وجود دارد که از آن جمله میتوان به موارد زیر اشاره کرد:
- انتخاب مرتبهای
در این روش، کروموزومها بر اساس مقدار برازندگی آن ها رتبه بندی شده و به ترتیب بدترین به بهترین رتبه مرتب میگردند. احتمال انتخاب هر کروموزوم بر اساس درصد نسبی رتبه خود میباشد.
- انتخاب تصادفی
در این روش والدین بر اساس یک روش کاملاً تصادفی از جمعیت انتخاب میشوند. این روش با توجه به عدم اهمیت به شانس بیشتر بهترینها برای تولید مثل، از کیفیت پایینی نیز برخوردار است.
- انتخاب رقابتی
در این روش یک زیر مجموعه کوچکی از کروموزومها به صورت تصادفی انتخاب شده و به رقابت میپردازند. سرانجام در این رقابت، بر اساس میزان برازندگی، یکی از آنها به پیروزی رسیده و انتخاب می شود. ایراد این روش این است که در آن هیچگاه کروموزوم دارای کمترین شانس برنده نخواهد شد.
- انتخاب بولتزمن
این روش بیشتر در الگوریتم انجماد تدریجی مورد استفاده قرار میگیرد. در این حالت دما از یک مقدار بالا در ابتدای الگوریتم شروع می کند و معنای آن این است که فشار انتخاب پایین است. دما به مرور کاهش مییابد و به دنبال آن، فشار انتخاب به مرور افزایش مییابد. بنابراین در این حالت، در ابتدای الگوریتم گوناگونی افزایش یافته و در انتها جستجوی محلی قوت مییابد.
- انتخاب چرخ رولت
روشی که غالباً در انتخاب والدین مورد استفاده میگیرد، همانطور که در شکل ۲-۱ می بینید، سطح چرخ رولت به بخش هایی تقسیم می شود که تعداد آنها برابر تعداد اعضای جمعیت و سطح هر بخش متناسب با مقدار برازندگی هر کروموزوم میباشد. سپس چرخ رولت به گردش در میآید تا در نقطهای به تصادف متوقف شود. این نقطه، کروموزوم انتخاب شده را مشخص میسازد. کروموزومهایی انتخاب میشوند که سطح بیش تر(شایستگی بالاتری) را دارا میباشند. این شیوه انتخاب سبب می شود که با گذشت زمان، تعداد کروموزومهای مطلوب در جمعیت افزایش یابد به طوریکه میانگین مقدار برازندگی جمعیت در مقایسه با جمعیت مرحله قبل بیشتر شود.
شکل ۲-۱- نمایش انتخاب چرخ رولت در الگوریتم ژنتیک (فتاحی، ۱۳۹۱)
تولید مثل: در قدم دوم، عملگرهای ترکیب مجدد و جهش روی افراد انتخاب شده به کار گرفته شده و کروموزومهای جدید تولید میگردد. در این مرحله، فرزندان جدید تولید میشوند. در این مرحله عملگر ترکیب مجدد (تقاطع)، فرآیندی است که در ۳ مرحله صورت میگیرد:
الف) اپراتور تولید مثل یک زوج والد را از حوضچه تولید مثل انتخاب مینماید.
ب) یک نقطه تقاطع به طور تصادفی در طول رشته انتخاب می شود.
ج) مقادیر رشتهها با توجه به نقطه تقاطع تعویض میگردند.
عملگر تقاطعی با یک احتمال از قبل تعیین شده، بر روی کروموزومهای والد عمل می کند. اگر هیچ تقاطعی صورت نگیرد، فرزندان دقیقأ مشابه والدین خواهند بود.
روشهای مختلفی برای عملگر تقاطع وجود دارد و بخشی از این روشها به شرح زیر هستند:
- تقاطع دو نقطهای
در این عملگر، دو نقطه شکست در طول رشته جواب در نظر گرفته می شود. در این حالت، ابتدا دو مکان تصادفی در طول رشته انتخاب شده و سپس به صورت یک در میان قسمت های والدها به فرزندان منتقل می شود.
- تقاطع چندنقطهای
این عملگر شبیه عملگر دونقطهای است، با این تفاوت که به جای دو نقطه، چند نقطه برای تقاطع انتخاب می شود. تقاطع در بخشهای شکسته شده دو کروموزوم به صورت یک در میان انجام میگیرد. باید توجه داشت افزایش تعداد نقاط شکست، عملکرد الگوریتم ژنتیک را کاهش میدهد ولی باعث می شود فضای مسئله به صورت کاملتری جستجو گردد.
- تقاطع یکنواخت
بر اساس این عملگر، یک ژن از هر دو والد به طور مستقل از سایر ژنها، شانس برابر برای حضور در کروموزوم یک فرزند را دارد. در این حالت، بر اساس یک توزیع تصادفی باینری مشخص می شود که یک ژن از کدام والدین انتخاب شده است. مثلاً اگر توزیع باینری ۱ را نشان داد، آن ژن از والد اول و اگر ۰ بود از والد دوم انتخاب میگردد.
- تقاطع از سه والد
در این روش، ۳ والد به صورت تصادفی انتخاب می شود. هر ژن از والد اول با همان ژن از والد دوم مقایسه می شود. در صورتی که مشابه باشند، همان ژن به فرزند منتقل می شود و در غیر این صورت با والد سوم مقایسه می شود. این روش بر این پایه استوار است که شباهتهای والدین کشف شده و بر اساس آنها فرزندانی تولید میگردد.
- تقاطع مرتب
از این عملگر زمانی استفاده می شود که مسئله مبتنی بر ترتیب باشد. در این روش دو نقطه تقاطع تصادفی انتخاب می شود و آن را به ۳ قسمت چپ، وسط و راست تقسیم می کند. عملگر به این ترتیب عمل مینماید که فرزند اول قسمت چپ و راست را از والد اول و قسمت وسط آن بر اساس ژنهای قسمت وسط والد اول به نحوی که ترتیب آن بر اساس والد دوم باشد، تعیین میگردد.
- تقاطع تک نقطهای
عملگر تقاطعی تک نقطهای معمولترین نوع عملگرهای تقاطع محسوب می شود که در مدل ارائه شده در این تحقیق هم از آن بهره گرفته شده است. در این عملگر دو کروموزوم به صورت تصادفی از یک نقطه شکسته میشوند و بخشهای شکسته شده دو کروموزوم با هم جابهجا میگردند. بدین ترتیب، دو کروموزوم جدید بدست میآید. به کروموزومهای اولیه، کروموزومهای والد و به کروموزومهای حاصل شده از عمل جا به جایی، فرزند میگویند (فتاحی، ۱۳۹۰). یک مثال از عملگر تقاطع تکنقطهای در شکل ۲-۲ نشان داده شده است.
شکل۲-۲- نمایش عملگر تقاطع تکنقطهای در الگوریتم ژنتیک (فتاحی، ۱۳۹۰)
بعد از تقاطع، کروموزومها تحت اپراتور جهش قرار میگیرند. عملگر جهش از افتادن الگوریتم در بهینه محلی جلوگیری مینمایند. جهش موجب می شود که گوناگونی جمعیت حفظ شود و ساختار ژنتیکی جدیدی در جمعیت با تغییرات تصادفی بعضی از ژنها (هر بیت از یک رشته بیتی به نام کروموزوم) به وجود آید. انتخاب ژنها بر اساس احتمال جهش صورت میگیرد.
شکلهای مختلفی برای جهش به شرح زیر موجود است:
- معکوس کردن
- تعویض
آنچه در انجام این تحقیق مورد استفاده قرار گرفته استفاده از روش تعویض برای عملگر جهش است. در این نوع جهش، دو موقعیت تصادفی از یک رشته انتخاب و ارزشهای مرتبط آنها با یکدیگر تعویض میگردد. شکل ۲-۳ نوعی از این جهش را نشان میدهد.
شکل۲-۳- نمایش عملگر جهش تک نقطهای در الگوریتم ژنتیک (فتاحی، ۱۳۹۰)
نکتهای که در تفاوت عملگرهای تقاطع و جهش قابل تأمل است این است که عملگر جهش عملیاتی است که تنها روی یک کروموزوم اجرا می شود در حالیکه عملگر تقاطع عملیاتی است که روی دو کروموزوم اجرا می شود.
ارزیابی: در این مرحله، میزان برازندگی فرزندان جدید تولید شده، ارزیابی میگردد.
جا به جایی: در این مرحله، افرادی از جمعیت قبلی کشته شده (حذف میگردند) و با افراد جدیدی که به تازگی تولید شده اند، جابهجا میگردند. به عبارت دیگر، در این مرحله، جمعیت، یک نسل را پشت سر گذاشته و افرادی از آن حذف و افرادی به آن اضافه میگردند. روشهای مختلفی برای انتخاب جمعیت جدید وجود دارد که به طور مثال میتوان به دو روش زیر اشاره کرد:
- تمام اعضای جمعیت جدید از میان کروموزومهای فرزندان انتخاب شوند.
- تعدادی از افراد جمعیت مرحله بعد، همان افراد جمعیت مرحله قبل بوده و بقیه از میان فرزندان جدید انتخاب گردند. البته در هر مورد، شایستهترین کروموزومها انتخاب می شود.
بر اساس تحقیقات نشان داده شده است که حذف همه کروموزومهای جمعیت مرحله قبل و انتخاب جمعیت جدید از میان فرزندان، ممکن است بسیاری از جوابهای مناسب را که در میان جمعیت مرحله قبل وجود دارد، حذف نماید.
قاعده توقف: الگوریتم زمانی متوقف میگردد که جمعیت به سمت راه حل بهینه همگرا گردد و به عبارت دیگر به آن برسد یا نزدیک شود. قواعد توقف متعددی برای الگوریتم ژنتیک وجود دارد که بعضی از روشهای آن به شرح زیر است:
- حداکثر تولید نسل. در این حالت الگوریتم زمانی متوقف می شود که تعداد مشخصی از تولید نسل اتفاق افتاده باشد.
- زمان سپریشده: زمانی که فرایند الگوریتم ژنتیک زمان خاصی را سپری کرد، الگوریتم متوقف می شود.
- عدم بهبود در برازندگی: در این حالت، در صورتیکه هیچ تغییری در بهترین برازندگی جمعیت بعد از تعداد مشخصی تولید نسل به وجود نیاید، الگوریتم ژنتیک متوقف می شود (فتاحی، ۱۳۹۰).
تولید جمعیت اولیه به طور تصادفی |
ارزیابی جمعیت |
ارضای شرط پایان؟ |
ترکیب با احتمال ۶۰% |
جهش با احتمال کمتر از ۱% |
جمعیت جدید |
انتخاب |
خروجی بهترین جدول |
شکل ۲-۴- فلوچارت الگوریتم ژنتیکی عادی و استاندارد (منجمی و نعیمی، ۱۳۸۸)