Метод хука дживса excel
Аннотация: Данная лекция рассматривает основные методы решения задач многомерной оптимизации, в частности, такие как метод Хука – Дживса, метод Нелдера – Мида, метод полного перебора (метод сеток), метод покоординатного спуска, метод градиентного спуска.
До сих пор мы обсуждали одномерные задачи оптимизации, в которых целевая функция зависела только от одного аргумента. Однако подавляющее число реальных задач оптимизации, представляющих практический интерес, являются многомерными: в них целевая функция зависит от нескольких аргументов, причем иногда их число может быть весьма большим.
Математическая постановка таких задач аналогична их постановке в одномерном случае: ищется наименьшее (наибольшее) значение целевой функции, заданной на некотором множестве G возможных значений ее аргументов.
Как и в одномерном случае, характер задачи и соответственно возможные методы решения существенно зависят от той информации о целевой функции, которая нам доступна в процессе ее исследования. В одних случаях целевая функция задается аналитической формулой, являясь при этом дифференцируемой функцией. Тогда можно вычислить ее частные производные , получить явное выражение для градиента, определяющего в каждой точке направления возрастания и убывания функции, и использовать эту информацию для решения задачи. В других случаях никакой формулы для целевой функции нет, а имеется лишь возможность определить ее значение в любой точке рассматриваемой области (с помощью расчетов, в результате эксперимента и т.д.). В таких задачах в процессе решения мы фактически можем найти значения целевой функции лишь в конечном числе точек, и по этой информации требуется приближенно установить ее наименьшее значение для всей области.
1. Метод Хука – Дживса
Этот метод был разработан в 1961 году, но до сих пор является весьма эффективным и оригинальным. Поиск состоит из последовательности шагов исследующего поиска вокруг базисной точки, за которой в случае успеха следует поиск по образцу.
Описание этой процедуры представлено ниже:
А. Выбрать начальную базисную точку b1 и шаг длиной hj для каждой переменной xj, j = 1, 2, . n . В приведенной ниже программе для каждой переменной используется шаг h , однако указанная выше модификация тоже может оказаться полезной.
Б. Вычислить f(x) в базисной точке b1 с целью получения сведений о локальном поведении функции f(x) . Эти сведения будут использоваться для нахождения подходящего направления поиска по образцу, с помощью которого можно надеяться достичь большего убывания значения функции. Функция f(x) в базисной точке b1 находится следующим образом:
1. Вычисляется значение функции f(b1) в базисной точке b1 .
2. Каждая переменная по очереди изменяется прибавлением длины шага.
Таким образом, мы вычисляем значение функции f(b1 + h1e1) , где e1 - единичный вектор в направлении оси х1 . Если это приводит к уменьшению значения функции, то b1 заменяется на b1 + h1e1 . В противном случае вычисляется значение функции f(b1 – h1e1) , и если ее значение уменьшилось, то b1 заменяем на b1-h1e1 . Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b1 остается неизменной и рассматриваются изменения в направлении оси х2 , т.е. находится значение функции f(b1 + h2e2) и т.д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b2 .
3. Если b2 = b1 , т.е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки b1 , но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.
4. Если , то производится поиск по образцу.
В. При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом:
1. Разумно двигаться из базисной точки b1 в направлении b2 - b1 , поскольку поиск в этом направлении уже привел к уменьшению значения функции. Поэтому вычислим функцию в точке образца
![]() | ( 1.1) |
![]() | ( 1.2) |
2. Затем исследование следует продолжать вокруг точки P1 ( Pj ).
3. Если наименьшее значение на шаге В,2 меньше значения в базисной точке b2 (в общем случае bj+1 ), то получают новую базисную точку b3 (bj+2) , после чего следует повторить шаг В,1. В противном случае не производить поиск по образцу из точки b2 (bj+1) а продолжить исследования в точке b2 (bj+1) .
Г. Завершить этот процесс, когда длина шага (длины шагов) будет уменьшена до заданного малого значения.
Шаг 2. Сделать пробный шаг y= – Dje j , где e j –j–й базисный вектор. Если f ( ) £ f (y), то перейти к шагу 3, иначе – к шагу 4.
Шаг 3. Сделать пробный шаг y= +Dje j . Если f ( ) £ f (y), то перейти к шагу 5, иначе – к шагу 4.
Шаг 4. Положить = у.
Шаг 5. Положить j = j + 1. Если j £ n, то перейти к шагу 2. В противном случае исследующий поиск окончен – получена точка для которой f ( ) f (y), если ¹ х.
Замечание. В результате исследующего поиска может оказаться, что =х. Тогда исследующий поиск считается неудачным. Если при этом норма приращения D =(D1. Dn ) мала, т.е. ||D|| £ e, где e – заданная точность, то полагают х * = х. Если заданная точность не достигнута, то полагают D=D/g (постоянная g >1 – коэффициент уменьшения шага) и повторяют исследующий поиск.
Приведем теперь полный алгоритм Хука – Дживса.
Шаг 0. Выбрать начальную точку х 0 , вектор приращений D =(D1. Dn ), коэффициент уменьшения шага g >1, параметр окончания поиска e > 0.
Шаг 1. Провести исследующий покоординатный поиск из точки х 0 , т.е. найти точку . Если ¹ х , то перейти к шагу 3, иначе – к шагу 2.
Шаг 3. Перемещение из точки х в направлении убывания – х 0 : положить х 1 = + ( – х 0 ) = 2 – х 0 .
Шаг 4. Провести исследующий поиск в точке х 1 , т.е. найти точку . Если f ( ) < f ( ), то положить х 0 = , = и перейти к шагу 3. Иначе – положить х 0 = и перейти к шагу 1.
Пример 3.7. Рассмотрим графическую иллюстрацию решения задачи f (х)=(x1+ 1) 2 +х 2 2 ®min методом Хука – Дживса из начальной точки х 0 =(2,3),вектор перемещений D=(1/2,1).
Целевая функция f (х) представляет собой квадрат расстояния между точками х и х * =(–1,0). Линии уровня f (х) – это окружности с центром в точке х * . Поэтому значения f (х) в промежуточных точках алгоритма легко сравнивать, оценивая их расстояния от точки х * на рис. 3.9. На рисунке пунктиром выделены траектории исследующего поиска, сплошными линиями – перемещения в направлении убывания. Убедитесь в соответствии графической иллюстрации описанному алгоритму.
Все описанные выше прямые методы безусловной минимизации функции многих переменных содержат детерминированные процедуры поиска точек с меньшим значением функции.
Однако разработано довольно много методов минимизации, где в процедуру поиска точек минимума намеренно вводят элементы случайности.
Процедура Хука-Дживса представляет собой комбинацию "исследующего" поиска с циклическим изменением переменных и ускоряющего поиска по найденному образцу. Исследующий поиск ориентирован на выявление направления вдоль "оврагов". Полученная в результате исследующего поиска информация используется затем в процессе поиска по образцу при движении по "оврагам".
Исследующий поиск:
Для проведения исследующего поиска необходимо задать величину шага, которая может быть различна для разных координатных направлений, и изменяться в процессе поиска. Поиск начинается в некоторой исходной точке. Делается пробный шаг вдоль одного из координатных направлений. Если значение целевой функции в пробной точке меньше, чем в исходной, то шаг считается удачным. В противном случае возвращаются в исходную точку и делают шаг в противоположном направлении. После перебора всех координат исследующий поиск заканчивается. Полученную в результате исследующего поиска точку называют базовой.
Поиск по образцу:
Поиск по образцу заключается в реализации единственного шага из полученной базовой точки вдоль прямой, соединяющей эту точку с предыдущей базовой точкой. Новая точка определяется по формуле:
Как только движение по образцу не приводит к уменьшению целевой функции, точка фиксируется в качестве временной базовой точки и выполняется исследующий поиск. При уменьшении значения целевой функции эта точка рассматривается как базовая точка. Если же исследующий поиск не дал результата, необходимо вернуться в предыдущую точку и провести исследующий поиск заново. Если такой поиск не приводит к успеху, то необходимо уменьшить величину шага. Поиск завершается, когда величина шага приращения становится достаточно малой.
Шаг 1. Задать: 1. Начальную точку ;
2. Приращение , ;
3. Коэффициент уменьшения шага ;
4. Параметр окончания поиска .
Шаг 2. Произвести исследующий поиск.
Шаг 3. Поиск удачный:
Да: перейти к шагу 5;
Шаг 4. Проверка на окончание поиска: ?
Да: прекратить поиск;
Нет: уменьшить приращение по формуле:
, ; Перейти к шагу 2.
Шаг 5. Провести поиск по образцу:
Шаг 6. Провести исследующий поиск, используя в качестве базовой точки: - полученная в результате точка
Шаг 7. Выполняется ли условие ?
Да: продолжить ; ;
перейти к шагу 5;
Нет: перейти к шагу 4.
Исходные данные:
Пусть .
Для того, чтобы применить данный метод необходимо задать следующие величины:
Итерации начинаются с исследующего поиска вокруг точки , которой соответствует значение функции
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Шаг 3. Таким образом, в результате исследующего поиска была найдена точка
Поскольку исследующий поиск был удачным, переходим к поиску по образцу:
Далее производим исследующий поиск вокруг точки :
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Получаем новую точку:
Поскольку , поиск по образцу следует считать успешным и становится новой базовой точкой при следующем проведении поиска по образцу:
Далее производим исследующий поиск вокруг точки :
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Получаем новую точку:
Поскольку , поиск по образцу следует считать успешным и становится новой базовой точкой при следующем проведении поиска по образцу:
Далее производим исследующий поиск вокруг точки :
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Получаем новую точку:
Поскольку , поиск по образцу следует считать удачным, и становится новой базовой точкой при следующем проведении поиска по образцу:
Далее производим исследующий поиск вокруг точки :
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Получаем новую точку:
Поскольку , поиск по образцу следует считать успешным и становится новой базовой точкой при следующем проведении поиска по образцу:
Далее производим исследующий поиск вокруг точки :
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Получаем новую точку:
Поскольку , поиск по образцу следует считать неудачным, отбрасывается и становится новой базовой точкой при следующем проведении исследующего поиска :
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Получаем новую точку:
Поскольку исследующий поиск был удачным, переходим к поиску по образцу:
Далее производим исследующий поиск вокруг точки :
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Получаем новую точку:
Поскольку , поиск по образцу следует считать успешным и становится новой базовой точкой при следующем проведении поиска по образцу:
Далее производим исследующий поиск вокруг точки :
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Получаем новую точку:
Поскольку , поиск по образцу следует считать успешным и становится новой базовой точкой при следующем проведении поиска по образцу:
Далее производим исследующий поиск вокруг точки :
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Получаем новую точку:
Поскольку , поиск по образцу следует считать успешным и становится новой базовой точкой при следующем проведении поиска по образцу:
Далее производим исследующий поиск вокруг точки :
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Получаем новую точку:
Поскольку , поиск по образцу следует считать неудачным,
отбрасывается и становится новой базовой точкой при следующем проведении исследующего поиска :
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Исследующий поиск не дал результатов, поэтому уменьшаем шаг: , базовая точка
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Получаем новую точку:
Поскольку исследующий поиск был удачным, переходим к поиску по образцу:
Далее производим исследующий поиск вокруг точки :
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Получаем новую точку:
Поскольку , поиск по образцу следует считать неудачным,
отбрасывается и становится новой базовой точкой при следующем проведении исследующего поиска :
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Исследующий поиск не дал результатов, поэтому прекращаем поиск. Искомая точка оптимума:
Решение поставленной задачи методом Хука-Дживса представлено на рисунке 2.
Метод Хука-Дживса относятся к категории эвристических методов (методам прямого поиска). Методы прямого поиска используют не менее n независимых направлений, где n -размерность вектора.
Элементарным примером метода, реализующего процедуру рекурсивного перебора на множестве направлений поиска, является метод циклического изменения переменных - каждый раз меняется только одна переменная. Затем вдоль каждого из координатных направлений последовательно проводится поиск точки экстремума на основе методов одномерной минимизации. Однако, если линии уровня ЦФ имеют овражный характер, то процедура поиска становится неэффективной и даже может привести к отсутствию сходимости к точке локального extr , если изменение координатных направлений поиска осуществляется в циклическом порядке (показано Пауэллом).
Модифицированный метод Хука-Дживса позволяет существенно ускорить сходимость за счет того обстоятельства, что поиск периодически проводится в направлении d i =x i -x i -1 .
По существу процедура Хука–Дживса представляет собой комбинацию двух поисков:
а) исследующий поиск (для выявления характера локального поведения ЦФ и определения направления движения вдоль "оврагов") с циклическим изменением переменных;
б) ускоряющий поиск по образцу с использованием определенных эвристических правил.
Исследующий поиск. Выбирается некоторая исходная точка x 0 . Задается величина шага ∆i, которая может быть различной для разных координатных направлений и изменяться в процессе поиска.
Если значение ЦФ в пробной точке меньше значения ЦФ в исходной точке, то шаг поиска успешный. В противном случае из исходной точки делается шаг в противоположном направлении. После перебора всех n координат исследующий поиск завершается. Полученная точка называется базовой.
Поиск по образцу. Осуществляется шаг из полученной базовой точки вдоль прямой, соединяющей эту точку с предыдущей базовой. Новая точка образца определяется по формуле:
xp k +1 =x k +(x k -x k -1 ).
Как только движение по образцу не приводит к уменьшению ЦФ, точка xp k +1 фиксируется в качестве временной базовой точки и вновь проводится исследующий поиск. Если в результате получается точка с меньшим значением ЦФ, чем в точке x k , то она рассматривается как новая базовая точка x k +1 . Но если исследующий поиск неудачен, то следует вернуться в точку x k и провести исследующий поиск с целью выявления нового направления минимизации. В конечном итоге возникает ситуация, когда такой поиск не приводит к успеху. В этом случае уменьшается шаг путем введения коэффициента α и возобновляется исследующий поиск.
Если исследуемая функция имеет овражный вид, то предпочтительнее использовать метод Хука-Дживса, а не метод Нелдера-Мида, так как в первом методе мы можем регулировать шаг в направлении убывания функции, в то время как во втором методе мы этого сделать не можем.
Схема алгоритма Хука–Дживса
Введем следующие обозначения: x k - текущая базовая точка; x k -1 - предыдущая базовая точка; xp k +1 - точка, построенная при движении по образцу; x k +1 - следующая (новая) базовая точка.
Критерий останова: |∆x|≤ε.
Шаг 1. Определить начальную точку x 0 ; приращения (шаги) ∆i; коэффициент уменьшения шага α>1; параметр окончания поиска εШаг 2. Провести исследующий поиск.
Шаг 3. Был ли исследующий поиск удачным (найдена ли точка с меньшим значением ЦФ)?
Да: переход на Шаг 5. Нет: продолжить, т.е. переход на Шаг 4.
Шаг 4. Проверка на окончание поиска. Выполняется ли неравенство |Δx| ≤ ε? Да: окончание поиска, т.е. текущая точка аппроксимирует точку экстремума x * .
Нет: уменьшить приращение ∆i/α; i=1,2. n. Переход на Шаг2.
Шаг 5. Провести поиск по образцу: xp k +1 =x k +(x k -x k -1 ).
Шаг 6. Провести исследующий поиск, используя точку xp k +1 в качестве временной базовой точки. Пусть в результате получена точка x k +1 .
Шаг 7. Выполняется ли неравенство: f(x k +1 ) < f(x k )?
Да: положить x k -1 = x k ; x k = x k +1 . Переход на Шаг 5.
Нет: переход на Шаг 4. Пример №1 . Найти минимум целевой функции методом Хука–Дживса с точностью ε=0.1.
f(x) = 8x1 2 +4x1x2+52 2 .
Шаг 1. Задаем начальную точку x 0 =(-4,-4); приращения (шаги): ∆x=(1,1); коэффициент уменьшения шага: α = 2; ε=0.1
Вычислим значение функции в т. x 0 =(-4,-4) T : f(x0) = 272
Шаг №2. Исследующий поиск.
Фиксируя переменную x2 = -4, дадим приращение x1:
x1=-4 + 1 = -3
f(-3;-4) = 200 1 =(-3;-3) T
Так как исследующий поиск был удачным, переходим к поиску по образцу:
x 2 =x 1 +(x 1 -x 0 ) = [-2;-2]
f(x 2 )=68
Далее проводится исследующий поиск вокруг точки x 2 .
Шаг №2. Исследующий поиск (после поиска по образцу).
Фиксируя переменную x2 = -2, дадим приращение x1:
x1=-2 + 1 = -1
f(-1;-2) = 36 k-1 = [-2;-2]
x k = [-1;-1]
Шаг 3. Поиск по образцу.
x 2 =(-1;-1) T
Так как исследующий поиск был удачным, переходим к поиску по образцу:
x 3 =x 1 +(x 1 -x 0 ) = [0;0]
f(x 3 )=0
Далее проводится исследующий поиск вокруг точки x 3 .
Шаг №2. Исследующий поиск (после поиска по образцу).
Фиксируя переменную x2 = 0, дадим приращение x1:
x1=0 + 1 = 1
f(0;0) = 8 > 0
Фиксируя переменную x1 = 0, дадим приращение x2:
x2=0 + 1 = 1
f(0;0) = 5 > 0
Исследующий поиск не был удачным.
Проверка на окончание поиска.
|∆x| = 1.4142 > 0.1
Неравенство не выполняется, поэтому уменьшаем приращение.
∆x1 = 1 / 2 = 0.5
∆x2 = 1 / 2 = 0.5
Шаг №2. Исследующий поиск.
Фиксируя переменную x2 = 0, дадим приращение x1:
x1=0 + 0.5 = 0.5
f(0;0) = 2 > 0
Фиксируя переменную x1 = 0, дадим приращение x2:
x2=0 + 0.5 = 0.5
f(0;0) = 1.25 > 0
Исследующий поиск не был удачным.
Проверка на окончание поиска.
|∆x| = 0.70711 > 0.1
Неравенство не выполняется, поэтому уменьшаем приращение.
∆x1 = 0.5 / 2 = 0.25
∆x2 = 0.5 / 2 = 0.25
Шаг №2. Исследующий поиск.
Фиксируя переменную x2 = 0, дадим приращение x1:
x1=0 + 0.25 = 0.25
f(0;0) = 0.5 > 0
Фиксируя переменную x1 = 0, дадим приращение x2:
x2=0 + 0.25 = 0.25
f(0;0) = 0.313 > 0
Исследующий поиск не был удачным.
Проверка на окончание поиска.
|∆x| = 0.35355 > 0.1
Неравенство не выполняется, поэтому уменьшаем приращение.
∆x1 = 0.25 / 2 = 0.125
∆x2 = 0.25 / 2 = 0.125
Шаг №2. Исследующий поиск.
Фиксируя переменную x2 = 0, дадим приращение x1:
x1=0 + 0.125 = 0.125
f(0;0) = 0.125 > 0
Фиксируя переменную x1 = 0, дадим приращение x2:
x2=0 + 0.125 = 0.125
f(0;0) = 0.0781 > 0
Исследующий поиск не был удачным.
Проверка на окончание поиска.
|∆x| = 0.17678 > 0.1
Неравенство не выполняется, поэтому уменьшаем приращение.
∆x1 = 0.125 / 2 = 0.0625
∆x2 = 0.125 / 2 = 0.0625
Шаг №2. Исследующий поиск.
Фиксируя переменную x2 = 0, дадим приращение x1:
x1=0 + 0.0625 = 0.0625
f(0;0) = 0.0313 > 0
Фиксируя переменную x1 = 0, дадим приращение x2:
x2=0 + 0.0625 = 0.0625
f(0;0) = 0.0195 > 0
Исследующий поиск не был удачным.
Проверка на окончание поиска.
|∆x| = 0.088388
На разработку методов прямого поиска для определения минимума функций и переменных было затрачено много усилий. Методы прямого поиска являются методами, в которых используются только значения функции. Мы рассмотрим подробно лишь один из них. Практика показала, что этот метод эффективен и применим для широкого числа приложений. Рассмотрим функцию двух переменных. Ее линии постоянного уровня 1 на рис. 1,
а минимум лежит в точке (x 1 * ,x 2 * ). Простейшим методом поиска является метод покоординатного спуска. Из точки А мы производим поиск минимума вдоль направления оси и , таким образом, находим точку В, в которой касательная к линии постоянного уровня параллельна оси . Затем, производя поиск из точки В в направлении оси , получаем точку С, производя поиск параллельно оси , получаем точку D, и т. д. Таким образом, мы приходим к оптимальной точке. Очевидным образом эту идую можно применить для функций n-переменных.
Теоретически данный метод эффективен в случае единственного минимума функции. Но на практике он оказывается слишком медленным. Поэтому были разработаны более сложные методы, использующие больше информации на основании уже полученных значений функции.
Метод Хука-Дживса был разработан в 1961 году, но до сих пор является весьма эффективным и оригинальным. Поиск состоит из последовательности шагов исследующего поиска вокруг базисной точки , за которой в случае успеха следует поиск по образцу. Он применяется для решения задачи минимизирования функции без учета ограничений .
Описание этой процедуры представлено ниже:
А. Выбрать начальную базисную точку b 1 и шаг длиной h 1 для каждой переменной x j , j = 1, 2,…, n. В приведенной ниже программе для каждой переменной используется шаг h , однако указанная выше модификация тоже может оказаться полезной.
Б. Вычислить f (х) в базисной точке b 1 с целью получения сведений о локальном поведении функции f (x). Эти сведения будут использоваться для нахождения подходящего направления поиска по образцу, с помощью которого можно надеяться достичь большего убывания значения функции. Функция f (x) в базисной точке b 1 , находится следующим образом:
1. Вычисляется значение функции f (b 1 ) в базисной точке b 1 .
2. Каждая переменная по очереди изменяется прибавлением длины шага. Таким образом, мы вычисляем значение функции f (b 1 +h 1 e 1 ), где e 1 – единичный вектор в направлении оси x 1 . Если это приводит к уменьшению значения функции, то b 1 заменяется на b 1 +h 1 e 1 . В противном случае вычисляется значение функции f (b 1 -h 1 e 1 ), и если ее значение уменьшилось, то b 1 заменяем на b 1 -h 1 e 1 . Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b 1 остается неизменной и рассматриваются изменения в направлении оси х 2 , т. е. находится значение функции f (b 1 +h 2 e 2 ) и т. д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b 2 .
3. Если b 2 =b 1 , т. е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки b 1 , но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.
4. Если b 2 b 1 , то производится поиск по образцу.
В. При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом:
2. Затем исследование следует продолжать вокруг точки Р 1 (Р i ) .
3. Если наименьшее значение на шаге В, 2 меньше значения в базисной точке b 2 (в общем случае b i+1 ), то получают новую базисную точку b 3 (b i+2 ), после чего следует повторить шаг В, 1. В противном случае не производить поиск по образцу из точки b 2 (b i+1 ), а продолжить исследования в точке b 2 (b i+1 ).
Г. Завершить этот процесс, когда длина шага (длины шагов) будет уменьшена до заданного малого значения.
Модифицированный метод Хука-Дживса
Этот метод нетрудно модифицировать и для учета ограничений .Было выдвинуто предложение , что для этого будет вполне достаточно при решении задачи минимизации присвоить целевой функции очень большое значение там,где ограничения нарушаются .К тому же такую идею просто реализовать с помощью програмирования .
Нужно проверить ,каждая ли точка ,полученная в процессе поиска , принадлежит области ограничений .Если каждая , то целевая функция вычисляется обычным путем . Если нет , то целевой функции присваивается очень большое значение . Таким образом , поиск будет осуществляться снова в допустимой области в направлении к минимальной точке внутри этой области.
В тексте прогаммы модифицированного метода прямого поиска Хука-Дживса сделана попытка реализовать такую процедуру. Рассматриваемая задача формулируется следующим образом :
Читайте также: