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

الگوریتم جستجوی ممنوعه (Tabu Search) (TS) یک الگوریتم بهینه‌سازی فراابتکاری است که برای اولین بار در سال ۱۹۸۶ توسط گلووِر Glover معرفی شد. در سال ۱۹۹۷، اولین کتابی که کاملاً به جستجوی ممنوعه اختصاص داشت توسط گلووِر و لاگونا منتشر شد. واژهٔ تابو از تُنگان زبان مردم جزایر پلینزی در اقیانوس آرام گرفته شده‌است. این واژه به معنای شیء مقدسی است که به دلیل قداست نباید آن را لمس کرد. بر اساس واژه‌نامهٔ وِبستر، امروزه این واژه در معنای «ممنوعیت ایجاد شده به دلیل فرهنگ اجتماعی برای ایجاد اقدام حفاظتی» یا «ممنوعیت چیزی که دارای ریسک است»، به کار می‌رود. معنای اخیر واژهٔ تابو، با تکنیک جستجوی ممنوعه کاملاً سازگار است. ریسکی که در الگوریتم جستجوی ممنوعه از آن اجتناب می‌شود، خطر مسیرهای نامناسب است.

نمودار جریان الگوریتم جستجوی ممنوعه

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

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

استراتژی‌های پیشرفتهٔ جستجوی ممنوعه

ساختار کلی جستجوی ممنوعه اغلب جوابگوی مسائل بزرگ نیست؛ بنابراین به منظور افزایش قدرت الگوریتم از استراتژی‌های زیر که معروف به استراتژی‌های پیشرفته جستجوی ممنوعه هستند استفاده می‌شود:

استراتژی فهرست کاندید(Candidate List Strategy): در یک TS عادی، برای حرکت از یک جواب فعلی به یک جواب همسایه، باید مقدار تابع هدف برای هر عنصر از همسایه‌ها ارزیابی شود. این کار می‌تواند از لحاظ محاسباتی بسیار هزینه بر باشد. روشی دیگر، این است که به جای آن که تمامی همسایه‌ها بررسی شود، تنها یک زیرمجموعهٔ تصادفی از همسایه‌ها در نظر گرفته شود، که در نتیجه هزینهٔ محاسباتی به‌طور قابل ملاحظه‌ای کاهش می‌یابد. انتخاب زیرمجموعه‌ای از جوابهای همسایه به صورت تصادفی، می‌تواند به عنوان یک مکانیزم ضد چرخه عمل کند؛ این کار اجازه می‌دهد که از فهرست ممنوعهٔ کوچکتری نسبت به کل همسایگی، استفاده شود. البته باید در نظر داشت که این کار یک عیب مهم دارد و آن احتمال از دست دادن جوابهای خوب است، بنابراین احتمال‌هایی را نیز می‌توان به کار برد تا معیارهای ممنوعه فعال شود.
استراتژی تقویت (Intensification Strategy): استراتژی تقویت به معنای یافتن حرکت‌های خوب و افزایش انجام آن حرکت‌ها در الگوریتم است. تقویت، در بسیاری از پیاده‌سازی‌های TS استفاده می‌شود، اما همیشه ضروری نیست، زیرا حالت‌های بسیاری وجود دارد که در آن‌ها جستجوی معمولی کفایت می‌کند.
استراتژی تنوع بخشی (Diversification Strategy): روش‌های مبتنی بر جستجوی محلی، آن‌قدر محلی هستند که زمان زیادی یا تمامی زمان خود را در بخش محدودی از فضای جستجو صرف می‌کنند. نتیجه‌ای که از این واقعیت می‌توان گرفت، این است که هر چند جواب‌های خوبی به وسیلهٔ این روشها به دست می‌آید، اما ممکن است جستجو از اکتشاف مناطق بهتر باز بماند و بنابراین به جواب‌هایی برسد که از جواب بهینه، بسیار دور هستند. تنوع‌بخشی، یک مکانیزم الگوریتمیک است که برای حل این مشکل تلاش می‌کند. برای انجام این کار، تنوع‌بخشی، جستجو را مجبور می‌کند به سوی مناطقی که تا کنون کشف نشده، حرکت کند.
مجوز دادن به جوابهای نشدنی: در حالت‌هایی که محدودیت‌های مسئله بسیار محدودکننده باشند و از جستجوی مؤثر فضای جواب جلوگیری کنند از این استراتژی استفاده می‌شود. طی این استراتژی محدودیت‌های مسئله آزاد شده و بجای آن‌ها یک مقدار جریمه به تابع هدف اضافه می‌شود.

منابع

↑ Glover, F. , Future paths for integer programming and links to artificial intelligence, Computers and Operations Research, Vol. 13, pp. 533–549, 1986.
↑ Glover F. and Laguna, M. , Tabu Search, Kluwer Academic Publishers, 1997.
↑ Glover F. and Glover, F. , and Laguna, M. , Tabu Search, In Handbook of Applied Optimization, Pardalos P.M. , and Resende M.G.C. , (Eds.), Oxford University Press, pp. 194-208, 2002.
↑ Merriam-Webster. Merriam-Websters's Collegiate Dictionary. Merriam-Websters, 1997.
↑ الگوریتم‌های بهینه‌سازی فراابتکاری/تالیف مسعود یقینی، محمد رحیم اخوان کاظم‌زاده. جهاد دانشگاهی واحد صنعتی امیر کبیر شابک ‎۹۷۸−۹۶۴−۲۱۰−۰۷۸−۱
↑ Gendreau, M. , AN INTRODUCTION TO TABU SEARCH, In Handbook of Metaheuristics, Glover, F. , Kochenberger, G.A. , (Eds.), Kluwer Academic publishers, Norwell, 2003.

. کورش عشقی؛ مهدی کریمی نسب؛ تحلیل الگوریتمها و طراحی روشهای فرابتکاری؛ انتشارات دانشگاه شریف؛ ۱۳۹۵

[[1]-1] Glover, F. , Future paths for integer programming and links to artificial intelligence, Computers and Operations Research, Vol. 13, pp. 533–549, 1986.

[[2]-2] Glover F. and Laguna, M. , Tabu Search, Kluwer Academic Publishers, 1997.

[[3]-3] Glover F. and Glover, F. , and Laguna, M. , Tabu Search, In Handbook of Applied Optimization, Pardalos P.M. , and Resende M.G.C. , (Eds.), Oxford University Press, pp. 194-208, 2002.

[[4]-4] Merriam-Webster. Merriam-Websters's Collegiate Dictionary. Merriam-Websters, 1997.

[[5]-5] الگوریتم‌های بهینه‌سازی فراابتکاری/تالیف مسعود یقینی، محمد رحیم اخوان کاظم‌زاده. جهاد دانشگاهی واحد صنعتی امیر کبیر شابک ‎۹۷۸−۹۶۴−۲۱۰−۰۷۸−۱

[[6]-6] Gendreau, M. , AN INTRODUCTION TO TABU SEARCH, In Handbook of Metaheuristics, Glover, F. , Kochenberger, G.A. , (Eds.), Kluwer Academic publishers, Norwell, 2003.