پایان نامه با واژگان کلیدی حقوق و دستمزد

دانلود پایان نامه ارشد

کروموزوم از ميان والدين مستقيماً به نسل بعدي منتقل ميگردد. براي عملگر جابجائي ابتدا يک استخر توليد ميشود و والدين از درون استخر انتخاب ميشوند و نهايتاً والدين براي عملگر جهش انتخاب ميگردند.
براي انجام جابجايي بهتر است که بهترين و اميدبخش ترين والدين انتخاب گردند چراکه والدين بهتر به طور متوسط فرزندان خوبي هم دارند. بنابراين يک نرمال سازي بر روي استخر توليد شده صورت ميپذيرد. براي هر نسل ميانگين و انحراف معيار تابع هدف محاسبه ميگردد. سپس کروموزومي که داراي ميانگين بهتري نسبت به ميانگين آن نسل باشد براي انجام جابجايي و يا جهش به استخر منتقل ميگردد. به اين ترتيب تضمين ميشود که بهترين کروموزوم ها نسلهاي بعدي را خواهند ساخت.
4-6-2-5- عملگرهاي بهبود يافته الگوريتم ژنتيک
همانطور که در بخش ساختار کروموزوم اشاره شد، اين ساختار از ماتريسهاي دو بعدي و سه بعدي تشکيل يافته است. بنابراين عملگرهاي کلاسيک الگوريتم ژنتيک قابل پياده سازي بر روي اين کروموزوم ها نيستند. بدين منظور عملگرهاي کلاسيک الگوريتم ژنتيک را براي اعمال بر روي ماتريسهاي سه بعدي بهبود ميدهيم.
عملگرهاي بهبود يافته به سه دسته ستوني، بلوکي و نامنظم تقسيم ميشوند و در ادامه به توضيح آن ها پرداخته خواهد شد:

* عملگر ستوني255
اين نوع عملگر به صورت ستوني عمل مينمايد. بدين ترتيب که ابتدا دو عدد تصادفي در محدوده سطر و ستون کروموزوم مربوطه توليد ميگردد. سپس عملگر (جهش يا جابجايي) در قسمت انتخاب شده اعمال ميگردد. براي مثال در شکل 4-16 ستون قرمز و سبز از دو کروموزوم A و B به صورت تصادفي انتخاب شده و عملگر جهش بر روي آن ها اعمال شده است.

شکل ‏4-16- عملگر جابجائي ستوني
* عملگر بلوکي256
اين نوع عملگر بصورت بلوکي عمل مينمايد. به اين ترتيب که ابتدا چند عدد تصادفي در محدوده ستون و سطر کروموزومهاي مربوطه توليد ميشود. سپس عملگر مورد نظر (جهش يا جابجائي) بر بلوک تشکيل شده توسط اين اعداد تصادفي، اعمال ميشود. براي مثال در شکل 4-17 ابتدا بلوکهاي قرمز و سبز از دو کروموزوم بصورت تصادفي انتخاب شده و عملگر جابجائي بر روي آن اعمال ميشود.

شکل ‏4-17- عملگر جابجائي بلوکي
* عملگر نامنظم257
اين نوع عملگر بصورت نامنظم اعمال ميشود. به اين ترتيب که چند درايه از کروموزوم به صورت تصادفي انتخاب ميشود و عملگر مربوطه (جابجايي يا جهش) بر روي آن اعمال ميگردد (شکل 4-18).

شکل ‏4-18- عملگر جابجائي نامنظم
4-6-2-6- اپراتورهاي تعديل258
دو نوع تعديل در اين الگوريتم بکار گرفته شده است که يکي روي قسمت A و ديگري روي قسمت B از کروموزوم اعمال ميشود:
اپراتور تعديل کننده قسمت A
با اعمال هر يک از عملگرها بر روي قسمت A، ترکيب بندي توليد و الگوي نيروي کار تغيير مينمايد که گاهي منجر به متجاوز شدن تعداد محصول توليد شده از ميزان منابع در دسترس ميشود که غيرموجه شدن کروموزوم را سبب ميشود. بنابراين در اين حالت يک اپراتور تعديلي مورد نياز است تا اين جواب نشدني را به يک جواب شدني تبديل نمايد. در اين قسمت يک اپراتور تعديلي طوري طراحي شده است که بصورت تصادفي جواب را تغيير ميدهد تا کروموزوم شدني حاصل شود. نکته مهم اين است که با قرار دادن يک شمارشگر، ميتوان تنظيم نمود چنانچه با تکرار متوالي اين عملگر بعد از تعداد معين، همچنان کروموزوم نشدني باقي مانده باشد، کروموزوم را حذف نموده و مجدداً بر اساس استراتژي توليد جواب شدني، اقدام به توليد کروموزوم جايگزين نمايد.
اپراتور تعديل کننده قسمت B
با اعمال اپراتورهاي مختلف روي قسمت B، برخي محدوديتهاي مربوط به مشتريان تحت سناريوهاي مختلف ممکن است دچار تناقض گردد. بنابراين يک اپراتور تعديل کننده در اين قسمت تعبيه شده است که با تغيير تصادفي برخي درايههاي اين کروموزوم سعي در شدني بودن آن نمايد، ضمن اينکه جابجايي سناريوها نيز به عنوان يک استراتژي تعديل مورد استفاده قرار ميگيرد. به اين ترتيب که يک کروموزوم تحت يک سناريو ممکن است نشدني باشد اما تحت سناريوي ديگري شدني شود به همين دليل جابجايي سناريوها نيز آزمون ميشود. اگر چنانچه با تکرار متوالي اين اپراتور تعديل کننده، کروموزوم مورد نظر همچنان نشدني باقي بماند. با استفاده از استراتژي توليد جواب شدني اوليه، بر اساس کروموزوم قسمت A مربوطه، نيازمندي ها و محدوديت ها تحت سناريوهاي مختلف محاسبه شده و يک کروموزوم شدني جايگزين کروموزم نشدني موجود ميشود.
4-6-3- قدم هاي الگوريتم ژنتيک پيشنهادي
1. پارامترهاي کنترلي U (تعداد کروموزومهاي هر نسل)، G (تعداد نسل ها)، ? (درصد عملگر جابجائي) و ? (درصد شايسته سالاري) را مقدار دهي نمائيد.
2. جمعيت اوليه را توليد کن.
3. شمارندههاي u= 1 (شمارنده جمعيت) و g = 1 (شمارنده نسل) را مقدار دهي اوليه کن.
4. تعداد کروموزومهايي که بايستي مستقيماً به نسل بعد منتقل شوند را از طريق فرمول زير محاسبه کن.
Nelitism = (U-1) ×?+1
5. تعداد دفعاتي که هر عملگر (جابجائي و جهش) بايستي بکار رود را از طريق فرمول زير محاسبه کن.
Ncrossover = (U- Nelitism) × ? + 1, Nmutation = U – Nelitism – Ncrossover
6. مقدار تابع برازندگي جمعيت جاري را تحت عنوان F(X1g), F(X1g), …, F(XUg)محاسبه کن.
7. مقدار برازندگي جمعيت را تحت عنوان Z1, Z1, …, ZU نرمال سازي کن که در آن ( ?g مقدار ميانگين برازندگي و ?g مقدار انحراف معيار برازندگي جمعيت ميباشد).
8. به تعداد Nelitism بهترين کروموزومهاي نسل قبل را مستقيماً به نسل جاري منتقل کن و قرار بده u = Nelitism – 1.
9. استخر ترکيب را انتخاب کن (جواب هايي از Xi که در آن Zi ? 0)
10. دو کروموزوم را به صورت تصادفي از استخر ترکيب انتخاب کن.
11. يکي از عملگرهاي سه گانه تعريف شده (ستوني، بلوکي و نامنظم) را بصورت تصادفي بر قسمتهاي مرتبط از کروموزومهاي انتخاب شده اعمال کن.
12. کروموزومهاي فرزند را تا رسيدن به يک کرموزوم شدني تعديل کن.
13. اگر مجموع مقادير تابع برازندگي فرزندان از مجموع مقادير تابع برازندگي والدين کمتر شد، هر دو را به نسل بعدي منتقل کن و قرار بده u = u + 2، در غير اينصورت اگر تابع برازندگي يکي از فرزندان کمتر از والدين باشد تنها همين کروموزوم را به نسل بعد منتقل کن و قرار بده u = u + 1.
14. اگر u Ncrossover + Nelitism برو به قدم 10.
15. يکي از کروموزومهاي نسل قبل را به صورت تصادفي انتخاب کن.
16. يکي از عملگرهاي جهش تعريف شده (ستوني، بلوکي و نامنظم) را بصورت تصادفي بر قسمتهاي مربوطه از کروموزوم انتخابي اعمال کن.
17. کروموزوم فرزند را تا رسيدن به جواب شدني تعديل کن.
18. کروموزوم فرزند شدني را مستقيماً به نسل بعدي منتقل کن.
19. اگر u U قرار بده u = u + 1 و برو به قدم 15.
20. اگر g G يا معيار توقف برقرار نشد قرار بده g = g + 1 و برو به قدم 6.
21. الگوريتم را متوقف کن و بهترين جواب بدست آمده را گزارش کن.
4-6-3-1- معيار توقف الگوريتم
تعداد نسل ها؛ در اين حالت، چنانچه تعداد نسل ها از يک عدد از پيش تعريف شده بيشتر گردد الگوريتم متوقف ميشود و بهترين جواب بدست آمده تا آن لحظه را گزارش ميدهد.
بازه زماني؛ در اين حالت، چنانچه زمان حل از يک مقدار تعيين شده براي آن بيشتر شود الگوريتم متوقف شده و بهترين جواب بدست آمده تا آن لحظه را گزارش ميدهد.
بهبود تابع برازندگي؛ در اين حالت، چنانچه بهبود در ميزان تابع برازندگي در چند دوره مشخص متوالي از يک درصد از پيش تعيين شده اي کمتر باشد، الگوريتم متوقف ميشود و بهترين جواب بدست آمده تا آن لحظه را گزارش ميدهد.
الگوريتم ژنتيک پيشنهادي در حلقه داخلي الگوريتم اپسيلون-محدوديت تعبيه شده است و در توليد جدول عايدات و نيز توليد جوابهاي پارتويي مسئله برنامهريزي تک هدفه تصادفي به کار ميرود. فلوچارت کلي الگوريتم پيشنهادي به صورت شکل 4-19 است.

