Лабораторная работа №4
Исследование метода релаксации
Описание метода
Алгоритм метода заключается в отыскании осевого направления, вдоль которого функция цели уменьшается наиболее сильно. Для этого в начальной точке поиска определяются производные оптимизируемой функции по всем независимым переменным.
Осевому направлению с наибыстрейшим убыванием целевой функции, очевидно, соответствует наибольшая по модулю производная. Если знак производной отрицательный, целевая функция убывает в направлении оси, если—положительный, в обратном направлении. По направлению убывания целевой функции производятся шаги до тех пор, пока не будет получено минимальное значение по выбранному осевому направлению. Тогда вновь определяются производные по всем переменным, за исключением той, по которой осуществлялся спуск, и снова находится осевое направление наибыстрейшего убывания функции цели, по которому производятся дальнейшие шаги, и т. д.
Критерием окончания поиска оптимума является достижение такой точки, при движении из которой по любому осевому направлению дальнейшего убывания функции не происходит. На практике в качестве признака оптимума часто применяется условие
, (4,1)
которое при σ—> 0 превращается в точное условие равенства нулю производных в точке оптимума. Разумеется, что условие (4,1) может быть использовано только в том случае, если оптимум лежит внутри допустимой области изменения независимых переменных X. Если же оптимум попадает на границу области X, критерий типа (4,1) непригоден и вместо него следует применять условие положительности всех производных по допустимым осевым направлениям. При этом допустимым осевым будет только направление внутрь области X. Обратное направление по той же оси ведет за Пределы области X, если, конечно, рассматриваемая ось не является в данной точке касательной к границе области X.
Алгоритм спуска для выбранного осевого направления может быть записан в виде следующей формулы:
, (4,2)
причем хj(k) — значение изменяемой переменной на k-ом шаге спуска; h(k) — величина k-ro шага^ которая может изменять свое значение в зависимости от номера шага; sgn z — функция знака; х(p) — вектор точки, в которой последний раз производилось вычисление производных целевой функции. Графическое изображение движения от исходного состояния к оптимуму показано на рисунке 3.
Очевидно, что скорость движения к минимуму зависит от того, насколько удачно выбран шаг h(k) изменения независимых переменных. При слишком малой величине шага число шагов, которое необходимо сделать, чтобы достичь оптимума, будет большим и, следовательно, потребуется много раз вычислять значения целевой функции на пути движения к оптимуму.
Если, напротив, величина шага с самого начала спуска выбрана слишком большой, вблизи оптимума может возникнуть «рыскание», так как при большой величине шага мала вероятность попадания в окрестность оптимума, в которой выполняется условие окончания поиска (4,1). Поэтому представляют интерес специальные приемы изменения величины шага в процессе поиска.
Простейший алгоритм изменения шага состоит в следующем. В начале спуска по одному из осевых направлении задается некоторый шаг h(0), равный, например, 0,1, что соответствует изменению значения физической переменной уj на 10% от принятого диапазона dj. С этим шагом производится спуск по выбранному осевому направлению до тех пор, пока для двух последующих вычислений значений целевой функции выполняется условие:
.
При нарушении условия на каком-либо j -м шаге направление спуска на оси изменяется на обратное и спуск продолжается из последней рассчитанной точки с уменьшенной вдвое величиной шага.
Формульная запись этого алгоритма имеет вид:
.
В результате использования такой стратегии шаг спуска по осевому направлению будет уменьшаться в районе минимума целевой функции и по этому направлению и поиск минимума можно прекратить, когда величина шага h(k) станет меньше заданной точности определения минимума ε в осевом направлении. Затем отыскивается новое осевое направление, в котором функция изменяется наиболее сильно. Начальный шаг в новом направлении уже можно выбрать не как заданную долю диапазона изменения независимой переменной, а как заданную долю расстояния, пройденного вдоль предыдущего осевого направления. Это позволяет автоматически уменьшать начальный шаг по каждому следующему осевому направлению при приближении к оптимуму целевой функции, в районе которого спуск по каждой оси происходит на небольшое расстояние.
Можно применить и другие стратегии изменения шага в процессе поиска. Хорошие результаты, например, могут быть иногда получены с использованием алгоритма изменения шага, основанного на свойствах чисел Фибоначчи.
Рис. 6. Характер движения к оптимуму в методе релаксации
Существенной особенностью метода релаксации является зависимость времени поиска от ориентации системы координат. На рисунке 7 показаны линии постоянного уровня одной и той же целевой функции в системах координат, отличающихся между собой поворотом осей.
Рис. 7. Зависимость времени поиска оптимума методом релаксации от ориентации системы координат.
Если в случае, изображенном на рисунке 7-а, для достижения минимума целевой функции необходимо только два цикла движения вдоль осевых направлений, то для случая, приведенного на рисунке 7-б, число таких циклов возрастает весьма существенно.
Рис. 8. Остановка поиска в методе релаксации на границе
Рис. 9. Остановка поиска в методе релаксации на „дне оврага".
Если на область изменения независимых переменных наложены ограничения типа неравенств, то при применении метода релаксации иногда могут возникать значительные трудности. В качестве примера можно привести случай, изображенный на рисунке 8, когда поиск оптимума методом релаксации «застревает» в любой точке границы. Точно так же обстоит дело, если у целевой функции имеются овраги, направление которых не совпадает с осевыми. При этом поиск «застревает» в любой точке «дна» оврага (рисунок 9).
Описание блок-схемы алгоритма
В блок-схеме алгоритма (см. рисунок 10) поиска экстремума методом релаксации в качестве целевой функции в блок-схеме рассматривается пример формулы двухмерного эллипса.
В блоке 1 предусмотрен ввод исходных данных: параметров эллипса – a и b, координат начальной точки поиска - x(1) и x(2), величина шага - h, заданной точности поиска -ε, значения величины изменения аргумента при нахождения частных производных – dx. Счетчик шагов (количество расчетов целевой функции) в начальный момент должен быть равен единице (n=1), так как до начала итерационных процедур требуется один раз рассчитать функцию цели – F0, которая рассчитывается во втором блоке.
В блоках 3-8 производится расчет двух частных производных, для чего в блоке 3 осуществляется организация цикла попеременного расчета частных производных двухмерной функции (i=1,2). В блоке 4 производится поочередное изменение аргумента x(i) на величину dx. В блоке 5 производится расчет целевой функции при измененном аргументе - F1, а в блоке 6 счетчик – n увеличивает свое значение на единицу. Блок 7 предназначен для расчета и запоминания величины изменения функции – R(i), для соответствующей i-ой координаты, а в блоке 8 осуществляется возврат в исходную точку i-ой координаты: x(i) – dx. После завершения расчета частной производной по первой координате – х(1) блок цикла 3 производит аналогичные действия по второй координате - х(2).
В блоке 9 рассчитывается критерий окончания поиска – Е в соответствии с формулой (4,1), а в блоке 10 осуществляется его сравнение со значением заданной точности ε. Если критерий Е будет меньше заданной точности,
|
|
|
 |
