Норенков И.П. - Автоматизированное производство (1054022), страница 37
Текст из файла (страница 37)
!"#$%!#&'&($"!))$*+($*,#&($"!)&*995@!"! 4%!#*%!#&F*:,$*$I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&M4.2. $B?48 /.-4549 43-+/+?:=++'D:,,+H+7:=+> /.-4549 /:-./:-+A.,74@4 384@8://+849:0+>. В САПР основными методами оптимизации являются поисковые методы. Поисковые методы основаны на пошаговом измененииуправляемых параметровXk+1 = Xk + ∆Xk,(4.5)где в большинстве методов приращение ∆Xk вектора управляемых параметров вычисляется по формуле∆Xk = hg(Xk).(4.6)Здесь Xk — значение вектора управляемых параметров на k-м шаге, h — шаг, а g(Xk) — направлениепоиска.
Следовательно,. если выполняются условия сходимости, то реализуется пошаговое (итерационное) приближение к экстремуму.Методы оптимизации классифицируют по ряду признаков.В зависимости от числа управляемых параметров различают методы #-*#/$"*#; и /*#8#/$"*#;оптимизации, в первых из них управляемый параметр единственный, во вторых размер вектора X неменее двух. Реальные задачи в САПР многомерны, методы одномерной оптимизации играют вспомогательную роль на отдельных этапах многомерного поиска.Различают методы 7+4#(*#; и 2$67+4#(*#; оптимизации по наличию или отсутствию ограничений.
Для реальных задач характерно наличие ограничений, однако методы безусловной оптимизациитакже представляют интерес, поскольку задачи условной оптимизации с помощью специальных методов могут быть сведены к задачам без ограничений.В зависимости от числа экстремумов различают задачи одно- и многоэкстремальные. Если метод ориентирован на определение какого-либо локального экстремума, то такой метод относится к 4#%)45*./ /$&#-)/.
Если же результатом является глобальный экстремум, то метод называют /$&#-#/84#2)45*#8# 0#'+%). Удовлетворительные по вычислительной эффективности методы глобального поиска для общего случая отсутствуют и потому на практике в САПР используют методы поиска локальных экстремумов.Наконец, в зависимости от того, используются при поиске производные целевой функции по управляемым параметрам или нет, различают методы нескольких порядков.
Если производные не используются, то имеет место метод *74$(#8# 0#"9-%), если используются первые или вторые производные, то соответственно метод 0$"(#8# или (&#"#8# 0#"9-%). Методы первого порядка называют также градиентными, поскольку вектор первых производных F(X) по N есть градиент целевой функцииgrad (F(X)) = (∂F/∂x1, ∂F/∂x2,...∂F/∂xn).Конкретные методы определяются следующими факторами:1) способом вычисления направления поиска g(Xk) в формуле (4.6);2) способом выбора шага h;3) способом определения окончания поиска.Определяющим фактором является первый из перечисленных в этом списке, он подробно описан ниже.Шаг может быть или постоянным, или выбираться исходя из одномерной оптимизации — поиска минимума целевой функции в выбранном направлении g(Xk). В последнем случае шаг будем называть оптимальным.Окончание поиска обычно осуществляют по правилу: если на протяжении r подряд идущих шагов траектория поиска остается в малой ε-окрестности текущей точки поиска Xk, то поиск следуетпрекратить, следовательно, условие окончания поиска имеет вид|Xk - Xk-r| < ε.E.-451 4504/.8042 43-+/+?:=++.
К методам одномерной оптимизации относятся методы дихотомического деления, золотого сечения, чисел Фибоначчи, полиномиальной аппроксимации и рядих модификаций.Пусть задан отрезок [A,B], на котором имеется один минимум (в общем случае нечетное число&.+.)$(*),$" . !"#$%!#&'&($"!))$*+($*,#&($"!)&*1005@!"! 4%!#*%!#&F*:,$*$I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&Mминимумов). Согласно /$&#-7 -',#&#/'1$+%#8# -$4$*'9 (рис. 4.3,а) отрезок делятпополам и в точках, отстоящих от центра :отрезка на величину допустимой погрешности q, рассчитывают значения целевойфункции F(C+q) и F(C-q). Если окажется,что F(C+q) > F(C-q), то минимум находит%+,.
4.3. Одномерная минимизация:ся на отрезке [A,C], если F(C+q) < F(C-q),адихотомическоеделение; б - золотое сечението минимум — на [C,B], если F(C+q) =F(C-q) — на [C-q,C+q]. Таким образом, на следующем шаге вместо отрезка [A,B] нужно исследоватьсуженный отрезок [A,C], [C,B] или [C-q,C+q].
Шаги повторяются, пока длина отрезка не уменьшитсядо величины погрешности q. Таким образом, требуется не более N шагов, где N — ближайшее кlog((B-A)/q) целое значение, но на каждом шаге целевую функцию следует вычислять дважды.По /$&#-7 6#4## +$1$*'9 (рис. 4.3,б) внутри отрезка [A,B] выделяют две промежуточные точки :1 и D1 на расстоянии s = aL от его конечных точек, где L = B-A — длина отрезка. Затем вычисляют значения целевой функции F(x) в точках :1 и D1.
Если F(C1) < F(D1), то минимум находится на отрезке [A,D1], если F(C1) > F(D1)), то — на отрезке [C1,B], если F(C1) = F(D1) — на отрезке [ C1, D1].Следовательно, вместо отрезка [A,B] теперь можно рассматривать отрезок [A,D1], [C1,B] или [C1, D1],т.е. длина отрезка уменьшилась не менее чем в L/(L-aL) = 1/(1-a) раз. Если подобрать значение ) так,что в полученном отрезке меньшей длины одна из промежуточных точек совпадет с промежуточнойточкой от предыдущего шага, т.е. в случае выбора отрезка [A,D1] точка D2 совпадет с точкой C1, а вслучае выбора отрезка [C1,B] точка C2 — с точкой D1, то это позволит сократить число вычисленийцелевой функции на всех шагах (кроме первого) в 2 раза.Условие получения такого значения ) формулируется следующим образом (1-2a)L k = aL k-1, откуда с учетом того, что Lk/Lk-1= 1/(1-a), имеем ) = 0,382.
Это значение и называют 6#4#&./ +$1$*'$/.Таким образом, требуется не более N шагов и N+1 вычисление целевой функции, где N можнорассчитать, используя соотношение (B-A)/E = (1-a)N при заданной погрешности [ определения экстремума.Согласно /$&#-7 1'+$4 H'2#*)11', используют числа Фибоначчи Ri, последовательность которых образуется по правилу Ri+2 = Ri+1 + Ri при R0 = R1 = 1, т.е. ряд чисел Фибоначчи имеет вид 1, 1, 2,3, 5, 8, 13, 21, 34, 55, 89, 144....
Метод аналогичен методу золотого сечения с тем отличием, что коэффициент ) равен отношению Ri-2 /Ri, начальное значение i определяется из условия, что Ri должно бытьнаименьшим числом Фибоначчи, превышающим величину (B-A)/E, где [ — заданная допустимая погрешность определения экстремума.
Так, если (I-K)/[ = 100, то начальное значение i = 12, посколькуR1= 144, и ) = 55/144 = 0,3819, на следующем шаге будет a = 34/89 = 0,3820 и т.д.По /$&#-7 0#4'*#/')45*#; )00"#%+'/)='' при аппроксимации F(x) квадратичным полиномом(4.7)P(x) = a0 + a1x + a2x2выбирают промежуточную точку : и в точках K, I, : вычисляют значения целевой функции.
Далеерешают систему из трех алгебраических уравнений, полученных подстановкой в (4.7) значений K,I,:вместо , и вычисленных значений функции вместо S(,). В результате становятся известными значения коэффициентов )k в (4.7) и, исходя из условия dP(x)/dx = 0, определяют экстремальную точку Fполинома. Например, если точка : выбрана в середине отрезка [A,B], то F = C + (C-A)(F(A)-F(B)) /(2(F(A)-2F(C)+F(B))).E.-451 B.?<,D49042 43-+/+?:=++. Среди методов нулевого порядка в САПР находят применение методы Розенброка, конфигураций (Хука-Дживса), деформируемого многогранника (НелдераМида), случайного поиска.
К методам с использованием производных относятся методы наискорейшего спуска, сопряженных градиентов, переменной метрики.L$&#- S#6$*2"#%) является улучшенным вариантом покоординатного спуска.Метод покоординатного спуска характеризуется выбором направлений поиска поочередно вдоль&.+.)$(*),$" . !"#$%!#&'&($"!))$*+($*,#&($"!)&*1015@!"! 4%!#*%!#&F*:,$*$I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&Mвсех n координатных осей, шаг рассчитывается на основе одномерной оптимизации, критерий окончания поиска |Xk Xk n| < ε, где ε — заданная точность определения локальногоэкстремума, n — размерность пространства управляемых параметров. Траектория покоординатного спуска для примерадвумерного пространства управляемых параметров показанана рис. 4.4, где Xk — точки на траектории поиска, xi — управляемые параметры.
Целевая функция представлена своимилиниями равного уровня, около каждой линии записано соответствующее ей значение F(X). Очевидно, что Q есть точкаминимума.При использовании метода покоординатного спуска ве- %+,. 4.4. Траектория покоординатного спускалика вероятность “застревания” поиска на дне оврага вдали от точки экстремума. На рис. 4.5 видно, что после попадания в точку C,расположенную на дне оврага, дальнейшие шаги возможны лишьв направлениях )) или bb, но они приводят к ухудшению целевойфункции. Следовательно, поиск прекращается в точке C.+ - 0 B .F 6 9 0 . . U(")8#/ называют часть пространства управляемыхпараметров, в которой наблюдаются слабые изменения производных целевойфункции по одним направлениям и значительные изменения с переменой знака— по некоторым другим направлениям.
Знак производной меняется в точках,принадлежащих дну оврага.В то же время при благоприятной ориентации дна оврага, а %+,. 4.5. "Застревание" покоординатногоспуска на дне оврагаименно при положении одной из координатных осей, близком кпараллельности с дном оврага, поиск оказывается весьма быстрым. Эта ситуация показана на рис. 4.6.Метод Розенброка заключается в таком повороте координатных осей, чтобы одна из них оказалась квазипараллельной дну оврага.
Такой поворот осуществляют на основе данных, полученныхпосле серии из n шагов покоординатного спуска. Положение новых осей si может быть получено линейным преобразованиемпрежних осей xi: ось s1 совпадает по направлению с вектором Xk+n- Xk; остальные оси выбирают из условия ортогональности к N1 идруг к другу.%+,. 4.6. Траектория покоординатногоДругой удачной модификацией покоординатного спуска яв- спуска при благоприятной ориентацииляется /$&#- %#*E'87")=';. В соответствии с этим методом внакоординатных осейчале выполняют обычную серию из n шагов покоординатного спуска, затем делают дополнительный шаг в направлении вектора Xk- Xk-n, как показано на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
