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

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

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

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

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

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

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

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

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

Компромисс

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

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

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

Примеры

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

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

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

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

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

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

Поиск

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

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

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

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

Антивирусная программа

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

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

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

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

Статистический анализ может быть проведен при использовании эвристики для оценки вероятности неправильных результатов. Чтобы использовать эвристику для решения задачи поиска или задачи о рюкзаке , необходимо проверить допустимость эвристики . Учитывая эвристическую функцию , предназначенную для аппроксимации истинного оптимального расстояния до целевого узла в ориентированном графе , содержащем общее количество узлов или вершин, помеченных , «допустимый» грубо означает, что эвристика недооценивает стоимость достижения цели или формально это для всех , где . ${\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 , что означает «найти». ^[5]

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

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

Рекомендации

1. Перл, Иудея (1984). Эвристика: стратегии интеллектуального поиска для решения компьютерных задач . США: Паб Addison-Wesley. Co., Inc., Ридинг, Массачусетс. п. 3. ОСТИ  5127296.
2. Аптер, Майкл Дж. (1970). Компьютерное моделирование поведения. Лондон: Hutchinson & Co., с. 83. ИСБН 9781351021005.
3. Джон Луи Бентли (1982). Написание эффективных программ . Прентис Холл. п. 11.
4. Аллен Ньюэлл и Герберт А. Саймон (1976). «Информатика как эмпирическое исследование: символы и поиск» (PDF) . Комм. АКМ . 19 (3): 113–126. дои : 10.1145/360018.360022 . S2CID  5581562.
5. «Определение эвристики на английском языке». Издательство Оксфордского университета. Архивировано из оригинала 23 октября 2016 года . Проверено 22 октября 2016 г. .