Skip to content
بازگشت به نتایج جست‌وجو

جستجوی ممنوعه — فراابتکار جستجوی محلی

معرفی‌شده توسط
Fred Glover
سال
1989
نوع
Local-search metaheuristic

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

جستجوی ممنوعه (Tabu Search) یک فراابتکار جستجوی محلی است که توسط فرد گلاور (Fred Glover) در سال ۱۹۸۹ معرفی شد و از یک لیست ممنوعه — حافظه کوتاه‌مدت راه‌حل‌های اخیراً پیموده شده — برای جلوگیری از تکرار و خروج از بهینه‌های محلی استفاده می‌کند. با ممنوع کردن صریح حرکاتی که تصمیمات اخیر را معکوس می‌کنند، الگوریتم فضای جستجو را به طور گسترده‌تری کاوش می‌کند و از طریق ساختارهای حافظه بلندمدت مانند معیارهای آرزو (aspiration criteria)، حتی در مسائل ترکیبیاتی بزرگ و پیچیده، به بهینه سراسری نزدیک می‌شود.

شهود پشت روش

تصور کنید در تاریکی در یک منظره کوهستانی حرکت می‌کنید و سعی در یافتن بلندترین قله دارید. یک جستجوگر محلی ساده همیشه به سمت بالا گام برمی‌دارد و در نزدیک‌ترین تپه‌ای که به آن می‌رسد، گیر می‌افتد. جستجوی ممنوعه یک دفترچه یادداشت از نقاطی که اخیراً بازدید کرده است را حمل می‌کند و از بازگشت به آن‌ها امتناع می‌ورزد، حتی اگر عقب‌گرد وسوسه‌انگیز به نظر برسد. این فراموشی اجباری در مورد حرکات اخیر، جستجو را از بن‌بست‌ها خارج کرده و به قلمرو کشف نشده هدایت می‌کند و به آن اجازه می‌دهد تا در نهایت به زمین‌های بسیار بلندتری نسبت به یک جستجوی محلی ساده دست یابد.

تاریخ

جستجوی ممنوعه توسط فرد گلاور در مقاله‌ای برجسته در سال ۱۹۸۹ در مجله ORSA Journal on Computing معرفی شد، جایی که به عنوان استراتژی برای هدایت جستجوی محلی با بهره‌گیری از حافظه حرکات گذشته ارائه شد. ایده‌های بنیادی در مونوگراف اسپرینگر گلاور و لاگونا در سال ۱۹۹۷ تثبیت و گسترش یافتند، که لیست ممنوعه کوتاه‌مدت متعارف، معیارهای آرزو، و استراتژی‌های تنوع‌بخشی و تشدید بلندمدت را که امروزه نیز در این روش مرکزی هستند، پایه‌گذاری کرد. از زمان معرفی، جستجوی ممنوعه به طور گسترده در تحقیق در عملیات، زمان‌بندی، لجستیک و طراحی ترکیبیاتی به کار گرفته شده است و همچنان در کنار تبرید شبیه‌سازی شده و الگوریتم‌های ژنتیک، یک فراابتکار معیار استاندارد باقی مانده است.

چه زمانی استفاده شود

جستجوی ممنوعه برای مسائل بهینه‌سازی ترکیبیاتی و گسسته که فضای راه‌حل برای روش‌های دقیق بسیار بزرگ است و ساختار مسئله امکان تعریف یک همسایگی معنی‌دار را فراهم می‌کند، بسیار مناسب است. کاربردهای معمول شامل مسائل زمان‌بندی، مسیریابی، تخصیص و توالی‌یابی است. این روش به ویژه زمانی مؤثر است که چشم‌انداز جستجو دارای بهینه‌های محلی زیادی باشد که روش‌های ساده‌تر را به دام می‌اندازند. این روش نیازی به مشتق‌پذیر یا پیوسته بودن تابع هدف ندارد. تعریف همسایگی و مدت ممنوعیت باید با دقت برای مسئله خاص تطبیق داده شوند؛ یک همسایگی ضعیف انتخاب شده یا مدت ممنوعیت بسیار کوتاه یا بسیار طولانی می‌تواند عملکرد را به طور قابل توجهی کاهش دهد. حداقل چند صد — و ایده‌آل بیش از هزار — تکرار برای اینکه جستجو فضای را به طور کافی کاوش کند، لازم است.

