Основы теории оптимизации (стр. 29 )

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

Процесс поиска начинается из начального приближения х°, которое принимается за базовую точку хr, характеризующуюся тем, что она является исходной точкой очередной итерации. Каждая итерация состоит из двух процедур: «пробного движения» в Δ-окрестности текущей точки испытания и «движения в допустимом направлении», т. е. в направлении вдоль которого гарантируется уменьшение функции Q(х). Процедура «пробного движения» заключается в обследовании Δ-окрестности базовой точки хr с целью определения допустимого (удачного в смысле уменьшения функции Q (х)) направления Sr. Для этого в циклическом порядке, начиная с i = 1, по формуле (1) изменяется каждая переменная xi, i = 1,2, …, n, где размер шага вдоль координатного направления Ii выбирается из условия (2). При этом начальный размер шага Δi для каждой из переменных может иметь различные значения. Если полученное значение λir не равно нулю, то при выполнении пробного движения вдоль (i+1)-й координаты в качестве значения Q(хr) рассматривается либо Q(хr+ΔiIi) (если λir=Δi), либо Q (хr – ΔiIi) (если λir = – Δi). После просмотра всех координатных направлений Ii получается точка xnr, в которой значение функции Q (хnr) меньше или равно значению функции в базовой точке Q (хr). Если окажется, что хnr = хr т. е. величина принятого пробного шага Δ настолько велика, что не позволяет определить допустимого направления, то необходимо его уменьшить (Δi = Δi/β, β > 1) и повторить пробные движения снова. Таким образом, по мере приближения к точке минимума х* длина пробного шага Δ уменьшается. Поиск считается законченным, если размер всех пробных шагов Δi, i=1, 2, …, n, станет меньше заданной точности ε.
В случае выполнения неравенства

Q (xnr) < Q (хr)

в качестве допустимого направления Sr выбирается вектор (xnr – хr), который указывает направление поиска вдоль дна оврага минимизируемой функции. Периодическое повторение пробных движений позволяет подстраивать траекторию поиска вдоль дна оврага в тех случаях, когда (вследствие криволинейности оврага) установленное на предыдущей r-й итерации допустимое направление Sr оказывается неудачным для (r + 1)-й итерации.

Процедура «движения в заданном направлении» сводится к следующей последовательности действий. Вдоль направления определяется по формуле

xir+1 = xr + h(xnr – xr), (5)

где h > 1 шаг вдоль допустимого направления.

После каждого шага i = 1, 2,…, вдоль допустимого направления относительно точки хir+1 проводится процедура «пробного движения», целью которой является определение, не нуждается ли направление S в коррекции. Если полученная после проведения n пробных движений точка xinr+1 не совпадает с точкой хir+1, то в качестве скорректированного допустимого направления выбирается вектор (хinr+1 – хir+1), вдоль которого делается шаг h > 1:

хi+1r+1 = хir + h(хinr+1 – хir+1), (6)

где xir+1 — «удачная точка» вдоль допустимого направления Sr. Если точка хinr лежит на одной прямой с точками хr и хnr, то направление Sr сохраняется (не корректируется). В обоих случаях вычисление функции Q(х) вдоль допустимого направления продолжается до тех пор, пока в очередных точках испытания хi+1r+1 получаются уменьшающиеся значения функции Q(х). Когда в допустимом направлении не удается найти точку испытания xi+1r+1 с меньшим значением функции Q(х), то поиск в направлении Sr считается законченным. В этом случае точка предыдущего удачного испытания xir+1 выбирается в качестве базовой точки для (r+1)-й итерации, из которой делается пробное движение с целью определения нового допустимого направления Sr+1.

На рис. 1 показана траектория поиска, реализующая пробные движения и движения в допустимом направлении для функции Q (x1, x2) «овражного» типа.

Рис. 1. Траектория поиска по методу конфигураций минимума функции Q(x) с «криволинейным» оврагом

