Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. A. Методы измерения мертвого времени
  2. HR– менеджмент: технологии, функции и методы работы
  3. I метод.
  4. I. 2. 1. Марксистско-ленинская философия - методологическая основа научной психологии
  5. I. 2.4. Принципы и методы исследования современной психологии
  6. I. Анализ методической структуры и содержания урока
  7. I. Методические указания к изучению курса

Метод конфигураций (метод Хука-Дживса [R. Hook, T.A. Jeeves]) представ­ляет собой комбинацию исследующего (пробного) поиска с циклическим изменением пере­менных и ускоряющего поиска по образцу. Исследующий поиск ориентирован на выявление локального поведения целевой функции и определение направления ее убывания вдоль "оврагов". Полученная информация используется при поиске по образцу при движении вдоль "оврагов".

Исследующий поиск начинается в некоторой начальной точке , называе­мой старым базисом. В качестве множества направлений поиска выбирается множество координатных направлений. Задается величина шага, которая может быть различной для разных координатных направлений и переменной в процессе поиска. Фиксируется первое координатное направление и делается шаг в сторону увеличения соответствующей переменной. Если значение функции в пробной точке меньше значения функции в исходной точке, шаг считается удачным. В противном случае необходимо вернуться в предыдущую точку и сделать шаг в противоположном направлении с последующей проверкой поведения функции. После перебора всех координат исследующий поиск завершается. Полученная точка называется новым базисом (на рис. 3.1 в точке произведен исследующий поиск и получена точка - новый базис). Если исследующий поиск с дан­ной величиной шага неудачен, то она уменьшается и процедура продолжается. Поиск заканчивается, когда текущая величина шага станет меньше некоторой величины.

Рисунок 3.1

 

Поиск по образцу заключается в движении по направлению от старого базиса к новому (от точки через точку , из точки через точку , из точки через точку на рис. 3.1). Величина ускоряющего шага задается ускоряющим множителем . Успех поиска по образцу определяется с помощью исследующего поис­ка из полученной точки (например, из точек 6, 11, 15 на рис. 3.1). Если при этом значение в наилучшей точке меньше, чем в точке предыдущего базиса, то поиск по образцу удачен (точки 6, 11 - результат удачного поиска по образцу, а точка 15 - неудачного). Если поиск по образцу неудачен, происходит возврат в новый базис, где продолжается исследующий поиск с уменьшенным шагом.

На рис. 3.1 удачный поиск отображается сплошными линиями, а неудач­ный - пунктирными, числа соответствуют порождаемым алгоритмом точкам. Обозначим через - координатные направления

При поиске по направлению меняется только переменная , а остальные переменные остаются зафиксированными.

Алгоритм:

Шаг 1. Задать начальную точку , число для остановки алгоритма, начальные величины шагов по координатным направлениям , ускоряющий множитель , коэффициент уменьшения шага . Положить .

Шаг 2. Осуществить исследующий поиск по выбранному координатному направлению:

а) если , шаг считается удачным. Положить и перейти к шагу 3;

б) если в пункте а) шаг неудачен, то делается шаг в противоположном направлении. Если , шаг считается удачным. В этом случае следует положить и перейти к шагу 3;

в) если в пунктах а) и б) шаги неудачны, положить .

Шаг 3. Проверить условия:

а) если , то положить и перейти к шагу 2;

б) если , проверить успешность исследующего поиска

- если , перейти к шагу 4;

- если , перейти к шагу 5;

Шаг 4. Провести поиск по образцу. Положить , , , и перейти к шагу 2.

Шаг 5. Проверить условие окончания:

а) если все , то поиск по закончить: ;

б) для тех , для которых , уменьшить величину шага: . Положить , , , и перейти к шагу 2

 

Замечания:

а) В алгоритме можно использовать одинаковую величину шага по координатным направлениям, то есть вместо применять .

б) Существует модификация метода, где при исследующем поиске и поиске по образцу используется одномерная минимизация.

Пример: Найти локальный минимум функции методом конфигураций

Решение:

1. Зададим - старый базис, , , .

Положим k = 0, i = 1, .

20. Т.к. то шаг неудачен.

Т.к. то шаг удачный: .

30. Т.к. i = 1 < 2 = n, то i = i + 1 = 2 и переходим к шагу 2.

21. Т.к. то шаг неудачен.

Т.к. то шаг удачный: .

31. Т.к. i = 2 = n = 2 и , переходим к шагу 4.

40. Положим - новый базис, i = 1, k = k + 1 = 1, найдем . Выполнен поиск по образцу. Переходим к шагу 2.

22. Т.к. и

то шаги неудачные, а .

32. Т.к. i = 1 < 2 = n, то i = i + 1 = 2 и переходим к шагу 2.

23. Т.к. и

то шаги неудачные, а .

33. Т.к. i = 2 = n = 2 и , переходим к шагу 4.

41. Положим - новый базис, i = 1, k = k + 1 = 2, найдем . Выполнен поиск по образцу. Переходим к шагу 2.

24. Т.к. то шаг удачен:

.

34. Т.к. i = 1 < 2 = n, то i = i + 1 = 2 и переходим к шагу 2.

25. Т.к. то шаг удачен:

.

35. Т.к. i = 2 = n = 2 и , то поиск по образцу неудачен. Осуществляется возврат в точку . Переходим к шагу 5.

50. Т.к. то уменьшим шаг: Положим i = 1, k = k + 1 = 3 и перейдем к шагу 2.

26. Т.к. и

то шаги неудачные, а .

36. Т.к. i = 1 < 2 = n, то i = i + 1 = 2 и переходим к шагу 2.

27. Т.к. и

то шаги неудачные, а .

37. Т.к. i = 2 = n = 2 и , то исследующий поиск неудачен. Перейдем к шагу 5.

51. Т.к. то поиск закончен: .

Геометрическая интерпретация решения задачи представлена на рисунке 3.2. Здесь изображены полученные точки; сплошной линией отмечены удачные итерации, а пунктирной – неудачные.

Рисунок 3.2


Дата добавления: 2015-07-20; просмотров: 632 | Нарушение авторских прав


Читайте в этой же книге: Метод вращающихся координат (метод Розенброка) | Метод сопряженных направлений (метод Пауэлла) | Методы первого порядка | Метод градиентного спуска с постоянным шагом | Метод наискорейшего градиентного спуска (Метод Коши) | Метод Гаусса - Зейделя | Метод Ньютона | Метод Ньютона - Рафсона | Метод Марквардта | Пример отчета по лабораторной работе |
<== предыдущая страница | следующая страница ==>
Общие принципы методов поиска безусловного экстремума| Метод деформируемого многогранника

mybiblioteka.su - 2015-2024 год. (0.01 сек.)