منابع پایان نامه ارشد درمورد پژوهشگران، نقطه تقاطع

شماره 2 به مشتری 4 اختصاص داده میشود .
در مرحله بعد عدد تصادفی بزرگتر از بین اعداد تصادفی موجود انتخاب میشود.
عرضه
مشتری
توزیع کننده
200
0.69
0.55
0.34
0.2
50
0.97
0.32
0.02
0.24
500
0.09
0.42
0.76
0.65
120
120
100
تقاضا
با توجه به عدد تصادفی انتخاب شده مقدار 120 واحد از توزیع کننده شماره 3 به مشتری 2 انتقال پیدا میکند .
عرضه
مشتری
توزیع کننده
200
0.69
0.55
0.34
0.2
50
0.97
0.32
0.02
0.24
380
0.09
0.42
0.76
0.65
120
100
تقاضا
این فرایند تا پایان پوشش کامل تقاضای مشتری ادامه پیدا میکند در شکل زیر نحوه پوشش کامل تقاضای مشتری توسط توزیع کنندگان آورده شده است . بنابراین تقاضای مشتریان بدین صورت برآورده شد.
مقدار محصول مورد نیاز
عرضه
مشتری
توزیع کننده
120
80
0.69
0.55
0.34
0.2
200
50
0.97
0.32
0.02
0.24
022
180
0.09
0.42
0.76
0.65
تقاضا
عرضه
مشتری
توزیع کننده
200
120
250
200
500
120
100
200
120
120
100
تقاضا
بنابراین فقط بر اساس مقدار محصول مورد نیاز باید انتقال از تولیدکننگان به توزیع کنندگان انتقال پیدا کند. در شکل زیر ماتریس انتقال تولیدکنندگان به توزیع کنندگان آورده شده است.
عرضه
توزیع کننده
تولیدکننده
550
0.58
0.46
0.33
700
0.84
0.79
0.67
220
200
120
تقاضا
دوباره بر اساس اعدادتصادفی تولید شده اقدام به تخصیص محصول نهایی به مراکز توزیع میکنیم . در شکل زیر جدول نهایی آورده شده است .
عرضه
توزیع کننده
تولیدکننده
550
0.58
0.46
0.33
60
0.84
0.79
0.67
تقاضا
عرضه
توزیع کننده
تولیدکننده
550
60
220
200
120
تقاضا
بنابراین مقدار انتقال از تولیدکنندگان به توزیع کنندگان نیز مشخص شد. در پایان نحوه نمایش کروموزوم مساله تکمیل شده، در شکل های زیر قابل مشاهده است .
1
1
1
1
در ادامه گام های الگوریتم را مورد بررسی قرار میدهیم .شکل زیر برگرفته از تحقیق تیانری وانگ و همکاران[133] گام های الگوریتم ژنتیک مرتب سازی نامغلوب را که برای حل مدل از آن استفاده شده است را نشان میدهد. در ادامه برای تشریح الگوریتم، قدم های الگوریتم مورد بررسی میگیرد.
3-6-3-3. مقدار دهی اولیه86 :
در این بخش اطلاعات اولیه که برای شروع الگوریتم نیاز میباشد شامل :
3-6-3-4. اندازه جمعیت اولیه87 :
تعدادی از کروموزومها با هم یک جمعیت را تشکیل میدهند. اندازه جمعیت اولیه همان تعداد کروموزومها میباشد که در هر مرحله باید نگهداری شوند. در یک جمعیت، همه ی کروموزومها اندازه ی یکسان دارند و بصورت اندازه جمعیت نشان داده میشود . اگر اندازه جمعیت کوچک باشد . همگرایی الگوریتم سریعتر خواهد بود اما همگرایی زودرس ممکن است منجر به افتادن در دام یک بهینه ی محلی شود. الگوریتم NAGA-II با یک سری جوابها به عنوان جواب اولیه شروع به کار میکند. جمعیت اولیه شامل یکسری جوابهای مسأله است که به طور ابتکاری یا تصادفی تولید شده اند.
3-6-3-5. تولید نسل88 :
تولید مثل معمولاً اولین عملی است که بر روی جمعیت اعمال میشود. در این روش یک سری کروموزوم از میان جمعیت انتخاب شده که در نهایت با عمل ادغام منجر به تولید فرزندان89 میشوند. اندازهی تولید نسل بر اساس روش سعی و خطا و پیشنهاد پژوهشگران مقدارهای 50 ، 75 و 150 پیشنهاد شده است که با تنظیم پارامتر میتوان مقدار مناسب را تعیین نمود. در این مساله به تعداد نسل اولیه جواب تصادفی تولید میشود و از استراتژی ردی جهت رد جواب های تصادفی تولید شده ی نشدنی وتولید جواب دیگر استفاده میشود . بدین معنی که تولید جواب های تصادفی تا جایی ادامه پیدا میکند تا به تعداد نسل اولیه مورد نیاز جواب تصادفی شدنی تولید شود . سپس از روش لبه بندی (مرتب سازی) نامغلوب سریع استفاده کرده و جواب ها را لبه بندی میکنیم.
3-6-3-6. روش مرتب سازی سریع نامغلوب90
مرتب کردن جمعیت بر اساس نامغلوبها با استفاده از مفهوم غلبه و مغلوب صورت میگیرد . به طور کلی برای مرتب کردن جمعیتی با اندازه N بر اساس سطوح نامغلوبها، هرجواب با تمام جوابهای دیگر موجود در جمعیت مقایسه میشود تا مشخص شود که آن جواب مغلوب میشود یا خیر. در نهایت یک تعداد حل وجود دارد که هیچ کدام غالب و مغلوب همدیگر نمیشوند لذا این جوابها، اولین مرز لبه91 از مرزهای نامغلوب را تشکیل می دهند . برای تعیین جوابهای موجود درلبه های بعدی، جوابهای موجود در لبه اول به طور موقت نادیده گرفته میشود و فرآیند فوق دوباره تکرار میشود. این فرآیند تا زمانی که تمام جواب ها درون مرزهای نامغلوب قرار گیرند ادامه مییابد. در شکل زیر به صورت شماتیک این روش نشان داده شده است .
3-6-3-7. فاصله ازدحام92:
یکی از معیارهایی که یک الگوریتم تکاملی در راه رسیدن به مرز بهینه پارتو همواره مدنظر قرار میدهد حفظ و گستردگی جوابها در مجموعه جوابهای بدست آمده میباشد. در واقع مرتب کردن غیرمغلوبها رویهای است در جهت رسیدن به جوابهای بهتر و مکانیزم تنوع هم درصدد تنوع گستردگی در این جوابها میباشد که در این الگوریتم این کار توسط فاصله ازدحام به این صورت انجام میشود.
برای تخمین تراکم اطراف یک جواب خاص در جمعیت، متوسط فاصله این جواب از هر دو جواب مجاور در دو سمت این جواب را براساس مقادیر اهداف محاسبه میکنیم. این مقدار را فاصله ازدحام مینامیم. برای محاسبه فاصله ازدحامی یک جواب خاص موجود دریک مرز، بزرگترین مستطیلی که آن جواب خاص درون مستطیل و دو جواب مجاور در دو سمت جواب، رأسهای مستطیل باشند را در نظر میگیریم و مجموع یک طول و یک عرض آن را به عنوان فاصله ازدحامی برای آن جواب خاص محاسبه میکنیم. الگوریتم زیر نحوه محاسبات مربوط به فاصله ازدحامی i_distance برای عضو دلخواه i م از یک مرزهای غیرمغلوب را نشان میدهد. برای محاسبه فاصله ازدحامی، ابتدا باید افراد جمعیت بر اساس مقدار هر تابع هدف به صورت صعودی مرتب شوند. سپس جوابهای موجود در ابتدا و انتهای هر مرز )جوابهای با بیشترین و کمترین مقدار تابع هدف( مقدار فاصله ازدحامی بینهایت به خود میگیرند .در زیر رویه محاسبه فاصله ازدحامی برای تمام جوابهای موجود در مرز نامغلوب f آورده شده است.
در این الگوریتم?n[j]?_distance مقدار تابع هدف m ام برایi امین عضو مجموعه nمیباشد. یک جواب با مقدار کمتری فاصله ازدحامی بیانکننده تراکم بیشتر جواب در اطراف آن جواب است. بنابراین مطلوب است برای مرحله بعد جوابهایی انتخاب شوند که در ناحیه با تراکم کمتر یا به عبارتی دارای فاصله ازدحامی بیشتر هستند چرا که با این کار تنوع و پراکندگی در جواب- های بدست آمده بیشتر میشود [65].
3-6-3-8. ارزیابی کروموزوم93 :
در این مرحله باید کروموزوم های تولید شده ارزیابی شوند . برای این منظور تابع برازندگی94 تعریف میشود . تابع برازندگی در این مساله همان مقادیر تابع هدف تعریف شده است.بدین معنی که برای ارزیابی کروموزوم ها مقادیر تابع هدف اول و دوم آنها مورد مقایسه قرار میگیرد .
3-6-3-9. استراتژی انتخاب95 :
در این مساله برای استراتژی انتخاب از روش تورنومنت استفاده شده است . روش کار بدین صورت است که دو کروموزم به صورت تصادفی انتخاب شده ، کروموزوم با رتبه لبه کوچکتر از بین این دو انتخاب میشود و در صورت برابر بودن رتبه لبه، فاصله ازدحام کروموزوم ها بررسی میشود . این عمل دو بار تکرار میشود تا دو کروموزوم والدین برای عملگر تقاطع مهیا شود .
3-6-3-10. عملگر تقاطع96 :
اندازهی احتمال عملگر تقاطع بر اساس روش سعی و خطا و پیشنهاد پژوهشگران مقدارهای 0.8 ، 0.85 و 0.9 پیشنهاد شده است که با تنظیم پارامتر میتوان مقدار مناسب را تعیین نمود.عملگر تقاطع بر روی دو کروموزوم والد حاصل از عملگر انتخاب، با احتمال عمل میکند و با ترکیب دو والد فرزند جدیدی را به وجود میآورد.
تعداد کل جمعیت * نرخ تقاطع= تعداد اعمال تقاطع
عملگر تقاطع در این مساله بصورت زیر انجام میشود.
پس از استفاده از روش تورنومنت و انتخاب والدین جهت اعمال عملگر تقاطع به صورت زیر عمل میکنیم.
با احتمال 2/1 تولید کننده یا توزیع کننده انتخاب میشود .
یک نقطه از کروموزم به تصادف انتخاب میشود .
دو قسمت ایجاد شده توسط نقطه مشخص شده در کروموزوم با هم جابجا میشوند .
در شکل زیر این گام ها نمایش داده شده است.
فرض کنید تولید کننده انتخاب شد. نقطه تقاطع
1
1
1
1
1
1
1
1
دوباره همان نقطه روی ماتریس انتقال اعمال میشود.
توزیع کننده
تولید کننده
150
500
100
200
توزیع کننده
تولید کننده
150
500
440
توزیع کننده
تولید کننده
50
100
440
0
پس از اجرای عملیات بالا ابتدا شدنی بودن فرزند تولید شده بررسی میشود . در صورت شدنی بودن ، فرزند مورد نظر را با تمام جواب های موجود در لبه آخر نسل قبل مقایسه می کنیم، در صورت بهتر بودن ، فرزند تولید شده به نسل بعد انتقال می یابد .
3-6-3-11. عملگر جهش97 :
اندازهی احتمال عملگر تقاطع بر اساس روش سعی و خطا و پیشنهاد پژوهشگران مقدارهای 0.25 ، 0.3 و 0.35 پیشنهاد شده است که با تنظیم پارامتر میتوان مقدار مناسب را تعیین نمود. برای اعمال جهش بطور تصادفی دو تا از ژن های بخش دوم کروموزوم انتخاب و ارزش آنها جا به جا میگردد. تعداد کروموزوم هایی که عملگر جهش بر روی آنها اعمل میگردد با توجه به رابطه زیر بدست می آید .
تعداد کل جمعیت * نرخ جهش = تعداد اعمال جهش
در این مساله عملگر جهش بصورت زیر انجام میشود.
انتخاب کروموزوم ها برای عملگر جهش به صورت تصادفی انجام میشود سپس با احتمال 2/1 تولید کننده یا توزیع کننده انتخاب شده و عملیات زیر را انجام میدهیم .
دو نقطه به صورت تصادفی روی کروموزوم انتخاب میکنیم .
این دو نقطه روی کروموزوم ها را با یکدیگر جابجا میکنیم .
فرض کنید یک کروموزوم از تولید کننده انتخاب شد
1
1
1
1
همان نقاط روی ماتریس انتقال اعمال میشود .
توزیع کننده
تولید کننده
150
500
100
200
توزیع کننده
تولید کننده
100
200
150
500
پس از اجرای عملیات جهش دوباره مثل مرحله تقاطع ابتدا شدنی بودن فرزند تولید شده بررسی میشود . در صورت شدنی بودن ، فرزند مورد نظر را با تمام جواب های موجود در لبه آخر نسل قبل مقایسه می کنیم، در صورت بهتر بودن ، فرزند تولید شده به نسل بعد انتقال می یابد .
3-6-3-12.نخبه گرایی :
روش کار بدین صورت است که درصدی (مثلا 8 درصد) از بهترین جواب ها به نسل بعد منتقل میشوند .
3-6-3-13.پیدا کردن همسایگی جواب ها با استفاده از الگوریتم شبیه سازی تبرید
3-6-3-311-. الگوریتم شبیه سازی تبرید98 (SA)
الگوریتم شبیه سازی تبرید یک الگوریتم جستجوی تصادفی بر مبنای مدل مونت کارلو است که به طور گسترده در عرصه های گوناگون مسایل

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