Эвристика (информатика) - Heuristic (computer science)

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

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

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

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

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

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

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

Компромисс

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

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

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

Примеры

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

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

Проблема коммивояжера

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

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

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

Поиск

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

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

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

Эвристический метод может выполнить свою задачу, используя деревья поиска. Однако вместо того, чтобы генерировать все возможные ветви решения, эвристика выбирает ветви с большей вероятностью, чем другие ветви. Она избирательна на каждом этапе принятия решения, выбирая те отрасли, которые с большей вероятностью дадут решения.^[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 {я, j} neq g}$ .

Этимология

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

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

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