برای جستجو در بین هزاران پایان نامه در موضوعات مختلف     

      و دانلود متن کامل آنها با فرمت ورد اینجا کلیک کنید     

 
دانلود پایان نامه

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