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

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

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

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

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

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

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

Tabu Search

Local Search

Search Space

Neighborhood Structure

Insertion

Swap

Tabu List

Short Term Memory

Medium Term Memory

Long Term Memory