В чем разница между эвристикой и метаэвристикой?

Ответ 1

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

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

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

Ответ 2

Чтобы дать правильную цитату, относительно Алехандро ответьте:

"Метаэвристика - это высокоуровневая проблемно-независимая алгоритмическая структура, которая предоставляет набор рекомендаций или стратегий для разработки алгоритмов эвристической оптимизации [...] Реализация алгоритма эвристической оптимизации по конкретным задачам в соответствии с руководящими принципами, изложенными в метаэвристическая структура также упоминается как метаэвристическая" (Sörensen, Glover on http://scholarpedia.org/article/Metaheuristics)

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

Кстати, пример quicksort Alejandro не кажется полностью адекватным по двум-трем причинам.

• Фактически эвристика и метаэвристика являются частью поля оптимизации. Поэтому проблема, которую они пытаются решить, - это поиск оптимального, а не сортировки.
• Эвристика обычно используется, когда проблемы, которые вы хотите решить, слишком сложны, в вычислительном смысле - это не относится к проблеме сортировки.
• То, что было указано на примере quicksort, если я это хорошо понимаю, - это случайный элемент. В принципе, вы можете иметь детерминированную эвристику - я никогда не сталкивался с детерминированной метаэвристикой, но, вероятно, ее можно было бы закодировать. Это может быть немного "игра со словами", но случайный элемент более точно характеризует "стохастический поиск", чем (мета) эвристики.

Ответ 3

Подробное объяснение см.:

Sörensen, K. (2015). Метаэвристика - метафора разоблачена. Международные транзакции в операционных исследованиях, 22 (1), 3-18.

Метаэвристика - это алгоритм высокого уровня, не зависящий от задачи рамки, в которой содержится набор руководящих принципов или стратегий для разработки эвристические алгоритмы оптимизации. Этот термин также используется для обозначения конкретная реализация алгоритма эвристической оптимизации в соответствии с руководящими принципами, изложенными в таких рамках (Sörensen, 2015).

Эвристика - это руководящие принципы, метаэвристика - это основа, которая их использует.