Эвристическая функция в искусственном интеллекте: краткий обзор

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

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

Что такое эвристическая функция?

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

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

Станьте самым высокооплачиваемым инженером по искусственному интеллекту! С нашей актуальной магистерской программой для инженеров по искусственному интеллектуУзнайте больше

Свойства алгоритма эвристического поиска

Алгоритмы эвристического поиска обладают следующими свойствами:

• Допустимое условие: если алгоритм дает оптимальный результат, он считается допустимым.
• Полнота: если алгоритм заканчивается решением, он считается завершенным.
• Свойство доминирования: если A1 и A2 представляют собой два эвристических алгоритма и имеют эвристические функции h1 и h2 соответственно, то A1 будет доминировать над A2, если h1 превосходит h2 для всех возможных значений узла n.
• Свойство оптимальности: если алгоритм является тщательным, допустимым и доминирует над другими алгоритмами, он будет оптимальным и, несомненно, даст оптимальный результат.

Различные категории методов эвристического поиска в ИИ

Мы можем разделить методы эвристического поиска на два типа:

Методы прямого эвристического поиска

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

Они используют произвольную последовательность операций и ищут решение во всем пространстве состояний. К ним относятся поиск в глубину (DFS) и поиск в ширину (BFS).

BFS — это метод эвристического поиска для построения диаграмм данных или быстрого сканирования пересечений или древовидных структур. DFS основан на вероятности того, что «последним пришёл — первым ушёл». Аналогично, структура данных стека LIFO используется для завершения процесса в рекурсии.

Слабые эвристические методы

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

Для изучения и расширения пользователям требуется дополнительная информация для вычисления предпочтений между дочерними узлами. К каждому узлу подключена эвристическая функция.

Давайте сначала рассмотрим некоторые стратегии, которые мы часто видим, прежде чем детализировать конкретные. Вот несколько примеров.

• А* Поиск
• Поиск по принципу «лучшее в первую очередь»
• Табу-поиск
• Двунаправленный поиск
• Постоянные проблемы с удовлетворением
• восхождение на холм

Станьте самым высокооплачиваемым инженером по искусственному интеллекту! С нашей актуальной магистерской программой для инженеров по искусственному интеллектуУзнайте больше

Примеры эвристических функций в ИИ

С помощью эвристической функции в ИИ можно решить самые разные проблемы.

Давайте поговорим о некоторых наиболее популярных из них.

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

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

Эта проблема может оказаться серьезной для небольшого числа городов. Но по мере роста числа городов найти решение становится все сложнее.

Эту проблему хорошо решает эвристика ближайшего соседа, которая предписывает компьютеру всегда выбирать ближайший неисследованный город в качестве следующей остановки на пути. Хотя NN лишь иногда предлагает оптимальное решение, часто оно настолько близко, что вариация незначительна и позволяет решить проблему продавца. Этот подход уменьшает сложность TSP с O(n!) до O (n^2).

Поисковая система

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

С нетерпением жду успешной карьеры в области искусственного интеллекта и машинного обучения. Зарегистрируйтесь в нашей программе профессиональной сертификации в области искусственного интеллекта и машинного обучения в сотрудничестве с Университетом Пердью прямо сейчас.

Заключение

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

Часто задаваемые вопросы

1. Что такое эвристическая функция, чтобы привести пример?

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

2. Где используется эвристическая функция?

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

3. Каковы виды эвристических функций?

Типы эвристических функций в AI:

Поиск в ширину (BFS) и поиск в глубину (DFS), двунаправленный поиск, поиск A*, имитация отжига, восхождение на холм, поиск наилучшего первого варианта и поиск по лучу.

4. Какова формула эвристической функции?

f(n)= g(n) + h(n), где

f(n)= ориентировочная стоимость самого дешевого решения

g(n)= стоимость достижения узла n из начального состояния

h(n)= стоимость достижения от узла n до целевого узла

5. Каковы четыре типа эвристик?

Четыре типа эвристики:

• Эвристика доступности
• Эвристика репрезентативности
• Эвристика привязки и корректировки
• Быстро и легко

Хотя все они уменьшают умственные усилия, необходимые для принятия решения, каждая эвристика применяется по-разному.

6. Каковы три типа эвристик?

Три эвристики, которые привлекли наибольшее внимание, — это репрезентативность, привязка и корректировка и доступность.