Эвристика (информатика)

Тип алгоритма, выдает приблизительно правильные решения

В математической оптимизации и информатике эвристика ( от греч. εὑρίσκω «нахожу, обнаруживаю» ^[1] ) — это метод, разработанный для более быстрого решения задач , когда классические методы слишком медленны для нахождения точного или приблизительного решения, или когда классические методы не могут найти ни одного точного решения в поисковом пространстве . Это достигается путем обмена оптимальности, полноты, точности или аккуратности на скорость. В некотором смысле это можно считать сокращением пути.

Эвристическая функция , также называемая просто эвристикой , — это функция , которая ранжирует альтернативы в алгоритмах поиска на каждом шаге ветвления на основе доступной информации, чтобы решить, какой ветви следовать. Например, она может аппроксимировать точное решение. ^[2]

Определение и мотивация

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

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

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

Эвристики лежат в основе всей области искусственного интеллекта и компьютерного моделирования мышления, поскольку они могут использоваться в ситуациях, когда нет известных алгоритмов . ^[3]

Компромисс

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

• Оптимальность: Когда существует несколько решений для данной проблемы, гарантирует ли эвристика, что будет найдено лучшее решение? Действительно ли необходимо найти лучшее решение?
• Полнота: Когда для заданной проблемы существует несколько решений, может ли эвристика найти их все? Действительно ли нам нужны все решения? Многие эвристики предназначены только для поиска одного решения.
• Точность и правильность: Может ли эвристика предоставить доверительный интервал для предполагаемого решения? Является ли планка погрешности решения неоправданно большой?
• Время выполнения : Является ли это самой известной эвристикой для решения этого типа проблем? Некоторые эвристики сходятся быстрее других. Некоторые эвристики лишь немного быстрее классических методов, и в этом случае «накладные расходы» на вычисление эвристики могут иметь негативное влияние.

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

Примеры

Более простая проблема

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

Задача коммивояжера

Пример приближения описан Джоном Бентли для решения задачи коммивояжера (TSP):

• «Учитывая список городов и расстояния между каждой парой городов, каков кратчайший возможный маршрут, который посещает каждый город ровно один раз и возвращается в исходный город?»

чтобы выбрать порядок рисования с помощью перьевого плоттера . Известно, что задача TSP является NP-трудной , поэтому оптимальное решение даже для задачи среднего размера трудно найти. Вместо этого жадный алгоритм может быть использован для получения хорошего, но не оптимального решения (это приближение к оптимальному ответу) за достаточно короткий промежуток времени. Эвристика жадного алгоритма говорит выбирать то, что в данный момент является лучшим следующим шагом, независимо от того, предотвращает ли это (или даже делает невозможным) хорошие шаги позже. Это эвристика в том смысле, что практика показывает, что это достаточно хорошее решение, в то время как теория показывает, что существуют лучшие решения (и даже указывает, насколько лучше, в некоторых случаях). ^[4]

Поиск

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

Ньюэлл и Саймон: гипотеза эвристического поиска

В своей речи при получении премии Тьюринга Аллен Ньюэлл и Герберт А. Саймон обсуждают гипотезу эвристического поиска: физическая система символов будет многократно генерировать и изменять известные структуры символов до тех пор, пока созданная структура не будет соответствовать структуре решения. Каждый последующий шаг зависит от предыдущего шага, таким образом, эвристический поиск узнает, какие пути следует использовать, а какие игнорировать, измеряя, насколько близок текущий шаг к решению. Следовательно, некоторые возможности никогда не будут сгенерированы, поскольку они, как оценивается, с меньшей вероятностью завершат решение.

Эвристический метод может выполнить свою задачу, используя деревья поиска. Однако вместо того, чтобы генерировать все возможные ветви решения, эвристика выбирает ветви, которые с большей вероятностью дадут результаты, чем другие ветви. Она избирательна в каждой точке принятия решения, выбирая ветви, которые с большей вероятностью дадут решения. ^[5]

Антивирусное программное обеспечение

Антивирусное программное обеспечение часто использует эвристические правила для обнаружения вирусов и других форм вредоносного ПО. Эвристическое сканирование ищет код и/или поведенческие шаблоны, общие для класса или семейства вирусов, с различными наборами правил для разных вирусов. Если обнаруживается, что файл или исполняемый процесс содержат соответствующие шаблоны кода и/или выполняют этот набор действий, то сканер делает вывод, что файл заражен. Самая продвинутая часть эвристического сканирования на основе поведения заключается в том, что оно может работать против высокорандомизированных самомодифицирующихся/мутирующих ( полиморфных ) вирусов, которые не могут быть легко обнаружены более простыми методами сканирования строк. Эвристическое сканирование имеет потенциал для обнаружения будущих вирусов без необходимости сначала обнаруживать вирус где-то еще, отправлять его разработчику вирусного сканера, анализировать и предоставлять пользователям сканера обновление обнаружения.

Подводные камни

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

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

Статистический анализ может быть проведен при использовании эвристики для оценки вероятности неверных результатов. Чтобы использовать эвристику для решения задачи поиска или задачи о рюкзаке , необходимо проверить, что эвристика является допустимой . При наличии эвристической функции, предназначенной для аппроксимации истинного оптимального расстояния до целевого узла в ориентированном графе, содержащем общее количество узлов или вершин, помеченных , «допустимая» означает примерно, что эвристика недооценивает стоимость достижения цели или формально, что для всех , где . ${\displaystyle h(v_{i},v_{g})}$ ${\displaystyle d^{\star }(v_{i},v_{g})}$ ${\displaystyle v_{g}}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle v_{0},v_{1},\cdots ,v_{n}}$ ${\displaystyle h(v_{i},v_{g})\leq d^{\star }(v_{i},v_{g})}$ ${\displaystyle (v_{i},v_{g})}$ ${\displaystyle {i,g}\in [0,1,...,n]}$

Если эвристика недопустима, она может никогда не найти цель, либо попав в тупик графа , либо перескакивая вперед и назад между двумя узлами и где . ${\displaystyle G}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{j}}$ ${\displaystyle {i,j}\neq g}$

Этимология

Слово «эвристика» вошло в употребление в начале 19 века. Оно образовано нерегулярно от греческого слова heuriskein , что означает «находить». ^[6]

Смотрите также

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

Ссылки

1. https://en.wiktionary.org/wiki/Heuristic_(computer_science)/heuristic
2. Pearl, Judea (1984). Эвристика: интеллектуальные стратегии поиска для решения компьютерных проблем . США: Addison-Wesley Pub. Co., Inc., Reading, MA. стр. 3. OSTI  5127296.
3. Аптер, Майкл Дж. (1970). Компьютерное моделирование поведения. Лондон: Hutchinson & Co. стр. 83. ISBN 9781351021005.
4. Джон Луис Бентли (1982). Написание эффективных программ . Prentice Hall. стр. 11.
5. Аллен Ньюэлл и Герберт А. Саймон (1976). «Компьютерная наука как эмпирическое исследование: символы и поиск» (PDF) . Comm. ACM . 19 (3): 113–126. doi : 10.1145/360018.360022 . S2CID  5581562.
6. "Определение эвристики на английском языке". Oxford University Press. Архивировано из оригинала 23 октября 2016 года . Получено 22 октября 2016 года .