تابع عضویت به صورت زیر تعریف می‌شود:
(3-12)
لذا شانس برقراری شرط با توجه به رابطه (2-4) به صورت زیر است:
(3-13)
برای حل مدل (3-11) از الگوریتم ژنتیک استفاده شده است. در ادامه، الگوریتم ژنتیک ارائه شده جهت حل مدل (3-11) را بیان شده است.
3-3-4- الگوریتم ژنتیک
در این قسمت به توضیح و تشریح الگوریتم ژنتیک به کار برده شده در این پایان‌نامه جهت حل مدل (3-11) پرداخته می‌شود.
3-3-4-1- معرفی کروموزوم‌ها30
کروموزوم‌ها در این الگوریتم، نه رمزنگاری31 می‌شوند و نه رمزگشایی32. بلکه به جای هر ژن33، اندیس نقطه کاندید استقرار قرار داده می‌شود. در واقع، تعداد ژن‌های هر کروموزوم برابر است با تعداد نقاط تقاضا به اضافه 2. در ژن‌های ابتدایی، شماره نقاطی که تسهیل در آن استقرار می‌یابد، قرار می‌گیرد تا مشخص شود که هر نقطه تقاضا به کدام تسهیل تخصیص می‌یابد. در ژن بعدی، عددی به تصادف قرار می‌گیرد که نشان‌دهنده مقدار تابع هدف برای تخصیص فوق الذکر است. و در ژن پایانی، شانس اینکه تخصیص فوق الذکر به مقدار تابع هدف فوق برسد را نشان می‌دهد. لازم به ذکر است که برای بدست آوردن این شانس، یک الگوریتم ژنتیک دیگر اجرا می‌شود. برای نمونه فرض کنید تعداد 7 نقطه تقاضا و 5 نقطه کاندید استقرار داریم. کروموزم زیر را در نظر بگیرید:

شکل (3-1) نمونه‌ای از کروموزوم الگوریتم ارائه شده
هفت ژن اول این کروموزوم نشان‌دهنده جایابی و تخصیص تسهیلات هستند. یعنی باید در نقاط 1 و 3 و 4 تسهیل مستقر شود. سپس تسهیل 1 به نقاط نقاضای 2 و 6 و 7، تسهیل 3 به نقاط تقاضای 4 و 5، و تسهیل 4 به نقاط تقاضای 1 و 3 تخصیص داده می‌شود.
دو ژن آخر بیان می‌کنند که این تخصیص با حداقل شانس 3/0 می‌تواند به مقدار تابع هدف 750 دست یابد.
3-3-4-2- جمعیت اولیه34
برای تولید جمعیت اولیه از مقداردهی تصادفی هوشمند به ژن‌های اولیه و محاسبه مقدار تابع هدف و شانس آن در دو ژن آخر استفاده می‌شود. منظور از مقداردهی تصادفی هوشمند اینست که به طورتصادفی محل از نقاط تقاضا انتخاب و تسهیلات در آنجا مستقر می‌شوند. سپس هر نقطه تقاضا به نزدیک‌ترین تسهیل تخصیص داده می‌شود. با استفاده از تولید تصادفی هوشمند، جمعیت اولیه نزدیک به جواب مسأله تولید می‌شود که باعث تسریع در رسیدن به جواب بهینه مسأله می‌شود. کد تولید تصادفی هوشمند جمعیت اولیه به صورت زیر است:
function ip = Initial Population (nop, nof)
% nop : number of nodes
% nof : number of facilities
% sof : Set of facilities
sof = generate random nodes for facilities through demand;
for i=1:nop
if i is in sof
ip(i) = i;
else
ip(i) = nearest facility node to node i;
end
end
اگر کروموزوم تولید شده شدنی بود، به جمعیت اولیه اضافه می‌شود. جمعیت اولیه سه برابر جمعیت در هر دور اجرای الگوریتم می‌باشد.
3-3-4-3- تست شدنی بودن35
فقط کروموزوم‌های شدنی می‌توانند وارد جمعیت شده و در عملیات‌های الگوریتم شرکت کنند. لذا لازم است پس از تولید کروموزوم، شدنی بودن آن بررسی شود.
جهت انجام تست شدنی بودن یک کروموزوم، باید موارد زیر رعایت شوند:
الف) کروموزوم باید محدودیت شانس را رعایت کند؛
ب) مقدار باید از بیشتر باشد؛
دراینصورت است که جواب شدنی بودن کروموزوم، مثبت است.
لازم به ذکر است با توجه به نوع تولید جمعیت اولیه و همچنین روش عملیات‌های تقاطع و جهش که در ادامه توضیح داده می‌شوند، نیازی به بررسی تعداد تسهیلات استقرار یافته در کروموزوم‌ها جهت تست شدنی بودن نمی‌باشد.
3-3-4-4- تابع ارزیابی36
تابع ارزیابی در این الگوریتم همان تابع هدف مسأله می‌باشد. در این تابع، مقدار و به ترتیب مقادیر دو ژن آخر است.
3-3-4-5- فرآیند انتخاب والد37
در فرآیند انتخاب والد، جهت انتخاب والد برای شرکت در عملیات تقاطع، از انتخاب تصادفی استفاده می‌شود.
3-3-4-6- عملیات تقاطع38
از عملیات تقاطع جهت تولید فرزند39 از والد استفاده می‌شود. طبق فرآیند انتخاب والد، یک جفت والد انتخاب می‌شود. برای انجام عملیات تقاطع، به صورت تصادفی یکی از دو روش تقاطع تک نقطه یا دو نقطه به کار برده می‌شود. در تقاطع تک نقطه یک عدد تصادفی تولید می‌شود که نشان‌دهنده ژنی در کروموزوم است که برای عملیات تقاطع از این ژن و جابجایی بخش‌های ایجاد شده بوسیله آن استفاده می‌شود. شکل (3-2) این عملیات را نشان می‌دهد.

