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

جستجوی تابوی مقاوم — فراابتکاری مبتنی بر تابو با مقاومت در برابر عدم قطعیت

معرفی‌شده توسط
Glover, F. (Tabu Search); robustness extensions by various authors
سال
1989 (TS); robust variant ~2000s
نوع
Metaheuristic with robustness mechanism
خانواده
Simulation / optimization

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

اندازه قلم

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

جستجوی تابوی مقاوم (RTS) فراابتکاری کلاسیک جستجوی تابو را با ارزیابی راه‌حل‌های کاندید نه تنها بر اساس مقدار هدف اسمی آن‌ها، بلکه بر اساس عملکردشان تحت عدم قطعیت، گسترش می‌دهد.

RTS به جای یافتن بهترین راه‌حل برای یک سناریوی واحد، به دنبال راه‌حل‌هایی است که در طیف وسیعی از سناریوها یا تحقق‌ها عملکرد خوبی دارند و بهینگی اوج را با قابلیت اطمینان مبادله می‌کنند.

شهود پشت روش

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

تاریخ

جستجوی تابو توسط فرد گلوور در سال‌های 1989–1990 به عنوان یک فراابتکاری مبتنی بر حافظه معرفی شد که با ممنوع کردن حرکات اخیراً معکوس شده، از بهینه‌های محلی فرار می‌کند. گسترش‌های مقاوم در اواخر دهه 1990 و دهه 2000 همزمان با افزایش علاقه به بهینه‌سازی مقاوم ظهور کردند؛ محققان ارزیابی‌های مبتنی بر سناریو و بدترین حالت را در ارزیابی همسایگی TS گنجاندند و جستجوی تابوی مقاوم را به عنوان ابزاری عملی برای مسائل مهندسی و لجستیک تحت عدم قطعیت معرفی کردند.

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

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

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

  • ارزیابی مقاومت بر روی مجموعه سناریوی بزرگ، هزینه محاسباتی را به ازای هر تکرار با |S| ضرب می‌کند، که می‌تواند ممنوعه باشد.
  • کیفیت مقاومت به شدت به کیفیت مجموعه سناریو بستگی دارد؛ پوشش ضعیف سناریو ممکن است اطمینان کاذب ایجاد کند.
  • طول عمر لیست تابو و اندازه همسایگی پارامترهای فراپارامتری خاص مسئله هستند که نیاز به تنظیم دارند.
  • بهینگی جهانی یا گواهی کیفیت راه‌حل را تضمین نمی‌کند.

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

نقاط قوت

  • راه‌حل‌هایی را پیدا می‌کند که در برابر تغییرات ورودی مقاوم هستند بدون اینکه نیاز به بررسی جداگانه مقاومت پس از اجرا داشته باشند.
  • عملکرد تجربی قوی جستجوی تابو را در مسائل ترکیبی دشوار (زمان‌بندی، VRP، انواع TSP) به ارث می‌برد.
  • معیار مقاومت انعطاف‌پذیر: از اهداف مینی‌ماکس، مقدار مورد انتظار، میانگین-واریانس و مبتنی بر صدک پشتیبانی می‌کند.
  • محدب بودن یا مشتق‌پذیری مسئله را الزامی نمی‌کند — برای اهداف جعبه سیاه و گسسته قابل استفاده است.
  • مکانیزم تابو از گیر افتادن در راه‌حل‌های بهینه محلی اما متوسط جهانی جلوگیری می‌کند.

کاربردها

  • مسیریابی وسایل نقلیه مقاوم تحت زمان‌های سفر تصادفی یا تقاضای مشتری
  • زمان‌بندی شغل-کارخانه و جریان-کارخانه با زمان‌های پردازش نامشخص
  • طراحی شبکه و برنامه‌ریزی ظرفیت تحت نوسان تقاضا
  • بهینه‌سازی زنجیره تأمین با زمان‌های تحویل یا هزینه‌های تأمین‌کننده نامشخص
  • تخصیص فرکانس در مخابرات تحت عدم قطعیت تداخل
  • بهینه‌سازی پرتفوی با بازده دارایی نامشخص با استفاده از محدودیت‌های ترکیبی

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

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

1

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

2

برای هر راه‌حل کاندید x که در طول جستجو با آن مواجه می‌شوید، مقدار هدف f(x, s) آن را تحت هر سناریوی s در S ارزیابی کنید. معیار مقاومت R(x) را محاسبه کنید — برای مثال، R(x) = max_{s in S} f(x,s) برای مقاومت مینی‌ماکس، یا R(x) = E[f(x,s)] + lambda * Var[f(x,s)] برای مقاومت میانگین-واریانس. این جایگزین ارزیابی اسمی واحد مورد استفاده در جستجوی تابوی کلاسیک می‌شود.

3

همسایگی N(x) راه‌حل فعلی x را با اعمال تمام حرکات ممکن (تعویض، درج، معکوس و غیره) تولید کنید. R(x') را برای هر همسایه x' ارزیابی کنید، به استثنای حرکاتی که در حال حاضر در لیست تابو قرار دارند مگر اینکه معیار استثنا برآورده شود. همسایه x* با بهترین مقدار مقاومت R(x*) را انتخاب کنید.

4

به x* منتقل شوید و معکوس حرکت اعمال شده را در لیست تابو با طول عمر t (معمولاً 5–20 تکرار) ثبت کنید. لیست تابو از چرخه جلوگیری می‌کند و اکتشاف را تشویق می‌کند. معیارهای استثنا — مانند پذیرش یک حرکت تابو اگر یک راه‌حل مقاوم جهانی بهتر تولید کند — ممکن است محدودیت تابو را لغو کنند.

5

اگر R(x*) نسبت به بهترین راه‌حل مقاوم شناخته شده فعلی بهبود یابد، آن را به‌روزرسانی کنید. تکرار را تا زمانی که معیار توقف برآورده شود ادامه دهید: حداکثر تکرارها، زمان سپری شده، یا عدم بهبود در تعداد مراحل مشخص شده. بهترین راه‌حل مقاوم یافت شده را به همراه پروفایل عملکرد سناریو-به-سناریوی آن برگردانید.

دام‌های رایج

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

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

جستجوی تابوی مقاوم چگونه با جستجوی تابوی تصادفی متفاوت است؟

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

مجموعه سناریوی S چقدر باید بزرگ باشد؟

قانون جهانی وجود ندارد. برای مجموعه‌های عدم قطعیت گسسته، در صورت امکان تمام سناریوهای معتبر را شمارش کنید. برای توزیع‌های پیوسته، 50–500 سناریوی نمونه‌برداری شده اغلب پوشش کافی را فراهم می‌کنند؛ تکنیک‌های کاهش واریانس مانند نمونه‌گیری هایپرکیوب لاتین می‌توانند کارایی را بهبود بخشند. تحلیل حساسیت بر روی |S| قبل از تعهد به تعداد سناریوی نهایی توصیه می‌شود.

آیا جستجوی تابوی مقاوم می‌تواند مسائل چندهدفه را مدیریت کند؟

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

کدام معیار مقاومت را باید انتخاب کنم؟

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

آیا جستجوی تابوی مقاوم برای نمونه‌های بسیار بزرگ مناسب است؟

این بستگی به هزینه ارزیابی سناریو دارد. اگر هر ارزیابی f(x,s) ارزان باشد (میلی‌ثانیه)، مقاومت بر روی صدها سناریو حتی برای نمونه‌های بزرگ نیز قابل تحمل باقی می‌ماند. اگر هر ارزیابی نیاز به شبیه‌سازی یا فراخوانی حل‌کننده گران‌قیمت داشته باشد، کاهش شدید سناریو یا مدل‌های جایگزین ضروری می‌شوند. ارزیابی موازی سناریوها در رشته‌ها یا ماشین‌های مختلف، یک کاهش رایج است.

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

منابع

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

    باز کردن مرجع DOI
    کپی شد.
  2. Dolan, E. D., Lewis, R. M., & Torczon, V. (2003). On the local convergence of pattern search. SIAM Journal on Optimization, 14(2), 567–583.

    باز کردن مرجع انتشار
    کپی شد.