|
 |
Рис. 10. Блок-схема алгоритма поиска экстремума методом релаксации
то в блоке 11 производится вывод результатов поиска: х(1), х(2), F, n. В противном случае управление передается на блоки 11-17 «движения» вдоль осевого направления с наибыстрейшим убыванием целевой функции.
В блоке 12 осуществляется сравнение модулей частных производных двух координат, после выбора наибольшей по модулю частной производной производится изменения этой переменной в соответствии с формулой (2,2) в блоке 12 или 14. После расчета значения новой целевой функции – F в блоке 15 и увеличения счетчика n на единицу в блоке 16, в блоке 17 сравниваются новое - F и старое – F0 значения функции цели. Если шаг был удачным, то управление передается на блок 12 для повторения итерации «продвижения» вдоль выбранной оси. При этом в блоке 18 производится переприсвоение ячейке F0 нового значения целевой функции – F для организации очередной итерации движения вдоль выбранной оси. Если шаг был неудачным, то блок 17 передает управление на блок 3 и процедура выбора нового осевого направления движения повторяется (блоки 3-8) и т.д.
Задание
1. Возьмите у преподавателя исходные данные: а, в, ε, х(1) и х(2), а также свой вариант вида функции цели.
2. Составьте программу в среде Matlab, реализующую алгоритм метода градиента (см. рисунок 10).
3. Выберите начальные значения параметров метода: изменение аргумента – dx и величину шага поиска – h. Найдите с помощью программы минимальное значение функции – F, координаты соответствующей точки х(1), х(2) и скорость сходимости алгоритма– n.
4. Дополните программу, реализующую алгоритм рисунка 10, фрагментами, позволяющими вывести в графическом виде на экран монитора стратегию поиска – изменение координаты х(1) и х(2).
5. Измените начальные значения параметров метода dx и h, как в сторону их увеличения, так и в сторону уменьшения. Проанализируйте полученные при этом результаты поиска.
6. Попробуйте сместить координаты начальной точки х(1) и х(2) и повторите поиск экстремума, сравните результаты с результатами, полученными в п.п. 3 и 5.
7. Измените значение величины критерия окончания поиска – ε сначала в два раза больше, а затем в два раза меньше. Повторите расчеты и сравните полученные результаты с результатами пункта 3.
8. Подготовьте отчет с анализом полученных результатов.
Контрольные вопросы
1. В чем заключается основная идея метода релаксации?
2. Из каких двух этапов состоит процедура поиска экстремума методом релаксации?
3. Какие стратегии изменения шага спуска Вы знаете и в чем их преимущества и недостатки?
4. Почему скорость сходимости данного алгоритма существенно зависит от ориентации «оврагов»?
5. Почему поиск методом релаксации зависит от типа ограничений?
6. Объясните почему при приближении к экстремуму желательно уменьшать шаги?
7. В каких блоках осуществляется расчет частных производных?
8. В каких блоках осуществляется собственно стратегия алгоритма (4,2) и что при этом происходит с координатами исходной точки?
9. Зачем в блоке 17 производится переприсвоение значений целевой функции?
10. Почему в качестве критерия окончания поиска принята величина Е?
11. На сколько единиц увеличивается показания счетчика шагов – n в течение одной итерации?
12. В каком блоке алгоритма производится расчет значения новой функции цели?
Таблица 5
Диапазон изменения исходных данных для метода релаксации
| a | b | dx | x(1) | x(5) | ε |
| -10; +10 | -10; +10 | -10; +10 | -10; +10 | -10; +10 | 0,001;0,01 |
Примечание: Конкретные значения исходных данных каждому студенту дает преподаватель в пределах указанных диапазонов.