Методические указания
к исследовательской лабораторной работе по дисциплине
“Математические основы кибернетики”
Тема: Метод прямого поиска экстремума.
Данная работа продолжает тему лабораторной работы №6, в которой рассматривались задачи нахождения экстремума функции (форма ее зависимости от вектора неизвестных параметров считалась заданной). В дополнение к уже изученному материалу будет изучен альтернативный подход к нахождению экстремума, основанный на использовании пробных шагов и выборе направлений по их результатам.
Вопросы для исследования:
· Изучить поисковый метод нахождения экстремума функции, аналитическое выражение которой не задано (метод Хука - Дживса).
1. Необходимые теоретические сведения
1.1. Критика градиентных методов поиска экстремума
Поскольку в методах типа наискорейшего спуска требуется использовать формулы для градиента, градиентные методы по самой своей постановке требуют знания аналитической связи (формулы) между минимизируемой функцией и аргументами. Задачи, в которых можно записать явное выражение для такой связи, встречаются довольно часто (пример такой задачи рассмотрен в подразделе данной работы).
Однако существует большое число важных для практики задач, в которой такая зависимость пользователю неизвестна, и имеется лишь информация качественного характера о наличии экстремума. Как уже отмечалось в описании лабораторной работы №6, к задачам такого типа относятся задачи настройки режимных параметров, например:
1. задача выбора соотношения топливо-воздух для котлов электростанций, при котором достигаются наилучшие условия для сжигания топлива;
2. задача настройки на условия наилучшего приема сигнала в радиотехнике;
3. задача выбора значений параметров автоматических регуляторов.
1.2. Общая схема, используемая в методах прямого поиска
Естественным способом решения таких задач является замена аналитического вычисления градиента пробными шагами (аналогично замене формального дифференцирования численным).
Далее всюду будем рассматривать задачи нахождения минимума скалярной функции f(x) векторного аргумента x = [x1, x2, ... xn]Т (без ограничений общности: задача нахождения максимума решается так же с помощью переобозначения функции: f(x)® max эквивалентно [- f(x)]® min.). Предполагаем, что вид функции f(x) явно не задан.
Все методы прямого поиска укладываются в следующую общую схему:
1. выберем произвольно точку начального приближения x(0);
2. процесс поиска экстремума организуется как итеративный;
3. рассмотрим k-й шаг итеративного процесса;
a) на этом шаге зафиксируем все элементы вектора x(k), кроме одного, например, j-го: [x1(k), x2(k), ... xj -1(k), xj+1(k), ... , xn(k)] фиксированы;
b) сделаем пробные приращения (обоих знаков) вокруг xj (k):
[xj (k+1)] (1) = xj (k) + Dxj (k) ; [xj (k+1)] (2) = xj (k) - Dxj (k)
c) найдем “улучшающее” направление – выберем
[xj (k+1)] Î {[xj (k+1)](1), [xj (k+1)](2}
такое, чтобы значение функции
f(x1(k), x2(k), ... xj -1(k), xj (k+1) , xj+1(k), ... , xn(k))
стало меньше (лучше), чем
f(x1(k), x2(k), ... xj -1(k), xj (k) , xj+1(k), ... , xn(k));
d) последовательно проделаем те же действия для всех элементов вектора x; это позволит “экспериментально”, “прощупывая” реакцию объекта на пробные возмущения, найти оценку градиента в окрестности точки x(k) и найти направление движения к экстремуму.
Мы видим, что поисковая процедура заменяет изучение минимизируемой функции во всей области значений аргументов изучением локального ее участка - как бы полосы, ведущей к экстремуму из произвольно выбранной точки. Весь процесс поиска похож на спуск слепого путника с горы (он “ощупывает” уклон вблизи себя и делает шаг; затем снова “ощупывает” и снова шагает - и в конечном итоге достигает низины, несмотря на то, что горы не видит).
1.3. Критика алгоритмов прямого поиска
Как видно из п.1.2, в алгоритмах прямого поиска в их простейшей форме совершенно не используется информация о форме минимизируемой функции. Это и обуславливает их применимость для прикладных задач, в которых формула минимизируемой функции не задана.
Платой за это является худшие (по сравнению с градиентными методами) показатели сходимости к экстремуму: поскольку нет информации для выбора шага, в процессе поиска алгоритм может либо “проскочить” экстремум (пробные шаги недопустимо велики), либо сходимость может быть очень медленной (пробные шаги недопустимо малы).
Кроме того, погрешности измерения при “пологой” форме функции могут исказить улучшающее направление (и алгоритм вообще не будет сходиться).
Получается, что “заявленные” преимущества алгоритмов прямого поиска, состоящие в чрезвычайно скромных требованиях к априорным сведениям о минимизируемой функции, фактически завышены: без изучения функции хороший процесс сходимости (и соответственно хорошие величины пробных шагов) являются скорее редкой удачей, чем общим правилом.
1.4. Идеи адаптации для алгоритмов прямого поиска
Представляет интерес извлечение информации о форме функции (конечно, не всей, а только вблизи траектории движения к экстремуму) в процессе движения - так, чтобы результаты прошлых итераций использовались для корректировки шага на текущей итерации. Такая идея является примером реализации весьма продуктивного подхода к решению задач управления и оптимизации - использования обучения и адаптации в ходе процесса управления.
Существо идеи:
1. если предыдущий шаг привел к улучшению функции, следующий шаг увеличиваем, движение к экстремуму ускоряется;
2. если предыдущий шаг привел к ухудшению функции, следует откорректировать направление движения и вернуться к первоначальной длине шага;
3. если при пробных движениях во всех направлениях функция ухудшается (это - признак попадания в окрестность экстремума), то:
a) если пробный шаг превышает заданную точность определения положения экстремума, то уменьшаем величину пробного шага (например, по формуле dxi /ew, где dxi - первоначальное значение шага, e- основание натуральных алгоритмов, w - число неудачных попыток определить улучшающее направление подряд);
b) в противном случае - заканчиваем поиск.
1.5. Алгоритм Хука и Дживса
На рис. 1 показаны основные шаги алгоритма.
Рис. 1. Последовательность действий в алгоритме Хука и Дживса
Комментарии к рисунку (для простоты рассматривается задача минимизации функции двух переменных x1 , x2 ).
Исходные данные для начала поиска экстремума (в нашем примере минимума):
a) До начала процесса поиска должны быть заданы исходные значения пробных шагов - вектора dx с элементами dx1 и dx2.
b) Также до начала процесса поиска должны быть заданы минимальные значения шагов dx1(min) и dx2(min) (определяют точность нахождения минимума).
c) Выбираем (произвольно) начальную точку (на рис.1 - точка 0 с координатами x(0) = [x1(0) , x2(0))]Т ). Назначаем ее базовой (от нее будет отсчитываться шаг к минимуму до тех пор, пока функция будет уменьшаться, что приведет к увеличению шага, если он удачен).
d) Определяем (непосредственным измерением) значение минимизируемой функции f(x), соответствующее x= x(0); обозначим это значение f0. Далее также будем опускать аргумент в обозначении функции: обозначение fj относится к функции f(x) в точке x = xj.
Исследующий поиск типа 1:
1. В окрестности этой точки совершаем пробный шаг, например, в сторону увеличения аргумента x1 : x1(пробное) = x1(0) + dx1 , значение x2(0) не изменяем. Происходит перемещение в точку 1 (см. рис. 1).
2. Определяем (непосредственным измерением) значение минимизируемой функции f(x) в точке 1, оно соответствует аргументу x= [x1(0) + dx1 , x2(0)]; обозначим это значение f1.
3. Проверяем, уменьшилось ли значение функции в результате данного пробного шага, т. е. проверяем, истинно ли [f1 - f0 < 0]. Если “да” - то направление пробного шага выбрано удачно.
4. Пусть в нашем случае [f1 - f0 < 0] ложно. Возвращаемся в точку 0 и делаем пробный шаг в противоположном направлении; x1(пробное) = x1(0) - dx1 , значение x2(0) по-прежнему не изменяем. Происходит перемещение в точку 2.
5. Проверяем, уменьшилось ли значение функции в результате данного пробного шага, т. е. проверяем, истинно ли [f2 - f0 < 0]. Если “да” - то направление пробного шага выбрано удачно. Если же и это изменение окажется неудачным, оставляем x1 = x1(0).
6. Пусть в нашем случае [f2 - f0 < 0] истинно, т. е. направление выбрано удачно. Перемещаем точку приближения к экстремуму в точку 2..
7. В окрестности точки 2 совершаем пробный шаг по другой координате - например, в сторону увеличения аргумента x2: x2(пробное) = x2(0) + dx2 , значение x1 = x1(0) - dx1 (соответствует точке 2). Происходит перемещение в точку 3 (см. рис. 1).
8. Определяем (непосредственным измерением) значение минимизируемой функции f(x) в точке 3, оно соответствует аргументу x= [x1(0) - dx1 , x2(0) + dx2 ] ; обозначим это значение f3.
9. Проверяем, уменьшилось ли значение функции в результате данного пробного шага, т. е. проверяем, истинно ли [f3 - f2 < 0]. Если “да” - то направление пробного шага выбрано удачно.
10. Пусть в нашем случае [f3 - f2 < 0] ложно. Возвращаемся в точку 2 и делаем пробный шаг в противоположном направлении; x2(пробное) = x2(0) - dx2 , при x1= x1(0) - dx1. Происходит перемещение в точку 4.
11. Проверяем, уменьшилось ли значение функции в результате данного пробного шага, т. е. проверяем, истинно ли [f4 - f2 < 0]. Если “да” - то направление пробного шага выбрано удачно. Если же и это изменение окажется неудачным, оставляем x2 = x2(0).
12. Если пробные шаги во всех направлениях по всем координатам окажутся неудачными, то следует уменьшить величины пробных шагов dx1 и dx2 (перейти к п. 6.2).
13. Пусть в нашем случае [f4 - f2 < 0] истинно, т. е. направление выбрано удачно. Перемещаем точку приближения к экстремуму в точку 4.Назначаем эту точку точкой для сравнения для оценки эффективности следующего шага поиска по образцу (см. ниже).
Таким образом, исследующий поиск типа 1 завершается определением направления движения к минимуму, т. е. оценки вектора, направленного против направления градиента. А также назначением базовой точки (на рис.1 - точка 0), от которой будет отсчитываться шаг к минимуму, и точки для сравнения (по ней мы будем определять целесообразность сохранения выбранного направления движения к минимуму).
Поиск по образцу:
В направлении, определенном в результате выполнения исследующего поиска типа 1, делаем шаг (называется поиском по образцу) из точки для сравнения 4 . Величина шага Dx = [Dx1,Dx2]Т определяется отсчетом от базовой точки (на рис.1 - точка 0). Формула для определения координаты точки (5 на рис. 1), в которую переходим после шага поиска:
x i(5) = x i(4) + Dx i = x i(4) + (x i(4) - x i(0)) = 2 x i(4) - x i
или, в общих обозначениях:
x i (в конце шага поиска по образцу) = 2x i (в точке для сравнения) - x i (в базовой точке)
i = 1,... n (2)
Получаем точку 5.
Исследующий поиск типа 2:
В окрестности точки, полученной в результате поиска по образцу (на рис.1 - точка 5) совершаем пробные шаги последовательно по каждой координате в ту же сторону, что оказалась успешной для базовой точки.
Начинаем с любого из аргументов - например, с x1. В базовой точке успешным было направление уменьшения аргумента. Сохраняем это направление: x1(пробное) = x1(5) - dx1 , значение x2(5) не изменяем. Происходит перемещение в точку 6. Возможно, значение функции по сравнению с достигнутым в точке для сравнения (точка 4) улучшится, т. е. получится f6 - f4 < 0. Тогда считаем направление поиска удачным и НЕ делаем пробных шагов по остальным координатам.
Пусть в нашем примере [ f6 - f4 < 0 ] ложно. Тогда следует вернуться в точку 5 и продолжить пробные шаги (в тех же направлениях, что привели к удаче на этапе исследующего поиска типа 1) по другим координатам - до ПЕРВОЙ удачи. Если все направления пробных шагов привели к неудаче, следует откорректировать направление поиска, см. п.5.
Пусть в нашем примере шаг в направлении “прежнего” (для базовой точки) успешного пробного шага для аргумента x2: x2(пробное) = x2(5) - dx2 при x1 = x1(5) (перемещение в точку 7) оказался успешным: [ f7- f4 < 0 ] истинно. Тогда, несмотря на неудачу пробного шага по координате x1 ([f6- f4 < 0 ] ложно), считаем выбранное направление движения правильным и не изменяем положение базовой точки.
Назначаем новую точку для сравнения (в нашем примере - точку 7)
Таким образом, исследующий поиск типа 2 завершается:
a) либо назначением новой точки для сравнения с сохранением прежнего направления движения к минимуму и переходу к поиску по образцу;
b) либо заключением о необходимости корректировки прежнего направления (см. п.5).
Поиск по образцу:
В направлении, определенном в результате выполнения исследующего поиска типа 1, делаем шаг поиска по образцу из точки для сравнения 7. Величина шага Dx = [Dx1,Dx2]Т определяется отсчетом от “старой” базовой точки (на рис.1 - точка 0). Формула для определения координаты точки (8 на рис. 1), в которую переходим после шага поиска:
x i(8) = x i(7) + Dx i = x i(7) + (x i(7) - x i(0)) = 2 x i(7) - x i
или, в более общих обозначениях:
x i (в конце шага поиска по образцу) = 2x i (в точке для сравнения) - x i (в базовой точке) 1,... n (4)
Получаем точку 8.
Мы видим, что произошло примерно двукратное увеличение длины шага (с точностью до длины пробных шагов dx1, dx2) благодаря сохранению “старой” базовой точки.
Исследующий поиск типа 2 (неудачный).
Пусть оба пробных шага из точки 8 оказались неудачными
[(f7- f9 < 0) Ç (f7- f10 < 0) ложно].
Тогда следует отменить шаг поиска по образцу и возвратиться в прежнюю точку для сравнения (точка 7).
Действия после неудачного исследующего поиска типа 2.
Назначаем базовой прежнюю точку для сравнения (на рис.1 - точка 7). Из этой точки проводим исследующий поиск типа 1. Возможны 2 случая:
a) Исследующий поиск типа 1 удачен. Тогда следует продолжить работу, начиная с п. 1 (базовая точка 7).
b) Исследующий поиск типа 1 Неудачен. Это означает попадание в область экстремума с точностью до текущей величины пробных шагов (вначале эта величина задана, равна dx1, dx2). Сравниваем эти величины с заранее заданной точностью поиска dx1min, dx2min. Возможны 2 случая:
1. Хотя бы один из пробных шагов ниже точности нахождения экстремума, т. е. (dx1>dx1min) È (dx2>dx2min). Экстремум не найден, следует уменьшить шаг по алгоритму:
dxi (новое) = dxi (исходное) / ew,
где е - основание натуральных логарифмов, w - число неудачных акций исследующего поиска типа 1 ПОДРЯД.
2. Оба пробных шага выше точности нахождения экстремума. Экстремум найден, работа алгоритма закончена.
1.6. Блок-схема алгоритма Хука и Дживса
1.7. Тестовый пример. Поиск минимума методом Хука и Дживса
Ниже рассмотрена процедура поиска минимума функции одной переменной. Уравнение функции (которое “не знает” алгоритм):
f(x) = x + 0.1 x2,
минимум - в точке x=3.5.
Приведенная ниже таблица может быть использована Вами как образец протокола поиска минимума в ходе выполнения лабораторной работы.
Таблица-ПРОТОКОЛ поиска минимума методом Хука-Дживса
№ шага | Значение аргумента | Значение функции (измеренное) | Результат | Назначения | Комментарии | |||||
Исследующий поиск типа 1 | ||||||||||
0 | 20 | 29 | - | Точкавыбирается базовой | Точка выбрана произвольно | |||||
1 | 20+0.5=20.5 | 30.675(<баз.) | Неудача | |||||||
2 | 20-0.5=19.5 | 27.379(>баз.) | Успех | |||||||
Поиск по образцу шаг=0.5 | ||||||||||
3 | 2*19.5-20 =19 | Базовая точка - п.0, длина шага=½19-19.5½=0.5 | ||||||||
Исследующий поиск типа 2 | ||||||||||
4 | 19-0.5=18.5 | 24.275 <сравн.= 27.379 | Успех | Новаяточка для сравнения | Пробный шаг - в направлении успешного для базовой точки | |||||
Поиск по образцу шаг=1.5 | ||||||||||
5 | 2*18.5-20 =17 | Базовая точка - п.0, длина шага=½17-18.5½=1.5 | ||||||||
Исследующий поиск типа 2 | ||||||||||
6 | 17-0.5=16.5 | 18.675 <сравн.= 24.275 | Успех | Новаяточка для сравнения | Базовая точка - там же, п.0 | |||||
Поиск по образцу шаг=3.5 | ||||||||||
7 | 2*16.5-20 =13 | Базовая точка - п.0, длина шага=½13-16.5½=3.5 | ||||||||
Исследующий поиск типа 2 | ||||||||||
8 | 13-0.5=12.5 | 9.875 <сравн.= 18.675 | Успех | Новаяточка для сравнения | Базовая точка - там же, п.0 | |||||
№ шага | Значение аргумента | Значение функции (измеренное) | Результат | Назначения | Комментарии | |||||
Поиск по образцу шаг=7.5 | ||||||||||
9 | 2*12.5-20=5 | Базовая точка - п.0, длина шага=½5-12.5½=73.5 | ||||||||
Исследующий поиск типа 2 | ||||||||||
10 | 5-0.5=4.5 | 1.875 <сравн.= 9.875 | Успех | Новаяточка для сравнения | Базовая точка - там же, п.0 | |||||
Поиск по образцу шаг=15.5 | ||||||||||
11 | 2*4.5-20= -11 | Базовая точка - п.0, длина шага=½-11-4.5½=15.5 | ||||||||
Исследующий поиск типа 2 | ||||||||||
12 | -11-0.5= - 11.5 | 24.275 >сравн.= 1.875 | Неудача | Смена направления поиска, смена базовой точки. | ||||||
Исследующий поиск типа 1 | ||||||||||
13 | 4.5+0.5=5 | 2 >баз.=1.875 | Неудача | Пробный шаг (+Dx) | Новая базовая точка – предшествующая точка для сравнения, п.1 | |||||
14 | 4.5-0.5=5 | 1.8 <баз.=1.875 | Успех | Новаяточка для сравнения | Пробный шаг (-Dx) | |||||
Поиск по образцу шаг=0.5 (возврат к исходному шагу) | ||||||||||
15 | 2*4-4.5=3.5 | 1.775 | Базовая точка - п.10, длина шага=½3.5-4.5½=0.5 | |||||||
Исследующий поиск типа 2 | ||||||||||
16 | 3.5-0.5=3 | 1.8 =сравн.=1.8 | Неудача | Смена направления поиска, смена базовой точки. | ||||||
Исследующий поиск типа 1 | ||||||||||
17 | 4.5+0.5=5 | 1.875 >баз.=1.8 | Неудача | Пробный шаг (+Dx) | Новая базовая точка - предшествующая точка для сравнения, п.14 | |||||
18 | 4.5-0.5=5 | 1.775 | Успех | Новаяточка для сравнения | Пробный шаг (-Dx) | |||||
Поиск по образцу шаг=0.5 (возврат к исходному шагу) | ||||||||||
19 | 2*3.5-4=3 | 1.8 | Базовая точка - п.15, длина шага=½3-3.5½=0.5 | |||||||
№ шага | Значение аргумента | Значение функции (измеренное) | Результат | Назначения | Комментарии | |||||
Исследующий поиск типа 2 | ||||||||||
20 | 3-0.5=2.5 | 1.875 >сравн.= 1.775 | Неудача | Смена направления поиска, смена базовой точки. | ||||||
Исследующий поиск типа 1 | ||||||||||
21 | 3.5+0.5=4.0 | 1.8 >баз.=1.775 | Неудача | Пробный шаг (+Dx) | Новая базовая точка – предшествующая точка для сравнения, п.18 | |||||
22 | 3.5-0.5=3 | 1.8 >баз.=1.775 | Неудача | Пробный шаг (-Dx) | Оба пробных шага неудачны. Уменьшение шага : Dxновый =Dx/(e1)=0.184 (показатель экспоненты= числу неудач исследующего поиска типа 1 подряд). | |||||
Исследующий поиск типа 1 | ||||||||||
23 | 3.5+0.184 =3.684 | 1.778 >баз.=1.775 | Неудача | Пробный шаг (+Dx) | Базовая точка – п.18 | |||||
24 |
=3.316 | 1.778 >баз.=1.775 | Неудача | Пробный шаг (-Dx) | Оба пробных шага неудачны. Уменьшение шага : Dxновый =Dx/(e2)=0.0677 (см. комментарий в п.22) | |||||
Исследующий поиск типа 1 | ||||||||||
25 | 3.5+0.0677 =3.5677 | 1.7755 >баз.=1.775 | Неудача | Пробный шаг (+Dx) | Базовая точка - п.18 | |||||
26 |
=3.4323 | 1.7755 >баз.=1.775 | Неудача | Пробный шаг (-Dx) | Оба пробных шага неудачны. Уменьшение шага : Dxновый =Dx/(e3)=0.0249 (см. комментарий в п.22) | |||||
№ шага | Значение аргумента | Значение функции (измеренное) | Результат | Назначения | Комментарии | |||||
Исследующий поиск типа 1 | ||||||||||
27 | 3.5+0.0249 =3.5249 | 1.77506 >баз.=1.775 | Неудача | Пробный шаг (+Dx) | Базовая точка - п.18 | |||||
28 |
=3.4751 | 1.77506 >баз.=1.775 | Неудача | Пробный шаг (-Dx) | Оба пробных шага неудачны. Уменьшение шага : Dxновый =Dx/(e4)=0.00916 меньше заданной точности (0.01). Поиск окончен. | |||||
2. Методика проведения работы
Лабораторная работа организуется в форме игры, в которой преподаватель исполняет роль поставщика сведений о значениях функции в точке, координаты которой указываются рабочими группами студентов. Рассматривается задача поиска минимума функции двух переменных.
Правила игры:
1. Преподаватель до начала игры заготавливает уравнение минимизируемой функции, подбирает исходные данные (см. п. 1.5).
2. В момент начала игры преподаватель сообщает каждой рабочей группе студентов различные варианты точки начального приближения к минимуму x(0) = [x1(0), x2(0)]T.
3. Студенты выбирают направление пробного шага и запрашивают преподавателя о значении функции после пробного изменения аргумента.
4. Студенты протоколируют процесс поиска (таблицей, аналогичной приведенной в п.1.8.1.7 - но для двух переменных).
5. Преподаватель помогает разрешать недоразумения в процессе поиска и проверяет, найден ли экстремум. Ставит оценку за проведение работы.
3. Содержание отчета по лабораторной работе
Отчет о работе должен быть представлен в виде протокола поиска минимума (форма протокола представлена ниже). Печатать протокол не обязательно - достаточно показать его преподавателю либо на экране дисплея, либо в черновике.
Форма Протокола поиска минимума методом Хука-Дживса.
(образец см. в п.1.7).
№ шага | Значение аргумента | Значение функции (измеренное) | Результат | Назначения | Комментарии | |
x1 | x2 | (указывает преподаватель) | ||||
Литература
Прикладное нелинейное программирование. – М.:Мир,1975.-с.157-163.