محدودیت‌ها و ملاحظات

  • عملکرد به تعریف همسایگی و مدت ممنوعیت حساس است؛ انتخاب‌های ضعیف می‌تواند جستجو را به دام بیندازد یا باعث تکرار آن با وجود مکانیزم ممنوعه شود.
  • به حداقل بودجه تکرار نیاز دارد — معمولاً بیش از ۱۰۰۰ تکرار — برای کاوش کافی همسایگی؛ با تکرارهای بسیار کم نتایج بهتر از جستجوی محلی ساده نیستند.
  • لیست ممنوعه به جای راه‌حل‌های کامل، ویژگی‌های حرکت را ذخیره می‌کند، بنابراین معیار آرزو برای جلوگیری از مسدود کردن ناخواسته حرکات واقعاً خوب لازم است.
  • برخلاف حل‌کننده‌های دقیق، جستجوی ممنوعه هیچ تضمین بهینگی ارائه نمی‌دهد و کیفیت نتیجه می‌تواند در اجراهای مختلف بسته به راه‌حل اولیه یا تصادفی بودن همسایگی، متفاوت باشد.

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • از طریق مکانیزم ممنوعه بدون نیاز به اطلاعات گرادیان، از بهینه‌های محلی خارج می‌شود.
  • قابل اعمال بر مسائل ترکیبیاتی، مختلط و حتی پیوسته — فرض نرمال بودن یا هیچ ویژگی توزیعی را ندارد.
  • حافظه در مقیاس‌های زمانی متعدد (لیست ممنوعه کوتاه‌مدت، تنوع‌بخشی/تشدید بلندمدت) را در بر می‌گیرد و امکان کاوش اصولی فضای جستجو را فراهم می‌کند.
  • اغلب راه‌حل‌های با کیفیت بالا را با بودجه محاسباتی نسبتاً متوسط در مقایسه با روش‌های دقیق در نمونه‌های بزرگ پیدا می‌کند.

کاربردها

  • زمان‌بندی شغل-کارگاه و جریان-کارگاه — بهینه‌سازی توالی عملیات برای حداقل کردن زمان تکمیل (makespan) یا تأخیر (tardiness).
  • مسیریابی وسایل نقلیه — یافتن مسیرهای تحویل کارآمد تحت محدودیت‌های ظرفیت و پنجره زمانی.
  • تخصیص و مکان‌یابی تسهیلات — تخصیص وظایف به منابع یا مکان‌یابی تسهیلات برای حداقل کردن هزینه.
  • رنگ‌آمیزی گراف، طراحی شبکه و مخابرات — حل مسائل بهینه‌سازی ساختاری گسسته.
  • انتخاب ویژگی و جستجوی ابرپارامتر — کاوش فضاهای پیکربندی گسسته در خطوط لوله یادگیری ماشین.

چگونه کار می‌کند

چگونه کار می‌کند

1

جستجو از یک راه‌حل کاندید اولیه آغاز می‌شود که می‌تواند به صورت تصادفی یا با یک ابتکار حریصانه (greedy heuristic) ساخته شود. لیست ممنوعه به عنوان یک صف با طول ثابت و خالی راه‌اندازی می‌شود و بهترین راه‌حل یافت شده تا کنون ثبت می‌گردد. ساختار همسایگی — قاعده‌ای که تعریف می‌کند کدام راه‌حل‌ها یک گام با راه‌حل فعلی فاصله دارند — باید به گونه‌ای تعریف شود که برای مسئله خاص معنی‌دار باشد.

2

از راه‌حل فعلی، تمام حرکات در همسایگی تعریف شده تولید و بر اساس تابع هدف ارزیابی می‌شوند. هر حرکت متناظر با یک اغتشاش کوچک است، مانند جابجایی دو عنصر در یک توالی یا واژگونی یک متغیر دودویی. همسایگی باید به اندازه کافی غنی باشد تا امکان کاوش معنی‌دار را فراهم کند، اما به اندازه کافی کوچک باشد تا در هر تکرار قابل مدیریت باشد.

3

هر حرکت کاندید در برابر لیست ممنوعه آزمایش می‌شود. اگر حرکت — یا ویژگی که آن را مشخص می‌کند — در لیست ظاهر شود، به عنوان ممنوعه طبقه‌بندی شده و ممنوع می‌شود، مگر اینکه معیار آرزو را برآورده کند: معمولاً، اگر راه‌حل حاصل بهتر از بهترین راه‌حل یافت شده تا کنون باشد، وضعیت ممنوعه لغو شده و حرکت مجاز می‌شود. این مکانیزم آرزو به الگوریتم انعطاف‌پذیری می‌دهد بدون اینکه نظم ضد تکرار خود را رها کند.

4

در میان تمام حرکات غیر ممنوعه (و هر حرکت ممنوعه‌ای که از معیار آرزو عبور کند)، بهترین حرکت انتخاب و اجرا می‌شود، حتی اگر مقدار هدف را بدتر کند. این تمایل به پذیرش وخامت اوضاع است که به الگوریتم اجازه می‌دهد از بهینه‌های محلی خارج شود، که ویژگی تعیین‌کننده جستجوی ممنوعه در مقایسه با صعود تپه ساده است.

