مقاله بهینه سازی ترکیبی با انطباق سیاست با استفاده از جستجوی فضای پنهان

چکیده

Combinatorial Optimization underpins many real-world applications and yet, designing performant algorithms to solve these complex, typically NP-hard, problems remains a significant research challenge. Reinforcement Learning (RL) provides a versatile framework for designing heuristics across a broad spectrum of problem domains. However, despite notable progress, RL has not yet supplanted industrial solvers as the go-to solution. Current approaches emphasize pre-training heuristics that construct solutions but often rely on search procedures with limited variance, such as stochastically sampling numerous solutions from a single policy or employing computationally expensive fine-tuning of the policy on individual problem instances. Building on the intuition that performant search at inference time should be anticipated during pre-training, we propose COMPASS, a novel RL approach that parameterizes a distribution of diverse and specialized policies conditioned on a continuous latent space. We evaluate COMPASS across three canonical problems – Travelling Salesman, Capacitated Vehicle Routing, and Job-Shop Scheduling – and demonstrate that our search strategy (i) outperforms state-of-the-art approaches on 11 standard benchmarking tasks and (ii) generalizes better, surpassing all other approaches on a set of 18 procedurally transformed instance distributions.

چکیده به فارسی (ترجمه ماشینی)

بهینه سازی ترکیبی بسیاری از برنامه های دنیای واقعی و در عین حال ، طراحی الگوریتم های عملکردی برای حل این پیچیده ، به طور معمول NP ، مشکلات یک چالش تحقیقاتی مهم است.یادگیری تقویت (RL) یک چارچوب همه کاره برای طراحی اکتشافی در طیف گسترده ای از حوزه های مشکل فراهم می کند.با این حال ، علیرغم پیشرفت قابل توجه ، RL هنوز حل کننده های صنعتی را به عنوان راه حل رفتن به دست نیاورد.رویکردهای فعلی بر اکتشافات قبل از آموزش تأکید می کنند که راه حل ها را ایجاد می کنند اما اغلب به روشهای جستجو با واریانس محدود متکی هستند ، مانند نمونه گیری از راه حل های متعدد از یک سیاست واحد یا استفاده از تنظیم دقیق محاسباتی گران قیمت از خط مشی در موارد مشکل فردی.با تکیه بر شهودی که جستجوی عملکرد در زمان استنتاج باید در طول قبل از آموزش پیش بینی شود ، ما قطب نما را پیشنهاد می کنیم ، یک رویکرد جدید RL که پارامتر کردن توزیع سیاست های متنوع و تخصصی که در یک فضای نهفته مداوم است ، پارامتر می کند.ما قطب نما را در سه مشکل متعارف ارزیابی می کنیم-فروشنده مسافرتی ، مسیریابی وسیله نقلیه خازن و برنامه ریزی فروشگاه شغلی-و نشان می دهیم که استراتژی جستجوی ما (i) از رویکردهای پیشرفته در 11 کار معیار استاندارد و (ب) تعمیم بهتر است، از همه رویکردهای دیگر در مجموعه ای از 18 توزیع نمونه روال تبدیل شده.