Материал: 1310

Fn 1 x2 a (b a) ;

Fn

f (x1), f (x2 ) значения функции в точках х1, х2 ;

Fn , Fn 1, Fn 2 числа Фибоначчи.

2. Если f(x1) > f(x2), то

b = x2, x2 = x1, x1 = a+(b − x2), f(x2) = f(x1), вычислить f(x1) (рис. 9).

Рис. 9. Деление отрезка по методу Фибоначчи

3. Критерий завершения вычислений: Число итераций больше, чем заданное количество. Наилучшая точка на отрезке [a, b] x = (x1 + x2) / 2.

Метод Фибоначчи обеспечивает наибольшую среди рассматриваемых методов точность решения.

36

8. МЕТОДЫ МНОГОМЕРНОЙ ОПТИМИЗАЦИИ

В современных САПР процедуры параметрического синтеза выполняются либо проектировщиком в процессе многовариантного анализа, либо реализуются на базе формальных методов оптимизации в автоматическом режиме. В последнем случае большинство постановок задач параметрической оптимизации технических объектов и систем сводятся к задачам многомерной оптимизации, в которых целевая функция и ограничения содержат несколько управляемых параметров и описываются нелинейными зависимостями, на значение которых к тому же накладываются дополнительные ограничения. В зависимости от количества переменных и типа искомого экстремума различают методы одномерной и многомерной, условной и безусловной оптимизации. Решение оптимизационной задачи в общем случае заключается в определении таких значений входных параметров исследуемого объекта или системы, которым соответствует наилучшее (минимальное или максимальное) значение целевой функции [4].

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

Так как технические системы, как правило, являются многомерными, с большим количеством входных параметров, то это требует использования методов многомерной условной оптимизации. Многие из таких методов, однако, предполагают сведение задачи к безусловной оптимизации путем преобразования целевой функции с дальнейшим применением соответствующих процедур. Поэтому изучение методов поиска экстремума функций нескольких переменных без ограничений является не менее важной задачей дисциплин, связанных с изучением систем автоматизированного проектирования [4].

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

37

Xk 1 Xk Xk ,

где в большинстве методов приращение Xk вектора управляемых параметров вычисляется по формуле

Xk h g(Xk ),

где Xk − значение вектора управляемых параметров на k-м шаге; h – шаг; а g(Xk) − направление поиска.

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

поскольку вектор первых производных F(X) по вектору параметров Х есть

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

Конкретные методы первого порядка определяются следующими факторами: 1) способом вычисления направления поиска g(Xk); 2) способом выбора шага h; 3) способом определения окончания поиска. Определяющим фактором является первый из перечисленных в данном списке, это является «основой» конкретного метода [2, 4] (рис. 10).

Методы многомерной оптимизации можно рассматривать как инструмент решения прикладных задач автоматизированного проектирования в современных программных комплексах САПР, которые относятся к числу наиболее сложных современных программных систем, основанных на математическом аппарате и языках программирования. К настоящему времени создано большое число приложений для САПР с различными степенью специализации и прикладной ориентацией [2, 4].

38

Рассмотрим три метода: метод градиента, метод крутого восхождения (метод наискорейшего спуска), метод сопряженных градиентов.

8.1. Метод градиента

Сущность этого метода сводится к выполнению следующих операций: 1. В исходной точке определяется градиент рассматриваемой

функции.

39

2. В направлении градиента осуществляют рабочий шаг.

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

а) определяются точки, откуда шагаем и куда шагаем; б) сравниваются отклики в этих точках и шаг считается удачным,

если величина целевой функции улучшилась, т.е. увеличилась при поиске максимума (max) и уменьшилась при определении минимума

(min).

В каждой новой точке вычисляется величина целевой функции. Алгоритм поиска следующий:

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

тимума величина шага принимается пропорционально величине первой производной по каждой координате.

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

При этом последняя удачная точка поиска считается глобальным экстремумом рассматриваемой функциии. Основным недостатком данного метода является большой объем выч слен й [4].

8.2. МетодСрелаксаций

Метод релаксаций заключается в следующем:

а) определяют частные производные рассматриваемой функции по всем координатным осям;

б) из всех вычисленных производных определяют наибольшую; в) в направлении наибольшей производной осуществляется

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

40