Элементы математического моделирования в программных средах MATLAB 5 и Scilab (Андриевский Фрадков)

После первого шага начальная ошибка уменьшается в 20 раз, после второго - еще в 19 раз, и уже для Е9 мы получим все шесть значащих цифр верных. Все дело в том, что формула (4.45), в отличие от (4.44), определяет устойчивый вычислительный процесс и погрешность результата каждого шага меньше погрешности исходных данных. Подробнее об устойчивости численных методов см., например, в [9, 112, 104].

П р а в и л о 7. Пользуйтесь только устойчивыми численными алгоритмами!

Заметим, что в современных вычислительных пакетах программ (в частности, в системе MATLAB на платформе PC Intel в средах ОС Windows-95/98) вычисления обычно выполняются с 32-разрядной арифметикой, тем не менее эффект накопления ошибок при неудачно организованных вычислениях может проявиться и пренебрегать вышеизложенными правилами не следует.

Разницы нет никакой между Правдой и Ложью, Если, конечно, и ту и другую раздеть.

Владимир Высоцкий

Г Л А ВА 5. О П Т И М И З А Ц И Я И СТРУКТУРНЫЙ СИНТЕЗ СИСТЕМ

5.1.Оптимизация технических объектов

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

Ниже приводится обзор некоторых основных терминов, используемых в оптимизации технических систем [72, 80, 97].

Оптимизация как выбор наилучшего варианта среди некоторого множества подразумевает наличие правил предпочтения одного варианта другому. Такое правило называют критерием оптимальности. В основе его построения лежит

целевая функция, которая называется также функцией качества. Аргументами этой функции являются управляемые параметры- внутренние параметры я, которые можно изменять на данном этапе проектирования. Через f(x) обозначим целевую функцию, а область ее определения - через Xq. Е С Л И множество Xd - дискретное, то задача относится к области

дискретного (целочисленного - в частном случае) программирования.

е-Окрестностью точки х0 называется множество 5е(х) точек, которые находятся от точки х0 на расстоянии, не превышающем заданное е > 0 :

5,(х0 ) = { х : ||х - Х о || < £ > .

(5-1)

Максимумом функции f(x) называют ее значение f(x*), если существует число е > 0, такое что для любой точки х G Se(x*) (х ф х*) выполняется неравенство

Дх) - /(*•) < 0.		(5.2)
Точку х* называют экстремальной точкой	(локальным	экс-
тремумом). Функция f(x) одно экстремальна	(унимодальна),
если она имеет один экстремум, и многоэкстремальна -		если
имеет более одного максимума (минимума).

172

Точкой глобального экстремума называется точка, в которой целевая функция имеет наибольшее (при решении задачи максимизации) значение среди всех локальных экстремумов.

К задачам безусловной оптимизации относятся задачи, в которых экстремум ищется в пределах неограниченного пространства параметров, т.е. задачи, в которых отсутствуют ограничения. Найденные при этом экстремумы называются

безусловными.

В задачах проектирования обычно присутствуют ограничения. Прямые ограничения описываются неравенствами

Xdi < х,- < xu.

(5.3)

(возможны и нестрогие неравенства, содержащие знаки <). Допустимой областью Хр в пространстве параметров на-

зывают область, удовлетворяющую прямым ограничениям:

ХР = {х : х е XD\ xdi < Xi < xu., i G [1 : n]}, n = dimX^. (5.4)

Кроме прямых ограничений имеются также функциональные

ограничения, имеющие вид неравенств или	равенств:
tp{x) > 0, ф{х) = 0.	(5.5)

Наличие ограничений приводит к задаче условной оптимиза-

ции, в результате решения которой находится условный	экс-
тремум. Область
ХР = {х : х 6 XD\ <р{х) > 0>(х) = 0}	(5.6)

в задачах проектирования называют также областью работоспособности.

5.1.2.Методы поисковой оптимизации

