Норенков И.П. Основы автоматизированного проектирования

Подождите немного. Документ загружается.

МАТЕМАТИЧЕСКОЕ

ОБЕСПЕЧЕНИЕ

СИНТЕЗА

ПРОЕКТНЫХ

РЕШЕНИЙ

4.1. Постановка задач

параметрического

синтеза

Место

процедур

синтеза

проектировании

Сущность проектирования заключается

принятии проектных решений, обес-

печивающих выполнение будущим объектом предъявляемых

нему требова-

ний.

Синтез проектных решений

—

основа проектирования;

от

успешного

вы-

полнения

процедуры синтеза

определяющей мере зависят потребительские

свойства будущей продукции. Конечно, анализ

—

необходимая составная часть

проектирования, служащая

для

верификации принимаемых проектных реше-

ний.

Именно анализ позволяет получить необходимую информацию

для

целе-

направленного выполнения процедур синтеза

итерационном процессе проек-

тирования.

Поэтому синтез

анализ неразрывно связаны.

Как

отмечено

в гл.

синтез подразделяют

на

параметрический

структур-

ный.

Проектирование начинается

со

структурного синтеза,

при

котором

ге-

нерируется принципиальное решение. Таким решением может быть облик

бу-

дущего летательного аппарата,

или

физический принцип действия датчика,

или

одна

из

типовых конструкций двигателя,

или

функциональная схема микропро-

цессора.

Но эти

конструкции

схемы выбирают

параметрическом виде,

т. е.

без

указания числовых значений параметров элементов. Поэтому, прежде

чем

приступить

верификации проектного решения, нужно задать

или

рассчитать

значения

этих параметров,

т. е.

выполнить параметрический

синтез.

Приме-

рами

результатов параметрического синтеза могут служить геометрические

размеры

деталей

механическом узле

или в

оптическом приборе, параметры

электрорадиоэлементов

электронной схеме, параметры режимов резания

технологической операции

т. п.

случае если

по

результатам анализа проектное решение признается нео-

кончательным,

то

начинается процесс последовательных приближений

при-

153

Математическое обеспечение синтеза проектных

решений

емлемому

варианту проекта.

Во

многих приложениях

для

улучшения проекта

удобнее варьировать значения параметров элементов,

т. е.

использовать

пара-

метрический синтез

на

базе многовариантного анализа.

При

этом задача пара-

метрического синтеза может быть сформулирована

как

задача определения

значений

параметров элементов, наилучших

позиций удовлетворения требо-

ваний

технического задания

при

неизменной структуре проектируемого объек-

та.

Тогда параметрический синтез называют параметрической оптимизацией,

или

просто

оптимизацией.

Если параметрический синтез

не

приводит

успе-

ху,

то

повторяют процедуры структурного синтеза,

т. е. на

очередных итераци-

ях

корректируют

или

перевыбирают структуру объекта.

Критерии

оптимальности

Процедуры параметрического синтеза

САПР либо выполняются челове-

ком

процессе многовариантного анализа

(в

интерактивном режиме), либо

ре-

ализуются

на

базе формальных методов оптимизации

(в

автоматическом

ре-

жиме).

последнем случае находят применение несколько постановок задач

оптимизации.

Наиболее распространенной является детерминированная постановка:

за-

даны условия работоспособности

на

выходные параметры

Y и

нужно найти

номинальные значения проектных параметров

X, к

которым относятся пара-

метры всех

или

части элементов проектируемого объекта. Назовем

эту

зада-

чу

оптимизации

базовой.

частном случае,

когда

требования

выходным

параметрам заданы нечетко,

числу рассчитываемых величин могут быть

отнесены

также нормы выходных параметров, фигурирующие

в их

условиях

работоспособности.

Если

проектируются изделия

для

дальнейшего серийного производства,

то

важное

значение приобретает такой показатель,

как

процент выпуска годных

изделий

процессе производства. Очевидно,

что

успешное выполнение усло-

вий

работоспособности

номинальном режиме

не

гарантирует

их

выполнения

при

учете

производственных погрешностей, задаваемых допусками парамет-

ров

элементов. Поэтому целью оптимизации становится максимизация про-

цента

выхода годных,

а к

результатам решения задачи оптимизации относятся

не

только номинальные значения проектных параметров,

но и их

допуски.

Базовая

задача оптимизации ставится

как

задача математического програм-

мирования

extrF(X),

(4.1)

XeD^.

В,=

{Х|<р(Х)>0,ч/(Х)

0},

где

F(X)

—

целевая функция;

X —

вектор управляемых (проектных) парамет-

ров;

ф(Х)

vj/(X)

—

функции-ограничения;

D^—

допустимая область

простран-

стве управляемых параметров. Запись (4.1) интерпретируется

как

задача

поиска

экстремума целевой функции путем варьирования управляемых пара-

метров

пределах допустимой области.

154

4.1.

Постановка

задач

параметрического

синтеза

Таким

образом,

для

выполнения расчета

но-

Уъ

Область

минальных

значений параметров необходимо,

во-

работоспособности

первых, сформулировать задачу

виде

(4.1),

во-

вторых, решить задачу поиска экстремума

F(X).

Сложность

постановки оптимизационных

проектных

задач обусловлена наличием

проек-

тируемых объектов нескольких выходных пара-

метров, которые

могут

быть критериями опти-

мальности,

но в

задаче (4.1) целевая функция

должна

быть одна. Другими словами, проектные

задачи

являются многокритериальными,

воз-

Рис

4.1.

Области

Парето

никает

проблема сведения многокритериальной

работоспособности

задачи

однокритериальной.

Применяют

несколько

способов выбора критерия оптимальности.

частном

критерии среди выходных параметров один выбирают

каче-

стве целевой функции,

условия работоспособности остальных выходных

параметров относят

ограничениям задачи

(4.1).

Эта

постановка вполне при-

емлема, если действительно можно выделить один наиболее критичный

вы-

ходной параметр.

Но в

большинстве

случаев

сказывается недостаток частно-

го

критерия (рис.

На

этом

рисунке представлено двумерное пространство выходных парамет-

ров

для

которых заданы условия работоспособности

>>,

}

Кривая

АВ

является границей достижимых значений выходных параметров.

Это

ограничение объективное

связано

существующими физическими

тех-

нологическими условиями производства, называемыми условиями реализуе-

мости.

Область,

пределах которой выполняются

все

условия реализуемости

работоспособности, называют

областью

работоспособности.

Множество

точек

пространства выходных параметров,

из

которых невозможно перемеще-

ние,

приводящее

улучшению всех выходных параметров, называют облас-

тью

компромиссов

или

областью

Парето. Участок кривой

АВ

(см. рис. 4.1)

относится

области Парето.

Если

качестве целевой функции

ситуации рис.

4.1.

выбрать параметр

}

то

результатом оптимизации будут параметры

соответствующие точке

В.

Но

это

граница области работоспособности,

и,

следовательно,

при

нестабиль-

ности внутренних

внешних параметров велика вероятность выхода

за

преде-

лы

области работоспособности. Конечно, результаты можно улучшить, если

применять

так

называемый метод уступок,

при

котором

качестве ограниче-

ния

принимают условие работоспособности

со

скорректированной

нормой

виде

где А —

уступка.

Но

возникает проблема выбора значений уступок,

т. е.

резуль-

таты оптимизации будут иметь субъективный характер. Очевидно,

что

ситуа-

ция

не

изменится, если целевой функцией будет выбран параметр

так как

оптимизация

приведет

точку

А.

155

Математическое обеспечение синтеза проектных

решений

Аддитивный

критерий объединяет

(свертывает)

все

выходные парамет-

ры

(частные критерии)

одну целевую функцию, представляющую собой

взве-

шенную

сумму

частных критериев

F(X)

= со

^(Х),

(4.2)

где со —

весовой коэффициент;

т —

число выходных параметров. Функция (4.2)

подлежит минимизации,

при

этом если условие работоспособности имеет

вид

то

со

< 0.

•'jj

Недостатки аддитивного критерия

—

субъективный подход

выбору

весо-

вых

коэффициентов

неучет

требований

ТЗ.

Действительно,

(4.2)

не

входят

нормы

выходных параметров.

Аналогичные недостатки присущи

