
جستجوی مقالات فارسی – ارائه یک مدل جدید جایابی و تخصیص در محیط غیرقطعی- قسمت ۱۴
تابع ارزیابی[۳۶]
تابع ارزیابی در این الگوریتم همان تابع هدف مسأله میباشد. در این تابع، مقدار و به ترتیب مقادیر دو ژن آخر است.
فرایند انتخاب والد[۳۷]
در فرایند انتخاب والد، جهت انتخاب والد برای شرکت در عملیات تقاطع، از انتخاب تصادفی استفاده میشود.
عملیات تقاطع[۳۸]
از عملیات تقاطع جهت تولید فرزند[۳۹] از والد استفاده میشود. طبق فرایند انتخاب والد، یک جفت والد انتخاب میشود. برای انجام عملیات تقاطع، به صورت تصادفی یکی از دو روش تقاطع تک نقطه یا دو نقطه به کار برده میشود. در تقاطع تک نقطه یک عدد تصادفی تولید میشود که نشاندهنده ژنی در کروموزوم است که برای عملیات تقاطع از این ژن و جابجایی بخشهای ایجاد شده بوسیله آن استفاده میشود. شکل (۳-۲) این عملیات را نشان میدهد.
نحوه عملکرد عملیات تقاطع تک نقطه
در تقاطع دو نقطه دو عدد تصادفی متفاوت تولید میشود که نشاندهنده دو ژن در کروموزوم است که برای عملیات تقاطع از این ژنها و جابجایی بخشهای میانی ایجاد شده بوسیله آن ها استفاده میشود. شکل (۳-۳) این عملیات را نشان میدهد.
نحوه عملکرد عملیات تقاطع دو نقطه
جهت تسریع در روند اجرای الگوریتم، پس از انجام عملیات تقاطع، فرزندان تولید شده بروز میشوند. چراکه پس از انجام عملیات تقاطع، امکان دارد تعداد تسهیلات مستقر شده برابر نباشد و لذا عملیات باید تکرار شود اما در بروز رسانی فرزندان، تعداد تسهیلات برابر شده و تغییرات لازم اعمال میشود. کد بروز رسانی فرزند تولید شده به صورت زیر است:
function nc = new child (c, sof, nof, nofs)
% c : child
% sof : set of facilities
% nofs : number of facilities in set
% nof : number of facilities
if nofs > nof
for k=1:(nofs-nof)
select randomly two sites and replace one of them with another;
end
elseif nofs < nof
for k=1:(nof-nofs)
select randomly a facility site (fs) and a non-facility site (nfs). Then, set a facility in nfs and change allocations from fs to nfs alternately;
end
else
child c is ok;
end
همچنین جهت بالا بردن کارایی عملیات تقاطع، در هر بار انجام عملیات، تقاطع چند مرتبه انجام شده (تعداد ملاقاتها[۴۰]) و بهترین تقاطع به عنوان عملیات تقاطع اصلی معرفی میگردد.
در حل مسائل با ابعاد بزرگ، عملیات تقاطع ممکن است اثربخشی خوبی نداشته باشد. لذا میتوان عملیات تقاطع را به جای دو والد با چند والد[۴۱] انجام داد [۳۴ ، ۳۵]. در اینصورت نتیجه تقاطع با سه والد، ۶ فرزند و نتیجه تقاطع با چهار والد، ۲۴ فرزند خواهد بود. فرزندان حاصل از این عملیات تقاطع نیز قبل از ورود به جمعیت بروز میشوند. شکل (۳-۴)، تقاطع با سه والد و دو نقطه تقاطع را نشان میدهد.
نحوه عملکرد عملیات تقاطع سه والد
برای هر یک از کروموزومهای جدید، مقدار تابع هدف محاسبه شده و در ژن ۸ قرار میگیرد. همچنین شانس دستیابی به مقدار تابع هدف ژن ۸ برای هر کروموزوم در ژن ۹ قرار میگیرد.
اگر هر دو کروموزوم جدید شدنی نباشند، عملیات تقاطع روی دو کروموزوم اولیه تکرار میشود. و اگر فقط یکی از کروموزومهای جدید شدنی باشد، تا سه مرتبه عملیات تقاطع برای بدست آوردن دو کروموزوم شدنی تکرار میشود. اگر باز هم فقط یکی از کروموزومها شدنی بود، فقط همان کروموزوم شدنی وارد جمعیت میشود.
عملیات جهش[۴۲]
در عملیات جهش، به صورت تصادفی یکی از سه روش جهش تک نقطهای، دو نقطهای و سه نقطهای بر روی کروموزومهای حاصل از عملیات تقاطع با یک نرخ جهش مشخص انجام میگیرد. برای نمونه در جهش دو نقطهای، دو عدد تصادفی متفاوت که نشاندهنده شماره دو ژن است تولید شده و آن ژنها با دو عدد تصادفی دیگر که نشاندهنده شماره دو نقطه است، جایگزین میشوند. سپس این کروموزوم جدید بروز شده و همانند قبل، ژنهای شماره ۸ و ۹ نیز تکمیل میشوند. شدنی بودن این کروموزوم جدید بررسی شده و اگر شدنی باشد، به جمعیت جدید افزوده میشود، در غیر اینصورت عملیات جهش تکرار میگردد. به عنوان مثال فرض کنید که قرار است دومین ژن با نقطه شماره ۵ و پنجمین ژن با نقطه شماره ۱ جایگزین شود. شکل (۳-۵) عملیات جهش دو نقطهای را نشان میدهد.
برای دانلود متن کامل این پایان نامه به سایت fumi.ir مراجعه نمایید. |