Что такое гиперэвристика?

Я хотел знать, в чем различия между гиперэвристикой и метаэвристикой, и каковы их основные области применения. Какие проблемы подходят для решения с помощью гиперэвристики?

TL: DR : Гиперэвристика - это метаэвристика, подходящая для решения тех же самых задач оптимизации, но (в принципе), обеспечивающая подход «быстрого прототипирования» для неопытных практиков. На практике существуют проблемы с преобладающим подходом, мотивирующим появление перспективы гиперэвристики «белого ящика» .

Более детально:

Метаэвристика - это методы поиска непостижимо большого пространства возможных решений, чтобы найти «высококачественное» решение. Популярные метаэвристики включают имитацию отжига, поиск по табу, генетические алгоритмы и т. Д.

Существенная разница между метаэвристикой и гиперэвристикой заключается в добавлении уровня поисковой косвенности: неформально гиперэвристику можно описать как «эвристика для поиска в пространстве эвристики». Поэтому можно использовать любую метаэвристику как гиперэвристическую, при условии, что природа «пространства эвристики», подлежащего поиску, определена надлежащим образом.

Поэтому область применения гиперэвристики такая же, как и метаэвристика. Их применимость (по отношению к метаэвристике) является «инструментом быстрого прототипирования»: первоначальная мотивация состояла в том, чтобы позволить непрофессионалам-практикам применять метаэвристику к своей конкретной задаче оптимизации (например, «Командировщик-продавец», временные окна плюс бин-бин). упаковка »), не требуя экспертизы в очень специфической проблемной области. Идея заключалась в том, что это может быть сделано:

1. Позволяет практикующим специалистам применять только очень простые (эффективные, рандомизированные) эвристики для преобразования потенциальных решений. Например, для TSP: «поменять местами два случайных города», а не, скажем, более сложную эвристику Лин-Кернигана .
2. Достигните эффективных результатов (несмотря на использование этой простой эвристики), комбинируя / упорядочивая их интеллектуальным способом, обычно используя некоторую форму механизма обучения.

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

Напротив, первоначальный мотиватор для селективной гиперэвристики заключался в том, что исследователи смогут создать гиперэвристический решатель, который затем, вероятно, будет хорошо работать в невидимой проблемной области, используя только простую рандомизированную эвристику.

Традиционно это было реализовано путем введения «гиперэвристического доменного барьера» (см. Рисунок ниже), в соответствии с которым общность между проблемными областями, как утверждается, достижима, не позволяя решающему устройству знать область, в которой это работает. Вместо этого это решило бы проблему, работая только с непрозрачными целочисленными индексами в списке доступных эвристик (например, как « Проблема многорукого бандита» ).

На практике этот подход «слепой области» не привел к решениям достаточного качества. Чтобы достичь результатов, сопоставимых с метаэвристикой, специфичной для проблемы, гиперэвристическим исследователям пришлось реализовать сложную эвристику, специфичную для проблемы, что не позволило достичь цели быстрого прототипирования.

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

Более поздний взгляд на гиперэвристику «белого ящика» поддерживает декларативный, многофункциональный подход к описанию проблемных областей. Этот подход имеет ряд заявленных преимуществ:

1. Теперь практикующим специалистам больше не нужно применять эвристику, а нужно просто указать проблемную область.
2. Это устраняет доменный барьер, придавая гиперэвристике тот же «информированный» статус о проблеме, что и метаэвристика для конкретной проблемы.
3. С описанием проблемы «белого ящика», печально известной теоремы «Нет бесплатного обеда» (которая по существу утверждает, что при рассмотрении в пространстве всех проблем черного ящика моделируемый отжиг с бесконечным графиком отжига в среднем так же хорош, как и любой другой подход), нет дольше применяется.

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Я работаю в этой области исследований, и поэтому невозможно удалить все личные предубеждения из ответа.