Алгоритмы локального поиска

Август 20, 2022

Главная
Информатика
Алгоритмы локального поиска

Содержание

2. АЛГОРИТМЫ ПОИСКА Алгоритмы локального поиска — группа алгоритмов, в которых поиск ведется только на основании текущего
3. ИСПОЛЬЗОВАНИЕ Алгоритмы локального поиска используются в том случае, когда существует несколько возможных целевых состояний, но некоторые
4. ПОИСК ВОСХОЖДЕНИЕМ К ВЕРШИНЕ Жадный итеративный алгоритм, выбирающий следующим состоянием наименее затратное, пока оно не достигнет
5. АЛГОРИТМ ИМИТАЦИИ ОТЖИГА Имитирует физический процесс, восходя к вершине, пока не достигнет локального максимума. При его
6. ГЕНЕТИЧЕСКИЙ АЛГОРИТМ Генерируется исходная популяция состояний, из которой выбирается часть с наибольшим значением функции приспособленности. Оставшиеся
7. ЛУЧЕВОЙ ПОИСК UCS (алгоритм Дейкстры) с сохранением значений правдоподобной вероятности значений текущего и предыдущего шага модели.
8. МЕТОДЫ МОНТЕ-КАРЛО Группа численных методов для изучения случайных процессов. Суть метода заключается в следующем: процесс описывается
9. МЕТОД МОНТЕ-КАРЛО ДЛЯ ПОИСКА В ДЕРЕВЕ ВЫБОР Каждую позицию мы рассматриваем как задачу многорукого бандита. Узлы
11. Скачать презентацию

Слайд 2

АЛГОРИТМЫ ПОИСКА
Алгоритмы локального поиска — группа алгоритмов, в которых поиск ведется

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

Слайд 3

ИСПОЛЬЗОВАНИЕ
Алгоритмы локального поиска используются в том случае, когда существует несколько возможных

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

Слайд 4

ПОИСК ВОСХОЖДЕНИЕМ К ВЕРШИНЕ
Жадный итеративный алгоритм, выбирающий следующим состоянием наименее затратное,

пока оно не достигнет локального максимума.

Слайд 5

АЛГОРИТМ ИМИТАЦИИ ОТЖИГА
Имитирует физический процесс, восходя к вершине, пока не достигнет

локального максимума. При его достижении используется функция “температуры”, которая определяет: стоит ли окончить поиск или продолжать его в попытке найти лучшее решение.

Слайд 6

ГЕНЕТИЧЕСКИЙ АЛГОРИТМ
Генерируется исходная популяция состояний, из которой выбирается часть с наибольшим

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

Слайд 7

ЛУЧЕВОЙ ПОИСК
UCS (алгоритм Дейкстры) с сохранением значений правдоподобной вероятности значений текущего

и предыдущего шага модели. На каждом шаге алгоритм отбирает N наиболее вероятных состояний для дальнейшего поиска.

Слайд 8

МЕТОДЫ МОНТЕ-КАРЛО
Группа численных методов для изучения случайных процессов. Суть метода

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

Слайд 9

МЕТОД МОНТЕ-КАРЛО ДЛЯ ПОИСКА В ДЕРЕВЕ
ВЫБОР
Каждую позицию мы рассматриваем как задачу

многорукого бандита. Узлы на каждом этапе выбираются согласно алгоритму UCB. Эта фаза действует до тех пор, пока не будет найден узел в котором еще не все дочерние узлы имеют статистику побед. На рисунке первое значение в узле это количество побед, второе общее количество игр в этом узле.

РАСШИРЕНИЕ

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

СИМУЛЯЦИЯ

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

Алгоритмы локального поиска

Содержание

АЛГОРИТМЫ ПОИСКААлгоритмы локального поиска — группа алгоритмов, в которых поиск ведется

ИСПОЛЬЗОВАНИЕАлгоритмы локального поиска используются в том случае, когда существует несколько возможных

ПОИСК ВОСХОЖДЕНИЕМ К ВЕРШИНЕЖадный итеративный алгоритм, выбирающий следующим состоянием наименее затратное,

АЛГОРИТМ ИМИТАЦИИ ОТЖИГАИмитирует физический процесс, восходя к вершине, пока не достигнет

ГЕНЕТИЧЕСКИЙ АЛГОРИТМГенерируется исходная популяция состояний, из которой выбирается часть с наибольшим

ЛУЧЕВОЙ ПОИСКUCS (алгоритм Дейкстры) с сохранением значений правдоподобной вероятности значений текущего

МЕТОДЫ МОНТЕ-КАРЛО Группа численных методов для изучения случайных процессов. Суть метода

МЕТОД МОНТЕ-КАРЛО ДЛЯ ПОИСКА В ДЕРЕВЕ ВЫБОРКаждую позицию мы рассматриваем как задачу

Похожие презентации