جستجوی ممنوعه (Tabu Search - TS)، در ریاضیات (Mathematics)

انواع روش های بهینه سازی (Optimization Methods) را در آموزش زیر شرح دادیم :

جستجوی ممنوعه (Tabu Search - TS) :

📌 معرفی

جستجوی ممنوعه (Tabu Search - TS) توسط فرد گلاور (Fred Glover) در سال ۱۹۸۶ معرفی شد. این یک الگوریتم فراابتکاری است که با استفاده از حافظه (Tabu List) از بازگشت به جواب های اخیرا بازدید شده جلوگیری می کند و به این ترتیب از بهینه های محلی خارج می شود.

🚫 مفاهیم اصلی

فهرست ممنوعه (Tabu List): لیستی از حرکت ها یا جواب های ممنوعه که برای مدت معین (Tenure) نمی توان از آنها استفاده کرد.

معیار آرزو (Aspiration Criteria): شرایطی که تحت آن یک حرکت ممنوعه می تواند انجام شود (مثلا اگر به جواب بهتری از بهترین جواب یافت شده منجر شود).

جستجوی محلی: TS یک جستجوی محلی پیشرفته است که در هر تکرار بهترین جواب همسایه غیرممنوع را انتخاب می کند.

📐 مراحل الگوریتم

یک جواب اولیه

و یک لیست ممنوعه خالی ایجاد کن.

تا شرط توقف:

مجموعه همسایه های

را تولید کن.

همسایه هایی که در لیست ممنوعه هستند را حذف کن (مگر اینکه معیار آرزو را ارضا کنند).

بهترین همسایه

را انتخاب کن.

را قرار بده.

لیست ممنوعه را به روزرسانی کن.