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

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

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

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

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

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

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

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

Компромисс

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

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

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

Примеры

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

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

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

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

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

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

Поиск

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

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

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

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

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

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

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

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

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

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

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

Этимология

Слово «эвристика» вошло в обиход в начале 19 века. Оно образовано неравномерно от греческого слова heuriskein , что означает «найти». ^[5]

См. также

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

Ссылки

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

[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 г. .

[1]

[2]

[3]

[4]

[5]