شکل (3-2) نحوه عملکرد عملیات تقاطع تک نقطه
در تقاطع دو نقطه دو عدد تصادفی متفاوت تولید می‌شود که نشان‌دهنده دو ژن در کروموزوم است که برای عملیات تقاطع از این ژن‌ها و جابجایی بخش‌های میانی ایجاد شده بوسیله آن‌ها استفاده می‌شود. شکل (3-3) این عملیات را نشان می‌دهد.

شکل (3-3) نحوه عملکرد عملیات تقاطع دو نقطه
جهت تسریع در روند اجرای الگوریتم، پس از انجام عملیات تقاطع، فرزندان تولید شده بروز می‌شوند. چراکه پس از انجام عملیات تقاطع، امکان دارد تعداد تسهیلات مستقر شده برابر نباشد و لذا عملیات باید تکرار شود اما در بروز رسانی فرزندان، تعداد تسهیلات برابر شده و تغییرات لازم اعمال می‌شود. کد بروز رسانی فرزند تولید شده به صورت زیر است:
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
همچنین جهت بالا بردن کارایی عملیات تقاطع، در هر بار انجام عملیات، تقاطع چند مرتبه انجام شده (تعداد ملاقات‌ها40) و بهترین تقاطع به عنوان عملیات تقاطع اصلی معرفی می‌گردد.
در حل مسائل با ابعاد بزرگ، عملیات تقاطع ممکن است اثربخشی خوبی نداشته باشد. لذا می‌توان عملیات تقاطع را به جای دو والد با چند والد41 انجام داد [34 ، 35]. در اینصورت نتیجه تقاطع با سه والد، 6 فرزند و نتیجه تقاطع با چهار والد، 24 فرزند خواهد بود. فرزندان حاصل از این عملیات تقاطع نیز قبل از ورود به جمعیت بروز می‌شوند. شکل (3-4)، تقاطع با سه والد و دو نقطه تقاطع را نشان می‌دهد.

این مطلب رو هم توصیه می کنم بخونین:   منبع پایان نامه درموردشخص ثالث، بازپرداخت

شکل (3-4) نحوه عملکرد عملیات تقاطع سه والد
برای هر یک از کروموزوم‌های جدید، مقدار تابع هدف محاسبه شده و در ژن 8 قرار می‌گیرد. همچنین شانس دستیابی به مقدار تابع هدف ژن 8 برای هر کروموزوم در ژن 9 قرار می‌گیرد.
اگر هر دو کروموزوم جدید شدنی نباشند، عملیات تقاطع روی دو کروموزوم اولیه تکرار می‌شود. و اگر فقط یکی از کروموزوم‌های جدید شدنی باشد، تا سه مرتبه عملیات تقاطع برای بدست آوردن دو کروموزوم شدنی تکرار می‌شود. اگر باز هم فقط یکی از کروموزوم‌ها شدنی بود، فقط همان کروموزوم شدنی وارد جمعیت می‌شود.
3-3-4-7- عملیات جهش42
در عملیات جهش، به صورت تصادفی یکی از سه روش جهش تک نقطه‌ای، دو نقطه‌ای و سه نقطه‌ای بر روی کروموزوم‌های حاصل از عملیات تقاطع با یک نرخ جهش مشخص انجام می‌گیرد. برای نمونه در جهش دو نقطه‌ای، دو عدد تصادفی متفاوت که نشان‌دهنده شماره دو ژن است تولید شده و آن ژن‌ها با دو عدد تصادفی دیگر که نشان‌دهنده شماره دو نقطه است، جایگزین می‌شوند. سپس این کروموزوم جدید بروز شده و همانند قبل، ژن‌های شماره 8 و 9 نیز تکمیل می‌شوند. شدنی بودن این کروموزوم جدید بررسی شده و اگر شدنی باشد، به جمعیت جدید افزوده می‌شود، در غیر اینصورت عملیات جهش تکرار می‌گردد. به عنوان مثال فرض کنید که قرار است دومین ژن با نقطه شماره 5 و پنجمین ژن با نقطه شماره 1 جایگزین شود. شکل (3-5) عملیات جهش دو نقطه‌ای را نشان می‌دهد.

