child c is ok;
end
همچنین جهت بالا بردن کارایی عملیات تقاطع، در هر بار انجام عملیات، تقاطع چند مرتبه انجام شده (تعداد ملاقات‌ها^[۴۰]) و بهترین تقاطع به عنوان عملیات تقاطع اصلی معرفی می‌گردد.
در حل مسائل با ابعاد بزرگ، عملیات تقاطع ممکن است اثربخشی خوبی نداشته باشد. لذا می‌توان عملیات تقاطع را به جای دو والد با چند والد^[۴۱] انجام داد [۳۴ ، ۳۵]. در اینصورت نتیجه تقاطع با سه والد، ۶ فرزند و نتیجه تقاطع با چهار والد، ۲۴ فرزند خواهد بود. فرزندان حاصل از این عملیات تقاطع نیز قبل از ورود به جمعیت بروز می‌شوند. شکل (۳-۴)، تقاطع با سه والد و دو نقطه تقاطع را نشان می‌دهد.
نحوه عملکرد عملیات تقاطع سه والد
برای هر یک از کروموزوم‌های جدید، مقدار تابع هدف محاسبه شده و در ژن ۸ قرار می‌گیرد. همچنین شانس دستیابی به مقدار تابع هدف ژن ۸ برای هر کروموزوم در ژن ۹ قرار می‌گیرد.

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

اگر هر دو کروموزوم جدید شدنی نباشند، عملیات تقاطع روی دو کروموزوم اولیه تکرار می‌شود. و اگر فقط یکی از کروموزوم‌های جدید شدنی باشد، تا سه مرتبه عملیات تقاطع برای بدست آوردن دو کروموزوم شدنی تکرار می‌شود. اگر باز هم فقط یکی از کروموزوم‌ها شدنی بود، فقط همان کروموزوم شدنی وارد جمعیت می‌شود.

عملیات جهش^[۴۲]
در عملیات جهش، به صورت تصادفی یکی از سه روش جهش تک نقطه‌ای، دو نقطه‌ای و سه نقطه‌ای بر روی کروموزوم‌های حاصل از عملیات تقاطع با یک نرخ جهش مشخص انجام می‌گیرد. برای نمونه در جهش دو نقطه‌ای، دو عدد تصادفی متفاوت که نشان‌دهنده شماره دو ژن است تولید شده و آن ژن‌ها با دو عدد تصادفی دیگر که نشان‌دهنده شماره دو نقطه است، جایگزین می‌شوند. سپس این کروموزوم جدید بروز شده و همانند قبل، ژن‌های شماره ۸ و ۹ نیز تکمیل می‌شوند. شدنی بودن این کروموزوم جدید بررسی شده و اگر شدنی باشد، به جمعیت جدید افزوده می‌شود، در غیر اینصورت عملیات جهش تکرار می‌گردد. به عنوان مثال فرض کنید که قرار است دومین ژن با نقطه شماره ۵ و پنجمین ژن با نقطه شماره ۱ جایگزین شود. شکل (۳-۵) عملیات جهش دو نقطه‌ای را نشان می‌دهد.
نحوه عملکرد عملیات جهش دو نقطه‌ای

فرایند تخصیص مجدد
در فرایند تخصیص مجدد که بر روی هر یک کروموزوم از کروموزوم‌های جمعیت فرزند انجام می‌شود، بدون تغییر در محل تسهیلات، تخصیص نقاط تقاضا به تسهیلات تغییر می‌کند بدین صورت که هر نقطه تقاضا به نزدیکترین تسهیل تخصیص می‌یابد. جمعیت حاصل از تخصیص مجدد به جمعیت فرزندان اضافه شده و وارد فرایند انتخاب جمعیت جدید می‌شوند.

فرایند انتخاب جمعیت
جمعیت قبلی (والد) و جمعیت جدید (فرزند) که حاصل عملیات تقاطع و عملیات جهش با نرخ جهش مشخص بر روی جمعیت فرزند است، لیستی را تشکیل می‌دهند. این لیست بر اساس تابع ارزیابی به صورت نزولی مرتب شده و سپس به تعداد جمعیت مورد نظر از ابتدای لیست انتخاب می‌شود. این جمعیت به عنوان جمعیت والد وارد دور بعدی الگوریتم می‌شود.

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