Posted on: ژانویه 19, 2019 Posted by: 92 Comments: 0

الگوریتم جستجوي ممنوعه-پایان نامه شبکه زنجیره تأمین

الگوریتم جستجوي ممنوعه (TS)

جستجوي ممنوع (TS[1]) در سال 1986 توسط فرد گلاور به عنوان يک الگوريتم فراابتکاري براي حل مسائل بهينه سازي ترکيبي معرفي شد [52]. TS در اصل روشي بود که براي فائق آمدن بر ضعف روش­هاي جستجوي محلي (LS[2]) و الگوريتم هاي ابتکاري طراحي شد و مي­توان آن را به نوعي ادامه و تعميم الگوريتم­هاي LS به شمار آورد[53] . پايه­اي ترين و مهم ترين مفاهيم TS شامل دو عنصر «فضای جستجو»[3]و «ساختار همسایگی»[4] مي­شود.

فضاي جستجوي LS يا TS در واقع تمام پاسخ هاي­شدني است که مي­توان در جريان جستجو به آنها برخورد کرد. نزديک ترين مفهوم پس از تعريف فضاي جستجو، مفهوم ساختار همسايگي است که نشان دهنده تمام پاسخ­هايي است که مي­توان با يک حرکت از پاسخ فعلي به آنها رسيد. اگر مجموعه تمام تغييراتي را که برروي پاسخ فعلي مي­توان انجام داد با  نشان دهيم، و  نشان دهنده تمام پاسخ هاي همسايه­اي باشد که مي­توان به اين طريق ساخت، خواهيم داشت :

با اين اوصاف مي­توان گفت که براي يک مسئله خاص اين قابليت وجود دارد که چندين ساختار همسايگي داشته باشيم (هر ساختار همسايگي متناظر با يک نوع حرکت يا تغيير  برروي پاسخ هاي شدني است). معروف ترين حرکاتي که در TS به کار مي رود و به کمک آن ها ساختار همسايگي تعريف مي شود شامل «قرار دادن»[5] و «جابجایی»[6] است. در حرکت قرار دادن، يکي از عناصر پاسخ انتخاب و در جايي بين باقي عناصر قرار مي گيرد و به اين شکل يک پاسخ جديد ساخته مي شود. در جابه جايي، مکان قرار گرفتن دو عنصر در پاسخ فعلي با يکديگر تعويض مي شود.

يکي ديگر از نکاتي که TS را از LS متمايز مي­کند، «لیست حرکت های غیر مجاز»[7] (TL) است. TL در واقع يک آرايه با طول مشخص  است که در آن تمام  حرکت اخيري که در جريان جستجو انجام شده اند ذخيره شده است و در صورت تکراري بودن يک حرکت (وجود آن در TL) از انجام آن جلوگيري مي­شود. در صورتي که حرکت تکراري نباشد، پس از انجام آن، حرکت انجام شده وارد TL مي­شود و اولين حرکتي که در TL وجود دارد از ليست خارج    مي­شود. از TL با عنوان «حافظه کوتاه مدت»[8] نيز ياد مي­شود. عناصر يا حرکت هايي که در TL ذخيره شده اند تا انجام تعداد مشخصي از حرکات (طول TL) قابليت بازيابي و انجام مجدد ندارند مگر اينکه انجام آنها به مقدار قابل توجهي و به اندازه يک معيار از پيش تعيين شده تابع هدف را بهبود دهد. در واقع ما تنها در صورتي که معيار پيش گفته ديده شد مي­توانيم يکي از عناصر TL را مورد استفاده قرار دهيم. اين معيار با عنوان Aspiration Criteria شناخته مي­شود.

علاوه بر حافظه کوتاه مدت، دو نوع حافظه «میان مدت»[9] و «بلند مدت»[10] نيز در TS کاربرد دارد. اين دو نوع حافظه در جريان جستجو اين امکان را فراهم مي­آورند که پاسخ­هاي بهتر امکان بيشتري جهت بروز داشته باشند و به همين نسبت پاسخ­هاي بدتر تاثير کمتري در فرآيند جستجو داشته باشند.

به طور كلي چهار چوب TS را به شكل زير مي ­وان نشان داد. (  مقدار فعلي،  بهترين پاسخ شناخته شده،  مقدار تابع هدف به ازاي ،  همسايگي  و  مقدار غير تابو يا اجازه داده شده توسط Aspiration Criteria است.)

[1] Tabu Search

[2] Local Search

[3] Search Space

[4] Neighborhood Structure

[5] Insertion

[6] Swap

[7] Tabu List

[8] Short Term Memory

[9] Medium Term Memory

[10] Long Term Memory

لینک جزییات بیشتر و دانلود این پایان نامه:

توسعه یک مدل بهینه سازی چند هدفه برای طراحی شبکه زنجیره تأمین در شرایط عدم قطعیت با در نظر گرفتن سطوح کیفی

Categories: