Норенков И.П. - Автоматизированное производство (1054022), страница 39
Текст из файла (страница 39)
Однако при численном решении (4.20), что имеет место при использовании алгоритмических моделей, возникают те же трудности, что и в методе Ньютона. Поэтому в САПР основными методами решения ЗМП являются методы штрафных функций и проекции градиента.Основная идея /$&#-#( >&")E*., E7*%='; — преобразование задачи условной оптимизациив задачу безусловной оптимизации путем формирования новой целевой функции Ф(N) введением висходную целевую функцию F(X) специальным образом выбранной функции штрафа S(X):Ф(N) = F(X) + rS(X),где r — множитель, значения которого можно изменять в процессе оптимизации.Среди методов штрафных функций различают методы внутренней и внешней точки. Согласнометодам внутренней точки ( иначе называемым методами 2)"5$"*., E7*%=';) исходную для поискаточку можно выбирать только внутри допустимой области, а для методов внешней точки как внутри,так и вне допустимой области (важно лишь, чтобы в ней функции целевая и ограничений были бы определены).
Ситуация появления барьера у целевой функции Ф(,) и соотношение между условным вточке x2 и безусловным в точке x1 минимумами F(,) в простейшем одномерном случае иллюстрируется рис. 4.10.Примеры штрафных функций:1) для метода внутренней точки при ограничениях ϕi(X)> 0mS(X) = ∑ (1/ ϕi(X)),i=Wгде m — число ограничений типа неравенств;2) для метода внешней точки при таких же ограниченияхmS(X) = ∑ (min{0, ϕi(X)})2 —i=Wздесь штраф сводится к включению в Ф(N) суммы квадратов активных (т.е.
нарушенных) ограничений;3) в случае ограничений типа равенств ψi(X) = 0%+,. 4.)0. Пояснение метода штрафныхфункцийLS(X) = ∑ (ψi(X))2.i=WЧем больше коэффициент r, тем точнее решение задачи, однако при больших r может ухудшаться ее обусловленность. Поэтому в начале поиска обычно выбирают умеренные значения r, увеличивая их в окрестностях экстремума.Основной вариант /$&#-) 0"#$%='' 8")-'$*&) ориентирован на задачи математического программирования c ограничениями типа равенств.Поиск при выполнении ограничений осуществляется в подпространстве (n-m) измерений, где n— число управляемых параметров, m — число ограничений, при этом движение осуществляется в направлении проекции градиента целевой функции F(X) на гиперплоскость, касательную к гиперповерхности ограничений (точнее к гиперповерхности пересечения гиперповерхностей ограничений).Поиск минимума начинают со спуска из исходной точки на гиперповерхность ограничений.
Далее выполняют шаг в указанном выше направлении (шаг вдоль гиперповерхности ограничений). Поскольку этот шаг может привести к заметному нарушению ограничений, вновь повторяют спуск на ги&.+.)$(*),$" . !"#$%!#&'&($"!))$*+($*,#&($"!)&*1065@!"! 4%!#*%!#&F*:,$*$I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&Mперповерхность ограничений и т.д. Другими словами, поиск заключается в выполнении пар шагов, каждая пара включает спуск на гиперповерхность ограничений и движение вдоль гиперповерхности ограничений.Идею метода легко пояснить для случая поиска в двумерном пространстве при одном ограничении ψ(X) = 0. На рис.
4.11 это ограничениепредставлено жирной линией, а целевая функция— совокупностью более тонких линий равногоуровня. Спуск обычно осуществляют по нормалик гиперповерхности ограничений (в данном случае к линии ограничения). Условие окончанияпоиска основано на сопоставлении значений це%+,. 4.)). Траектория поиска в соответствии с методомлевой функции в двух последовательных точках, проекции градиента: Q - условный экстремум; 0, ), 2, 3 получаемых после спуска на гиперповерхностьточки на траектории поискаограничений.Рассмотрим вопрос, касающийся получения аналитических выражений для направлений спускаи движения вдоль гиперповерхности ограничений.:07+%.
Необходимо из текущей точки поиска ( попасть в точку C, являющуюся ближайшей к (точкой на гиперповерхности ограничений, т.е. решить задачуmin |B-A|при условии ψ(X)=0, которое после линеаризации в окрестностях точки ( имеет видψ(B) + (grad ψ(B))T(A-B) = 0.Используя метод множителей Лагранжа, обозначая C-(=U и учитывая, что минимизация расстояния равнозначна минимизации скалярного произведения U на U, запишемФ(C) = UTU + λ (ψ(B)+(grad ψ(B)) TU);∂Ф/∂C = 2U + λ (grad ψ(B)) = 0;(4.21)(4.22)∂Ф/∂λ= ψ(B) + (grad ψ(B))TU = 0.Тогда из (4.21) получаем выражениеU = - 0,5λ (grad ψ(B)),подставляя его в (4.22), имеемψ(B) - 0,5λ (grad ψ(B))T grad ψ(B)= 0;откудаλ = (0,5(grad ψ(B))T grad ψ(B))-1ψ(B).и окончательно, подставляя λ в (4.21), находимU = - grad ψ(B)(grad ψ(B))T grad ψ(B))-1 ψ(B).N('@$*'$ (-#45 8'0$"0#($",*#+&' #8")*'1$*';.
Шаг в гиперплоскости D, касательной к гиперповерхности ограничений, следует сделать в направлении вектора S, на котором целевая функцияуменьшается в наибольшей мере при заданном шаге h. Уменьшение целевой функции при переходеиз точки C в новую точку * подсчитывают, используя формулу линеаризации F(X) в окрестностяхточки C:F(C) - F(A) = h(grad F(A))TS,где grad F(A)TS — приращение F(X), которое нужно минимизировать, варьируя направления S(4.23)min F(C) = min ((grad F(A))TS),где вариация S осуществляется в пределах гиперплоскости D; gradψ(A) и S — ортогональные векто&.+.)$(*),$" .
!"#$%!#&'&($"!))$*+($*,#&($"!)&*1075@!"! 4%!#*%!#&F*:,$*$I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&Mры. Следовательно, минимизацию (4.23) необходимо выполнять при ограничениях(grad ψ(A))TS = 0,STS = 1.Последнее ограничение говорит о том, что при поиске направления движения, вектор S долженлишь указывать это направление, т.е.
его длина несущественна (пусть S — единичный вектор).Для решения (4.23) используем метод множителей ЛагранжаФ(S,λ,q) = (grad F(A))TS + λ(grad ψ(A))TS + q(STS-1),где λ и q — множители Лагранжа;∂Ф/∂S = grad F(A) + λ grad ψ(A) + qS = 0;(4.24)∂Ф/∂λ = (grad ψ(A))TS = 0;(4.25)(4.26)∂Ф/∂q = STS-1 = 0.Из (4.24) следует, чтоS = -(grad F(A) + λ grad ψ(A) )/q;подставляя S в (4.25), получаем(grad ψ(A))T grad F(A) + λ (grad ψ(A))T grad ψ(A) = 0,откудаλ = - [(grad ψ(A))T grad ψ(A)] -1 (grad ψ(A))T grad F(A), S == - {gradF(A)-gradψ(A)[(gradψ(A))Tgradψ(A)]-1(gradψ(A))TgradF(A)} / q =(4.27)= - {E - grad ψ(A)[(grad ψ(A))T grad ψ(A)]-1 (grad ψ(A)) T}grad F(A) / q.Таким образом, матрица% = E - grad ψ(A)[(grad ψ(A))T grad ψ(A)]-1 grad ψ(A))Tпредставляет собой проектирующую матрицу, а вектор S, рассчитанный по (4.27), — проекцию градиента gradF(A) на гиперповерхность ограничений.Частным случаем применения метода проекции градиента являются задачи оптимизации с максиминным критерием.
Действительно, для поиска экстремума функции минимумаmax min Zj (X),Xjгде Zj — нормированная величина j-го выходного параметра yj, удобно применять метод проекции градиента. В качестве ограничений задачи в исходной постановке фигурируют только прямые ограничения,max i > xi > xmin i.Здесь ,maxi и xmini— граничные значения допустимого диапазона варьирования параметра ,i. В процессе поиска, если минимальной является функция Zq(X) и траектория поиска пересекает гребеньZq(X) - Zk(X) = 0,(4.28)то поиск продолжается в направлении проекции градиента функции Zq(X) на гиперповерхность гребня (4.28).4.3. "4,-:0497: ?:5:A ,-8<7-<804@4 ,+0-.?:"84=.5<81 ,+0-.?: 384.7-016 8.I.0+2. Принятие проектных решений охватывает широкийкруг задач и процедур — от выбора вариантов в конечных и обозримых множествах до задач творческого характера, не имеющих формальных способов решения.Соответственно в САПР применяют как средства формального синтеза проектных решений, выполняемого в автоматическом режиме, так и вспомогательные средства, способствующие выполнению синтеза проектных решений в интерактивном режиме.
К вспомогательным средствам относятсябазы типовых проектных решений, системы обучения проектированию, программно-методическиекомплексы верификации проектных решений, унифицированные языки описания ТЗ и результатовпроектирования.&.+.)$(*),$" . !"#$%!#&'&($"!))$*+($*,#&($"!)&*1085@!"! 4%!#*%!#&F*:,$*$I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&MЗадачи синтеза структур проектируемых объектов относятся к наиболее трудно формализуемым.Существует ряд общих подходов к постановке этих задач, однако практическая реализация большинства из них неочевидна.
Поэтому имеются лишь “островки” автоматического выполнения процедурсинтеза среди “моря” проблем, ждущих автоматизации.Именно по этой причине структурный синтез, как правило, выполняют в интерактивном режимепри решающей роли инженера-разработчика, а ЭВМ играет вспомогательную роль: предоставлениенеобходимых справочных данных, фиксация и оценка промежуточных и окончательных результатов.Однако в ряде приложений имеются и примеры успешной автоматизации структурного синтезав ряде приложений; среди них заслуживают упоминания в первую очередь задачи конструкторскогопроектирования печатных плат и кристаллов БИС, логического синтеза комбинационных схем цифровой автоматики и вычислительной техники, синтеза технологических процессов и управляющихпрограмм для механообработки в машиностроении и некоторые другие.Структурный синтез заключается в преобразовании описаний проектируемого объекта: исходное описание содержит информацию о требованиях к свойствам объекта, об условиях его функционирования, ограничениях на элементный состав и т.п., а результирующее описание должно содержатьсведения о +&"7%&7"$, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
