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

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

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

١١٠٠١٠١١ + ١١٠١١١0١ = ١١٠١١١١١
در عمل تقاطعی یکنواخت، بیت ها به صورت تصادفی از والد ١ یا والد ٢ کپی می شوند.
١١٠٠١٠١١ + ١١٠١١١٠١ = ١١٠١١١١١
باید خاطر نشان ساخت که اثر استفاده از هر کدام از انواع عملگرهای تقاطعی در سرعت همگرایی الگوریتم، دقیقاً مشخص نمی باشد و به مساله مورد نظر بستگی دارد.
عملگر جهشی
این عملگر روی هر یک از کروموزوم های حاصل از عملگر تقاطعی عمل می کند. بدین ترتیب که به ازای هر بیت از کروموزوم، یک عدد تصادفی تولید می گردد. اگر مقدار این عدد تصادفی از مقدار Pm (احتمال انجام جهش) کمتر باشد، در آن بیت عمل جهش انجام می شود و در غیر اینصورت، در آن بیت عمل جهش انجام نمی گیرد. عمل جهش در هر بیت با تولید تصادفی عدد ٠ یا ١ و جایگزینی آن بجای بیت مورد جهش انجام می گیرد.
مراحل اجرای الگوریتم ژنتیک
پس از بیان مفاهیم اولیه، مراحل مختلف در استفاده از الگوریتم ژنتیک مورد بررسی قرار می گیرد. ابتدا با توجه به صورت مساله، متغیرهایی که باید تعیین شوند، مشخص می شوند. سپس این متغیرها به نحو مناسبی کد گذاری شده و به شکل کروموزوم نمایش داده می شوند. براساس تابع هدف، یک تابع برازندگی برای کروموزوم ها تعریف می گردد و یک جمعیت اولیه دلخواه نیز بطور تصادفی انتخاب میشود. به دنبال آن، میزان تابع برازندگی برای هر کروموزوم جمعیت اولیه حساب می شود. سپس مراحلی که در شکل 3-10 نمایش داده شده است به ترتیب زیر انجام می گیرد. آنچه که تاکنون به عنوان ساختار کلی الگوریتم ژنتیک ارائه شده است، توسط بیکر و گرفنستت ارائه گردیده است و خلاصه آن به صورت شکل 3-10 می باشد:
شکل 3- 10: مراحل اجرای الگوریتم ژنتیک
مرحله ١:
در این مرحله، تعداد مناسبی از زوج کروموزوم ها بر اساس میزان برازندگی آنها انتخاب می شوند تا درمراحل بعدی مورد استفاده قرار بگیرند. کروموزوم هایی که دارای عدد برازندگی بالایی هستند، ممکن است چندین بار در مراحل تولید انتخاب شوند، در حالیکه کروموزوم هایی که برازندگی آن ها کم می باشد، ممکن است هیچگاه انتخاب نگردند. ساده ترین روش برای اجرای این مرحله، استفاده از مدل چرخ رولت است. در این مدل، سطح چرخ به بخش هایی تقسیم می شود که تعداد آن ها برابر با تعداد اعضای جمعیت و سطح هر بخش متناسب با مقدار برازندگی هر کروموزوم است. سپس چرخ به گردش درمی آید تا در نقطه ای به تصادف متوقف گردد. این نقطه، کروموزوم انتخاب شده را مشخص می سازد.
شکل 3-11 شمایی از چرخ رولت را نشان می دهد:
شکل 3- 11:چرخ رولت
در این شکل کروموزوم های ١ و ٢ دارای برازندگی بیشتری نسبت به کروموزوم های ٣ و ۴ هستند و بنابراین در مرحله انتخاب، شانس بیشتری دارند. این شیوه انتخاب سبب می شود که با گذشت زمان، تعداد کروموزوم های مطلوب در جمعیت افزایش یابد بطوریکه میانگین مقدار برازندگی جمعیت، درمقایسه با جمعیت مرحله قبل، بیشتر می شود. پیاده سازی مدل چرخ رولت در کامپیوتر، می تواند شامل مراحل زیر باشد:
کروموزوم های جمعیت به شکل دنباله درآورده می شوند. سپس مجموع مقدار برازندگی هر کروموزوم با مقدار برازندگی تمام کرموزوم های قبل از آن محاسبه می گردد. یک عدد تصادفی n بین صفر و مجموع برازندگی تمام کروموزوم های جمعیت ایجاد می شود. از بین کروموزوم ها، اولین کروموزومی که مقدار برازندگی آن به اضافه مقدار برازندگی همه کروموزوم های قبل از آن، بیشتر از n باشد، انتخاب می گردد. جدول 3-1 نمونه ای از انتخاب کروموزوم ها با استفاده از مدل چرخ رولت را نشان می دهد.
جدول 3- 1: انتخاب کروموزوم ها با استفاده از مدل چرخ رولت
9
8
7
6
5
4
3
دسته بندی : علمی