فایل دانشگاهی – مساله مکان یابی تخصیص چند تسهیله ظرفیت بندی شده در حضور منابع …

بطوریکه n اندازه جمعیت[۶۱] هر نسل می باشد. حال کروموزوم ها را براساس مرتب کرده و که همان مقادیر تجمعی می باشد به صورت زیر بدست می آید:

(۱۴٫۳) ,

در روش انتخاب چرخه رولت بدین صورت عمل می شود که برای انتخاب هر کروموزوم ابتدا یک عدد تصادفی بین صفر و یک تولید شده و سپس عدد مذکور در هر بازه ای که قرار گرفت کروموزوم متناظر با آن انتخاب می شود. البته روش پیاده کردن چرخه رولت بدین شکل است که یک دایره را درنظر گرفته و آن را به تعداد کروموزوم ها طوری تقسیم می کنیم که هر بخش متناظر با مقدار برازندگی کروموزوم مربوطه باشد. حال چرخ را چرخانده و هر کجا که چرخ متوقف شد به شاخص چرخ نگاه کرده، کروموزوم مربوط به آن بخش انتخاب می گردد.
۳-۶-۱-۴- تابع برازش
همانطور که دیده شد در فرایند انتخاب بارها از عبارت کروموزوم مناسب تر صحبت به بیان می آید. بدیهی است که برای تشخیص کروموزوم مناسب تر باید یک شاخص جهت ارزیابی کروموزوم ها وجود داشته باشد.
در مورد مسائل بهینه سازی توابع، معمولا این شاخص همان مقدار تابع هدف مساله می باشد، یعنی هر کروموزوم تبدیل به جواب متناظر شده و در تابع هدف قرار می گیرد، آنگاه مقدار تابع هدف برای هر جوابی که بهتر باشد کروموزوم متناظر با آن جواب مناسبب تر خواهد بود. اما در مورد بعضی مسائل که پیچیده تر هستند باید اقدام به تعریف این تابع برازش نمود.
۳-۶-۱-۵- استراتژی برخورد با محدودیت ها
بحث دیگری که در اجرای الگوریتم ژنتیک وجود دارد، چگونگی برخورد با محدودیت های مساله است زیرا عملگرهای ژنتیک مورد استفاده در الگوریتم باعث تولید کروموزوم های غیرموجه می شود. چند تکنیک معمول جهت مواجهه با محدودیت وجود دارد که در ادامه به چندتا از آنها اشاره می شود.
۳-۶-۱-۵-۱- استراتژی اصلاح عملگرها[۶۲]
یک روش برای جلوگیری از تولید کروموزوم غیرموجه این است که عملگر ژنتیکی طوری تعریف گردد که پس از عمل بر روی کروموزوم ها، کروموزوم تولید شده نیز موجه باشد. در این حالت یکسری مشکل ها وجود دارند. مثلا پیدا کردن عملگری که دارای شرایط فوق باشد بسیار دشوار بوده و از مساله ای به مساله دیگر متفاوت می باشد.
۳-۶-۱-۵-۲- استراتژی ردی[۶۳]
در این روش پس از تولید هر کروموزوم آن را از نظر موجه بودن تست کرده و در صورت غیرموجه بودن حذف می گردد این روش بسیار ساده و کارا می باشد.
۳-۶-۱-۵-۳- استراتژی اصلاحی[۶۴]
در این روش به جای اینکه کروموزوم غیرموجه حذف گردد تبدیل به یک کروموزوم موجه می گردد. این روش نیز مانند روش اول به مساله وابسته بوده و یافتن فرآیند اصلاح گاهی بسیار پیچیده می باشد.
۳-۶-۱-۵-۴- استراتژی جریمه ای[۶۵]
در این روش بر خلاف سه روش قبل که از ورود جواب های غیر موجه جلوگیری می کردند، جواب های غیرموجه با احتمال کم امکان حضور می یابند. سه روش فوق دارای این اشکال بودند که به هیچ نقطه ای بیرون از فضای موجه توجه نمی کردند، اما در بعضی از مسائل بهینه سازی، جواب های غیرموجه درصد زیادی از جمعیت را اشغال می کنند. در چنین شرایطی اگر جستجو فقط در ناحیه موجه انجام گیرد شاید یافتن جواب موجه خیلی وقت گیر و مشکل باشد. استراتژی جریمه ای از متداولترین تکنیک های مورد استفاده برای پذیرش با جواب های غیرموجه می باشد که در آن از ابتدا محدودیت های مساله درنظر گرفته نمی شوند، سپس برای هر تخلف از محدودیت ها، یک جریمه اختصاص داده می شود که این جریمه در تابع هدف قرار می گیرد.
۳-۶-۲- ساختار کلی الگوریتم ژنتیک
ساختار کلی یک الگوریتم ژنتیک را می توان به صورت ذیل تصور کرد.
ابتدا پیش از هر چیز باید مکانیسمی برای تبدیل هر جواب مساله به یک کروموزوم تعریف کرد. پس از آن یک مجموعه از کروموزوم ها که در حقیقت مجموعه ای از جواب های مساله هستند به عنوان یک جمعیت آغازین[۶۶]تهیه می گردند. این مجموعه که اندازه آن دلخواه است و توسط کاربر تعریف می شود، اغلب به صورت تصادفی ایجاد می گردد.
بعد از این مرحله باید با بکارگیری عملیات ژنتیک[۶۷] اقدام به ایجاد کروموزوم های جدید موسوم به نوزاد[۶۸] نمود. این عملیات به دو گونه عمده تقاطعی و جهشی تقسیم می شوند. همچنین برای گزینش کروموزوم هایی که باید نقش والدین را بازی کنند دو مفهوم نرخ تقاطعی[۶۹] و نرخ جهشی[۷۰] کاربرد فراوان دارند که این دو نیز پیش از شروع الگوریتم توسط کاربر تعیین می شوند.
بعد از تولید یک سری کروموزوم جدید یا اولاد باید با استفاده از عمل تحول[۷۱] اقدام به انتخاب[۷۲] برازنده- ترین کروموزوم ها نمود. این فرآیند که در فرآیند انتخاب نمود می یابد، گلچین کردن کروموزوم های برازنده در میان والدین و اولاد است، به طوریکه تعداد کروموزوم های منتخب برابر با اندازه جمعیت اولیه باشد. فرآیند انتخابی مبتنی بر مقدار برازندگی[۷۳] هر رشته است. در حقیقت فرآیند ارزیابی[۷۴] محوری ترین بحث در فرآیند انتخاب است.
تا بدین مرحله یک تکرار یا یک نسل از الگوریتم طی شده است. الگوریتم پس از طی چندین نسل به تدریج به سمت جواب بهینه همگرا می شود. شرط توقف مساله نیز طی کردن تعداد معینی تکرار است که پیش از آغاز الگوریتم توسط کاربر تعیین می شود.ساختار کلی یک الگوریتم ژنتیک را بصورت ذیل بیان شده است:

نوشته ای دیگر :
ارتباط بین سبک های هویت و سلامت اجتماعی با نقش واسطه ای ...

دانلود متن کامل این پایان نامه در سایت abisho.ir

r/>

روند الگوریتم ژنتیک

Step 1: Set t:=0