1 Системный подход к проектированию сложных систем
 Скачать 0.97 Mb.
|
|
Методы многомерной оптимизации Рис. 3.6. Целевая функция и линии равного уровня Метод покоординатного спуска В методе покоординатного спуска, иначе называемом методом Гаусса – Зейделя, направление поиска совпадает с направлением координатных осей в пространстве управляемых параметров. Величину шага выбирают методом оптимального шага (решая при этом задачу одномерной оптимизации). Траектория покоординатного спуска для двумерного случая показана на рисунке 3.7. Целевая функция (ЦФ) отображена линиями равного уровня, значения которых нанесены на каждую линию. Точка Э соответствует минимуму ЦФ. Метод Гаусса – Зейделя прост, но малонадежен, особенно для так называемых овражных целевых функций. x 1 x 2 I(X)=I(x 1 ,x 2 ) Э x 1 * x 2 * I=25 I=15 I=20 I*=13 I=25 I=20 I*=13 I=15 Рис. 3.7. К методу Гаусса-Зейделя Оврагом называется часть пространства управляемых параметров, в которой наблюдаются слабые изменения производных ЦФ по одним направлениям, но значительные изменения (с переменой знака!) – по некоторым другим направлениям. Знак производной меняется в точках, принадлежащих дну оврага. Рис. 3.8. Остановка процедуры поиска в точке линии дна оврага Если целевая функция имеет «овражный» характер, то при использовании метода покоординатного спуска велика вероятность остановки, или «застревания» процедуры поиска в точках линии дна оврага. Из рисунка 3.8 видно, что после попадания в точку А, расположенную на дне оврага, дальнейшие шаги возможны только в направлениях aa или bb, но они приводят к ухудшению целевой функции. Следовательно, поиск прекращается в точке А. Метод Розенброка В то же время при благоприятной ориентации дна оврага, а именно при положении одной из координатных осей, близком к параллельности с дном оврага, поиск оказывается весьма быстрым. Эта ситуация показана на рис. 3.9. Рис. 3.9. К методу Розенброка Метод Розенброка заключается в таком повороте координатных осей, чтобы одна из них оказалась квазипараллельной дну оврага. Такой поворот осуществляют на основе данных, полученных после серии из n шагов покоординатного спуска. Положение новых осей q i может быть получено линейным преобразованием прежних осей x i :ось q 1 , совпадает по направлению с вектором x k+n –x k , остальные оси выбирают исходя из условия ортогональности к x 1 и друг кдругу. Метод конфигураций Удачной модификацией покоординатного спуска является метод конфигураций. В соответствии с этим методом вначале выполняют обычную серию из n шагов покоординатного спуска, затем делают дополнительный шаг (его размер определяется одномерной оптимизацией) в направлении вектора x k – x k-n , как показано на рис. 3.10. Рис. 3.10. К методу конфигураций Дополнительный шаг выполняют в направлении вектора x 3 - x 1 , что и приводит в точку x 4 , которая значительно ближе к экстремуму. Вслед за этим серия шагов покоординатного спуска повторяется и т.д. – вплоть до окончания поиска. Метод деформируемого многогранника Поиск экстремума методом деформируемого многогранника основан на построении многогранника с (n+1) вершинами на каждом шаге поиска, где n — размерность пространства управляемых параметров. В начале поиска эти вершины выбирают произвольно, на последующих шагах выбор подчинен правилам метода. Эти правила на примере двумерной задачи оптимизации иллюстрируются рис. 3.11. Выбраны вершины исходного треугольника: x 1 , x 2 , x 3 . Новая вершина x 4 находится на луче, проведенном из худшей вершины x 1 (из вершины с наибольшим значением целевой функции) через центр тяжести ЦТ многогранника, причем рекомендуется x 4 выбирать на расстоянии d от ЦТ, равном |ЦT – x 1 | . Новая вершина x 4 заменяет худшую вершину x 1 Рис. 3.11. К методу деформируемого многоугольника Если оказывается, что x 4 имеет лучшее значение целевой функции среди вершин многогранника, то расстояние d увеличивают – так, как показано на рисунке: увеличение d дает точку x 5 В новом многограннике с вершинами x 2 , x 3 , x 5 худшей является вершина x 2 , аналогично получают вершину x 6 , затем вершину x 7 и т. д. Если новая вершина окажется худшей, то в многограннике нужно сохранить лучшую вершину, а длины всех ребер уменьшить, например, вдвое (стягивание многогранника клучшей вершине). Поиск прекращается при выполнении условия уменьшения размеров многогранника до предела. Метод Монте-Карло Метод Монте-Карло относится к методам случайного поиска (существует много других случайных алгоритмов поиска). В пространстве управляемых параметров выделяется область допустимых значений параметров x i min < x i i max (i=1,2,…,n) которой ставится в соответствие нормированная область управляемых параметров, где каждый из параметров может принимать значения от нуля до единицы. Генератор псевдослучайных чисел (ПСЧ), выдает числа на интервале [0,1], используемые для определения координат текущей выбранной точки в пространстве нормированных параметров, и в этой точке вычисляется значение целевой функции. Из всех исследованных выбирается точка с минимальным значением ЦФ (рис. 3.12). Цель поиска достигается при попадании в некоторую заданную область в пространстве параметров объемом Δ. Вероятность такого попадания, в случае проведения N испытаний, определяется по формуле: Отсюда можно найти количество испытаний, необходимое для обеспечения попадания в заданную Δ-окрестность с вероятностью P: Так как чаще всего, P>>Δ, то количество испытаний должно быть очень велико. К методу Монте-Карло x 1 x 2 I(X)=I(x 1 ,x 2 ) x 1 x 2 I(X)=I(x 1 ,x 2 ) I 0 =22 I 2 =17 I 1 =18 I=25 I=20 I=15 0 1 0 1 X 0 X 1 x 1 x 2 X 2 0,3 0,1 0,8 0,7 0,5 0,2 X i Генератор ПСЧ Целевая функция ( ЦФ) Линии равного уровня ЦФ Линии равного уровня ЦФ © Область поиска Рис. 3.12. К методу Монте-Карло N P ) 1 ( 1 ) 1 log( ) 1 log( P N Градиентные методы Градиентные методы относятся к методам первого порядка и используют для определения направления продолжения поиска градиент целевой функции в пространстве управляемых параметров: Такие методы позволяют достичь экстремума целевой функции за меньшее число шагов по сравнению с методами нулевого порядка, но требуют большего количества вычислений на каждом шаге. Метод наискорейшего спуска На каждом шаге поиска экстремума, осуществляется вычисление градиента целевой функции и производится шаг в направлении противоположном градиенту (т.к. нам необходимо обнаружить минимум, а градиент направлен в сторону возрастания целевой функции): g = – grad I(x)/||grad I(x)||. Деление на норму вектора градиента выполнено постольку, поскольку вектор g – единичный. Величина шага h k выбирается по методу оптимального шага: Метод сопряженных градиентов (Флетчера-Ривза) Направление поиска определяется как: где g k – вектор управляемых параметров на k–м шаге; g k-1 – вектор градиента на предыдущем k–1 шаге; β k – коэффициент, учитывающий предысторию поиска и равный скалярному произведению градиентов на k–1 и k–2 шагах: T n T n x x x x x I x I x I x I grad ] ,..., , [ , ,..., , ) ( 2 1 2 1 ) ( min 1 k k k h g h x k , ) ) ( ( / ) ) ( ( 1 1 1 1 k k k k k k k g x I grad g x I grad g ) ( ), ( ) ( ), ( 2 2 1 1 k k k k k x grad x grad x grad x grad Метод Ньютона Метод Ньютона основан на использовании необходимых условий безусловного экстремума целевой функции I(x): grad I(x) = 0 . (1) Выражение (1) представляет собой систему алгебраических уравнений, для решения которой можно применить известный численный метод, называемый методом Ньютона. Корень системы (1) есть стационарная точка, т. е. возможное решение экстремальной задачи. Метод Ньютона является итерационным, он основан на линеаризации (1) в окрестности текущей точки поиска x k grad I(x) = grad I(x k ) + Г(x – x k ) = 0. (2) Г – матрица Гессе. Матрицей Гессе называют матрицу вторых частных производных целевой функции по управляемым параметрам. Выражение (2) – это система линейных алгебраических уравнений. Ее корень есть очередное приближение x k+1 крешению x k+1 =x k T Г -1 (x k ) grad I(x k ) Если процесс сходится, то решение достигается за малое число итераций, окончанием которых служит выполнение условия |x k+1 – x k | < ε. Главный недостаток метода – высокая трудоемкость вычисления и обращения матрицы Г, к тому же ее вычисление численным дифференцированием сопровождается заметными погрешностями, что снижает скорость сходимости. Рис. 3.13. К алгоритму метода Ньютона х F(х) х 2 x* х 0 х 1 х 3 х 4 х 5 F(x 0 ) F(x 1 ) F(x 2 ) F(x 3 ) F(x 4 ) F(x 5 ) Для одномерного случая метод Ньютона можно проиллюстрировать следующим образом (рис. 3.13). Требуется найти корень уравнения F(x)=0, которому соответствует точка пересечения графика функции F(x) с осью x. В начальной точке поиска x 0 вычисляется значение функции F(x0) и находится (приближенно) значение производной, которой соответствует касательная прямая. Далее находится точка пересечения x 1 этой касательной с осью x. Затем весь цикл повторяется – до нахождения искомого корня x*. Методы поиска условных экстремумов Метод множителей Лагранжа ориентирован на поиск экстремума при наличии ограничений типа равенств ψ(x) = 0, т.е. на решение задачи Суть метода заключается в преобразовании задачи условной оптимизации в задачу безусловной оптимизации с помощью образования новой целевой функции где Λ = (λ 1 , λ 2 , λ 3 , ... , λ m ) – вектор множителей Лагранжа, m – число ограничений. Необходимые условия экстремума функции Ф(x): (3) Система содержит n+m алгебраических уравнений, где n – размерность пространства управляемых параметров, ее решение дает искомые координаты экстремальной точки, а также m значений множителей Лагранжа. Пример отыскания координат точки экстремума целевой функции методом множителей Лагранжа для случая одного линейного ограничения типа равенства показан на рис. 3.14. } 0 ) ( | { ) ( x x D D x x x x I extr , ) ( ) ( ) , ( 1 m i i i x x I x Ф 0 ) ( ) , ( ; 0 ) ( ) ( ) , ( 1 x x Ф x x x x I x x Ф m i i i I усл (X) I безусл (X) x 1 x 2 I(X ) ψ(X)=x 2 -5x 1 =0 x 1 * x 2 * x 1 * x 2 * Условие (ограничение): Рис. 3.14. К методу множителей Лагранжа Метод множителей Лагранжа является по существу аналитическим и в принципе позволяет найти аналитическое решение системы уравнений (3), но при этом и целевая функция должна быть задана уравнением. Если использовать численное решение системы уравнений (3), что имеет место при использовании алгоритмических моделей, то возникают те же трудности, что и в методе Ньютона. Поэтому основными методами решения задачи математического программирования являются методы штрафных функций и проекции градиента. Методы штрафных функций Основная идея методов штрафных функций – преобразование задачи условной оптимизации в задачу безусловной оптимизации путем формирования новой целевой функции Ф(x) введением в исходную целевую функцию I(x) специальным образом выбранной функции штрафа S(x): Ф(x) = I(x) + rS(x), где r – множитель, значения которого можно изменять в процессе оптимизации. Методы штрафных функций подразделяют на методы внутренней и внешней точки. Примеры штрафных функций: 1) для метода внутренней точки при ограничениях φ i (x)> 0: где m — число ограничений типа неравенств; 2) для метода внешней точки при таких же ограничениях: здесь штраф сводится к включению в Ф(x) суммы квадратов активных (т.е. нарушенных) ограничений; 3) в случае ограничений типа равенств ψ i (x) = 0: Чем больше коэффициент r, тем точнее решение задачи, однако при больших значениях r может ухудшаться ее обусловленность. Поэтому в начале поиска обычно выбирают умеренные значения r, увеличивая их в окрестностях экстремума. Метод внутренней точки Метод допускает, что исходную для поиска точку можно выбирать только внутри допустимой области. Также называется методом барьерных функций. Ситуация появления барьера у целевой функции Ф(x) и соотношение между безусловным в точке x 1 и условным в точке x 2 минимумами I(x) в простейшем одномерном случае иллюстрируется рис. 3.15. m i i x x S 1 ) ( 1 ) ( 2 1 )}] ( , 0 { [min ) ( x x S i m i )] ( [ ) ( 2 1 x x S i l i Область выполнения ограничений φ i (x)> 0 I(x) Ф(x) φ(x) S(x) x 1 x 2 x I(x),Ф(x), S(x), φ(x) Ограничение - Исходная ЦФ - Новая ЦФ Рис. 3.15. Пример к методу внутренней точки Штрафная функция в данном примере: S(x)=1/φ(x) В общем случае для метода внутренней точки при ограничениях φ i (x)> 0 : где m — число ограничений типа неравенств. Метод проекции градиента (ПГ) Метод ПГ ориентирован на задачи математического программирования c ограничениями типа равенств. Поиск при выполнении ограничений осуществляется в подпространстве (n- m) измерений, где n – число управляемых параметров, m – число ограничений, при этом движение осуществляется в направлении проекции градиента целевой функции I(x) на гиперплоскость, касательную к гиперповерхности ограничений (ГПО), или точнее, к гиперповерхности пересечения всех ГПО). Поиск минимума начинают со спуска из исходной точки на ГПО. Далее выполняют шаг в указанном выше направлении (шаг вдоль ГПО). Поскольку этот шаг может привести к заметному нарушению ограничений, вновь повторяют спуск на ГПО и т.д. Другими словами, поиск заключается в выполнении пар шагов, каждая пара включает спуск на ГПО и движение вдоль ГПО. , ) ( 1 ) ( 1 m i i x X S Пример применения метода ПГ Случай поиска в двумерном пространстве при одном ограничении ψ(x) = 0 иллюстрирует рис. 3.16. На рисунке это ограничение представлено жирной красной линией, а целевая функция I(x) – совокупностью более тонких синих линий равного уровня. Спуск обычно осуществляют по нормали к ГПО (в данном случае к линии ограничения). Условие окончания поиска основано на сопоставлении значений целевой функции в двух последовательных точках, получаемых после спуска на гиперповерхность Рис. 3.16. Траектория поиска по методу ПГ x 1 x 2 0 1 3 2 4 5 6 7 Э ψ(x)=0 I=25 I=17 I=20 I=15 I=12 I=7 I=10 |