В последние годы алгоритмы для решения задач автоматического планирования и диспетчеризации стали вновь популярными в области машинного обучения. Понимание принципов их работы поможет увеличить производительность ваших моделей. К тому же, благодаря разработке таких мощных вычислительных технологий, как квантовых компьютеров, вскоре вновь будет использоваться искусственный интеллект, основанный на поиске.
Что такое алгоритм поиска в искусственном интеллекте?
Поиск в рамках искусственного интеллекта — это процесс перемещения из исходного состояния в целевое через промежуточные.
Почти любая задача в рамках искусственного интеллекта может быть сформулирована при помощи этих терминов:
- Состояние — потенциальные исходы в задаче.
- Переход — смена одного состояния другим.
- Исходное состояние — состояние системы на момент начала поиска. С него мы начинаем поиск.
- Промежуточное состояние — состояние, в которое совершается переход на пути от исходного к целевому.
- Целевое состояние — состояние, при достижении которого поиск останавливается.
- Область поиска — множество состояний.
Неинформированный поиск
Неинформированный поиск используется в том случае, когда нет информации о стоимости перехода из одного состояния в другое.
Существует три главных классических алгоритма неинформированного поиска:
- Поиск в глубину— обходит область поиска, используя LIFO-стек для определения следующей вершины.
Преимущества: хорошо работает в глубоких графах, эффективен по памяти.
Недостатки: есть вероятность зацикливания. - Поиск в глубину с итеративным углублением— обходит область поиска, используя LIFO-стек для определения следующей вершины. Когда алгоритм достигает заранее заданной глубины, он очищает стек, увеличивает счётчик достижения предельной глубины и запускает поиск заново из текущей вершины.
- Поиск в ширину— обходит область поиска, используя FIFO-очередь для определения следующей вершины.
Информированный поиск
Информированный поиск используется в том случае, когда мы знаем точную стоимость или же оценку стоимости смены состояний.
- UCS — обходит область поиска, используя очередь с приоритетом и текущий счёт. Текущий счёт для каждого состояния — стоимость достижения состояния из его родителя, то есть, из предыдущего состояния.
- A*— обходит область поиска, используя очередь с приоритетом и текущий счёт. Текущий счёт для каждого состояния — стоимость достижения состояния через его родителя в пути и эвристическая оценка стоимости перехода из текущей вершины в целевую.
Допустимое значение эвристической оценки должно удовлетворять следующим двум условиям: во-первых, эвристическая оценка должна быть меньше минимальной стоимости перехода из текущей вершины в целевую; во-вторых, она должна быть меньше эвристической оценки каждой из родительских вершин и стоимости достижения состояния в текущем пути. - IDA*— версия поиска A* с итеративным углублением.
Локальный поиск
Алгоритмы локального поиска используются в том случае, когда существует несколько возможных целевых состояний, но некоторые из них лучше других, то есть, возникает необходимость найти лучший из нескольких. Они довольно часто используются для оптимизации алгоритмов машинного обучения.
- Поиск восхождением к вершине — жадный итеративный алгоритм, выбирающий следующим состоянием наименее затратное, пока оно не достигнет локального максимума.
- Алгоритм имитации отжига — имитирует физический процесс, восходя к вершине, пока не достигнет локального максимума. При его достижении используется функция “температуры”, которая определяет: стоит ли окончить поиск или продолжать его в попытке найти лучшее решение.
- GSAT— алгоритм поиска восхождением к вершине на конъюнктивной нормальной форме. Для каждого возможного параметра подбирается случайное множество булевых значений. Если эти значения удовлетворяют предусловиям целевого состояния, то работа алгоритма завершена. Если же нет, то значения инвертируются таким образом, чтобы выражение соответствовало максимальному числу предусловий. Процесс повторяется заново с новым случайным множеством значений для ранее инвертированных переменных.
- Генетический алгоритм— генерируется исходная популяция состояний, из которой выбирается часть с наибольшим значением функции приспособленности. Оставшиеся состояния рандомно объединяются, немного мутируют, а затем вновь производится отбор лучших решений в следующее поколение.
- Лучевой поиск— UCS с сохранением значений правдоподобной вероятности значений текущего и предыдущего шага модели. На каждом шаге алгоритм отбирает N наиболее вероятных состояний для дальнейшего поиска.
- Метод Монте-Карло— рандомизированный алгоритм поиска, который возвращает лучшее приближение верного результата поиска. Он довольно быстрый, но не точный.
- Лас-Вегас— как и предыдущий, рандомизированный алгоритм, однако он прекращает свою работу лишь в том случае, если найден верный результат. Таким образом, алгоритм всегда точный, но зачастую медленный.
// алгоритм Лас-Вегас
repeat:
k = RandInt(n)
if A[k] == 1,
return k;
- Атлантик Сити — ограниченный вероятностный алгоритм поиска с полиномиальным временем работы. Он объединяет в себе сильные и слабые стороны алгоритмов Монте-Карло и Лас-Вегас.
Читайте также:
- Топ-10 ошибок анализа данных
- Для чего нужны стеки?
- Алгоритмы машинного обучения простым языком. Часть 1
Перевод статьи Aaron (Ari) Bornstein: AI Search Algorithms Every Data Scientist Should Know