мультипликативному критерию, целе-

вая

функция которого имеет

вид

ДХ)=Д^(Х).

(4.3)

Нетрудно

видеть,

что

если прологарифмировать

(4.3),

то

мультипликатив-

ный

критерий превращается

аддитивный.

Более предпочтительным является

максиминный

критерий,

качестве

целевой функции которого принимают выходной параметр, наиболее неблаго-

получный

позиций выполнения условий работоспособности.

Для

оценки сте-

пени

выполнения условия

работоспособности

у'-го

выходного параметра вво-

дят

запас

работоспособности

этого параметра

S и

этот

запас можно

рассматривать

как

нормированный

у'-й

выходной параметр. Например (здесь

для

лаконичности изложения предполагается,

что все

выходные

пара-

метры приведены

виду,

при

котором условия работоспособности становятся

неравенствами

форме

у <

(T-

)IT,

или

(T-y )/8,

НОМ

где

ном

—

номинальное значение,

а 5 —

некоторая характеристика рассеяния

у'-го

выходного параметра, например,

трехсигмовый

допуск. Тогда целевая фун-

кция

максиминном

критерии есть

Здесь запись

[1: т]

означает множество целых чисел

диапазоне

от 1 до т.

Задача

(4.1)

при

максиминном критерии конкретизируется следующим обра-

зом:

F(X)

= max

min

(X), (4.4)

XeD

У6

т]

156

4.2.

Обзор

методов

оптимизации

где

допустимая область

определяется только прямыми ограничениями

на

управляемые параметры

х:

Область

работо-

способности

.опусковая

область

Рис.

4.2.

Области

допусковая

работоспособности

Задачи

оптимизации

учетом

допусков

Содержательную сторону оптимизации

учетом допусков поясняет рис. 4.2,

на

котором

представлены области работоспособности

допусковая

двумерном пространстве управ-

ляемых параметров. Если собственно допус-

ки

заданы

и не

относятся

управляемым

параметрам,

то

цель оптимизации

—

макси-

мальным образом совместить

эти

области так,

чтобы вероятность выхода

за

пределы облас-

ти

работоспособности была минимальной.

Решение этой задачи исключительно трудо-

емко,

так как на

каждом шаге оптимизации

нужно

выполнять оценку упомянутой вероят-

ности методами статистического анализа,

а для

сложных моделей объектов

таким

методом является метод статистических испытаний. Поэтому

на

прак-

тике

подобные задачи решают, принимая

те или

иные допущения.

Например, если допустить,

что

цель оптимизации достигается

при

совме-

щении

центров областей работоспособности

Э и

допусковой

ном

то

оптимиза-

ция

сводится

задаче

центрирования,

т. е. к

определению центра

Э.

Задачу

центрирования обычно решают путем предварительного нормирования управ-

ляемых параметров

