تحقیق با موضوع میشود.، تولید، میانی

نقلیه خروجی به ترتیب به خرده فروشهای 2 و 1 تحویل داده میشوند. محصول 1 توسط دومین وسیله نقلیه خروجی موجود در این بارانداز میانی به خرده فروش 1 تحویل داده میشود. به طور مشابه، در بارانداز میانی دوم، محصولات 4-6 در یک گروه قرار داده شده و توسط دومین وسیله نقلیه موجود در این بارانداز میانی به خرده فروشها تحویل داده میشوند.
بر اساس بخشهای یک تا چهار، اولین وسیله نقلیه ورودی موجود در مکان تأمینکننده 1 پس از تحویل دادن محصول 2 به بارانداز میانی اول، محصول 5 را به بارانداز میانی دوم تحویل داده و به مکان این تأمینکننده بر میگردد. همچنین، اولین وسیله نقلیه ورودی موجود در مکان تأمینکننده دوم پس از تحویل محصول 1 به بارانداز میانی اول به مکان این تأمینکننده بر میگردد. علاوه بر این، دومین وسیله نقلیه موجود در مکان تأمینکننده دوم ابتدا محصول 3 را به بارانداز میانی اول سپس، محصولات 4 و 6 را به بارانداز میانی دوم تحویل داده و به مکان این تأمینکننده بر میگردد.
مطابق بخشهای دو و چهار، اولین وسیله نقلیه خروجی مربوط به بارانداز میانی اول به ترتیب پس از ملاقات خرده فروشهای 2 و 1 به بارانداز میانی اول بر میگردد. دومین وسیله نقلیه خروجی این بارانداز میانی پس از ملاقات خرده فروش 1 به این بارانداز میانی بر میگردد. همچنین، دومین وسیله نقلیه موجود در بارانداز میانی دوم به ترتیب پس از ملاقات خرده فروشهای 2 و 3 به بارانداز میانی دوم بر میگردد.
علاوه بر این مطابق بخش 5، اولین وسیله نقلیه ورودی موجود در مکان تأمینکننده 1 پس از گذشت 50 دقیقه از مبدا زمان شروع به حرکت میکند. همچنین، زمان شروع حرکت اولین و دومین وسیله نقلیه موجود در مکان تأمینکننده دوم به ترتیب پس از گذشت 80 و 250 دقیقه از مبدا زمان است.
از آنجایی که در نسل اول وجود جمعیتی از کروموزومها ضروری میباشد، یک جمعیت از کروموزومها به طور تصادفی تولید و به عنوان جمعیت اول در نظر گرفته میشوند. اما، با توجه به ساختار مورد استفاده در الگوریتم ارائه شده، تضمینی در مورد موجه69 بودن کلیه جوابهای تولید شده در ارتباط با محدودیتهای (3-62) تا (3-64)، (3-72) و (3-75) وجود ندارد. از این رو،
کروموزومهای تولید شده در جمعیت اول و همچنین فرزندان تولید شده به وسیله عملگرهای ژنتیک ممکن است غیر موجه (نشدنی) باشند. از طرف دیگر به دلیل وجود محدودیتهای زیاد در مسأله مورد بررسی، مجاز دانستن کروموزومهای غیرموجه در جمعیت ممکن است باعث دستیابی به
جوابهای با کیفیت بالا از طریق جستجو در فضای نشدنی شود. بنابراین وجود کروموزومهای غیرموجه در جمیعت مجاز بوده و به منظور جبران نقض محدودیتهای فوق از یک سری توابع جریمه استفاده میشود.
3-8-2- ارزیابی میزان برازندگی کروموزومها
با توجه به تطابق فرآیند جستجو توسط الگوریتم ژنتیک با فرآیند تکامل طبیعی و از آنجایی که در فرآیند تکامل طبیعی اشخاص (کروموزومهای) برتر دارای شانس بیشتری برای بقا در نسلهای بعدی هستند در الگوریتم ژنتیک نیز کروموزومهای برتر شانس بیشتری برای بقا دارند. از این رو در الگوریتم ژنتیک برای محاسبه میزان برازندگی (شایستگی) کروموزومها از یک تابع برازندگی (معمولا تابع هدف مسأله) استفاده میشود. در الگوریتم توسعه داده شده در این تحقیق به دلیل مجاز بودن کوروموزمهای غیرموجه در جمعیت، تابع برازندگی علاوه بر تابع هدف مسأله (معادله (3-47)) توابع دیگری را به منظور محاسبه میزان درجه غیرموجه بودن کوروموزومها شامل میشود. بنابراین برای یک کوروموزوم ch تابع برازندگی (تابع هزینه تعمیمیافته) بر طبق معادله (3-77) محاسبه میشود.
(3-77)
در معادله (3-77) Z(ch) نشاندهنده مقدار تابع هدف برای کوروموزوم ch و B1(ch) تا B4(ch) و B5(ch) به ترتیب بیانگر عبارات جریمه برای محدودیتهای ظرفیت و پنجره زمانی هستند. همچنین از αj ها که معرف ضرایب جریمه هستند به عنوان ابزاری موثر به منظور شاخصتر کردن اثر جریمهها در تابع برازندگی استفاده میشود.
عبارت جریمه مربوط به نقض محدودیتهای ظرفیت وسایل نقلیه ورودی (3-62) به صورت زیر محاسبه میشود:
(3-78)
و برای نقض محدودیتهای (3-63) مربوط به ظرفیت وسایل نقلیه خروجی بر طبق معادله
(3-79)
(3-79)
و برای نقض محدودیتهای (3-64) مربوط به ظرفیت تأمینکنندگان به منظور عرضه محصولات مختلف بر طبق معادله (3-80)
(3-80)
و برای نقض محدودیتهای (3-72) مربوط به ظرفیت محوطه نگهداری باراندازهای میانی بر طبق معادله
(3-81)
محاسبه میشوند. در معادله (3-81)، τ فقط شامل زمانهای ورود محصولات به باراندازهای میانی میشود. بنابراین در صورت نقض ظرفیت محوطه نگهداری یک بارانداز میانی، میزان جریمه مستقل از طول زمانی است که ظرفیت بارانداز میانی نقض میشود و فقط به تعداد دفعات نقض ظرفیت بستگی دارد. در نهایت میزان جریمه مربوط به نقض محدودیتهای پنجره زمانی (3-75) (اتمام عملیات استراتژی فرابارانداز در طول افق برنامهریزی) مطابق با معادله (3-82) محاسبه میشود.
(3-82)
3-8-3- عملگر انتخاب
مطابق با فرآیند تکامل طبیعی، در الگوریتم ژنتیک نیز در هر نسل مجموعهای از کروموزومها به منظور تولید فرزندان انتخاب میشوند. در الگوریتم ژنتیک از عملگر انتخاب به منظور انتخاب والدین استفاده میشود. مهمترین نقش عملگر انتخاب را میتوان در ایجاد تفاوت بین کوروموزومهای موجود در هر نسل بیان کرد به گونهای که کروموزومهای با کیفیت بالاتر (شایستهتر) شانس بیشتری به منظور تولید فرزندان داشته باشند. این کار باعث انتقال خصوصیات خوب موجود در والدین و تکامل این خصوصیات میشود. با این وجود به منظور ایجاد تنوع در جمعیت و جستجوی مناطق بیشتری از فضای جواب، عملگر انتخاب باید به نحوی طراحی شود که کروموزومهای با کیفیت پایین (از لحاظ برازندگی) نیز دارای شانس انتخاب باشند.
با توجه به توضیحات فوق، در این تحقیق از روش انتخاب چرخ رولت70 به عنوان یک روش متناسب با برازندگی کروموزومها (کروموزومهای برازندهتر شانس بیشتری برای انتخاب دارند) به منظور انتخاب والدین استفاده میشود. بنابراین با استفاده از روش چرخ رولت و برابر با اندازه جمعیت71، والد انتخاب شده (تعداد فرزندان تولید شده برابر با اندازه جمعیت هستند) و سپس با استفاده از عملگرهای همگذری و جهش فرزندان تولید میشوند. ساختار کلی مکانیزم چرخ رولت به صورت زیر میباشد:
گام1) کم کردن مقدار تابع برازندگی (تابع هزینه تعمیمیافته) هر کروموزوم از بدترین مقدار تابع برازندگی موجود در جمعیت (GZmax):
(3-83)
گام2) محاسبه مقدار احتمال تجمعی هر کروموزوم:
(3-84)
گام3) تولید کردن یک عدد تصادفی بین صفر و یک و انتخاب کروموزوم ch در صورتی که:
(3-85)
همچنین در انتخاب کروموزومهای نسل بعد از یک عملگر انتخاب ترکیبی شامل استراتژی
نخبهگرایی72 (قابل ذکر است که در این استراتژی کروموزومهای نخبه انتخاب میشوند) و روش چرخ رولت توضیح داده شده در بالا استفاده میشود. بدین نحو که نخست درصدی از جوابهای نخبه به وسیله استراتژی نخبهگرایی و مابقی جمعیت به وسیله روش چرخ رولت انتخاب میشوند.
3-7-4- عملگر همگذری
عملگر همگذری به وسیله ادغام ژنهای والدین و به منظور ایجاد تنوع در جمعیت و جستجوی مناطق جستجو نشده فضای جواب بر روی جفت والدهای انتخاب شده مطابق با احتمال همگذری اعمال میشود.
در این تحقیق از یک عملگر همگذری ترکیبی متشکل از عملگر همگذری یک نقطه73 به منظور اعمال بر بخشهای یک و دو، عملگر همگذری ترتیبی74 به منظور اعمال بر بخشهای سه و چهار به طور جداگانه و عملگر همگذری حسابی کلی75 به منظور اعمال بر بخش پنج استفاده میشود. قابل ذکر است که نتایج تجربی حاکی از این است که اعمال هر سه عملگر همگذری بر روی والدین موجب کاهش سرعت همگرایی الگوریتم میشود. ساختار کلی این عملگر همگذری به شرح زیر است:
گام1) یک عدد تصادفی در بازه صفر و یک تولید کنید. چنانچه عدد تولید شده کوچکتر یا مساوی 5/0 است گام 2 و در غیر این صورت گام 3 را اجرا کنید.
گام2) عملگر همگذری یک نقطه را بر روی بخشهای اول و دوم و عملگر همگذری حسابی کلی را بر روی بخش پنجم والدین اجرا کنید.
گام3) عملگر همگذری ترتیبی را به طور جداگانه بر روی بخشهای سه و چهار والدین اجرا کنید.
3-7-5- عملگر جهش
عملگر جهش با تغییر دادن مقدار (ارزش) ژنهای انتخاب شده و به منظور ایجاد تنوع در جمعیت بر روی فرزندان تولید شده مطابق با احتمال جهش اعمال میشود. هدف این عملگر را میتوان کمک به فرآیند جستجو به منظور خارج شدن از نقاط بهینه محلی76 بیان کرد.
در الگوریتم ارائه شده از عملگرهای جهش تعویض77 و تغییر آهسته78 استفاده میشود. عملگر جهش تعویض بر روی چهار بخش اول به طور جداگانه و عملگر تغییر آهسته بر روی بخش پنجم کروموزوم اعمال میشوند. ساختار کلی عملگر جهش مورد استفاده به صورت زیر است:
گام1) یک عدد تصادفی در بازه صفر و یک تولید کنید.
گام2) چنانچه عدد تولید شده کوچکتر یا مساوی 5/0 است، مراحل زیر و در غیر این صورت گام 3 را اجرا کنید.
1.2. عملگر جهش را بر روی دو بخش اول کروموزوم به طور جداگانه اعمال کنید.
2.2. به ازای هر یک از ژنهای بخش پنج یک عدد تصادفی در بازه صفر و یک تولید کنید. چنانچه عدد تولید شده کوچکتر یا مساوی 05/0 است، دو عدد تصادفی α و β را در بازه صفر و یک تولید کنید. اگر مقدار α کوچکتر یا مساوی 5/0 است، β درصد از مقدار فعلی ژن انتخاب شده را به مقدار فعلی اضافه و در غیر این صورت β درصد از مقدار فعلی ژن انتخاب شده را از مقدار فعلی کم کنید.
گام3) عملگر جهش تعویض را بر روی بخشهای سه و چهار به طور جداگانه اعمال کنید.
3-7-6- نحوه اصلاح کروموزومهای نامعتبر
با توجه به ساختار کروموزوم، مشخص است که مجموع مقدار ژنهای مربوط به بخش اول و همچنین بخش دوم یک کروموزوم باید برابر با مجموع کل محصولات سفارش داده شده به وسیله
خرده فروشها باشد. با این وجود، اجرای عملگرهای همگذری و جهش ممکن است باعث تولید کروموزومهایی شوند که فاقد این خصوصیت هستند، بنابراین اصلاح این کروموزومها ضروری میباشد. در این تحقیق از یک روش اصلاح چرخهای79 [65] برای اصلاح کروموزومهای نامعتبر استفاده میشود.
بر اساس این روش و در ارتباط با هر یک از بخشهای اول و دوم، اگر مجموع مقدار ژنهای آن بخش از تعداد محصولات سفارش داده شده توسط همه خرده فروشها کمتر باشد به مقدار فعلی ژنی که به صورت تصادفی انتخاب شده است یک واحد اضافه میشود در حالی که اگر مجموع مقدار
ژنهای آن بخش از تعداد محصولات سفارش داده شده توسط همه خرده فروشها بیشتر باشد از مقدار فعلی ژنی که به صورت تصادفی انتخاب شده است یک واحد کم میشود. این فرآیند تا برابر شدن مجموع مقدار ژنها با تعداد محصولات سفارش داده شده توسط همه خرده فروشها تکرار
میشود.
شکل (3-9) نحوه عملکرد این روش به منظور اصلاح یک کروموزوم تولید شده پس از اعمال عملگرهای همگذری و جهش برای مثال (3-3) ارائه میکند. همان طوری که از شکل مشخص است مجموع مقدار ژنها در بخ

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