Классические методы безусловной оптимизации применяют, когда дано аналитическое выражение целевой функции. Как известно [80, 113], необходимым условием безусловного экстремума является равенство нулю вектора градиента целевой Функции по управляемым параметрам:

v,/(®') = 0.

173

Точки, удовлетворяющие этому условию, называются стационарными. Чтобы стационарная точка была экстремальной, достаточно выполнения неравенства

ДхТ ГДх < 0

(5.7)

в некоторой окрестности х*. Здесь через Г обозначена матрица Гессе (гессиан) рассматриваемой функции.

Зная координаты экстремальной точки, нельзя сделать никаких заключений о локальном или глобальном характере этого экстремума, не исследуя f(x) во всей области определения. Исключением являются задачи с унимодальной целевой функцией.

При известных аналитических выражениях целевой функции и ограничений условная оптимизация выполняется с помощью метода множителей Лагранжа, который применим к задачам с ограничениями типа равенств. Согласно этому методу, задача условной минимизации f(x) заменяется задачей безусловной минимизации следующей функции Лагранжа:

Ф(х,A) 4 /(х) + Yt \k1>k f(z) = /(*)+ < A,V(x) >,	(5.8)
Jk=i
где А = [Аь А2 ,..., Ар]т - вектор множителей Лагранжа.	Ме-

тод множителей Лагранжа может быть распространен и на задачи с ограничениями типа неравенств с помощью известной теоремы Куна-Таккера [80, 113].

Классические методы нахождения экстремумов целевых функций при проектировании практически не применяются, так как случаи аналитического задания целевых функций крайне редки [72]. Характерной ситуацией является наличие алгоритмических математических моделей. В такой ситуации используют поисковую оптимизацию, при которой поиск экстремума выполняется поледовательными шагами, ведущими от исходной точки х° в заданную ^-окрестность точки экстремума х*. Каждый шаг процесса оптимизации заключается в переходе от точки в точку х*. Лля такого перехода нужно определить направление перемещения дк и величину шага Л* в этом направлении, такие что х* = x*-i + hkgkТаким образом, содержанием любого алгорима поисковой оптимизации должны быть способы выбора:

174

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

-величины шага hk\

-формул для нормирования оптимизируемых параме-

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

Эффективность поиска зависит от того, как сделан этот выбор. Составляющими эффективности являются

-надежность, т.е. вероятность достижения заданной е- окрестности экстремальной точки;

-точность, характеризуемая гарантированным значе-

нием е;

-экономичность, отождествляемая с потерями на поиск, т.е. трудоемкость процедуры оптимизации, которая обычно оценивается числом обращений к ММ объекта.

Способ выбора направления поиска gk является определяющим для методов безусловной оптимизации, которые бывают нулевого, первого и второго порядков.

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

X не используются. В методах первого и второго порядков

используются соответственно первые и вторые производные (Vr /(x), Гх /(х)).

Для выбора величины шага поиска hk обычно используются два способа. В способе оптимального шага на каждом к-м

шаге поиска экстремума исходной задачи minr f(x)	решается
вспомогательная задача одномерной оптимизации:
mm f(xk_x + hkgk).	(5.9)
Лк

Ее решением является оптимальная величина шага, миними-

зирующая f(x)		на луче, выходящем в направлении дк из точ-
ки хк_х.	В способе		задаваемого шага величина hk постоянна
на всей	траектории		поиска либо на ее частях, выделяемых
в зависимости		от близости к исходному экстремуму. При

выполнении условий попадания в заданную окрестность экстремальной точки X* значение hk уменьшается.

	Нормирование управляемых	параметров осуществляется ли-
	бо способом линейной нормализации		параметров
	д Xi		(5.10)
	Ui =	t*

175

где	- константа, равная	единице измерения	величины xi)
либо способом логарифмической нормализации			параметров
	щ ±	log ( | i ) .	(5.11)

В качестве условия попадания в заданную окрестность оптимальной точки х* принимается условие малости расстояния, на которое прошло продвижение в пространстве параметров в результате последних г шагов. Это расстояние вычисляется по формуле

	Pk = ||uk - Uk-rII,			(5.12)