Применение алгоритма F31 оказывается эффективным при минимизации функций Q (х) с «прямолинейными оврагами». В этом случае экспериментально показано, что число испытаний, необходимое для локализации точки минимума х* с заданной точностью ε, прямо пропорционально числу переменных n.

Недостатком алгоритма является то, что в процессе проведения пробных движений направление дна оврага может быть пропущено, так как пробные шаги делаются только параллельно координатным осям. По этой же причине поиск может «остановиться» на дне оврага вдали от точки истинного минимума х*, если в базовой точке линии уровня минимизируемой функции (Q (х) = const) очень изогнуты.

Алгоритм метода конфигураций (метод Хука-Дживса)

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

Эта процедура продолжается до тех пор, пока в окрестностях базисных точек удается находить приемлемые направления спуска.

Алгоритм

Шаг 1. Задаются начальное приближение (первая базисная точка)

,

начальный шаг h для поиска направления спуска, точность решения d (предельное значение для шага h). Присваивается k=0.

Шаг 2. (Первый этап). Определяется направление минимизации целевой функции f(x)=f(x(1), x(2),…,x(n)) в базисной точке

. Для этого последовательно дают приращение переменным x(j) в точке хк. Присвоим z=xk. Циклически даем приращение переменным x(j) и формируем z(j)=xk(j)+h, если f(z)<f(xk), если же нет, то z(j)=xk(j)-h, если f(z)<f(xk), иначе z(j)=xk(j). Так для всех j (j=1,2,…,n).

Шаг 3. Если z=xk, то есть не определилось подходящее направление, то обследование окрестности базисной точки хк повторяется, но с меньшим шагом h (например, h=h/2).

  Если h>d, то перейти к шагу 2, то есть повторить обследование точки хk.

Если h£d, то поиск заканчивается, то есть достигнуто предельное значение для шага h и найти приемлемое направление спуска не удается. В этом случае полагается  .

Шаг 4. (Второй этап). Если z¹xk, то требуется найти новую базисную точку в направлении  вектора z-xk: xk+1=xk + l(z-xk), где l - коэффициент «ускорения поиска». Определяется такое значение l=lk, при котором достигается наименьшее значение целевой функции в выбранном направлении, то есть функции  f(xk +l(z-xk) = j(l).

В зависимости от способа выбора lk возможны варианты метода:

а) lk=l=const постоянная для всех итераций;

б) задается начальное l0=l, а далее lk=lk-1, если f(xk+1)<f(xk), иначе дробим lk, пока не выполнится это условие;

в) lk определяется решением задачи одномерной минимизации функции j(l).

  Таким образом определяется новая базисная точка xk+1=xk + l(z-xk). Полагаем k=k+1 и поиск оптимального решения повторяется с шага 2.

Для устранения отмеченного выше недостатка метода конфигураций в алгоритме F32, реализующем метод вращающихся координат, предлагается вместо того, чтобы изменять каждую переменную xi независимо параллельно координатной оси, осуществлять на r-й итерации преобразование системы координат (х) таким образом, чтобы в новой системе координат (ξ) одна из осей совпадала с направлением дна оврага, а остальные были бы к ней ортогональны. После проведения одномерного поиска вдоль n взаимно ортогональных направлений строится новая система координат, и так до тех пор, пока точка минимума х* не будет локализована с заданной точностью ε.

Первая итерация в алгоритме F32 полностью совпадает с процедурой поиска по методу Гаусса — Зейделя F30. Вдоль направлений Ii, i = 1,2, …, n, параллельных координатным осям, поочередно решается одномерная задача оптимизации (4). На последующих итерациях одномерная задача оптимизации решается для каждого линейно-независимого взаимно ортогонального направления ξi, i = 1, 2, …, n. Начиная с базовой точки хr, определяется шаг λ1r вдоль направления ξ1r, при котором достигается min Q (хr + λ1ξ1r).