ژانویه 26, 2021

مساله مکان یابی تخصیص تسهیلات و انبار مرکزی با تقاضای برنولی- قسمت ۳۵

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

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

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

برای دانلود متن کامل پایان نامه به سایت azarim.ir مراجعه نمایید.