جستجوی ممنوعه تصادفی — فراابتکاری تصادفی با حافظه
- معرفیشده توسط
- Glover, F. (base TS); stochastic extensions by various authors (1990s–2000s)
- سال
- 1990s
- نوع
- Stochastic metaheuristic optimizer
- خانواده
- Simulation / optimization
این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید
چه کاری انجام میدهد؟
جستجوی ممنوعه تصادفی (STS) بسطی از جستجوی ممنوعه کلاسیک است که تصادفی بودن را به مراحل کاوش همسایگی و انتخاب حرکت وارد میکند. با ترکیب حافظه ممنوعه — که راهحلهای اخیراً بازدید شده را ممنوع میکند — با پذیرش احتمالی یا نمونهبرداری تصادفی کاندیدا، STS به طور مؤثرتری از بهینههای محلی فرار کرده و چشماندازهای راهحل ناهموار را که TS قطعی ممکن است در پیمایش آنها شکست بخورد، کاوش میکند.
شهود پشت روش
جستجوی ممنوعه کلاسیک با حرکت همیشگی به بهترین همسایه مجاز، فضای راهحل را پیمایش میکند و از حافظه کوتاهمدت (لیست ممنوعه) برای جلوگیری از چرخه زدن استفاده میکند. با این حال، در عمل، بهترین حرکت مجاز همچنان میتواند الگوریتم را در یک منطقه از چشمانداز به دام اندازد. جستجوی ممنوعه تصادفی، تصادفی بودن کنترلشدهای را تزریق میکند: حرکت بعدی به جای انتخاب حریصانه، به صورت احتمالی از مجموعهای از همسایگان کاندیدا انتخاب میشود و اغتشاشات تصادفی برای متنوعسازی جستجو به طور متناوب معرفی میشوند. این امر انضباط هدایتشده با حافظه TS را حفظ میکند و در عین حال قدرت اکتشافی را که نزول قطعی خالص فاقد آن است، اضافه میکند.
تاریخ
جستجوی ممنوعه توسط فرد گلاور در سال 1986 به طور رسمی معرفی شد و در مقالات برجسته از 1989 تا 1990 بسط داده شد. بسطهای تصادفی در دهه 1990 ظهور کردند زیرا محققان تشخیص دادند که ارزیابی همسایگی قطعی یک گلوگاه در مسائل در مقیاس بزرگ است. نمونهبرداری تصادفی کاندیدا، پذیرش احتمالی حرکت و تزریق نویز برای بهبود تنوعبخشی گنجانده شد و منجر به آنچه به طور کلی جستجوی ممنوعه تصادفی نامیده میشود، گردید. این تکنیک به طور گسترده در تحقیق در عملیات، طراحی مهندسی و بهینهسازی ابرپارامترهای یادگیری ماشین کاربرد دارد.
چه زمانی استفاده شود
هنگام حل مسائل بهینهسازی ترکیبی یا پیوسته جعبه سیاه با چشماندازهای ناهموار و چندوجهی که جستجوی محلی قطعی به طور مداوم در آنها به دام میافتد (مانند زمانبندی، مسیریابی، انتخاب ویژگی)، از جستجوی ممنوعه تصادفی استفاده کنید. این روش به ویژه زمانی ارزشمند است که ارزیابی کامل همسایگی از نظر محاسباتی پرهزینه باشد و نمونهبرداری تصادفی ضروری شود. از STS زمانی که مسئله محدب یا تکوجهی است استفاده نکنید — روشهای مبتنی بر گرادیان یا دقیق سریعتر و بهینه هستند. از آن زمانی که به بهینگی جهانی تضمینشده نیاز دارید اجتناب کنید، زیرا STS هیچ تضمین همگرایی فراتر از راهحلهای یافتشده ابتکاری ارائه نمیدهد. همچنین زمانی که تابع هدف به راحتی به طور کامل ارزیابی میشود و جستجوی ممنوعه قطعی با جستجوی جامع همسایگی امکانپذیر است، از آن اجتناب کنید.
محدودیتها و ملاحظات
- هیچ تضمین نظری برای یافتن بهینه جهانی وجود ندارد؛ کیفیت راهحل به شدت به تنظیمات پارامتر بستگی دارد.
- طول عمر ممنوعیت و اندازه لیست کاندیدا نیاز به تنظیمات خاص مسئله دارند؛ انتخابهای نادرست منجر به همگرایی زودرس یا پیشرفت کند میشود.
- اجراهای تصادفی بدون یک بذر تصادفی ثابت، غیرقابل تکرار هستند و ارزیابی و حسابرسی را پیچیده میکنند.
- سربار حافظه با اندازه لیست ممنوعه افزایش مییابد؛ نمایشهای ممنوعیت مبتنی بر ویژگی برای فضاهای راهحل بزرگ مورد نیاز است.
شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.
نقاط قوت
- با ترکیب حافظه با کاوش احتمالی، مؤثرتر از جستجوی ممنوعه قطعی از بهینههای محلی فرار میکند.
- با نمونهبرداری از کاندیداها، ساختارهای همسایگی بزرگ را مقیاسپذیر میکند و هزینه محاسباتی هر تکرار را کاهش میدهد.
- حافظه ممنوعه از چرخه زدن، یک حالت شکست رایج در روشهای صرفاً تصادفی مانند صعود تپه با شروع مجدد تصادفی، جلوگیری میکند.
- چارچوب انعطافپذیر: احتمال اغتشاش و طول عمر ممنوعیت را میتوان برای تعادل بین تشدید و تنوعبخشی تنظیم کرد.
- برای مسائل ترکیبی (TSP، زمانبندی) و بهینهسازی پیوسته با تطبیق جزئی قابلاجرا است.
کاربردها
- مسیریابی وسایل نقلیه و بهینهسازی لجستیک تحت تقاضای نامشخص
- زمانبندی شغل-کارگاهی و باز-کارگاهی با زمانهای پردازش تصادفی
- انتخاب ویژگی در مجموعه دادههای یادگیری ماشین با ابعاد بالا
- طراحی شبکه و بهینهسازی توپولوژی
- بهینهسازی سبد سهام با محدودیتهای انتخاب دارایی ترکیبی
- تنظیم ابرپارامتر برای مدلهای شبیهسازی پیچیده
چگونه کار میکند
چگونه کار میکند
یک راهحل اولیه x0 (به صورت تصادفی یا ابتکاری) تولید کنید. لیست ممنوعه T را خالی قرار دهید، طول عمر ممنوعیت tau، حد تکرار I_max، و پارامترهای تصادفی (مانند اندازه لیست کاندیدا k، احتمال اغتشاش p_perturb) را تعریف کنید.
در هر تکرار، به جای ارزیابی همه همسایگان، به طور تصادفی زیرمجموعهای N_s از همسایگی کامل N(x_current) را نمونهبرداری کنید. این امر هزینه هر تکرار را کاهش داده و تصادفی بودن را در مورد اینکه کدام مناطق از فضا کاوش میشوند، معرفی میکند.
حرکت بعدی x_next را از N_s انتخاب کنید: یا (الف) بهترین کاندیدای غیرممنوعه را با احتمال 1-p_perturb انتخاب کنید، یا (ب) با احتمال p_perturb یک کاندیدای غیرممنوعه تصادفی را برای تنوعبخشی انتخاب کنید. معیارهای جاهطلبی ممکن است وضعیت ممنوعیت را لغو کنند اگر x_next راهحل شناختهشده بهتر را بهبود بخشد.
x_current (یا ویژگی حرکت) را به لیست ممنوعه T اضافه کنید. اگر |T| > tau، قدیمیترین ورودی را حذف کنید. اگر f(x_next) < f(x_best)، راهحل برتر فعلی x_best را بهروزرسانی کنید.
نمونهبرداری همسایگی را از طریق بهروزرسانی ممنوعیت تکرار کنید تا زمانی که حداکثر تکرار I_max، مقدار هدف مطلوب برآورده شود، یا هیچ بهبودی برای یک پنجره صبر رخ ندهد. x_best را به عنوان راهحل نهایی برگردانید.
دامهای رایج
- تنظیم طول عمر ممنوعیت خیلی کوتاه، علیرغم لیست ممنوعه، باعث چرخه زدن میشود؛ خیلی طولانی، مناطق امیدوارکننده را بیجهت مسدود میکند.
- استفاده از لیست کاندیدا که خیلی کوچک است (نمونهبرداری تهاجمی) میتواند باعث شود جستجو به طور مداوم همسایگان خوب را از دست بدهد.
- نادیده گرفتن معیارهای جاهطلبی باعث میشود الگوریتم حرکات بهبود دهنده جهانی را که تصادفاً ممنوع هستند، رد کند.
- گزارش تنها یک اجرا بدون شروع مجددهای متعدد یا بذرها، تصویری گمراهکننده از کیفیت راهحل معمول ارائه میدهد.
- اشتباه گرفتن جستجوی ممنوعه تصادفی با تبرید شبیهسازی شده: هر دو تصادفی هستند اما اساساً متفاوتند — STS از حافظه صریح استفاده میکند در حالی که SA از پذیرش احتمالی مبتنی بر دما بدون حافظه استفاده میکند.
پرسشهای متداول
جستجوی ممنوعه تصادفی چگونه با تبرید شبیهسازی شده متفاوت است؟
هر دو فراابتکاری تصادفی هستند، اما STS از حافظه ممنوعه صریح برای ممنوع کردن حرکات اخیراً بازدید شده استفاده میکند و از چرخه زدن جلوگیری میکند. SA حافظهای ندارد — بدتر شدن راهحلها را با احتمالی که با گذشت زمان (برنامه دما) کاهش مییابد، میپذیرد. STS به طور کلی در مسائل ترکیبی که بازدید مجدد حرکات یک خطر واضح است، قویتر است.
چند تکرار (I_max) باید اجرا کنم؟
قانون جهانی وجود ندارد. یک عمل رایج اجرای چندین آزمایش مستقل (مانند 10-30 شروع مجدد) با بودجهای متناسب با اندازه مسئله است، سپس نتایج بهترین و میانگین گزارش میشود. برای ارزیابی، بودجه کل ارزیابی تابع مورد استفاده توسط روشهای رقیب را مطابقت دهید.
آیا جستجوی ممنوعه تصادفی میتواند متغیرهای پیوسته را مدیریت کند؟
بله، اما نیاز به تعریف یک همسایگی پیوسته (مانند اغتشاش گوسی در اطراف راهحل فعلی) و یک ویژگی مناسب برای لیست ممنوعه (مانند یک منطقه یا جهت) دارد. بیشتر ادبیات STS مسائل ترکیبی را هدف قرار میدهد؛ برای فضاهای پیوسته، تکامل تفاضلی یا CMA-ES اغلب جایگزینهای طبیعیتری هستند.
نقش معیارهای جاهطلبی چیست؟
معیارهای جاهطلبی وضعیت ممنوعیت یک حرکت را لغو میکنند اگر پذیرش آن راهحلی بهتر از بهترین راهحل یافت شده تا کنون ارائه دهد. بدون جاهطلبی، الگوریتم ممکن است حرکات بهبود دهنده جهانی را که تصادفاً ممنوع هستند، به طور دائم رد کند و کیفیت راهحل را به شدت محدود کند.
آیا باید بذر تصادفی را برای تکرارپذیری ثابت کنم؟
بله، هنگام گزارش نتایج در تحقیقات، بذر را برای اطمینان از تکرارپذیری ثابت کنید. در عمل، با بذرهای متعدد اجرا کنید و آمار (میانگین، بهترین، انحراف معیار) را گزارش دهید تا تصویری قابل اعتماد از عملکرد الگوریتم در سراسر چشمانداز تصادفی ارائه دهید.
روشهای مرتبط
منابع
Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74-94.
باز کردن مرجع DOIکپی شد.Hu, J., Fu, M. C., & Marcus, S. I. (2007). A model reference adaptive search method for global optimization. Operations Research, 55(3), 549-568.
باز کردن مرجع DOIکپی شد.