روش جستجوی ممنوع (Tabu Search)، در ریاضیات (Mathematics)
انواع روش های عددی (Numerical Methods) را در آموزش زیر شرح دادیم :
روش جستجوی ممنوع (Tabu Search) :
الگوریتم جستجوی محلی با حافظه برای جلوگیری از تکرار
توضیح ساده: جستجوی ممنوع (Tabu Search) یک الگوریتم فراابتکاری است که توسط فرد گلوور در سال ۱۹۸۶ معرفی شد. این روش بر اساس جستجوی محلی (Local Search) ساخته شده است، اما با اضافه کردن یک حافظه (لیست ممنوع) از بازگشت به جواب های اخیرا دیده شده جلوگیری می کند. این مکانیسم به الگوریتم اجازه می دهد از بهینه های محلی فرار کند و نواحی جدیدی از فضای جستجو را کاوش نماید. جستجوی ممنوع در مسائل ترکیباتی مانند مسیریابی، زمان بندی، و تخصیص بسیار موفق بوده است.
شرح گام به گام: الگوریتم جستجوی ممنوع پایه:
۱. یک جواب اولیه x (مثلا تصادفی) و یک لیست ممنوع (Tabu List) خالی ایجاد کنید.
۲. بهترین جواب یافت شده را x_best = x قرار دهید.
۳. تا رسیدن به شرط توقف (تعداد تکرار):
- همسایه های x را تولید کنید (با تغییرات کوچک).
- همسایه هایی که در لیست ممنوع هستند (یا معیار آرزومندی - Aspiration Criterion - آنها را مجاز نمی کند) را حذف کنید.
- از بین همسایه های مجاز، بهترین را از نظر تابع هدف انتخاب کنید: x_new.
- x را به x_new به روز کنید.
- حرکت معکوس (ویژگی های حرکت) را به لیست ممنوع اضافه کنید (لیست معمولا اندازه ثابت دارد و قدیمی ها حذف می شوند).
- اگر f(x_new) بهتر از f(x_best) است، x_best = x_new را به روز کنید.
۴. x_best را به عنوان جواب برگردانید.
معیار آرزومندی (Aspiration) به یک حرکت ممنوع اجازه می دهد اگر به جوابی بهتر از بهترین جواب یافت شده منجر شود، انجام شود.
مثال عددی: مسئله مسیریابی وسایل نقلیه (VRP) برای توزیع کالا. جستجوی ممنوع با تعریف حرکات (مثلا جابجایی یک مشتری بین دو مسیر) و نگه داشتن لیستی از جابجایی های اخیر، می تواند مسیرهای بسیار خوبی بیابد. این روش در صنعت حمل و نقل کاربرد دارد.
مزایا: کارآمد برای مسائل ترکیباتی، توانایی فرار از بهینه محلی، استفاده از حافظه برای هدایت جستجو.
معایب: تنظیم پارامترها (اندازه لیست ممنوع، معیار آرزومندی) نیاز به تجربه دارد. ممکن است برای برخی مسائل کند باشد.
کاربردها: در مسیریابی، در زمان بندی، در تخصیص فرکانس، در طراحی شبکه های مخابراتی، در بهینه سازی طرح ریزی.
نکته: جستجوی ممنوع یکی از موفق ترین روش ها برای مسائل بهینه سازی ترکیباتی است.
