Раскрытие границ изученной эвристики локального поиска: вы самый могущественный из кротких?

Таблица ссылок

Аннотация и введение

Связанных с работой

Оценка Max-Cut

Оценка для SAT

Резюме и прогноз, ссылки

Дополнительные материалы

Абстрактный

В последние годы объединение нейронных сетей с эвристикой локального поиска стало популярным в области комбинаторной оптимизации. Несмотря на значительные вычислительные требования, этот подход показал многообещающие результаты при минимальном ручном проектировании. Однако мы выявили три критических ограничения в эмпирической оценке этих попыток интеграции. Во-первых, случаи средней сложности и слабых базовых показателей создают трудности при точной оценке эффективности подходов, основанных на обучении. Во-вторых, отсутствие исследования абляции затрудняет количественную оценку и точную приписывание улучшений архитектуре глубокого обучения. Наконец, обобщение изученной эвристики в различных распределениях остается недостаточно изученным. В этом исследовании мы проводим всестороннее исследование этих выявленных ограничений. Удивительно, но мы продемонстрировали, что простая обучаемая эвристика, основанная на Табу-поиске, превосходит современную обучаемую эвристику (SOTA) с точки зрения производительности и возможности обобщения. Наши результаты бросают вызов преобладающим предположениям и открывают захватывающие возможности для будущих исследований и инноваций в области комбинаторной оптимизации.

1. ВВЕДЕНИЕ

Разработка эффективных эвристик или алгоритмов аппроксимации для NP-сложных задач комбинаторной оптимизации (CO) — сложная задача, часто требующая знаний предметной области и обширного метода проб и ошибок. Таким образом, идея автоматизации этого требовательного и утомительного процесса проектирования с помощью машинного обучения для изучения алгоритмов, использующих внутреннюю структуру проблемы, вызвала значительный интерес среди исследователей (Bello et al., 2016; Khalil et al., 2017; Bengio et al. ., 2021; Донг и др., 2021). В частности, значительная часть этих работ (Khalil et al., 2017; Barrett et al., 2020; Yolcu and P´oczos, 2019) сосредоточена на использовании графовых нейронных сетей (GNN) для решения проблем CO. Несмотря на вычислительные требования, эти подходы на основе GNN продемонстрировали конкурентоспособную производительность по сравнению с эвристикой SOTA, адаптированной к конкретным проблемам.

Хотя эти потенциальные достижения обещают многообещающе, некоторые опасения остаются. Превосходную эффективность изученной эвристики можно объяснить выбором конкретных экземпляров и базовых показателей. В частности, если базовые показатели слабы, изученная эвристика может легко превзойти их. Без жестких примеров и правильного выбора базовой линии изученная эвристика может легко продемонстрировать производительность, сравнимую с эвристикой SOTA, а это может привести к переоценке реальных возможностей изученной эвристики. Более того, сравнения с эвристикой SOTA иногда не учитываются из-за проблем с масштабируемостью архитектур глубокого обучения.

Подмножество подходов, основанных на обучении (Khalil et al., 2017; Yolcu and P'oczos, 2019; Barrett et al., 2020, 2022), включает в себя функциональность или поведение традиционных эвристик, потенциально предлагая улучшенную или повышенную производительность за счет интеграции эвристики. принципы с компонентами машинного обучения. Если всестороннее сравнение с интегрированной эвристикой и исследование абляции архитектуры глубокого обучения отсутствуют, становится сложно определить конкретный вклад архитектуры глубокого обучения. Следовательно, если интегрированная эвристика надежна, изученная эвристика может легко превзойти базовую эвристику, в то время как архитектура глубокого обучения играет незначительную роль.

Еще одно большое достижение изученной эвристики (Khalil et al., 2017; Barrett et al., 2020; Toenshof et al., 2019), первоначально обученной на более мелких и конкретных экземплярах из определенного дистрибутива, демонстрирует впечатляющую производительность при тестировании на более крупных экземплярах из определенного дистрибутива. разные дистрибутивы. Это достижение является значительным достижением, соответствующим основной цели использования подходов, основанных на обучении: снизить необходимость в обширной настройке и специфичных для предметной области знаниях, которые часто требуются для эвристики. Хотя классические эвристики с гиперпараметрами также могут столкнуться с проблемами, если они точно настроены для конкретного распределения, они также могут обобщаться на различные распределения. Основной вопрос вращается вокруг того, действительно ли изученные эвристики демонстрируют лучшую обобщаемость по сравнению с классическими эвристиками. Тщательное и глубокое сравнение выученных эвристик с классическими эвристиками дает ценную информацию об обобщаемости выученных эвристик.

Изученным эвристикам часто не хватает теоретических гарантий, что делает эмпирическую оценку единственным методом понимания сильных и слабых сторон предлагаемых методологий. Мы считаем, что несколько фундаментальных, но ключевых вопросов остаются неисследованными в эмпирической оценке этих работ. Хотя эти вопросы актуальны для всех типов изученной эвристики, мы задаем их и отвечаем на них, анализируя часто цитируемые и недавние рецензируемые публикации, посвященные изучению эвристики локального поиска. Наша цель — не предоставить исчерпывающие критерии для проблем CO, обсуждаемых в нашей работе, а скорее помочь будущим исследователям в оценке их исследований.

Конкретно мы задаем и отвечаем на следующие вопросы:

1. Могут ли изученные эвристики быть чрезмерно параметризованы? Абсолютно. Заменив GNN в ECO-DQN линейной регрессией и используя подмножество функций из ECO-DQN (Barrett et al., 2020), которое связано с поиском табу (Glover, 1990), мы представляем сокращенную версию ECO-DQN, названную SoftTabu. . Наше исследование показывает, что SoftTabu демонстрирует превосходную производительность и возможность обобщения по сравнению с ECO-DQN для задачи NPhard Maximum-Cut (Max-Cut).

2. Можно ли смещение исходного уровня объяснить превосходной эффективностью изученных эвристик? Да, мы демонстрируем, что SoftTabu, ванильная обучаемая эвристика, может превзойти S2V-DQN (Халил и др., 2017) для задачи Max-Cut и GNNSAT (Yolcu and P´oczos, 2019) для логической выполнимости (SAT).

*3. Может ли изученная эвристика продемонстрировать превосходную обобщаемость благодаря предвзятости выбора экземпляра? * Да, мы демонстрируем, что ECO-DQN демонстрирует плохую генерализацию на более сложных экземплярах и легко попадает в ловушку в пространстве поиска.