مفاهیم اولیه در الگوریتم ژنتیک
اصول پایه
الگوریتم های ژنتیکی براساس تئوری تکاملی داروین می باشند و جواب مساله ای که از طریق الگوریتم ژنتیک حل می شود مرتباً بهبود می یابد. الگوریتم ژنتیک با یک مجموعه از جواب ها که از طریق کرموزومها نشان داده می شوند شروع می شود. این مجموعه جواب ها جمعیت اولیه نام دارند. در این الگوریتم جواب های حاصل از یک جمعیت برای تولید جمعیت بعدی استفاده می شوند. در این فرایند امید است که جمعیت جدید نسبت به جمعیت قبلی بهتر باشد. انتخاب بعضی از جواب ها از میان کل جواب ها(والدین) به منظور ایجاد جواب های جدید یا همان فرزندان بر اساس میزان مطلوبیت آن ها می باشد. طبیعی است که جواب های مناسب تر شانس بیشتری برای تولید مجدد داشته باشند. این فرایند تا برقراری شرطی که از پیش تعیین شده است مانند تعداد جمعیت ها یا میزان بهبود جواب ادامه می یابد.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
شمای کلی الگوریتم ژنتیک
١) تولید جمعیت تصادفی شامل n کروموزوم
٢) بررسی تابع هدف (x) f هر کروموزوم در جمعیت
٣) ایجاد یک جمعیت جدید بر اساس تکرار قدم های زیر:
۳-١) انتخاب دو کروموزوم والد از یک جمعیت بر اساس میزان مطلوبیت آن ها
۳-٢) درنظر گرفتن مقدار مشخصی برای احتمال اعمال عملگر تقاطعی
وسپس انجام عملیات ترکیب بر روی والدین به منظور ایجاد فرزندان. اگر هیچ ترکیب جدیدی صورت نگیرد، فرزندان همان والدین خواهند بود.
٣-۳) در نظر گرفتن احتمال جهش وسپس تغییرفرزندان با اعمال عملگرجهشی
۳-۴) جایگزینی فرزندان جدید در جمعیت جدید
۴) استفاده از جمعیت جدید برای اجراهای بعدی الگوریتم
۵) توقف اجرای الگوریتم در صورت مشاهده شرایط توقف و برگرداندن بهترین جواب در جمعیت فعلی
۶) رفتن به قدم ٢
همانطور که مشاهده می شود، اصول پایه ای الگوریتم ژنتیک بسیار عمومی است. بنابراین برای مسائل مختلف فاکتورهای مختلف زیادی وجود دارد که باید مورد بررسی قرار گیرد. اولین سؤال این است که ایجاد یک کروموزوم چگونه است؟ یا اینکه چه نوعی از کدینگ انتخاب شود؟
دوعملگر بسیار مهم و پایه ای الگوریتم ژنتیک عملگرهای تقاطعی وجهشی می باشند. سؤال بعدی این است که برای ترکیب والدین به منظور ایجاد فرزندان جدید چگونه والدین را انتخاب کنیم. این کار به طرق مختلف می تواند صورت بگیرد، اما ایده اصلی در تمامی آن ها این است که والدین بهتر انتخاب شوند، به این امید که والدین بهتر باعث ایجاد فرزندان بهتر شوند. مساله ای که ممکن است در اینجا مورد سؤال باشد این است که اگر جمعیت جدید تنها از طریق فرزندان جدید ایجاد شود، این فرایند منجر به حذف بهترین کرموزوم های نسل قبل می گردد. برای جلوگیری از این پیشامد، همیشه بهترین جواب نسل قبل را بدون هیچ تغییری به نسل جدید منتقل می کنیم.
کد کردن
الگوریتم ژنتیک بجای اینکه بر روی پارامترها یا متغیرهای مساله کارکند، با شکل کد شده آن ها بطور مناسب سر و کار دارد. روش های کدگذاری متداول در الگوریتم ژنتیک عبارتند از کدینگ باینری، کدینگ درختی، کدینگ ارزشی و کدینگ جهشی. تعداد بیت هایی که برای کدگذاری متغیرها استفاده می شود وابسته به دقت مورد نظر برای جواب ها، محدوده تغییرات پارامترها و رابطه بین متغیرها می باشد.
انواع کدینگ
کدینگ به دو صورت کلی می باشد :
کدینگ مستقیم
در این روش کل یک جواب به عنوان یک کروموزوم در نظر گرفته می شود. برای مسائل پیچیده چنین روشی مناسب نیست، زیرا عملگرهای ژنتیکی بخاطرگستردگی زیاد فرزندان، غیرکاربردی می شوند و در نتیجه منجر به جواب های غیرقابل قبول و غیرقانونی می شوند.
کدینگ غیرمستقیم
در این روش تنها قسمتی از یک جواب بصورت یک کروموزوم کد می شود.
روش های کدینگ
کدینگ باینری
این نوع کدینگ، متداولترین نوع کدینگ می باشد. در این روش کدگذاری، هر کروموزوم یک رشته از بیت های شامل ٠و ١ می باشد. کدینگ باینری می تواند حالت های زیادی را پوشش دهد.
شکل ۳- ۱: کدینگ باینری
از طرف دیگر این نوع کدینگ برای خیلی از مسائل حالت طبیعی ندارد و اغلب اوقات لازم است که بعد از تقاطع و جهش اصلاحاتی صورت بگیرد.
کدینگ جهشی
این نوع کدینگ می تواند در مسائل ترتیبی نظیر مساله فروشنده دوره گرد یا مساله ترتیب کارها بکار رود. در کدینگ جهشی، هر کروموزوم یک رشته از اعداد می باشد. شکل زیر نمونه ای از این نوع کدینگ را نشان می دهد.
شکل ۳- ۲: کدینگ جهشی
کدینگ جهشی تنها برای مسائل ترتیبی مفید است حتی برای همین مسائل نیز گاهی اوقات باید تقاطع ها و جهش های اصلاحی به منظور ایجاد کروموزوم های سازگار و مناسب انجام شود.
کدینگ ارزشی
این نوع کدینگ درمسائلی که در آن ها مقادیر پیچیده نظیر اعداد حقیقی بکارمی روند استفاده می شود. استفاده از کدینگ باینری برای چنین مسائلی بسیار سخت می باشد. در کدینگ ارزشی هر ژن یک کروموزوم ارزش خاصی دارد. این پارامتر باارزش می تواند عدد، حرف یا کلمه باشد. در این نوع کدینگ نیاز به توسعه عملگرهای جابجایی و جهش جدیدی برای مسائل خاص می باشد.
شکل ۳- ۳: کدینگ ارزشی
