عملکرد بهتری داشته باشند. اما بهتر است همیشه بهترین کروموزومهای نسل قبلی بدون هیچ تغییری به نسل جدید منتقل شوند.
تفاوت عملگر چند نقطهای در مقایسه با عملگر تقاطع تک نقطه ای دراین است که نقطه شکست دو کروموزوم، بیش از یکی است و تقاطع در بخشهای شکسته شده دو کروموزوم به صورت یک در میان انجام میگیرد. شکل 3-9 مثالی از عمل تقاطع دو نقطه ای را نشان میدهند.
شکل 39. تقاطعی دو نقطه ای
در عمل تقاطعی یکنواخت، بیتها به صورت تصادفی از والد ١ یا والد ٢ کپی میشوند.
شکل 35. عمل تقاطعی یکنواخت
باید خاطر نشان ساخت که اثر استفاده از هر کدام از انواع عملگرهای تقاطع در سرعت همگرایی الگوریتم، دقیقا مشخص نمی باشد و به مساله مورد نظر بستگی دارد.
3-2-1-5-9- عملگر جهش
عملیات جهش به منظور جلوگیری از افتادن الگوریتم ژنتیک در دام بهینههای محلی انجام میشود. این عملگر روی هر یک از کروموزومهای حاصل از عملگر تقاطعی عمل میکند. عملگر جهش با احتمال Pm انجام میشود.
3-2-1-5-10- روش های انتخاب
در الگوریتم ژنتیک، روشهای انتخاب مختلف زیادی وجود دارد که میتواند بکار گرفته شود تا افرادی را برای انتقال به نسل بعدی انتخاب نماید که برخی از این روش ها در زیر فهرست میشوند:
انتخاب بر اساس بهترین ها93 :
این انتخاب، روشی برای نگهداری یک کپی از بهترین کروموزومها در نسل جدید است. به تجربه ثابت شده است که این مکانیزم عملکرد الگوریتم ژنتیک را بهبود داده و در ضمن زمان همگرایی94 را کوتاه مینماید.
انتخاب بر اساس چرخ رولت95 :
در این مدل، سطح چرخ به بخشهایی تقسیم میشود که تعداد آنها برابر با تعداد اعضای جمعیت و سطح هر بخش متناسب با مقدار برازندگی هر کروموزوم است. سپس چرخ به گردش درمیآید تا در نقطهای به تصادف متوقف گردد. این نقطه، کروموزوم انتخاب شده را مشخص میسازد. شکل 3-10 شمایی از چرخ رولت را نشان می دهد.
شکل 36. چرخ رولت
انتخاب بر اساس تورنامنت96 :
در این روش، زیرگروههایی از افراد (معمولاً با 2 یا 3 فرد) از جمعیت بزرگتر انتخاب میشوند، و اعضای هر زیر گروه با یکدیگر رقابت میکنند و تنها یک فرد از هر زیرگروه برای تولید مجدد انتخاب میشود که آن فرد میتواند بهترین کروموزوم بر اساس میزان برازندگی باشد.
شکل 37. انتخاب تورنامنت
3-2-1-6- ارائه الگوریتم پیشنهادی
3-2-1-7- نمایش کروموزوم
در این تحقیق از یک شمای سلسله مراتبی دو لایهای برای کد کردن جواب مساله استفاده شده است. جدول 3-1 نمونهای از این کروموزوم را برای یک مساله با 6 ماشین و 8 قطعه نشان میدهد.
Part
Machine
Chromosome
8
7
6
5
4
3
2
1
6
5
4
3
2
1
14
13
12
11
10
9
8
7
6
5
4
3
2
1
Locus
1
2
2
1
2
2
1
1
2
1
1
1
2
2
Layer 1
4
7
8
1
3
2
6
5
5
2
6
1
4
3
Layer 2
جدول 31. نمایش جواب مساله توسط کروموزوم
همانطوریکه مشاهده میکنید کروموزوم شامل دو لایه ژن با طول برابر است. لایه اول برای کد کردن نتایح تشکیل سلول و لایه دوم برای ارائه اطلاعات چیدمان و زمانبندی مورد استفاده قرار گرفته است. هر لایه از ژنها به دو دسته تقسیم شده است که بخش اول شامل m ژن که مطابق با تعداد ماشینها میباشد و بخش دوم شامل n ژن که مرتبط با قطعه ها است. به این ترتیب هر لایه از کروموزم دارای m+n ژن خواهد بود.
در لایه اول، از کدینگ مستقیم استفاده شده است و آلل97 (هر یک از مقادیر متفاوتی که یک ژن میتواند دارا باشد) هر ژن شماره سلولی که قطعه یا ماشین مورد نظر در آن قرار گرفته است را نمایش میدهد. به عنوان مثال، ماشین 1 به سلول 2 و ماشین 3 به سلول 1 اختصاص یافته است. سلول 1 شامل {m3,m4,m5,p1,p2,p5,p8} و سلول 2 شامل {m1,m2,m6,p3,p4,p6,p7} است. در لایه دوم از کدینگ غیرمستقیم بهره گرفتهایم و آلل هر ژن موقیعت وزنی98 هر ماشین یا قطعه را ارائه مینماید. برای مثال موقعیت وزنی ماشین 1 ، 3 و برای ماشین 4 این مقدار برابر 4 است. این فاکتور برای قطعههای 3 و 6 به ترتیب 2 و 8 میباشد. با مرتب سازی ماشینها مطابق موقعیت وزنی به صورت کاهشی{m4,m6,m2,m1,m5,m3}، ترتیب قرارگیری ماشینها در سلول 1 به صورت {m4,m5,m3} و در سلول 2 به صورت {m6,m2,m1} خواهد بود به طوریکه در هر سلول ماشینها به ترتیب از موقعیت 1 مستقر میشوند، به طور مثال در سلول 2، ماشین 1 در موقعیت 3 و در سلول 1، ماشین 4 در موقعیت 1 قرار خواهند گرفت. به طور مشابه، قطعهها نیز با توالی {p6,p7,p2,p1,p8,p4,p3,p5}، زمانبندی خواهند شد با در نظر گرفتن اطلاعات هر دو لایه، چیدمان ماشینها در هر سلول و تخصیص قطعهها در سلول 1 به ترتیب به صورت {m4,m5,m3} و {p2,p1,p8,p5} بوده و به طور مشابه برای سلول 2 با توجه به صورت{m6,m2,m1} و {p6,p7,p4,p3} خواهد بود.
3-2-1-8- ایجاد جمعیت اولیه
مرحله دوم اجرای الگوریتم ژنتیک، ایجاد جمعیت اولیه میباشد، تعداد حل اولیه که در جمعیت در نظر گرفته میشود اندازه جمعیت است که در این تحقیق تمام حل اولیه به صورت تصادفی تولید شده است. تعیین اندازه جمعیت مناسب یکی از تصمیمگیریهای مهم در اجرای الگوریتم ژنتیک میباشد، چراکه اگر اندازه جمعیت کوچک باشد ممکن است نتوانیم به حل خوبی دست پیدا کنیم و از طرف دیگر اگر این مقدار خیلی بزرگ باشد ممکن است پردازنده زمان زیادی برای یافتن حل بهتر صرف کند. به همین منظور برای یافتن مقدار مناسب اغلب از آزمون و خطا استفاده میشود.
3-2-1-9- تابع برازندگی
در اجرای الگوریتم ژنتیک، از یک تابع برازندگی برای ارزیابی و تعیین اینکه آیا یک کروموزوم برای استفاده جهت تولید کروموزمهای جدید باقی مانده و به عنوان فرزند در نسل جدید استفاده خواهد شد یا خیر مورد استفاده قرار میگیرد. تابع برازندگی برای محاسبه میزان ارزش یک کروموزوم بکار میرود. در این تحقیق، تابع برازندگی تغییر حالتی از تابع زمان تکمیل کارها میباشد که این تغییر برای تبدیل هدف مینیمم سازی به ماکزیمم سازی است و به صورت زیر میباشد:
f(x) = Cmax – g(x) , g(x) Cmax
f(x) = 0 , otherwise
روشهای مختلفی برای انتخاب ضریب Cmax وجود دارد که در این مطالعه بزرگترین مقدار زمان تکمیل کار از مقادیر جمعیت کنونی است.
3-2-1-10- انتخاب
هدف مرحله انتخاب این است که به مناسبترین جوابها این اجازه را بدهیم تا در تولید فرزندان نسل بعدی در نظر گرفته شوند. به هر جوابی متناسب با میزان ارزش و برازندگی آن، یک احتمال مشخص برای انتخاب شدن اختصاص مییابد. با اینکه جوابهای بهتر احتمال بیشتری برای انتخاب شدن جهت تولید نسل بعدی را دارند اما همه جوابهای جمعیت شانس انتخاب شدن خواهند داشت. در این پژوهش برای مرحله انتخاب از روش تورنامنت استفاده شده است و به طور پیش فرض از زیر گروه 4 عددی برای این روش استفاده شده است.
3-2-1-11- تقاطع
تولید نسل جدید (فرزندان) با استفاده از عملگرهای تقاطع و جهش بر روی والدین انتخاب شده در مرحله قبل انجام میگیرد. تقاطع اطلاعاتی از دو والد را به نحوی ترکیب میکند که دو فرزند ایجاد شده شباهتهایی را به والدین خود خواهند داشت. از جمله روشهای مرسوم در مدلهای الگوریتم ژنتیک برای عملگر تقاطع، روش تک نقطهای99، دو نقطهای100 و یکنواخت101 را میتوان نام برد. با این حال این عملگرها ممکن است کروموزومهای غیرقانونی تولید کنند که برای رفع این مشکل از راههایی چون تقاطع تطبیقی اندک102، تقاطع ترتیبی103 و تقاطع چرخهای104 و دیگر روشها میتوان بهره گرفت.
در این مطالعه، با توجه به قالب کروموزومی سلسله مراتبی منحصربفرد استفاده شده، از تقاطع تک نقطهای و تقاطعPMX استفاده شده است. در ابتدا یک نقطه قطع به طور تصادفی در طول کروموزوم انتخاب میشود، اگر این نقطه دقیقا بین دو بخش قطعه و ماشین باشد به سادگی از تقاطع تک نقطعهای برای ترکیب دو کروموزوم استفاده میشود و بخش بعد از این نقطه در دو کروموزوم جابجا میشوند. در غیر اینصورت (یعنی نقطه قطع در داخل بخش قطعه یا ماشین باشد)، برای لایه اول کروموزوم تقاطع تک نقطهای بکار گرفته شده و برای لایه دوم برای پیشگیری از ایجاد کروموزم غیرقانونی از تقاطع PMX استفاده شده است. در جدول 3-2 مثالی از عملگر تقاطع نمایش داده شده است. به عنوان مثال نقطعه انتخابی برای تقاطع در محلی بین موقعیت 3 و 4 در بخش ماشین است به این ترتیب با حالت دوم تقاطع روبرو هستیم بعد از اعمال تقاطع فرزندان ایجاد شده غیرقانونی هستند چراکه در لایه دوم فرزند اول و دوم به ترتیب دارای دو مقدار 3 و 5 هستیم برای رفع این مشکل، مقدار آللهایی که با این مشکل روبرو هستند و بعد از نقطه تقاطع قرار دارند را به مقدار حالت قبل از تقاطع باز میگردانیم و اگر باز هم دچار چنین مشکلی شدیم آن را به مقداری از مقادیر قبلی این بخش که مجاز
جدول 32. مثالی از تقاطع مورد استفاده
است، تغییر میدهیم. در مثال با توجه به باز گرداندن مقدار 6 به هر دو آلل مشکل رفع نمیشود به همین خاطر برای فرزند اول مقدار 5 و برای فرزند دوم مقدار 3 جایگزین میشود.
3-2-1-12- جهش
برای اعمال عملگر جهش کروموزم را به 4 بخش تقسیم شده است در واقع لایه اول بخش ماشین و بخش قطعه دو بخش را شامل شده و لایه دوم بخش ماشین و بخش قطعه دو بخش بعدی را تشکیل میدهند. جهش در هر یک از این بخشها صورت میگیرد بطوریکه در هر بخش دو آلل به صورت تصادفی انتخاب شده و مقادیرشان با هم عوض میشوند. به این ترتیب در هر سه بخش تشکیل سلول، چیدمان سلول و زمانبندی جهش صورت خواهد گرفت.
3-2-1-13- معیار توقف
الگوریتم ژنتیک از نسلی به نسل دیگر تغییر میکند و در هر تکرار فرآیندهای انتخاب، ترکیب، جهش و ارزیابی انجام میشوند، این مراحل تا زمان رسیدن به معیار توقف ادامه مییابد. در این مطالعه از تعداد نسل مشخص و ثابت برای شاخص توقف استفاده شده است.
کد کامل این الگوریتم در پیوست ارائه شده است.
فصل چهارم
محاسبات و تحلیل نتایج
4-1- مقدمه
در این فصل در ابتدا برای بیان اعتبار سنجی مدل مثالی را که توسط نرم افزار Lingo 9.0 حل شده است را ارائه مینماییم و سپس مثالهایی با مقیاس بزرگتر که توسط نرم افزار Matlab R2010b و با بهره گیری از رویکرد الگوریتم ژنتیک حل شدهاند ارائه شده و مورد بررسی قرار خواهند گرفت.
4-2- اعتبارسنجی و ارائه مثال عددی
برای اعتبارسنجی مدل پیشنهادی چندین مثال در نرم افزار لینگو حل شده است و مقادیر بدست آمده با حل دستی مقایسه شده است که در ادامه به شرح یکی از این مثالها میپردازیم.
در مثال پیش رو 5 ماشین و 5 قطعه به همراه اطلاعات توالی عملیاتهای قطعهها و زمان فرآیندها را داریم و میخواهیم این ماشینها و قطعهها را به 3 سلول اختصاص دهیم به طوریکه در هر سلول استقرار حداکثر 2 ماشین مجاز است. ماشینها به موقعیت خاصی از سلول اختصاص مییابند. قطعهها نیز به سلولها اختصاص یافته و زمانبندی علمیاتها بر روی ماشینها تعیین میگردد. اطلاعات روابط ماشین و قطعه و زمان فرآیندها در جدول 4-1 ارائه شده است. در هر سلول حداقل یک ماشین و حداکثر دو ماشین میتواند قرار بگیرد. پارامترهای ورودی به شرح زیر هستند:
M = 5
Lm = 1
NC = 3
Ta = 1
P = 5
Um = 2
A = 108
Te = 2
dkk’ = [■(0&2&2@2&0&3@2&3&0)] dpp’ = [■(0&1@1&0)]
جدول 41. اطلاعات اولیه مثال
P5
P4
P3
P2
P1
Machine-Part
3
1
1
M1
2
2
M2
1
3
M3
1
2
2

مطلب مرتبط :   پایان نامه با کلید واژه هایمعنادار بودن، ارزش بازار، بازار سهام

Written by 

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