5

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

6

الگوریتم تا زمانی که یک معیار توقف برآورده شود، تکرار می‌کند: حداکثر تعداد تکرارها، مقدار هدف مورد نظر، یا تعداد ثابتی از تکرارها بدون بهبود. بهترین راه‌حل یافت شده در طول کل جستجو به عنوان نتیجه بازگردانده می‌شود. انتخاب بودجه تکرار مناسب حیاتی است — تکرارهای بسیار کم مانع از کاوش کافی همسایگی می‌شوند.

دام‌های رایج

  • تنظیم مدت ممنوعیت بسیار کوتاه اجازه تکرار را می‌دهد و هدف مکانیزم ممنوعه را بی‌اثر می‌کند؛ مدت ممنوعیت باید برای اندازه مسئله تنظیم شود.
  • تنظیم مدت ممنوعیت بسیار طولانی جستجو را بیش از حد محدود می‌کند و مانع از بازگشت الگوریتم به مناطقی می‌شود که ممکن است حاوی بهبود باشند.
  • اجرای کمتر از تقریباً ۱۰۰۰ تکرار به این معنی است که جستجو به اندازه کافی از همسایگی کاوش نکرده است — اگر محاسبات محدود است، به تبرید شبیه‌سازی شده (simulated annealing) بازگردید که می‌تواند نتایج مفیدی را با تکرارهای کمتر سریع‌تر تولید کند.
  • استفاده از همسایگی بیش از حد محدود (مثلاً فقط جابجایی‌های تکی در یک ساختار پیچیده) منجر به جستجوی سطحی می‌شود؛ اطمینان حاصل کنید که همسایگی به اندازه کافی غنی است تا تمام مناطق امیدوارکننده فضای راه‌حل را به هم متصل کند.
  • نادیده گرفتن معیار آرزو می‌تواند مسیر به بهینه سراسری را به طور دائمی مسدود کند اگر آن حرکت ممنوعه باشد؛ همیشه حداقل لغو استاندارد بهترین راه‌حل را پیاده‌سازی کنید.

پرسش‌های متداول

جستجوی ممنوعه چگونه با تبرید شبیه‌سازی شده متفاوت است؟

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

مدت لیست ممنوعه چقدر باید باشد؟

مدت ممنوعیت (tabu tenure) — تعداد تکرارهایی که یک حرکت ممنوع باقی می‌ماند — وابسته به مسئله است. یک نقطه شروع رایج، مدتی متناسب با ریشه دوم اندازه مسئله است، اما این باید به صورت تجربی تنظیم شود. مدت ممنوعیت بسیار کوتاه اجازه تکرار را می‌دهد؛ مدت ممنوعیت بسیار طولانی جستجو را بیش از حد محدود می‌کند. استراتژی‌های مدت ممنوعیت تطبیقی یا تصادفی می‌توانند حساسیت به این انتخاب را کاهش دهند.

آیا جستجوی ممنوعه تضمین می‌کند که بهینه سراسری را پیدا کند؟

خیر. جستجوی ممنوعه یک فراابتکار است و هیچ تضمین بهینگی ارائه نمی‌دهد. هدف آن یافتن راه‌حل‌های با کیفیت بالا به طور کارآمد است، اما نتیجه به ساختار همسایگی، مدت ممنوعیت، تعداد تکرارها و راه‌حل اولیه بستگی دارد. برای تضمین بهینگی، یک روش دقیق مانند برنامه‌ریزی عدد صحیح لازم است، هرچند روش‌های دقیق ممکن است برای نمونه‌های بزرگ از نظر محاسباتی غیرممکن باشند.

معیار آرزو چیست و چرا لازم است؟

معیار آرزو قاعده‌ای است که وضعیت ممنوعه یک حرکت را تحت شرایط خاصی لغو می‌کند. رایج‌ترین معیار این است: اگر اجرای یک حرکت ممنوعه منجر به راه‌حلی بهتر از بهترین راه‌حل یافت شده تا کنون شود، محدودیت ممنوعیت برداشته شده و حرکت مجاز می‌شود. بدون این لغو، مکانیزم ممنوعه می‌تواند مسیر به بهینه سراسری را به طور دائمی مسدود کند اگر آن مسیر از یک حرکت اخیراً پیموده شده عبور کند.

روش‌های مرتبط

منابع

  1. Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    باز کردن مرجع انتشار
    کپی شد.
  2. Glover, F. & Laguna, M. (1997). Tabu Search. Springer.

    شابک: 9780792349907
    کپی شد.