Лекция 4 (1121244)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Л.А. Растригин. Статистические методы поиска.- М.: Наука, 1968.

Основой методов случайного поиска служит итерационный процесс:

_k – величина шага,

  (₁,,_n) – некоторая реализация n-мерного случайного вектора .

min f(X)

g_i(X)  0, i=1,,m (1.1.)

X  S

Н
енаправленный случайный поиск (метод Монте-Карло)

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

1. Алгоритмом выбора пробных состояний на текущем шаге.

2. Решающим правилом, по которому на каждом шаге выбирается новое текущее приближение решения.

Алгоритмы направленного случайного поиска:

• алгоритм с парной пробой,

• алгоритм с возвратом при неудачном шаге,

• алгоритм с линейной экстраполяцией,

• алгоритм наилучшей пробы,

• алгоритм статистического градиента.

C1<C2<C3

Построить алгоритм с возвратом при неудачном шаге.

min f(X)

g_i(X)  0, i=1,,m (1.1.)

X  S

Шаг 1. Выбрать:

• параметр точности ε > 0,

• начальный шаг α > 0,

• коэффициент уменьшения шага γ > 1,

• предельное число неудачных попыток K,

• начальное приближение .

Вычислить:

целевую функцию .

Шаг 2. построить алгоритм

Шаг 1. Выбрать:

• параметр точности ε > 0,

• начальный шаг α > 0,

• коэффициент уменьшения шага γ > 1,

• предельное число неудачных попыток K,

• начальное приближение .

Вычислить: целевую функцию .

Шаг 2. Установить счетчик неудачных попыток: j=1.

Шаг 3. Получить реализацию случайного вектора ξ.

Шаг 4. Найти пробную точку: .

Шаг 5. Проверить выполнение ограничений и Y∈S. Если ограничения выполняются, то перейти к шагу 6, иначе к шагу 3 (возможно также считать это неудачной попыткой – переход к шагу 7).

Шаг 6. Вычислить f(Y). Если f(Y) < f(X), то X = Y, f(X) = f(Y), и перейти к шагу 3. Иначе, перейти к шагу 7.

Шаг 7. Увеличить счетчик попыток j = j + 1. Если j ≤ K, то перейти к шагу 3, иначе к шагу 8.

Шаг 8. Проверка условия достижения точности. Если α < ε, то поиск завершить, полагая , . Иначе – положить

α = α/γ и перейти к шагу 2.

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

Это достигается введением вектора памяти

- вероятность выбора положительного направления по j-ой координате на k-ом шаге.

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

1. Алгоритмом выбора пробных состояний на текущем шаге.

2. Решающим правилом, по которому на каждом шаге выбирается новое текущее приближение решения.

3. Алгоритмом самообучения, которые корректирует вектор предыстории с точки зрения информации, полученной на текущем шаге.

Самообучение методом исключения.

Ограничение – число возможных направлений конечно.

Исключаются из рассмотрения «неудачные» направления → повышается вероятность отыскания «удачных» направлений.

Недостаток - большой объем памяти.

Покоординатное экспоненциальное обучение.

Элементы вектора Х изменяются на строго определенную по модулю величину. Она одинакова для всех элементов. Разница лишь в направлении изменения.

Число возможных направлений:

Алгоритм покоординатного самообучения с произвольным законом изменения вероятности.

Пусть

Вид функции может быть различным, но она должна быть:

• монотонной,

• неубывающей.

Линейная зависимость:

Экспоненциальная зависимость:

- шаг, определяющий скорость обучения.

Избежать передетерминирования можно наложив ограничения на область изменения w:

Чувствительность алгоритма к выбору наилучшего направления поиска можно улучшить, учитывая степень участия каждого элемента вектора Х в изменении целевой функции:

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

k – параметр забывания

При отсутствии опыта и алгоритм вырождается в равновероятностный поиск:

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

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

d выбирается так чтобы всегда обеспечивалось неравенство:

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лекций