Norenkov.Osnovy.Avtomatizirovannogo.Proektirovania.2002 (525024), страница 38
Текст из файла (страница 38)
Далее решают систему из трех алгебраических уравнений,полученных подстановкой в (4.7) значений А, В, С вместо х и вычисленныхзначений функции вместо Р(х). В результате становятся известными значениякоэффициентов ak в (4.7), и, исходя из условия dP(x)/dx = 0, определяют экстремальную точку Э полинома. Например, если точка С выбрана в середине отрезка [А, В], то Э = С + (С - A)(F(A) - F(B)) I (2(F(A) - 2F(C) + F(B))).Методы безусловной оптимизацииСреди методов нулевого порядка в САПР находят применение методы Розенброка, конфигураций, деформируемого многогранника, случайного поиска.К методам с использованием производных относятся методы наискорейшегоспуска, сопряженных градиентов, переменной метрики.Метод Розенброка является улучшенным вариантом метода покоординатного спуска.Метод покоординатного спуска характеризуется выбором направлений поиска поочередно вдоль всех п координатных осей, шаг рассчитывается наоснове одномерной оптимизации, критерий окончания поиска \\t - \k_ J < е,где е — заданная точность определения локального экстремума, п — размерность пространства управляемых параметров.
Траектория покоординатногоспуска для примера двумерного пространства управляемых параметров показана на рис. 4.4, где Xt — точки на траектории поиска, xt — управляемые параметры. Целевая функция представлена своими линиями равного уровня, околокаждой линии записано соответствующее ей значение F(X).
Очевидно, что Эесть точка минимума.1604.2. Обзор методов оптимизацииХТ.Рис. 4.4. Траектория покоординатногоспускаРис. 4.5. «Застревание» покоординатного спуска на дне оврагаПри использовании метода покоординатного спуска велика вероятность «застревания» поиска на дне оврага вдали от точки экстремума. На рис. 4.5 видно, что после попадания в точку А, расположенную на дне оврага, дальнейшиешаги возможны лишь в направлениях аа или bb, но они приводят к ухудшениюцелевой функции. Следовательно, поиск прекращается в точке А.П р и м е ч а н и е .
Оврагом называют часть пространства управляемых параметров,в которой наблюдаются слабые изменения производных целевой функции по однимнаправлениям и значительные изменения с переменой знака по некоторым другим направлениям. Знак производной меняется в точках, принадлежащих дну оврага.В то же время при благоприятной ориентации дна овраг а, а именно при положении одной из координатных осей, близком к параллельности с дном оврага,поиск оказывается весьма быстрым. Эта ситуация показана на рис.
4.6.Метод Розенброка заключается в таком повороге координатных осей, чтобыодна из них оказалась квазипараллельной дну оврага. Такой поворот осуществляют на основе данных, полученных после серии из п шагов покоординатного спуска. Положение новых осей st может быть получено линейным преобразованием прежних осей xi: ось s} совпадаетпо направлению с вектором Xt+/i - Xk; оставь- х2ные оси выбирают из условия ортогональности к X, и друг к другу.Другой удачной модификацией покоординатного спуска является метод конфигураций (Хука - Дживса). В соответствии с этимметодом вначале выполняют обычную сериюиз п шагов покоординатного спуска, затемделают дополнительный шаг в направлениивектора X t - Х^_ я , как показано на рис.
4.7,где дополнительный шаг выполняют в на- Рис. 4.6. Траектория покоординатправлении вектора Х3— X,, что и приводит в но го спуска при благоприятнойориентации координатных осейточку Х4.6 Основы автоматизированногопроектирования1614 Математическое обеспечение синтеза проектных решенийПоиск экстремума методом деформируемого многогранника (Непдера - Мида) основан на построении многогранника с (п + 1)вершинами на каждом шаге поиска, гдеп - размерность пространства управляемыхпараметров. В начале поиска эти вершинывыбирают произвольно, на последующих шагах выбор подчинен правилам метода.Эти правила поясняются рис. 4.8 на примере двумерной задачи оптимизации.
Выбраны вершины исходного треугольника: X,,Рис. 4.7. Иллюстрация методаХ 2 , Х 3 . Новая вершина Х4находится на луче,конфигурацийпроведенном из худшей вершины X, (из вершины с наибольшим значением целевой функции) через центр тяжести ЦТ многогранника, причем рекомендуется Х4 выбирать на расстоянии d от ЦТ, равном|ЦТ - Х,|. Новая вершина Х4 заменяет худшую вершину X,.
Если оказывается,что Х4 имеет лучшее значение целевой функции среди вершин многогранника,то расстояние d увеличивают. На рисунке именно эта ситуация имеет место иувеличение J дает точку Х 5 . В новом многограннике с вершинами Х 2 , Х3, Х 5худшей является вершина Х 2 , аналогично получают вершину Х6, затем вершину Х ? и т. д. Если новая вершина окажется худшей, то в многограннике нужносохранить лучшую вершину, а длины всех ребер уменьшить, например вдвое(стягивание многогранника к лучшей вершине). Поиск прекращается при выполнении условия уменьшения размеров многогранника до некоторого предела.Случайные методы поиска характеризуются тем, что направления поиска gвыбирают случайным образом.Рис.
4.8. Иллюстрация метода деформируемого многогранника1624.2. Обзор методов оптимизацииОсобенностью метода наискорейшего спуска является выполнение шагов поиска в градиентном направленииXk+l=Xk + hk grad F(Xk~) I |grad F(Xt)\,шаг /^выбирается оптимальным с помощью одномерной оптимизации.При использовании метода наискорейшего спуска, как и большинства другихметодов, эффективность поиска существенно снижается в овражных ситуациях. Траектория поиска приобретает зигзагообразный вид с медленным продвижением вдоль дна оврага в сторону экстремума.
Чтобы повысить эффективность градиентных методов, используют несколько приемов.Один из приемов, использованный в методе сопряженных градиентов(называемом также методом Флетчера - Ривса), основан на понятии сопряженTности векторов. Векторы А и В называют Q-сопряженными, если A QB = О,где Q — положительно определенная квадратная матрица того же порядка, чтои размер N векторов А и В (частный случай сопряженности — ортогональностьтвекторов, когда Q является единичной матрицей порядка N); А — векторстрока; В — вектор-столбец.Особенность сопряженных направлений для Q = Г, где Г — матрица Гессе,в задачах с квадратичной целевой функцией F(X) заключается в следующем:одномерная минимизация F(X) последовательно по ./V сопряженным направлениям позволяет найти экстремальную точку не более чем за N шагов.П р и м е ч а н и е .
Матрицей Гессе называют матрицу вторых частных производныхцелевой функции по управляемым параметрам.Основанием для использования поиска по Г-сопряженным направлениямявляется то, что для функций F(X) общего вида может быть применена квадратичная аппроксимация, что на практике выливается в выполнение поискаболее чем за N шагов.Пример. Поиск экстремума выполняют в соответствии с формулойX = X,_, + A S .(4.8)Направление Si+1 поиска на очередном шаге связано с направлением поиска S, напредыдущем шаге 'соотношениемS +1 = -gradF(X) + w,S,(4.9)где w- коэффициент. Кроме того, учитывают условие сопряженности8Т_,Г8,= 0(4.10)и линейную аппроксимацию grad F (X) в окрестностях точки Xgrad F(X+1) = grad F(X) + Г(Х+1 - X, ).(4.1 1)Поскольку шаг h рассчитывается исходя из условия одномерной, оптимизации, то,во-первых, справедливо соотношениеS^grad F(X) = 0,(4.12)во-вторых, имеемоткуда получаемdFIdh = (dF(X)/dX)(6X/dh)6*= grad ^(X)Tgrad FQL, _,) = 0.(4.13)1634 Математическое обеспечение синтеза проектных решенийАлгоритм поиска сводится к применению формулы (4.9), пока не будет выполненоусловие окончания вычислений|gradF(X4)|<E.Чтобы определить коэффициент w , решают систему уравнений (4.8) - (4.
1 3) путемподстановки в (4. 10) величин Si+| из (4.9) и S из (4.8)илиS|+irS = (WjS, - grad F(X ))т Г(Х - X . ,)/А == (w,S - gradF(X))TIT-' (gradF(X) - grad F(X _,))//; = О,(w, S - grad F(X ))T (grad F(\) - grad F(X _ ,)) = 0,откудаw, S/ (grad F(X) - grad F(X _ ,)) - grad F(X )T grad F(X ) + grad F(X )T grad F(X,_ ,) = 0и с учетом (4.
1 2) и (4. 1 3)w S^grad F(X ,) + grad F(X )T grad F(X ) = 0.Следовательно,w = grad F(X)T grad F(X) / (S] grad F(X _ ,)).(4.14)На первом шаге поиска выбирают S, = - grad F (X0) и находят точку X, . На втором шаге по формуле (4. 14) рассчитывают w p по формулам (4.9) и (4.8) определяют 82и Х2 и т. д.Метод переменной метрики (иначе метод Девидона - Флетчера - Пауэлла) можно рассматривать как результат усовершенствования метода второгопорядка - метода Ньютона.Метод Ньютона основан на использовании необходимых условий безусловного экстремума целевой функции F(X)gradF(X) = 0.(4.15)Выражение (4.15) представляет собой систему алгебраических уравнений,для решения которой можно применить известный численный метод, называемый методом Ньютона.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
