دانلود مقالات ISI درباره جستجوی ممنوع یا تابو سرچ + ترجمه فارسی

الگوریتم جستجوی ممنوع یا تابو سرچ (Tabu Search) با استفاده از مفهوم تابو و در نظر گرفتن بعضی از اعمال به عنوان اعمال تابو، بهینه سازی را انجام می دهد. تابو به معنای مقدس و غیر قابل نزدیک می باشد. این الگوریتم توسط گلاور در سال ۱۹۸۶ برای بهبود الگوریتم های جستجوی محلی ارایه شد. اصول این الگوریتم طوری است که حرکات خاصی را برای جستجوی محلی مجاز می داند که گرچه ممکن است این حرکات در کوتاه مدت نتیجه خاصی نداشته باشند ولی در بلند مدت می توانند الگوریتم را به سمت بهینه سراسری راهنمایی کنند. برای رسیدن به جواب بهینه در یک مسئله بهینه‌سازی، الگوریتم جستجوی ممنوعه ابتدا از یک جواب اولیه شروع به حرکت می‌کند. سپس الگوریتم بهترین جواب همسایه را از میان همسایه‌های جواب فعلی انتخاب می‌کند. در صورتی که این جواب در فهرست ممنوعه قرار نداشته باشد، الگوریتم به جواب همسایه حرکت می‌کند؛ در غیراین‌صورت الگوریتم معیاری به نام معیار تنفس را چک خواهد کرد. بر اساس معیار تنفس اگر جواب همسایه از بهترین جواب یافت شده تا کنون بهتر باشد، الگوریتم به آن حرکت خواهد کرد، حتی اگر آن جواب در فهرست ممنوعه باشد. پس از حرکت الگوریتم به جواب همسایه، فهرست ممنوعه بروزرسانی می‌شود؛ به این معنا که حرکت قبل که بوسیلهٔ آن به جواب همسایه حرکت کردیم در فهرست ممنوعه قرار داده می‌شود تا از بازگشت مجدد الگوریتم به آن جواب و ایجاد سیکل جلوگیری شود. در واقع فهرست ممنوعه ابزاری در الگوریتم جستجوی ممنوعه‌است که توسط آن از قرار گرفتن الگوریتم در بهینهٔ محلی جلوگیری می‌شود. پس از قرار دادن حرکت قبلی در فهرست ممنوعه، تعدادی از حرکت‌هایی که قبلاً در فهرست ممنوعه قرار گرفته بودند از فهرست خارج می‌شوند. مدت زمانی که حرکت‌ها در فهرست ممنوعه قرار می‌گیرند توسط یک پارامتر که زمان ممنوعه (tabu tenure) نام دارد تعیین می‌شود. حرکت از جواب فعلی به جواب همسایه تا جایی ادامه می‌یابد که شرط خاتمه دیده شود. شرط‌های خاتمه متفاوتی می‌توان برای الگوریتم در نظر گرفت. به طور مثال محدودیت تعداد حرکت به جواب همسایه می‌تواند یک شرط خاتمه باشد. تابو سرچ دارای حافظه کوتاه مدت و بلند مدت می باشد در صورتی که الگوریتمی مانند شبیه سازی تبرید بدون حافظه می باشد. در الگوریتم تابو سرچ جواب هایی که در تابع هدف بهبود ایجاد نمی کنند ولی ممکن است ما را به جواب بهینه سراسری رهنمون سازند، مجاز می باشند. البته با این شرط که آن حرکت ها در لیست ممنوع قرار نداشته باشند. الگوریتم Tabu Search برای این کار نیاز دارد تا از روند بازگشتی به جواب های پیشین و گیر افتادن در بهینه محلی جلوگیری نماید. به همین جهت لیستی از حرکات ممنوع در حافظه این الگوریتم ثبت می شود تا از تکرار آن حرکات جلوگیری شود.