Методы случайного поиска. Адаптивный метод случайного поиска. Метод случайного поиска с возвратом при неудачном шаге

Страницы работы

Фрагмент текста работы

Методы случайного поиска

Постановка задачи

Пусть дана функция f(x), ограниченная снизу на множестве Rn и имеющая непрерывные частные производные во всех его точках.

Требуется найти безусловный минимум функции f(x) многих переменных, т.е. найти такую точку x*ÎRn, что

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

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

Стратегия поиска

Задается начальная точка x0. Каждая последующая точка находится по

формуле

гдеtk > 0 – величина шага; xk – случайный вектор единичной длины (определяется в n-мерном пространстве и предполагается что он с равной степенью вероятности может принимать любое направление в этом пространстве), определяющий направление поиска; k– номер итерации. На текущей итерации при помощи генерирования случайных векторов xk получаются точки, лежащие на гиперсфере радиуса tk с центром в точке xk (рисунок 1). Если значение функции в полученной точке не меньше, чем в центре, шаг считается неудачным (точки y1, y2 при поиске из x0; y1, y3 при поиске из x1). Если число неудачных шагов из текущей точки достигает некоторого числа М, дальнейший поиск продолжается из той же точки, но с меньшим шагом до тех пор, пока он не станет меньше заранее заданной величины R. Если же значение функции в полученной точке меньше, чем в центре, шаг считается

удачным и в найденном направлении делается увеличенный шаг, играющий роль ускоряющего шага. Если при этом значение функции снова меньше, чем в центре, направление считается удачным и дальнейший поиск продолжается из этой точки (точки z3 = x1 при поиске из x0, z4 = x2 при поиске из x1). Если же значение функции стало не меньше, чем в центре, направление считается неудачным и поиск продолжается из старого центра (в точке y2 при поиске из x1 функция меньше, чем в x1, а в точке z2 уже не меньше, поэтому направление (z2x1) неудачное).

Рисунок 1

Алгоритм

Шаг 1. Задаем начальную точку x0, коэффициенты расширения a≥1 и 0<b<1, M – максимальное число неудачно выполненных испытаний на текущей итерации, t0 = 1 – начальную величину шага, R – минимальную величину шага, N – максимальное число итераций. Полагаем k=0, j=1.

Шаг 2. Получаем случайный вектор  где xij – случайная величина, равномерно распределенная на интервале [–1, 1].

Шаг 3. Вычисляем

Шаг 4. Проверяем выполнение условий

а) если f(yj) < f(xk), шаг удачный. Полагаем zj = xk + a(yjxk). Определяем, является ли текущее направление yjxk удачным:

-  если f(zj) < f(xk), направление поиска удачное. Полагаем xk+1 = zj, tk+1 = atk, k=k+1 и проверяем условие окончания. Если k<N, полагаем j=1 и переходим к шагу 2. Если k=N, поиск завершаем: x* @ xk;

-  если f(zj) ≥ f(xk), направление поиска неудачное, переходим к шагу 5;

б) если f(yj) ≥ f(xk), шаг неудачный и переходим к шагу 5.

Шаг 5. Оцениваем число неудачных шагов из текущей точки:

а) если j<М, полагаем j= j + 1 и переходим к шагу 2;

б) если j=М, проверяем условие окончания:

-  если tkR, процесс заканчивается: x* @ xk, f(x*) @ f(xk);

-  если tk> R, полагаем tk= btk, j=1 и переходим к шагу 2.

Замечания:

1. Величина xij, равномерно распределенная на интервале [–1, 1], генерируется обычно с помощью датчиков псевдослучайных чисел на ЭВМ. Вырабатывается случайная величина hij, равномерно распределенная на интервале [0, 1], а затем используется линейное преобразование: xij = 2hij – 1.

2. Рекомендуются следующие параметры алгоритма: a = 1,618; b = 0,618; М = 3n. Начальный шаг t0R можно задать произвольно.

3. Если выполнено условие окончания tkR, то в качестве ответа можно использовать любую точку внутри шара с радиусом tk и центром в точке xk.

Метод случайного поиска с возвратом при неудачном шаге

Стратегия поиска

Задается начальная точка x0. Каждая последующая точка находится по

формуле

гдеtk > 0 – величина шага; xk – случайный вектор единичной длины, определяющий направление поиска; k– номер итерации. На текущей итерации при помощи генерирования случайных векторов xk получаются точки, лежащие на гиперсфере радиуса tk с центром в точке xk (рисунок 2). Если значение функции в полученной точке не меньше, чем в центре, шаг считается неудачным (точки y1, y2 при поиске

из x0; y1, y2, y3 при поиске из x1), происходит возврат в текущий центр и поиск продолжается. Если число неудачных шагов из текущей точки достигает некоторого числа М, дальнейший поиск продолжается из той же точки, но с меньшим шагом до тех пор, пока он не станет меньше заранее заданной величины R. Если же значение функции в полученной точке меньше, чем в центре, шаг считается удачным и дальнейший поиск продолжается из этой точки.

Алгоритм

Рисунок 2

Шаг 1. Задаем начальную точку x0, коэффициент сжатия 0<b<1, M – максимальное число неудачно выполненных испытаний на текущей итерации, t0 = 1 – начальную величину шага, R – минимальную величину шага, N – максимальное число итераций. Полагаем k=0, j=1.

Шаг 2. Получаем случайный вектор  где xij – случайная величина, равномерно распределенная на интервале [–1, 1].

Шаг 3. Вычисляем

Шаг 4. Проверяем выполнение условий

а) если f(yj) < f(xk), шаг удачный. Полагаем xk+1 = yj, tk+1 = tk, k=k+1 и проверяем условие окончания. Если k<N, полагаем j=1 и переходим к шагу 2. Если k=N, поиск завершаем: x* @ xk;

б) если f(yj) ≥ f(xk), шаг неудачный и переходим к шагу 5.

Шаг 5. Оцениваем число неудачных шагов из текущей точки:

а) если j<М, полагаем j= j + 1 и переходим к шагу 2;

б) если j=М, проверяем условие окончания:

-  если tkR, процесс заканчивается: x* @ xk, f(x*) @ f(xk);

-  если tk> R, полагаем tk= btk, j=1 и переходим к шагу 2.

Метод наилучшей пробы

Стратегия поиска

Задается начальная точка x0. Каждая последующая точка находится по

формуле

гдеtk > 0 – величина шага; xk – случайный вектор единичной длины, определяющий направление поиска; k– номер итерации. На текущей итерации при помощи генерирования случайных векторов xk получаются М точек y1, …, yМ, лежащих на гиперсфере радиуса tk с центром в точке xk (рисунок

Похожие материалы

Информация о работе

Тип:
Конспекты лекций
Размер файла:
86 Kb
Скачали:
0