Значение (мета) эвристических методов

1. Для оптимизации из Википедии :

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

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

   • Интересно, как определить, является ли метод оптимизации метаэвристическим или нет? Например,

     (1) Является ли симплекс-метод линейного программирования метаэвристическим?

     (2) Являются ли большинство методов нелинейного программирования, таких как градиентный спуск, метод множителей Лагранжа, методы штрафа, методы внутренних точек (барьерные методы), метаэвристическими?

     (3) Являются ли все методы без градиента, такие как метод Нелдера-Мида или метод симплексного спуска, метаэвристическими?

   • Какие методы оптимизации не являются метаэвристическими?

2. В более широком смысле (выход за рамки оптимизации) для методов решения проблем из Википедии :

   Эвристика относится к методам, основанным на опыте , для решения проблем, обучения и обнаружения . Если исчерпывающий поиск нецелесообразен, эвристические методы используются для ускорения процесса поиска удовлетворительного решения. Примеры этого метода включают использование эмпирического правила, обоснованного предположения, интуитивного суждения или здравого смысла.

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

   Интересно, как понять значение слова "эвристический"?

   • Как я могу определить, является ли метод «решения проблем, обучения и обнаружения» эвристическим или нет?

   • Какие методы «решения проблем, обучения и обнаружения» не являются эвристическими?

Спасибо и всего наилучшего!

Эвристика - это то, что работает во многих случаях на практике, хотя нет подробного аргумента, почему она должна работать хорошо.

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

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

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

Я не буду перебирать симплекс и Nelder-Mead, поскольку @ArnoldNeumaier уже дал очень хорошее объяснение, но хотел добавить свои 2 цента.

Одна из лучших цитат, которые я слышал некоторое время назад, чтобы описать разницу между эвристикой и метаэвристикой: эвристика - довольно хорошее правило. Метаэвристика - довольно хорошее правило для нахождения довольно хороших правил.

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

• Как мне настроить параметры этой эвристики, чтобы улучшить производительность для этой проблемы?
• Это эвристика лучше, чем эта эвристика?

Существует множество метаэвристик, которые вы можете использовать для решения проблем, обучения и обнаружения , а именно:

• Имитация отжига : я использовал этот в задаче для оптимизации размещения подключенных компонентов в сетке, чтобы минимизировать общую стоимость подключения, например.
• Рой частиц
• Муравьиная колония
• Табу поиск

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

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