یکشنبه 30 شهریور 1399 | Sunday 20 th of September 2020 صفحه اصلی گروه الکترونیکی کامپیوتر
الگوریتم جستجوی ممنوعه (Tabu Search)

الگوریتم جستجوی ممنوعه (TS)، یک الگوریتم بهینه‌سازی فرااکتشافی است که برای اولین بار در سال ۱۹۸۶ توسط Gloverمعرفی شد [Glov86]. در سال ۱۹۹۷، اولین کتابی که کاملاً به جستجوی ممنوعه اختصاص داشت توسط Gloverو Lagonaمنتشر شد [Glov97]. واژه تابو از تُنگان، زبان مردم جزایر پلینزی در اقیانوس ارام گرفته شده‌ است. این واژه به معنای شی مقدسی است که به دلیل قداست نباید ان را لمس کرد. بر اساس واژه‌نامه وِبستر، امروزه این واژه در معنای «ممنوعیت چیزی که دارای ریسک است» به کار می‌رود. معنای اخیر واژهتابو، با تکنیک جستجوی ممنوعه کاملاً سازگار است. ریسکی که در الگوریتمجستجوی ممنوعه از ان اجتناب می‌شود، خطر مسیرهای نامناسب است [Glov02].

برای رسیدن به جواب بهینه در یک مساله بهینه‌سازی، الگوریتم جستجوی ممنوعه ابتدا از یک جواب اولیه، شروع به حرکت می‌کند. در هر دور تکرار الگوریتم، یک همسایگی برای جواب جاری تعریف می­شود.سپس الگوریتم، بهترین جواب همسایه را از میان همسایه‌های جواب فعلی انتخاب می‌کند. در صورتی که این جواب در لیست ممنوعه (TL)[1]قرار نداشته باشد، الگوریتم به سوی جواب همسایه حرکت می‌کند، در غیر این ‌صورت، الگوریتم معیاری به نام معیار تنفس[2] را بررسی خواهد کرد. بر اساس معیار تنفس، اگر جواب همسایه از بهترین جواب یافت شده تاکنون بهتر باشد، الگوریتم به ان حرکت خواهد کرد، حتی اگر ان جواب در لیست ممنوعه باشد [Kama10].

پس از حرکت الگوریتم به جواب همسایه، لیست ممنوعه بروزرسانی می‌شود، به این معنا که حرکت قبل که به وسیله‌ ان به جواب همسایه حرکت کردیم در لیست ممنوعه قرار داده می‌شود تا از بازگشت مجدد الگوریتم به ان جواب و ایجاد سیکل جلوگیری شود. در واقع لیست ممنوعه ابزاری در الگوریتم جستجوی ممنوعه ‌است که توسط ان از قرار گرفتن الگوریتم در بهینه‌ محلی جلوگیری می‌شود. پس از قرار دادن حرکت قبلی در لیست ممنوعه، تعدادی از حرکت‌هایی که قبلا در لیست ممنوعه قرار گرفته بودند، از لیست خارج می‌شوند. مدت زمانی که حرکت‌ها در لیست ممنوعه قرار می‌گیرند، توسط یک پارامتر که زمان ممنوعه (tabu tenure) نام دارد تعیین می‌شود. حرکت از جواب فعلی به جواب همسایه تا جایی ادامه می‌یابد که شرط خاتمه دیده شود. شرط‌های خاتمه متفاوتی می‌توان برای الگوریتم در نظر گرفت. به طور مثال محدودیت تعداد حرکت به جواب همسایه می‌تواند یک شرط خاتمه باشد.

الگوریتم­های فرا اکتشافی بسیاری برای دستیابی به حداقل یک جواب خوب (نه لزوما بهترین) برای یک مساله به وجود امده است. بسیاری از این روش­ها، از یک مکانیزم Local Search(LS)بهره می­گیرند. LSرا می­توان یک روال جستجوی تکرارشونده دانست که از یک جواب ممکن و شدنی شروع می­کند و با انجام اصلاحات انتقالی جزیی (Move)، انرا تا رسیدن به یک بهینه موضعی ادامه می­دهد. با در نظر داشتن این نکته که در حالت معمول این بهینه موضعی، چیزی بیش از یک جواب متوسط نیست.

در LSمعمولا کیفیت جواب به دست امده، تا حد زیادی بستگی به غنای انتقال­های تعریف شده دارد و این مساله اساسی در رویکردهای مبتنی بر LSاست. اصل اولیه درTabu Search ، مجاز دانستنانتقال­هایی که بهبودی به همراه ندارند، برای ادامه دادن جستجو درLS است، وقتی که به یک بهینه موضعی برمی­خوریم. البته در این روش برای اجتناب از دور زدن و رسیدن به جواب­هایی که پیش از این به دست امده، از حافظه­ای به نامTabu List استفاده می­کنیم.

این حافظه جواب­های اخیر و یا انتقال­های اخیر را در خود ضبط می­کند. در واقع یک TSساده را می­توان ترکیبی از یک حافظه کوتاه مدت با LSدانست. انتقال­های ممنوع، در حافظه­ای کوتاه مدت(Short Term Memory)  ذخیره می­شوند تا (برای مدتی معین) انجام مجموعه ای معین از انتقال­ها را ممنوع سازند. این مدت معین، یا اصطلاحاTabu Tenure بنا بر الگوریتم حل و نوع مساله و ماهیت انتقال­ها متغیر است. حافظه مورد استفاده برای نگهداری انتقال­های ممنوع، معمولا گردشی و دارای طول ثابت است.



[1] Tabu List

[2] aspiration criterion

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26