(

последующим вписыванием гиперкуба

максимально

возможными размерами

нормированную область работоспособности.

Примечание.

Нормирование проводят

таким

образом,

что

допусковая область

приобретает форму гиперкуба, получающегося после

нормирования.

Очевидно,

что

решение задачи центрирования позволяет

не

только оптими-

зировать

номинальные

значения проектных параметров,

но и их

допуски, если

последние относятся

управляемым параметрам.

4.2. Обзор методов

оптимизации

Классификация

методов

математического

программирования

Основными методами оптимизации

САПР являются поисковые методы,

которые

основаны

на

пошаговом изменении управляемых параметров

=Х.

ДХ.,

(4.5)

+ 1 К

где

большинстве

методов

приращение

вектора управляемых парамет-

ров

вычисляется

по

формуле

hg(X

(4.6)

157

Математическое обеспечение синтеза проектных

решений

Здесь

—

значение вектора управляемых параметров

на

k-м

шаге;

—

шаг;

g(X

)

—

направление поиска. Следовательно, если выполняются условия схо-

димости,

то

реализуется пошаговое (итерационное) приближение

экстремуму.

Методы

оптимизации классифицируют

по

ряду признаков.

зависимости

от

числа управляемых параметров различают методы

од-

номерной

многомерной

оптимизации,

первых

из них

управляемый пара-

метр единственный,

во

вторых

размер вектора

X не

менее

двух.

Реальные

задачи

САПР многомерны, методы одномерной оптимизации играют вспо-

могательную роль

на

отдельных этапах многомерного поиска.

Различают методы условной

безусловной оптимизации

по

наличию

или

отсутствию ограничений.

Для

реальных задач характерно наличие ограниче-

ний,

однако методы безусловной оптимизации также представляют интерес,

поскольку

задачи условной оптимизации

помощью специальных методов

мо-

гут

быть сведены

задачам

без

ограничений.

зависимости

от

числа экстремумов различают задачи одно-

многоэкст-

ремальные. Если метод ориентирован

на

определение какого-либо локального

экстремума,

то

такой

метод

относится

локальным

методам.

Если

же ре-

зультатом является глобальный экстремум,

то

метод называют

методом

гло-

бального

поиска.

Удовлетворительные

по

вычислительной эффективности

методы глобального поиска

для

общего случая отсутствуют,

потому

на

прак-

тике

САПР используют методы поиска локальных экстремумов.

Наконец,

зависимости

от

того,

используются

при

поиске производные

це-

левой

функции

по

управляемым параметрам

или

нет, различают методы

не-

скольких

порядков. Если производные

не

используются,

то

имеет

место

ме-

тод

нулевого порядка, если используются первые

или

вторые производные,

то

соответственно метод первого

или

второго порядка. Методы первого

по-

рядка

называют также градиентными, поскольку вектор первых производных

.F(X)

по X

есть градиент целевой функции

grad

(F(X))

(dFldx

dFldx

...,

дР1дх

Конкретные

методы определяются следующими факторами:

способом вычисления направления поиска

g(X

)

формуле

(4.6);

способом выбора шага

/г;

способом определения окончания поиска.

Определяющим фактором является первый

из

перечисленных

этом спис-

ке,

он

подробно описан далее.

Шаг

может

или

быть

постоянным,

или

выбираться исходя

из

одномерной

оптимизации

—

поиска минимума целевой функции

выбранном направлении

g(X

последнем случае

шаг

будем называть оптимальным.

Окончание поиска обычно осуществляют

по

правилу:

если

на

протяжении

подряд идущих шагов траектория поиска остается

малой е-окрестности

те-

кущей

точки поиска

то

поиск следует прекратить, следовательно, условие

окончания

поиска имеет

вид

|Х

< е.

158

4.2. Обзор

методов

оптимизации

Методы

одномерной

оптимизации

методам одномерной оптимизации относятся методы дихотомического

деления,

золотого сечения, чисел Фибоначчи, полиномиальной аппроксимации

ряд их

модификаций.

Пусть задан отрезок

[А, В], на

котором имеется один минимум

(в

общем

случае нечетное число минимумов). Согласно

методу

дихотомического

де-

ления (рис. 4.3,

а)

отрезок делят пополам

и в

точках, отстоящих

от

центра

отрезка

на

величину

допустимой

погрешности

рассчитывают значения целе-

вой

функции

F(C + q) и F(C - q).

Если окажется,

что F(C + q) > F(C - q), то

минимум находится

на

отрезке

[А,С],

если

F(C + q) <

F(C

- q), то

минимум

—

на

[С,В],

если

F(C + q) = F(C - q) — на [С - q, С + q].

Таким образом,

на

следующем шаге вместо отрезка

[А, В]

нужно исследовать суженный отрезок

[Л,С],

[С, В] или [С -

q,С

+ q].

Шаги повторяются, пока длина отрезка

не

уменьшится

до

значения погрешности

Таким образом, требуется

не

более

шагов,

где

N—

ближайшее

к log

((B-A)/q)

целое значение,

но на

каждом шаге

целевую функцию

следует

вычислять дважды.

соответствии

методом

золотого

сечения

(рис. 4.3,

б)

внутри отрезка

[А,В]

выделяют

две

промежуточные точки

Z),

на

расстоянии

5 = aL от его

конечных

точек,

где L — В - А —

длина отрезка. Затем вычисляют значения

целевой

функции

F(x)

точках

С,

£>,.

Если

F(C

)

F(D

то

минимум нахо-

дится

на

отрезке

[A,D^\,

если

F(C

{

)

F(D

)),

то — на

отрезке

[С

В],

если

F(C

}

)

F(Z)j)

— на

отрезке

[С,,

Z>J.

Следовательно, вместо отрезка

[А,В]

те-

перь

можно рассматривать отрезок

[A,D^\,

}

В] или

[С,,

D^,

т. е.

длина

от-

резка

уменьшилась

не

менее

чем в

L/(L

- aL) =

1/(1

- а)

раз. Если подобрать

значение

так,

что в

полученном отрезке меньшей длины одна

из

промежу-

точных точек совпадет

промежуточной точкой

от

предыдущего шага,

т. е. в

случае выбора отрезка

[А,

£>,]

точка

совпадет

точкой

С,,

а в

случае выбо-

ра

отрезка

[С,,

В]

точка

— с

точкой

{

то это

позволит сократить число

вычислений

целевой функции

на

всех

шагах (кроме

первого)

в 2

раза.

Условие

получения такого значения

формулируется следующим образом:

-2d)L

откуда

учетом

того,

что

1/(1 -а), имеем

а =

0,382.

Это

значение

называют золотым сечением.

F(x)

С В х

Рис. 4.3. Методы дихотомического деления

(а) и

золотого сечения

(б)

С,

Z),

В х

159

Математическое

обеспечение

синтеза

проектных

решений

Таким образом,

требуется

не

более

шагов

и N + 1

вычисление целевой

функции,

где

можно рассчитать, используя соотношение

(В

А)/Е

d)N

при

заданной погрешности

определения экстремума.

Согласно

методу

чисел

Фибоначчи,

используют числа Фибоначчи

по-

следовательность которых образуется

по

правилу

i+2

i+t

при

т.

е. ряд

чисел Фибоначчи

имеет

вид 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...

Метод аналогичен методу золотого сечения

с тем

отличием,

что

коэффициент

равен отношению

начальное значение

определяется

из

условия,

что

должно быть наименьшим числом Фибоначчи, превышающим величину

•(В-А)/Е,

где Е—

заданная допустимая погрешность определения экстремума.

Так,

если

(В

-А)/Е

100,

то

начальное значение

= 12,

поскольку

./?,=

144,

а =

55/144

0,3819,

на

следующем шаге будет

34/89

0,3820

и т. д.

соответствии

методом

полиномиальной

аппроксимации

при

аппрок-

симации

F(x)

квадратичным полиномом

Р(х)

а^х

(4.7)

выбирают промежуточную точку

Сив

точках

А, В, С

вычисляют значения

целевой функции.

решают

систему

из

трех

алгебраических уравнений,

полученных подстановкой

(4.7) значений

А, В, С

вместо

х и

вычисленных

значений

функции вместо Р(х).

результате становятся известными значения

коэффициентов

(4.7),

и,

исходя

из

условия

dP(x)/dx

= 0,

определяют экстре-

мальную точку

полинома. Например, если точка

выбрана

середине

от-

резка

[А,

В], то Э = С + (С -

A)(F(A)

F(B))

(2(F(A)

2F(C)

F(B))).

Методы

безусловной оптимизации

Среди

методов нулевого порядка

САПР находят применение методы

Ро-

зенброка,

конфигураций, деформируемого многогранника, случайного поиска.

методам

использованием производных относятся методы наискорейшего

спуска,

сопряженных градиентов, переменной метрики.

Метод

Розенброка

является улучшенным вариантом метода покоординат-

ного

спуска.

Метод

покоординатного спуска характеризуется выбором направлений

по-

иска

поочередно вдоль

всех

координатных осей,

шаг

рассчитывается

на

основе

одномерной оптимизации, критерий окончания поиска

< е,

где е —

заданная точность определения локального экстремума,

п —

размер-

ность пространства управляемых параметров. Траектория покоординатного

спуска

для

примера двумерного пространства управляемых параметров пока-

зана

на

рис. 4.4,

где

—

точки

на

траектории поиска,

—

управляемые пара-

метры. Целевая функция представлена своими линиями равного уровня, около

каждой

линии записано соответствующее

ей

значение

F(X).

Очевидно,

что Э

есть точка минимума.

160

4.2.

Обзор

методов

оптимизации

Т.

Рис.

4.4.

Траектория покоординатного

спуска

Рис.

4.5.

«Застревание» покоординат-

ного спуска

на дне

оврага

При

использовании метода покоординатного спуска велика вероятность «за-

стревания» поиска

на дне

оврага вдали

от

точки экстремума.

На

рис.

4.5

вид-

но,

что

после попадания

точку

А,

расположенную

на дне

оврага, дальнейшие

шаги

возможны лишь

направлениях

аа

или bb, но они

приводят

ухудшению

целевой функции. Следовательно, поиск прекращается

точке

А.

Примечание.

Оврагом

называют часть пространства

управляемых

параметров,

которой наблюдаются слабые изменения производных целевой

функции

по

одним

направлениям

значительные

изменения

переменой

знака

по

некоторым другим

на-

правлениям. Знак производной меняется

точках, принадлежащих

дну

оврага.

В то же

время

при

благоприятной ориентации

дна

овраг

а, а

именно

при

поло-

жении одной

из

координатных осей, близком

параллельности

дном оврага,

поиск оказывается весьма быстрым.

Эта

ситуация

показана

на

рис. 4.6.

Метод Розенброка заключается

таком повороге координатных осей, чтобы

одна

из них

оказалась квазипараллельной

дну

оврага.

Такой

поворот осуще-

ствляют

на

основе данных, полученных после серии

из

шагов покоординатно-

го

спуска. Положение новых осей

может быть получено линейным преобра-

зованием прежних осей

ось

}

совпадает

по

направлению

вектором

t+/i

;

оставь-

ные

оси

выбирают

из

условия ортогонально-

сти к

друг

другу.

Другой удачной модификацией покоорди-

натного спуска является

метод

конфигура-

ций

(Хука

Дживса).

соответствии

этим

методом вначале выполняют обычную серию

из

шагов покоординатного спуска, затем

делают

дополнительный

шаг в

направлении

вектора

Х^_

как

показано

на

рис. 4.7,

где

дополнительный

шаг

выполняют

в на-

Рис. 4.6.

Траектория

покоординат-

правлении

вектора

—

X,,

что и

приводит

точку

но

го

спуска

при

благоприятной

ориентации координатных

осей

Основы автоматизированного

проектирования

161

Математическое

обеспечение

синтеза

проектных

решений

Рис. 4.7. Иллюстрация метода

конфигураций

Поиск

экстремума

методом

деформиру-

емого

многогранника

(Непдера

Мида)

ос-

нован

на

построении многогранника

(п

вершинами

на

каждом

шаге

поиска,

где

размерность пространства управляемых

параметров.

начале поиска

эти

вершины

выбирают произвольно,

на

последующих

ша-

гах

выбор подчинен правилам метода.

Эти

правила поясняются рис.

4.8 на

при-

мере двумерной задачи оптимизации. Выб-

раны

вершины исходного треугольника:

X,,

Новая вершина

находится

на

луче,

проведенном

из

худшей вершины

(из

вер-

шины

наибольшим значением целевой функции) через центр тяжести

ЦТ

мно-

гогранника, причем рекомендуется

выбирать

на

расстоянии

от ЦТ,

равном

|ЦТ

Х,|.

Новая вершина

заменяет худшую вершину

X,.

Если оказывается,

что

имеет лучшее значение целевой функции среди вершин многогранника,

то

расстояние

увеличивают.

На

рисунке именно

эта

ситуация имеет место

увеличение

дает

точку

новом многограннике

вершинами

худшей является вершина

аналогично получают вершину

затем верши-

ну

и т. д.

Если

новая

вершина окажется худшей,

то в

многограннике нужно

сохранить

лучшую

вершину,

длины всех ребер

уменьшить,

например вдвое

(стягивание многогранника

лучшей вершине). Поиск прекращается

при вы-

полнении условия уменьшения размеров многогранника

до

некоторого преде-

ла.

Случайные методы поиска характеризуются тем,

что

направления поиска

выбирают случайным образом.

Рис.

4.8.

Иллюстрация

метода

деформируемого

многогранника

162