شکل (3-5) نحوه عملکرد عملیات جهش دو نقطه‌ای
3-3-4-8- فرآیند تخصیص مجدد
در فرآیند تخصیص مجدد که بر روی هر یک کروموزوم از کروموزوم‌های جمعیت فرزند انجام می‌شود، بدون تغییر در محل تسهیلات، تخصیص نقاط تقاضا به تسهیلات تغییر می‌کند بدین صورت که هر نقطه تقاضا به نزدیکترین تسهیل تخصیص می‌یابد. جمعیت حاصل از تخصیص مجدد به جمعیت فرزندان اضافه شده و وارد فرآیند انتخاب جمعیت جدید می‌شوند.
3-3-4-9- فرآیند انتخاب جمعیت
جمعیت قبلی (والد) و جمعیت جدید (فرزند) که حاصل عملیات تقاطع و عملیات جهش با نرخ جهش مشخص بر روی جمعیت فرزند است، لیستی را تشکیل می‌دهند. این لیست بر اساس تابع ارزیابی به صورت نزولی مرتب شده و سپس به تعداد جمعیت مورد نظر از ابتدای لیست انتخاب می‌شود. این جمعیت به عنوان جمعیت والد وارد دور بعدی الگوریتم می‌شود.
3-3-4-10- معیار توقف
برای متوقف شدن الگوریتم، دو شرط قرار داده می‌شود:
الف) به اتمام رسیدن تعداد تکرارهای الگوریتم،
ب) عدم تغییر بهترین جواب در تعداد تکرارهای مشخص شده.
در پایان، کروموزوم با بیشترین مقدار تابع ارزیابی در جمعیت آخر، به عنوان جواب انتخاب می‌شود.
کد اصلی این الگوریتم در پیوست ب ارائه شده است.
در فصل بعد، چند مثال را با استفاده از مدل ارائه شده، مدل و با استفاده از روش حل و الگوریتم بیان شده حل شده و کارایی مدل ارائه شده را نشان داده می‌شود.

فصل 4:
نتایج و تفسیر آنها

4-1- مقدمه
در این فصل، به ارائه‌ی داده‌ها، نتایج و تحلیل و تفسیر آنها پرداخته می‌شود. جهت آگاهی از صحت اجرای الگوریتم، ابتدا آن‌را بر روی مجموعه داده‌های گالوائو43 که در صفحه وب ارکات44 موجود می‌باشند، پیاده سازی شده است. این داده‌ها قطعی و بدون تقاضا هستند. سپس به صورت تصادفی به هر یک از نقاط، تقاضا تخصیص داده و با الگوریتم ارائه شده حل شده است. این موارد با جواب بهینه و نرم‌افزار جایابی داسکین45 مقایسه شده‌اند. پس از اطمینان از درستی و کارایی الگوریتم، مدل ارائه شده بر روی یک مسأله احتمالی پیاده‌سازی می‌شود.
پس از آگاهی از صحت و کارایی مدل و الگوریتم بر روی مسائل فوق، سراغ مسائل ترکیبی در مقالات مختلف رفته و کارایی مدل را با اجرا بر روی این نوع مسائل نشان داده شده است.
4-2- محتوا
4-2-1- اجرای الگوریتم بر روی داده‌های قطعی
برای آگاهی از صحت اجرای الگوریتم، از مجموعه داده‌های گالوائو استفاده شده است که برای 100 نقطه تقاضا با تعداد تسهیلات 5، 10، 15، 20، 25، 30، 35 و 40 حل شده و در صفحه وب ارکات موجود می‌باشد. لازم به ذکر است که این مسأله –میانه قطعی و بدون تقاضا است. لذا برای اینکه الگوریتم طراحی شده با این مسأله تطابق پیدا کند، آن را با تقاضای 1 برای تمامی نقاط و با شانس 1 برای برقرار بودن محدودیت شانس، حل شد که جواب‌ها بسیار نزدیک به بهینه بود. همچنین مسائل فوق با استفاده از نرم افزار جایابی داسکین (روش آزادسازی لاگرانژی46 و الگوریتم ژنتیک) نیز حل شد که نتایج در جدول (4-1) آورده شده است.
جدول (4-1) نتایج حاصل از الگوریتم ارائه شده و نرم‌افزار جایابی داسکین بر روی داده‌های گالوائو
تعداد نقاط تقاضا
تعداد تسهیلات
مقدار بهینه گالوائو
روش آزادسازی لاگرانژی نرم افزار جایابی
الگوریتم ژنتیک نرم افزار جایابی
الگوریتم ژنتیک ارائه

دسته‌ها: No category

دیدگاهتان را بنویسید