Основы КомПМ РЭС - Слайды

Введение в теорию оптимизации (1))

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

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

Математически задача оптимизации описывается множеством решений X и функцией F, определенной на X. Оптимизировать – это означает найти такое решение, что

x X ,

F(x) ≤F(z) z X

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

Снурницин В.Р., НГТУ	Основы компьютерного проектирования и моделирования РЭС	Слайд 31

Введение в теорию оптимизации (2))

Элементы аналитической теории оптимизации

Необходимые условия существования экстремальных точек (максимума или минимума) целевой функции одной f(x) или многих переменных f(x1,…,xn) выражаются через производную (одним уравнением) или градиент (системой уравнений)

df (x)	=0	или f (x ,..., x ) =0
dx		1	n

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

Снурницин В.Р., НГТУ	Основы компьютерного проектирования и моделирования РЭС	Слайд 32

Введение в теорию оптимизации (3))

Методы одномерного поиска:

простой перебор, исключение интервалов, золотого сечения и Фибоначчи

В методах поиска оптимальных точек предполагается, что доступны для измерений или вычислений только значения целевой функции f(x), которая на нормированном интервале неопределенности x [0,1] унимодальна, т.е. имеет единственный минимум (максимум).

Простой перебор – равномерный поиск в этом случае сводится к вычислению f(x) на сетке значений x в n точках и выбору минимального значения f(x). При этом погрешность поиска равна 2/(n+1). Если учесть унимодальность целевой функции, то можно сократить количество экспериментов. Любой процесс поиска начинается с двух экспериментов.

В методе половинного деления точки эксперимента располагаются на расстоянии ошибки эксперимента ε от середины интервала. После n экспериментов интервал неопределенно-

сти равен Ln = 2-n/2 + (1 – 2-n/2)ε.

В методе золотого сечения точки эксперимента располагаются по правилу «золотого сечения» на расстоянии 0.618 от концов интервала. После n экспериментов минимум лежит в интервале Ln = 1/(1.618)n-1.

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

Снурницин В.Р., НГТУ	Основы компьютерного проектирования и моделирования РЭС	Слайд 33

Введение в теорию оптимизации (4))

Задачи оптимизации радиотехнических устройств:

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

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

Для решения задач оптимизации имеется набор методов оптимизации, которые можно разделить на два вида:

•градиентные методы – методы наискорейшего спуска, метод Ньютона и др. в которые используют аналитические формулировки задачи оптимизации;

•прямые методы оптимизации – метод покоординатного спуска, методы поиска по образцам (Хука-Дживса, сопряженных направлений Пауэлла, симплексный поиск, случайный поиск).

Алгоритмы основных методов оптимизации изложены в методических указаниях и контрольных заданиях данного учебно-методического комплекса.

Снурницин В.Р., НГТУ	Основы компьютерного проектирования и моделирования РЭС	Слайд 34

Литература

1.Автоматизация проектирования радиоэлектронных средств: Учеб. пособие для вузов / Под ред. О.В. Алексеева. – М.: Высшая Школа, 2000. – 479 с.

2.К. Влах, К. Сингхал. Машинные методы анализа и проектирования электронных схем. М.: Радио и связь, 1988 – с. 560

3.Фидлер Дж.К., Найтингел К. Машинное проектирование электронных схем / Пер. с англ. – М.: Высшая школа, 1985 – 384 с.

4.Реклейтис Г., Рейвиндран А., Рэгедел К. Оптимизация в технике / Пер. с англ. – М.: Мир, 1988. – Кн. 1. – 347 с.

5.Банди Б. Методы оптимизации. Вводный курс / Пер. с англ. – М.: Радио и связь, 1988 – 128 с.

Снурницин В.Р., НГТУ	Основы компьютерного проектирования и моделирования РЭС	Слайд 35