Тема 8. Задачи и методы оптимизации

1.Постановка задач оптимизации

При постановке задач оптимизации в САПР необходимо преобразовывать физические представления о назначении и степени полезности объекта в математическую формулировку экстремальной задачи, т.е. нужно сформулировать цели оптимизации и формализовать понятие оптимальности. Цели оптимизации выражаются в критерии оптимальности - правиле предпочтения сравниваемых вариантов. Основу критерия оптимальности составляет целевая функция F(X), аргументом которой является вектор управляемые параметры. Обычно в этот вектор при параметрической оптимизации входят все или некоторая часть внутренних параметров оптимизируемого объекта. Целевая функция должна быть такой, чтобы по ее значению можно было определить степень достижения цели.

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

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

Таким образом, формулировка задачи оптимизации имеет вид:

найти экстремум целевой функции F(X) в области работоспособности, заданной ограничениями j(X)>0 и y(X)=0.

Примеры задач оптимизации в САПР:

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

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

2)оптимизация электронных схем на функционально-логическом уровне проектирования.

Это задачи структурной оптимизации - минимизация логических функций, числа внутренних состояний конечного автомата, числа наборов в контролирующих теста, а также параметрической оптимизации - минимизации задержки распространения сигналов и мощности рассеяния в фрагментах БИС;

3)оптимизация систем массового обслуживания.

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

4)оптимизация на конструкторском уровне.

Эти задачи чаще всего связаны с выбором структуры проектируемого объекта - размещения элементов, трассировка и компоновка изделия.

Таким образом, задачи оптимизации в САПР, условно можно разбить на две группы:

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

- задачи структурной оптимизации, которые имеют комбинаторный характер с дискретными переменными.

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

Формы критериев бывают частные, обобщенные и статистические.

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

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

1)взвешенная сумма квадратов разностей значений полученной(расчитанной, экпериментальной) и желаемой характеристик объекта;

2)максимальное по абсолютной величине отклонение полученной характеристики от желаемой.

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

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

2.Методы оптимизации

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

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

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

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

1)по характеру экстремума - различают методы условной, безусловной, локальной и глобальной оптимизации (условная оптимимзация успешно сводится к безусловной, а для глобальной оптимизации в настоящее время отсутствуют алгоритмически надежные методы);

2)от количества управляемых параметров - различают методы одномерного и многомерного поиска. Одномерный поиск играет вспомогательную роль при проектированиии и заключается в определении величины оптимального шага в выбранном направлении;

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