и условие	попадания имеет вид		< 6, где 6 > О -	заданный
параметр	алгоритма.
Критерием прекращения		поиска являются условия: pk < 6 и
h>k <	Вместо pk < 6 иногда используется условие /(я*) —
-f{xk-r) < S.
Метод	покоординатного	спуска	{метод Гаусса-Зейделя) ха-

рактеризуется тем, что в нём избранное множество направлений поиска составляют направления вдоль п координатных осей пространства параметров. Для определения Л* используется способ оптимального шага. В условии (5.12) г принимается равым 7i, т.е. поиск заканчивается, если в цикле из п шагов вдоль каждой из координатных осей пройдено расстояние, меньшее 6.

Метод конфигураций включает выполнение циклов из п шагов покоординатного спуска. После каждого цикла делается один дополнительный шаг, определяемый с помощью одномерной оптимизации (5.9) вдоль направления Uk — Uk-n-

Метод Розенброка характеризуется тем, что в нем реализована идея поворота координатых осей после каждого цикла из п шагов покоординатного спуска таким образом, чтобы одна из осей новых координат оказалась параллельной линии, соединяющей точки Uk и i7jfc_n, т.е. заняла бы положение, близкое к параллельному по отношению к линии дна оврага.

Методы случайного поиска характеризуются большим числом реализующих их алгоритмов. Одним из них является метод, при котором элементы вектора gk - равномерно распределенные в диапазоне [—1,1] случайные числа и используется способ задаваемого шага. Неудачные шаги, приводящие к ухудшению целевой функции, не выполняются.

176

Метод наискорейшего спуска предписывает вести поиск в направлении, противоположном градиенту целевой функции

			9k = — Vr/(xjfc_i);							(5.13)
hk выбирается по способу оптимального шага.
	В задачах безусловной оптимизации известно большое чи-
сло и других методов, например						методы		сопряженных		гра-
диентов,		сопряженных		направлений,			переменной метрики [72,
80,	113].
	Более сложными для решения являются задачи условной
оптимизации. При их решении применяются методы									штраф-
ных функций, барьерных				функций,		проекции		градиента	[80].
	Следует также остановиться на задаче							дискретной		опти-
мизации,		когда поиск оптимального решения ведется по счет-
ному (конечному)			множеству		точек.		Здесь известны			такие
методы,		как метод	локальной		оптимизации,			метод	ветвей и
границ и ряд других.
	П р и м е р 5.1.1. В качестве иллюстративного примера рас-

смотрим задачу нахождения экстремума функции двух переменных и ее решение с помощью пакета MATLAB.

Рис. 5.1. Линии равного уровня (а) и график функции Розенброка (6).

К стандартным программам решения типовых оптимизационных задач предъявляются достаточно серьезные требования по эффективности и удобству использования. Лля сравнения эффективности различных алгоритмов оптимизации разработан ряд тестовых задач [80]. Одной из них явля-

177

ется задача минимизации функции Розенброка [113]

