}
}
newChro.Fit();
return newChro;
}
عملگر جهش
در عملگر جهش پس از انتخاب یک کروموزوم، دو ژن بصورت تصادفی انتخاب شده سپس مکان این دو ژن با هم جابجا می شود در هنگام تعویض مکان دو ژن، پارامتر b هر دو ژن نیز معکوس می شوند به این صورت که اگر پارامتر نگداری ژن 1 بود 0 می شود و اگر 0 بود 1.
شکل ‏310: عملگر جهش دو نقطه ای
کد مربوط به عملگر جهش:
public Chromosome Mutation()
{
Chromosome temp = new Chromosome(this);
Random rnd1 = new Random(c++);
Random rnd2 = new Random(c++);
//*********************************************************************************start
int a = rnd1.Next(0, temp.Chro.Count); // will return number from 0 to temp.Chro.Count-1
int b = rnd2.Next(0, temp.Chro.Count);
if (((Gene)temp.chro[a]).Maintenance == 0)
((Gene)temp.chro[a]).Maintenance = 1;
((Gene)temp.chro[a]).Maintenance = 0;
if (((Gene)temp.chro[b]).Maintenance == 0)
((Gene)temp.chro[b]).Maintenance = 1;
((Gene)temp.chro[b]).Maintenance = 0;
Gene c1 = new Gene((Gene)temp.chro[a]);
Gene c2 = new Gene((Gene)temp.chro[b]);
//*********************************************************************************end
temp.chro[a] = c2;
temp.chro[b] = c1;
//*********************************************************************************start
temp.Fit();
return temp;
}
تعویض جمعیت
جهت انتخاب بهترین فرزند ها برای نسل بعد ابتدا جمعیت اولیه بر اساس شایستگی کروموزومها مرتب شده و سپس به تعداد مجموع عملگر تبادل105 و عملگر جهش کروموزومهایی که شایستگی برابری با هم دارند از جمعیت اولیه حذف میشوند.
شرط خاتمه
شرط خاتمه الگوریتم می تواند هر یک از شرط های در نظر گرفته شده در فصل قبلی باشد. در الگوریتم پیشنهادی، شرط خاتمه؛ تولید تعداد مشخصی نسل در نظر گرفته شده است.
فصل چهارم محاصبات و یافته های تحقیق
در این فصل نحوه پیاده سازی و نتایج حاصل از شبیه سازی الگوریتم پیشنهادی و مقایسه الگوریتم شرح داده شده است. با توجه به این نکته که تاکنون شرط نگهداری ماشین در مسئله سیستم باز در نظر گرفته نشده ما الگوریتم پیشنهادی خود را که حل مسئله سیستم باز با در نظر گرفتن نگهداری ماشین به صورت چند جمعیتی که به اختصار MMOSMGA106 می نامیم با حل مسئله سیستم باز با در نظر گرفتن نگهداری ماشین که به اختصار MMOSGA107 می نامیم مقایسه می کنیم.
پیاده سازی الگوریتمها
برای پیاده سازی این الگوریتم از زبان برنامه سازی C#.Net 2008 استفاده شده است. برنامه روی کامپیوتری با پردازنده دو هستهای با فرکانس 2.2 گیگاهرتز و رم 4 گیگابایت اجرا شده است. برای مقایسه الگوریتم ها از 4 داده تست استفاده شده است. محاسبات با پارامتر های زیر از الگوریتم ژنتیک انجام شده است.
طراحی داده های تست و پارامترهای الگوریتم
الگوریتم ‌پیشنهادی ‌MMOSMGA باالگوریتم MMOSGA مقایسه شده است در جدول 4-1 چهار نمونه داده تست برای مقایسه الگوریتم ‌پیشنهادی‌ باالگوریتم MMOSGA وجود دارد و جدول 4-2 نتایج حاصل از اجرای پارامترهای ورودی جدول 4-1 بر روی الگوریتم پیشنهادی می باشد.
جدول ‏41: پارامترهای ورودی الگوریتم پیشنهادی
نمونه
ماشین
کار
جمعیت اولیه
تعداد نسل
تست 1
4
4
150
500
تست 2
4
8
200
1000
تست 3
5
15
250
2000
تست 4
10
20
250
3000
جدول ‏42: : نتایج اجرای داده های تست جدول 4-1
نمونه
زمان پردازش MMOSMGA
بهترین شایستگی MMOSMGA
بدترین شایستگی MMOSMGA
زمان پردازش MMOSGA
بهترین شایستگی MMOSGA
بدترین شایستگی MMOSGA
تست 1
85 ثانیه
458
1816
80
458
1831
تست 2
434 ثانیه
1311
5300
412
1386
5354
تست 3
1560 ثانیه
2876
8446
1426
3308
9235
تست 4
7200 ثانیه
5008
14691
6355
6320
15268
نتایج حاصل از شبیه سازی
شکل 4-1 مقایسه نمودار بهترین شایستگی داده تست 1 را برای دو الگوریتم فوق نشان میدهد. همانطور که مشاهده می‌کنید الگوریتم MMOSMGA نسبت به الگوریتم MMOSGA ضمن رسیدن به جواب بهینه تر، و در جواب های مشابه بسیار سریع تر و در تعداد نسل های کمتری به این معیار رسیده است.
شکل ‏41: نمودار مقایسه بهترین شایستگی الگوریتم ها برای داده تست 1
شکل زیر مقایسه نمودار بهترین شایستگی داده تست 3 را برای دو الگوریتم فوق نشان میدهد. همانطور که می بینید در تمامی نسل ها الگوریتم پیشنهادی جواب های بهینه تری یافته و تا پایان نیز این نتایج بهتر را ادامه داده است.
شکل ‏42: : نمودار مقایسه بهترین شایستگی الگوریتم ها برای داده تست 3
شکل زیر مقایسه نمودار بهترین شایستگی داده تست 4 را برای دو الگوریتم فوق نشان میدهد. با توجه به اندازه مساله و مقایسه با داده های تست دیگر به این نتیجه می رسیم که درصد بهبود نتایج به شکل قابل ملاحظه ای در مسائل بزرگ تر بهبود می یابد.
شکل ‏43: : نمودار بهترین شایستگی الگوریتم ها برای داده تست 4
شکل 4-4 مقایسه نمودار پراکندگی جمعیت داده تست 3 را برای دو الگوریتم نشان می‌دهد.
شکل ‏44: : پراکندگی جمعیت اولیه برای داده تست 2
همانطور که در شکل 4-4 و 4-5 مشخص است پراکندگی جمعیت در الگوریتم پیشنهادی نسبت به الگوریتم MMOSGA بیشتر است که دلیل آن استفاده از استفاده از عملگرهای ژنتیک متنوع و مناسب است. به همین دلیل الگوریتم پیشنهادی به جواب های بهتری نیز دست می‌یابد.
شکل ‏45: پراکندگی جمعیت اولیه برای داده تست 4
فصل پنجم نتیجه گیری و پیشنهادات
همانطور که گفته شد مسئله زمانبندی سیستم باز از رده مسائل سخت است و روش های ابتکاری زیادی برای حل این مسئله توسعه یافته است. در میان این روش ها الگوریتم ژنتیک یکی از پر کاربردترین روش ها برای حل مساله زمانبندی سیستم باز است.
در این مساله به دو شکل می توان راه حل های قبلی را بهینه کرد:
بهینه تر کردن زمان دستیابی به جواب قابل قبول
بهینه تر کردن جواب های موجود
از طرف دیگر در این مساله نگهداری ماشین در نظر گرفته نمی شود که این امر قابلیت نگهداری سیستم را کاهش می دهد.
در این پایان نامه یک الگوریتم ژنتیک برای زمانبندی سیتم باز پیشنهاد شده که مساله نگهداری ماشین را نیز در نظر می گیرد. هدف، کاهش هزینه های تولید با استفاده از کمینه کردن طول زمانبندی در چنین سیستم هایی می باشد. در این الگوریتم از تکنیک چند جمعیتی استفاده شده است تا بتوان تمامی فضای حل مساله را پوشش داد و همزمان بتوان به عملگرها تنوع داده تا ماهیت جستجوی تصادفی الگوریتم ژنتیک حفظ گردد.
برای سنجش کارایی الگوریتم پیشنهادی، از الگوریتم MMOSGA استفاده شده است که این الگوریتم نیز جهت مقایسه به وجود آمده که مسئله نگهداری ماشین را نیز در نظر می گیرد الگوریتمها با استفاده از زبان برنامه نویسی C#.net 2008 پیاده سازی شدند و برای مقایسه تمامی ویژگیهای الگوریتم ها از 4 مجموعه داده به منظور تست الگوریتم ها استفاده شده است. این داده ها، سیستمهای باز با اندازه کوچک، متوسط و بزرگ را در بر می گیرد. نتایج تجربی نشان داد الگوریتم پیشنهادی نتایج بهتری را در هر سه دسته از سیستم های باز یعنی کوچک، متوسط و بزرگ می یابد. میزان این بهبود می تواند در سیستم های تولید بزرگ تر بارزتر باشد.
همان گونه که در شکل 4-4 و 4-5 فصل 4 مشاهده شد مجموعه جواب های الگوریتم پیشنهادی فضای بیشتری از مجموعه جواب را پوشش داده و این می تواند به یافتن جواب های بهینه کمک کند این عملکرد با استفاده از ویژگی چند جمعیتی در الگوریتم ژنتیک به انجام رسیده است که می توان آن را به عنوان پردازش همزمان چند الگوریتم ژنتیک با جمعیت‌های متفاوت و پاس کردن کروموزومهای شایسته تر به یکدیگر تشریح کرد.
برای تکمیل کارهای انجام شده در این پایان نامه می توان فعالیت پژوهشی متعددی انجام داد که می توان به موارد ذیل اشاره کرد:
الگوریتم ژنتیک تا حدود خیلی زیاد وابسته به پارامترهای خود است. میتوان تاثیر پارامترهای مختلف در کارایی الگوریتم پیشنهادی را سنجید.
استفاده از تکنیک جستجوی محلی: جستجوی محلی می تواند در بهبود جواب در الگوریتم های هوشمند مفید باشد از جمله تکنیک های جستجوی محلی میتوان جستجوی حرام، تپه نوردی و شبیه سازی ذوب فلزات را نام برد.
در نظر گرفتن یک زمان حداکثر برای تحویل کار به بازار.
در نظر گرفتن حداکثر هزینه تولید.
در نظر گرفتن مساله خرابی ماشین.
استفاده از مدل پتری نت به عنوان ابزاری برای مدل سازی، شبیه سازی و ارزیابی کارایی الگوریتم پیشنهادی.
فهرست منابع و مأخذ
[1] علیرضا مهدی / مقدمهای بر الگوریتم ژنتیک و کاربردهای آن / تهران: انتشارات ناقوس / 1386
[2] C. Low, Y .Yeh, Genetic algorithm-based heuristics for an open shop scheduling problem with setup, processing, and removal times separated, Robotics and Computer-Integrated Manufacturing, Vol. 25, pp. 314–322, 2009.
[3] M.L. Pinedo, Scheduling: Theory, Algorithms and systems, Fourth Edition, Springer,
2012.
[4] C.F. Liaw, A tabu search algorithm for the open shop scheduling problem, Computers & Operations Research, Vol. 26, pp. 109-126, 1999.
[5] Blum, C., Beam-ACO- hybridizing ant colony optimization with beam search: an application to open shop scheduling, Computers & Operations Research 32, pp. 1565-
1591, 2005.
[6] D.Y. Sha, C.Y. Hsu, A new particle swarm optimization for the open shop scheduling problem, Computers and Operational Research, Vol. 35, pp. 3243-3261, 2008.
[7] C.F. Liaw, An efficient tabu search approach for the two-machine preemptive open shop scheduling problem, Computers & Operations Research, Vol. 30, pp. 2081-2095, 2003.
[8] M.E. Matta, A genetic algorithm for the proportionate multiprocessor open shop, Computers & Operations Research 36, pp.2601-2618, 2009.
[9] S. Noori-Darvish, R. Tavakkoli-Moghaddam, Minimizing the total tardiness and makespan in an open shop scheduling problem with sequence-dependent setup times, Journal of Industrial Engineering International, 2012, http://www.jiei-tsb.com/content/811125.
[10] Y. Huang, J. Lin, A new bee colony optimization algorithm with idle-time-based filtering scheme for open shop-scheduling Problems, Expert Syst. 2011.
[12] A. Sedeno-Noda, D. Alcaide Lopez de Pablo, C. Gonzalez-Martin, A network flow based method to solve performance cost and makespan open-shop scheduling problems with time-windows, European Journal of

این مطلب رو هم توصیه می کنم بخونین:   منابع پایان نامه درموردسرعت پردازش
دسته‌ها: No category

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