2015-08-21
8188
Описание алгоритма:
Процедура Хука-Дживса представляет собой комбинацию "исследующего" поиска с циклическим изменением переменных и ускоряющего поиска по найденному образцу. Исследующий поиск ориентирован на выявление направления вдоль "оврагов". Полученная в результате исследующего поиска информация используется затем в процессе поиска по образцу при движении по "оврагам".
Исследующий поиск:
Для проведения исследующего поиска необходимо задать величину шага, которая может быть различна для разных координатных направлений, и изменяться в процессе поиска. Поиск начинается в некоторой исходной точке. Делается пробный шаг вдоль одного из координатных направлений. Если значение целевой функции в пробной точке меньше, чем в исходной, то шаг считается удачным. В противном случае возвращаются в исходную точку и делают шаг в противоположном направлении. После перебора всех 
координат исследующий поиск заканчивается. Полученную в результате исследующего поиска точку называют базовой.
Поиск по образцу:
Поиск по образцу заключается в реализации единственного шага из полученной базовой точки вдоль прямой, соединяющей эту точку с предыдущей базовой точкой. Новая точка определяется по формуле:
Как только движение по образцу не приводит к уменьшению целевой функции, точка 
фиксируется в качестве временной базовой точки и выполняется исследующий поиск. При уменьшении значения целевой функции эта точка рассматривается как базовая точка. Если же исследующий поиск не дал результата, необходимо вернуться в предыдущую точку и провести исследующий поиск заново. Если такой поиск не приводит к успеху, то необходимо уменьшить величину шага. Поиск завершается, когда величина шага приращения становится достаточно малой.
Алгоритм метода:
Шаг 1. Задать: 1. Начальную точку 
;
2. Приращение 
, 
;
3. Коэффициент уменьшения шага 
;
4. Параметр окончания поиска 
.
Шаг 2. Произвести исследующий поиск.
Шаг 3. Поиск удачный:
Да: перейти к шагу 5;
Нет: продолжить.
Шаг 4. Проверка на окончание поиска: 
?
Да: прекратить поиск;
Нет: уменьшить приращение по формуле:
, 
; Перейти к шагу 2.
Шаг 5. Провести поиск по образцу: 
Шаг 6. Провести исследующий поиск, используя 
в качестве базовой точки: 
- полученная в результате точка
Шаг 7. Выполняется ли условие 
?
Да: продолжить 
; 
;
перейти к шагу 5;
Нет: перейти к шагу 4.
Ход решения:
Исходные данные:
Шаг 1.
Пусть 
.
Для того, чтобы применить данный метод необходимо задать следующие величины:
Итерации начинаются с исследующего поиска вокруг точки 
, которой соответствует значение функции 
Шаг 2.
Фиксируя 
, даём приращение переменной 
:
Следовательно, необходимо зафиксировать 
и дать приращение переменной 
:
Шаг 3. Таким образом, в результате исследующего поиска была найдена точка 
Поскольку исследующий поиск был удачным, переходим к поиску по образцу:
Шаг 5.
Шаг 6.
Далее производим исследующий поиск вокруг точки 
:
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать 
и дать приращение переменной :
Шаг 7.
Получаем новую точку:
Поскольку 
, поиск по образцу следует считать успешным и 
становится новой базовой точкой при следующем проведении поиска по образцу:
Шаг 5.
Шаг 6.
Далее производим исследующий поиск вокруг точки 
:
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать 
и дать приращение переменной :
Шаг 7.
Получаем новую точку:
Поскольку 
, поиск по образцу следует считать успешным и 
становится новой базовой точкой при следующем проведении поиска по образцу:
Шаг 5.
Шаг 6.
Далее производим исследующий поиск вокруг точки 
:
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать 
и дать приращение переменной :
Шаг 7.
Получаем новую точку:
Поскольку 
, поиск по образцу следует считать удачным, и 
становится новой базовой точкой при следующем проведении поиска по образцу:
Шаг 5.
Шаг 6.
Далее производим исследующий поиск вокруг точки 
:
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать 
и дать приращение переменной :
Шаг 7.
Получаем новую точку:
Поскольку 
, поиск по образцу следует считать успешным и 
становится новой базовой точкой при следующем проведении поиска по образцу:
Шаг 5.
Шаг 6.
Далее производим исследующий поиск вокруг точки 
:
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать 
и дать приращение переменной :
Шаг 7.
Получаем новую точку:
Поскольку 
, поиск по образцу следует считать неудачным, 
отбрасывается и 
становится новой базовой точкой при следующем проведении исследующего поиска:
Шаг 2.
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать 
и дать приращение переменной :
Шаг 3.
Получаем новую точку:
Поскольку исследующий поиск был удачным, переходим к поиску по образцу:
Шаг 5.
Шаг 6.
Далее производим исследующий поиск вокруг точки 
:
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать 
и дать приращение переменной :
Шаг 7.
Получаем новую точку:
Поскольку 
, поиск по образцу следует считать успешным и 
становится новой базовой точкой при следующем проведении поиска по образцу:
Шаг 5.
Шаг 6.
Далее производим исследующий поиск вокруг точки 
:
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать 
и дать приращение переменной :
Шаг 7.
Получаем новую точку:
Поскольку 
, поиск по образцу следует считать успешным и 
становится новой базовой точкой при следующем проведении поиска по образцу:
Шаг 5.
Шаг 6.
Далее производим исследующий поиск вокруг точки 
:
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать 
и дать приращение переменной :
Шаг 7.
Получаем новую точку:
Поскольку 
, поиск по образцу следует считать успешным и 
становится новой базовой точкой при следующем проведении поиска по образцу:
Шаг 5.
Шаг 6.
Далее производим исследующий поиск вокруг точки 
:
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать 
и дать приращение переменной :
Шаг 7.
Получаем новую точку:
Поскольку 
, поиск по образцу следует считать неудачным,
отбрасывается и 
становится новой базовой точкой при следующем проведении исследующего поиска:
Шаг 2.
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать 
и дать приращение переменной :
Исследующий поиск не дал результатов, поэтому уменьшаем шаг: 
, базовая точка 
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать 
и дать приращение переменной :
Шаг 3.
Получаем новую точку:
Поскольку исследующий поиск был удачным, переходим к поиску по образцу:
Шаг 5.
Шаг 6.
Далее производим исследующий поиск вокруг точки 
:
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать 
и дать приращение переменной :
Шаг 7.
Получаем новую точку:
Поскольку 
, поиск по образцу следует считать неудачным,
отбрасывается и 
становится новой базовой точкой при следующем проведении исследующего поиска:
Шаг 2.
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать 
и дать приращение переменной :
Исследующий поиск не дал результатов, поэтому прекращаем поиск. Искомая точка оптимума: 
Решение поставленной задачи методом Хука-Дживса представлено на рисунке 2.
 |
| Рисунок 2 – решение задачи методом Хука-Дживса |