شکل ‏4-19- فلوچارت روش حل پيشنهادي مدل سوم
4-7- مثال هاي عددي براي مدل 3
به منظور اعتبارسنجي و سنجش کاربردپذيري مدل پيشنهادي و همين طور کارايي الگوريتم پيشنهادي سه کلاس مختلف از مثالهاي عددي با ابعاد کوچک، متوسط و بزرگ ارائه ميشود. در بخش اول از نتايج محاسباتي، مسائل با ابعاد کوچک و متوسط با الگوريتم پيشنهادي حل گرديده است و نتايج حل با جواب بهينه بدست آمده با الگوريتم AUGMECON در نرم افزار GAMS مقايسه شده است. در بخش دوم جواب بدست آمده براي مسائل با ابعاد بزرگ با گزارش حد پائين جواب بدست آمده از نرم افزار بعد از گذشت يک ساعت و نيم مقايسه شده است. در نهايت منحني پارتوي بدست آمده و تضاد بين اهداف مختلف مورد بررسي قرار ميگيرد.
در اين بخش، ده مثال با ابعاد کوچک بصورت تصادفي طراحي شده و هر يک دو مرتبه حل شده است. يک مرتبه با استفاده از الگوريتم AUGMECON و يک مرتبه به کمک الگوريتم پيشنهادي، نتايج نشان ميدهد، مجموعه جواب پارتويي براي هر دو روش تقريباً يکسان است و زمان حل نيز تقريباً در همه موارد کمتر از پانزده دقيقه زمان ميبرد.
در مثالهاي طراحي شده با ابعاد متوسط که تعداد آن ها نيز ده تاست الگوريتم پيشنهادي بعد از يک ساعت و نيم مجموعه جواب پارتويي را تشکيل ميدهد در صورتيکه براي الگوريتم AUGMECON چندين ساعت به طول ميانجامد. در نهايت پنج مثال با ابعاد بزرگ به صورت تصادفي توليد شد و نتايج نشان ميدهد الگوريتم AUGMECON نمي تواند در زمان منطقي جوابي را گزارش دهد، اين درحاليست که الگوريتم پيشنهادي قادر به حل مسئله در مدت زمان قابل قبول است. بنابراين در اين مسائل جوابهاي بدست آمده از الگوريتم پيشنهادي با حد پائين بدست آمده از AUGMECON بعد از گذشت يک ساعت و نيم، مقايسه شده است. تعداد سناريوها در مسائل با ابعاد کوچک و متوسط برابر 10 و 50 در نظر گرفته شده است. از آنجا که ابعاد مسئله با افزايش تعداد سناريوها بصورت نمائي افزايش مييابد، آزمايش مسائل با ابعاد بزرگ را با تعداد سناريوهاي 50، 100، 500 و 1000 تکرار نموده ايم تا کارايي الگوريتم پيشنهادي را در برابر افزايش تعداد سناريوها بسنجيم.
4-7-1- تشريح مثال
يک زنجيره تأمين سه سطحي مفروض است و قرار است يک برنامهريزي توليد کلي در اين زنجيره تأمين صورت پذيرد. تعداد دورههاي افق برنامهريزي برابر 12 ماه فرض شده است. تعداد سطوح کاري، محصولات نهائي و مواد اوليه به ترتيب برابر 5، 5 و 10 در نظر گرفته شده است. اين شرکت داراي j کارخانه و c نقطه مشتري است که در نقاط مختلف واقع شده اند. مواد اوليه از S تأمين کننده که نزديک کارخانه ها واقع شده، تأمين ميگردد. تابع هدف اول را که هزينه کل سيستم توليد و زنجيره تأمين است به عنوان تابع هدف اصلي مسئله در نظر گرفته و دو تابع هدف ديگر (رضايتمندي مشتريان، بهرهوري کارکنان) را به ترتيب به 3 و 9 قسمت مساوي تقسيم نموديم. همچنين فرض شده که تقاضا از توزيع نرمال با ميانگين و انحراف معيار به ترتيب 1000 و 100 پيروي مينمايد (N (?:1000, ?:100)) و ?2, ?1 را نيز برابر 1 تنظيم نموديم. توابع توزيع پارامترهاي هزينه اي و پارامترهاي مربوطه در جدول 4-21 آمده است.
جدول ‏‏4-21- توابع توزيع پارامترهاي هزينه اي
آيتم هزينه اي
توزيع احتمال
هزينه نگهداري محصول نهائي ($/unit period)
Uniform (3, 10)
هزينه نگهداري مواد اوليه ($/ unit period)
Uniform (1, 15)
هزينه استخدام (10$/manpower)
Normal (?:6, ?2:3)
هزينه اخراج (10$/manpower)
Normal (?:50, ?2:3)
حقوق و دستمزد (10$/manpower)
Uniform (20, 30)
هزينه آموزش (10$/manpower)
Normal (?:20, ?2:5)
هزينه توليد ($/min)
Uniform (0.5, 1.5)
هزينه حمل و نقل ($/unit)
Uniform (0.015, 0.25)
هزينه خريد مواد اوليه ($)
Uniform (1, 2.5)
هزينه کمبود ($/period. unit)
Normal (?:2.5, ?2:1.5)
4-7-2- نتايج محاسباتي مثال هاي عددي با ابعاد کوچک و متوسط
به منظور ارزيابي کارائي الگوريتم پيشنهادي در اين قسمت 10 مسئله با ابعاد کوچک و متوسط طراحي شده است و مجموعه جواب پارتوي بدست آمده با خروجي الگوريتم AUGMECON از

پایان نامه
Previous Entries پایان نامه با واژگان کلیدی توسعه مدل Next Entries منابع پایان نامه ارشد با موضوع قانون کار، سابقه خدمت