f{x) = 100 (х2 - х2)	2 + (1 - x j 2 ,	х€7г	2 ,	(5.14)
при начальном значении I ° =	[-1.2,1] . Функция		(5.14)	ПЛОХО
обусловлена (число ее обусловленности /х = 2500), 1				невы-
пуклая, имеет параболический овраг (рис.		5.1). Нетрудно

убедиться, что минимум функции Розенброка лежит в точке

= (i,i).

Пакет MATLAB имеет развитую библиотеку процедур поиска экстремума. Так, имеется тулбокс OPTIMIZATION, версия 2.0 которого содержит около пятнадцати процедур решения задач условной и безусловной минимизации, в том числе и для векторных целевых функций. Ряд оптимизационных программ включен также в "NAG Foundation Toolbox", являющийся библиотекой процедур численных и статистических методов. Наиболее простой и обычной для использования является процедура fmins, входящая в библиотеку основных функций системы (тулбокс MATLAB). 2 Рассмотрим использование этой процедуры для решения задачи минимизации функции (5.14).

Пользователь должен составить rn-функцию, вычисляющую значение /(х). Лля рассматриваемой задачи эта функция может иметь вид:

function f=frose(x)

f=100*(x(2)-x(l)~2)~2+(l-x(l)~2);

Запишем эту функцию в файл под именем frose.m. Составим теперь головную программу, в которой указаны

начальные значения параметров и содержится обращение к процедуре fmins:

х0= [ - 1 . 2, 1]; x=fmins('frose',х0)

1 Обусловленностью точки минимума х* функции /(х) называется чи-

сло /i = Ш (sup ||i - х"||2/ inf ||i - хт\\Л	, где 1Ь = {х : /(х) = Дх*)+6},
\xGLt	/

[80]. Значение /1 характеризует степень вытянутости линий уровня /(х) в окрестности экстремума х*.

2 В новых версиях пакета эта процедура заменяется аналогичной fminsearch.

178

результаты решения задачи представлены на рис. 5.1, 5.2 в виде траектории процесса поиска экстремума, значений целевой функции /(х) и расстояния до точки оптимума R(x) = = ||х — х*|| в зависимости от номера шага (итерации) к.

В результате вычислений получено значение 6х = х — х* « «[2.2 • 10"5,4.2 • 10-*]т за число итераций N = 159. 1 Начальное значение /(х°) = 24.2, найденное значение /(х^)«8 . 2 • Ю~10.

Рис. 5.2. Значения функции /(х*) (а) и расстояния Я(х*) до точки экстремума (б) в процессе оптимизации.

5.2.Задачи структурного синтеза систем

Эти задачи являются наиболее сложными с точки зрения формализации. Сейчас наблюдается интенсивное развитие методов дискретной математики и их внедрение в практику проектирования, но в большинстве случаев основную роль при структурном проектировании играет по-прежнему человек [72].

5.2.1.Классификация задач синтеза

Задача синтеза включает в себя:

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

- параметрический синтез - расчет его параметров.

1 По данным работы [80], близкие результаты получены так называе-

мым методом Пауэлла [72, 80, 97, 113].

179

Параметрический синтез обычно выполняют с помощью описанных выше методов оптимизации с учетом того, что в ряде оптимизационных задач приходится прибегать к специальным методам дискретного программирования.

Близкие к структурному синтезу задачи возникают в конструировании при выборе профиля детали, например формы крыла. Такие задачи обычно сводятся к задачам параметрической оптимизации, если произвести разбиение профиля на некоторое число участков и в качестве элементов вектора X использовать координаты избранных точек поверхности.

Структура объектов определяется природой элементов и способом их связи между собой. Здесь речь идет о межэлементных связях - функциональных, информационных, кинематических, электрических, либо о взаимном расположении элементов в пространстве, если речь идет о пространственной конструкции. В общем случае синтез структуры является задачей выбора некоторого варианта, представляющего собой элемент не более чем счетного множества. Если число вариантов конечно, то такая задача называется комбинаторной. Иерархичность синтезируемой структуры представляется деревом технических решений. Проведению синтеза помогает декомпозиция процедуры синтеза, что приводит к сокращению вариантов для перебора. Декомпозиция процедур синтеза целесообразна также в рамках разделения процесса проектирования на этапы предварительного, эскизного и технического проектирования.

Сложность задачи синтеза отождествляется со сложностью ее решения.

К уровню 1 сложности относят наиболее простые задачи; собственно синтез отсутствует, так как структура либо задана, либо очевидна.

Уровень 2 сложности синтеза - это выбор нужного варианта из конечного множества, причем все элементы этого множества заранее известны и их количество невелико.

К уровню 3 сложности относят задачи выбора во множестве с большим, но конечным числом вариантов при условии, что число вариантов и сами варианты заранее известны.

К уровню 4 сложности относят задачи выбора варианта во множестве с заранее неизвестным числом элементов или вообще в бесконечном множестве.

180