الگوریتم ژنتیک
43 صفحه در قالب word
مقدمه
الگوریتم ژنتیک، یک روش جستجوی احتمالی است که از شبیهسازی تکامل زیستی و طبیعی استفاده میکند.
الگوریتمهای ژنتیک با به کارگیری اصول انتخاب طبیعی و بقای بهترینها برای تولید تخمینهای هر چه بهتر یک جواب روی جمعیتی از جوابهای بالقوه عمل مینماید. در هر نسل، مجموعهای جدید از تخمینها توسط فرآیند انتخاب افراد مطابق با سطح برازندگیشان در دامنه مسأله و پرورش آنها با هم با استفاده از عملگرهای گرفته شده از ژنتیک طبیعی ایجاد میگردد. این فرآیند ما را به سمت تکامل جمعیتهایی از افراد، که با محیط مربوطهشان بهتر از والدینشان وفق داده شدهاند هدایت میکند.
اصول بنیادی الگوریتم ژنتیک اولین بار در سال 1975 توسط جان هلند، در دانشگاه میشیگان آمریکا، ابداع شد. (19) در ادامه این فصل به معرفی مفاهیم موجود در الگوریتم ژنتیک خواهیم پرداخت.
جمعیت در الگوریتم ژنتیک
الگوریتم ژنتیک، با تعریف یک کروموزوم[1] یا یک آرایه از مقادیر پارامتری که باید بهینه باشد شروع میشود. هر درایه در هر کروموزوم ژن نامیده میشود. مجموعهای از این کروموزومها جمعیت[2] الگوریتم را تشکیل میدهد.
همچنین هر تکرار از الگوریتم ژنتیک را یک نسل می گویند.
اگر مسئله دارای Npar پارامتر متغیر باشد میتوان هر کروموزوم را به صورت نشان داد که Pi، i امین پارامتر مسئله است. یکی از ویژگیهای الگوریتم ژنتیک این است که به جای تمرکز بر روی یک نقطه از فضای جستجو یا یک کروموزوم بر روی جمعیتی از کروموزومها کار میکند، بدین ترتیب در هر مرحله، الگوریتم ژنتیک دارای جمعیتی از کروموزومها بوده که خواص موردنظر را بیشتر از جمعیت مرحله قبل دارا است.
تابع هدف و برازندگی
تابع هزینه[3] مقدار تابع هدف به ازای یک دسته پارامتر (یک کروموزوم) است و می تواند به صورت یک تابع ریاضی، یا نتیجه یک آزمایش یا نتیجه یک بازی باشد.
تابع هدف جهت تعیین اینکه افراد چگونه در محدوده مسئله ایفای نقش مینمایند، مورد استفاده قرار میگیرد. در حالت مسئله بیشینهسازی، شایستهترین افراد دارای بیشترین مقدار عددی تابع هدف مربوطه هستند. این مقدار برازندگی[4] ، تنها به عنوان یک مرحله میانی در تعیین کارایی مربوطه افراد در الگوریتم ژنتیک به کار میرود. مناسب بودن یا نبودن جواب با مقداری که از تابع برازندگی[5] به دست میآید سنجیده میشود. هر چه که یک جواب مناسبتر باشد مقدار برازندگی بزرگتری دارد و احتمال بقای کروموزوم متناظر با آن بیشتر خواهد بود. این احتمال متناسب با مقدار مقدار برازندگی به دست آمده از هر کروموزوم در نظر گرفته میشود.
انتخاب
پس از ارزیابی کروموزومهای موجود در نسل حاضر، باید نسل جدیدی با استفاده از نسل حاضر تولید شود. انتخاب، مکانیزمی است که تعیین می کند کدامیک از کروموزوم های موجود در نسل حاضر بطور مستقیم یا غیر مستقیم برای تولید نسل بعد برگزیده شوند.کروموزوم های انتخاب شده تشکیل جمعیت والد[6] (جمعیت میانی[7] ) را می دهند. این انتخاب با توجه به میزان شایستگی کروموزوم های موجود در نسل حاضر صورت میگیرد و باید بگونهای باشد که کروموزومهای با شایستگی بیشتر نسبت به کروموزومهای با شایستگی کمتر شانس بیشتری برای مشارکت در تولید نسل بعد داشته باشند .
معمولاً انتخاب کروموزومها برای تولید نسل بعد متناسب با مقدار شایستگی آنها صورت میگیرد.
ساده ترین روش برای اجرای این مرحله، استفاده از مدل چرخ رولت[8] است (20). در این مدل، سطح چرخ به بخشهایی تقسیم می شود که تعداد آنها برابر با تعداد اعضای جمعیت و سطح هر بخش متناسب با مقدار برازندگی هر کروموزوم است. سپس چرخ به گردش درمی آید تا درنقطهای به تصادف متوقف گردد. این نقطه، کروموزوم انتخاب شده را مشخص می سازد. شکل شمایی از چرخ رولت را نشان می دهد.
یکی دیگر از روش هایی که در این بخش مورد استفاده قرار می گیرد روش تورنمنت[9] میباشد .در این روش در هر تکرار یک مجموعه عضوی از نسل فعلی انتخاب شده و بهترین آنها در جمعیت والد قرار میگیرد. این کار به تعداد اعضای جمعیت والد صورت میگیرد.
از مواردی که عموماً در مرحله انتخاب انجام میگیرد استفاده از استراتژی نخبه پروری[10] می باشد .این استراتژی بدین صورت عمل میکند که قبل از انجام عمل انتخاب ، درصد از کروموزوم های با برازندگی بالا از جمعیت کنونی را حفظ کرده و مستقیماً به نسل بعد انتقال می دهد.
ادغام[11]
در فرآیند تولید مثل، فرزندان خصوصیات ژنتیکی والدین خود را به ارث میبرند، بدین معنی که برخی خصوصیات بیولوژیکی فرزند شبیه خصوصیات بیولوژیکی پدر و برخی مانند خصوصیات بیولوژیکی مادر است. در الگوریتم ژنتیک این فرآیند توسط عملگر ادغام شبیه سازی میشود. این عملگر بر روی یک جفت از کروموزومها عمل میکند و میتواند به صورت تک نقطهای، چند نقطهای و یکنواخت باشد . عملگر تقاطعی تک نقطه ای[12]، دو کروموزوم را از جمعیت والد به طور تصادفی از یک نقطه شکسته و بخش های شکسته دو کروموزوم را جابجا می کند. بدین ترتیب دو کروموزوم جدید بدست می آید. به کروموزومهای حاصل شده از عمل ادغام، کروموزوم های فرزند[13] می گویند.شکل شمایی از عملگر تقاطع تک نقطه ای را نشان می دهد.
ممکن است هنگام انتقال از فایل ورد به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است
متن کامل را می توانید در ادامه دانلود نمائید
چون فقط تکه هایی از متن برای نمونه در این صفحه درج شده است ولی در فایل دانلودی متن کامل همراه با تمام ضمائم (پیوست ها) با فرمت ورد word که قابل ویرایش و کپی کردن می باشند موجود است
الگوریتم ژنتیک