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

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

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

3-6-1-3-2- عملگرهای تقاطعی
عملگرهایی که یک یا چند نقطه از دو یا چند جواب را انتخاب و مقادیر آنها را تعویض می کنند. این عملگرها یک جواب را درنظر گرفته و محل هایی از جواب را با جواب های دیگر معاوضه کرده و جواب های جدید را بوجود می آورند. به این نوع عملگرها، عملگرهایتقاطعی گفته می شود.
عملگر تقاطعی در یک لحظه بر روی دو کروموزوم اعمال شده و دو نوزاد به وسیله ترکیب ساختار دو کروموزوم ایجاد می گردد. یک مفهوم مهم که در ارتباط با این عملگر مطرح است نرخ تقاطعی می باشد.
3-6-1-3-3- مکانیسم نمونه گیری
مکانیسمنمونهگیری به چگونگی انتخاب کروموزوم ها از فضای نمونه گیری مربوط می شود و یکی از رویکردهای آن نمونه گیری تصادفی است:
دو نمونه گیری تصادفی که اکثرا از آنها استفاده می شود عبارتند از: انتخاب چرخه رولت و انتخاب کلی تصادفی. انتخاب چرخه رولت که اولین بار توسط هالند پیشنهاد شد یکی از مناسب ترین انتخاب های تصادفی بوده که ایده آن احتمال انتخاب می باشد. احتمال انتخاب متناظر با هر کروموزوم، براساس برازندگی آن محاسبه می شود بطوریکه اگر مقدار برازندگی کروموزوم k ام باشد، احتمال بقای متناظر با آن کروموزوم عبارت است از:
(13.3)
,
بطوریکه n اندازه جمعیت هر نسل می باشد. حال کروموزوم ها را براساس مرتب کرده و که همان مقادیر تجمعی می باشد به صورت زیر بدست می آید:
(14.3)
,
در روش انتخاب چرخه رولت بدین صورت عمل می شود که برای انتخاب هر کروموزوم ابتدا یک عدد تصادفی بین صفر و یک تولید شده و سپس عدد مذکور در هر بازه ای که قرار گرفت کروموزوم متناظر با آن انتخاب می شود. البته روش پیاده کردن چرخه رولت بدین شکل است که یک دایره را درنظر گرفته و آن را به تعداد کروموزوم ها طوری تقسیم می کنیم که هر بخش متناظر با مقدار برازندگی کروموزوم مربوطه باشد. حال چرخ را چرخانده و هر کجا که چرخ متوقف شد به شاخص چرخ نگاه کرده، کروموزوم مربوط به آن بخش انتخاب می گردد.
3-6-1-4- تابع برازش
همانطور که دیده شد در فرایند انتخاب بارها از عبارت کروموزوم مناسب تر صحبت به بیان می آید. بدیهی است که برای تشخیص کروموزوم مناسب تر باید یک شاخص جهت ارزیابی کروموزوم ها وجود داشته باشد.
در مورد مسائل بهینه سازی توابع، معمولا این شاخص همان مقدار تابع هدف مساله می باشد، یعنی هر کروموزوم تبدیل به جواب متناظر شده و در تابع هدف قرار می گیرد، آنگاه مقدار تابع هدف برای هر جوابی که بهتر باشد کروموزوم متناظر با آن جواب مناسبب تر خواهد بود. اما در مورد بعضی مسائل که پیچیده تر هستند باید اقدام به تعریف این تابع برازش نمود.
3-6-1-5- استراتژی برخورد با محدودیت ها
بحث دیگری که در اجرای الگوریتم ژنتیک وجود دارد، چگونگی برخورد با محدودیت های مساله است زیرا عملگرهای ژنتیک مورد استفاده در الگوریتم باعث تولید کروموزوم های غیرموجه می شود. چند تکنیک معمول جهت مواجهه با محدودیت وجود دارد که در ادامه به چندتا از آنها اشاره می شود.
3-6-1-5-1- استراتژی اصلاح عملگرها
یک روش برای جلوگیری از تولید کروموزوم غیرموجه این است که عملگر ژنتیکی طوری تعریف گردد که پس از عمل بر روی کروموزوم ها، کروموزوم تولید شده نیز موجه باشد. در این حالت یکسری مشکل ها وجود دارند. مثلا پیدا کردن عملگری که دارای شرایط فوق باشد بسیار دشوار بوده و از مساله ای به مساله دیگر متفاوت می باشد.
3-6-1-5-2- استراتژی ردی
در این روش پس از تولید هر کروموزوم آن را از نظر موجه بودن تست کرده و در صورت غیرموجه بودن حذف می گردد این روش بسیار ساده و کارا می باشد.
3-6-1-5-3- استراتژی اصلاحی
در این روش به جای اینکه کروموزوم غیرموجه حذف گردد تبدیل به یک کروموزوم موجه می گردد. این روش نیز مانند روش اول به مساله وابسته بوده و یافتن فرآیند اصلاح گاهی بسیار پیچیده می باشد.
3-6-1-5-4- استراتژی جریمه ای
در این روش بر خلاف سه روش قبل که از ورود جواب های غیر موجه جلوگیری می کردند، جواب های غیرموجه با احتمال کم امکان حضور می یابند. سه روش فوق دارای این اشکال بودند که به هیچ نقطه ای بیرون از فضای موجه توجه نمی کردند، اما در بعضی از مسائل بهینه سازی، جواب های غیرموجه درصد زیادی از جمعیت را اشغال می کنند. در چنین شرایطی اگر جستجو فقط در ناحیه موجه انجام گیرد شاید یافتن جواب موجه خیلی وقت گیر و مشکل باشد. استراتژی جریمه ای از متداولترین تکنیک های مورد استفاده برای پذیرش با جواب های غیرموجه می باشد که در آن از ابتدا محدودیت های مساله درنظر گرفته نمی شوند، سپس برای هر تخلف از محدودیت ها، یک جریمه اختصاص داده می شود که این جریمه در تابع هدف قرار می گیرد.
3-6-2- ساختار کلی الگوریتم ژنتیک
دسته بندی : علمی