<<
>>

Традиционные методы оптимизации

Особенностью проектирования СБИС является проблема «проклятия размерности». С одной стороны — это большая область поиска решений, с другой стороны — громадные массивы информации, описывающие объект проектирования.

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

Ограничениями являются временные задержки, площадь кристалла, предельные размеры корпуса, максимальное число выводов и т. п.

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

2 В. М. Курейчик, Б. К. Лебедев, О. Б. Лебедев

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

Во-первых, в оптимизационных задачах часто указывается исходное множество альтернативных вариантов решений. Из этого множества выбирается оптимальное решение. Это исход­ное множество решений называется пространством решений. В дальнейшем его будем обозначать через M.

Во-вторых, некоторые решения априорно отвергаются в каче­стве «плохих». Другими словами, в пространстве решений зада­ются ограничения, которым должны удовлетворять оптимальные решения. Эти ограничения позволяют выделить в пространстве решений M некоторое подмножество Mzтех решений, которые удовлетворяют заданным ограничениям D.

В-третьих, указывается принцип сравнения любых двух до­пустимых решений с тем, чтобы можно было выяснить, какое из них лучше. Как правило, этот способ сравнения задается с по­мощью критерия оптимальности (или функционала, функции качества, функции полезности и т.п.) [2.1-2.4].

Согласно Л. Лопатникову [2.1], критерий оптимальности — тот признак, по которому функционирование системы признается наилучшим из возможных вариантов ее функционирования. Дру­гими словами, критерий оптимальности — показатель, выража­ющий предельную меру экономического эффекта принимаемого решения для сравнительной оценки возможных альтернатив и выбора наилучшего из них. Например, это может быть макси­мум или минимум стоимости, кратчайший путь и т. п. Критерий оптимальности носит количественный характер для того, чтобы качественный признак решения, выражаемый нечетким поня­тием «лучше-хуже», переводить в количественное определение «больше-меньше». Критерию оптимальности соответствует мате­матическая форма — целевая функция. Возможным выражени­ем критерия оптимальности является шкала оценок полезности, ранжирования, предпочтений и т. п.

Обозначим критерий следующим образом:

где R— множество неотрицательных вещественных чисел. Зная функцию Q,можно реализовать процедуру сравнения вариан­тов решений, при этом решение m ∈M'лучше, чем решение m'∈M', если Q(m) < Q(m') (при поиске наименьшего значения Q). В этом случае говорят, что оптимизационная задача состоит

в минимизации критерия Q,т.

є.требуется найти такое допусти­мое решение m"∈M1, что

Модель оптимизационной задачи запишем в виде кортежа длины три: (M, D, Q},где M — пространство решений; D— ограничения, выделяющие в M область допустимых решений M'⊆M; Q : M' → R— критерий оптимизации. Требованием оптимизации является выражение:

Решение m''∈M', удовлетворяющее требованию оптимизации, называется оптимальным [2.1, 2.5].

Целью оптимизационной задачи является выбор допустимого или оптимального решения из множества альтернатив для до­стижения поставленной цели. Оптимизационная задача должна удовлетворять двум основным требованиям:

— должны существовать как минимум два решения;

— надо знать, в каком смысле искомое решение должно быть наилучшим.

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

— область применения;

— содержание задачи;

— класс математических моделей.

Классификацию математических моделей проводят:

(a) по элементам модели: детерминированные и случайные;

(b) по искомым переменным: непрерывные и дискретные;

(c) по зависимостям, описывающим ЦФ, ограничениям и гра­ничным условиям: линейные и нелинейные.

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

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

— при заданном результате минимизировать используемые ре­сурсы.

Максимум и минимум значения ЦФ в оптимизационных за­дачах объединяют определением экстремума. Наибольшее или наименьшее значение функции без учета того, где находится та­кое значение — внутри заданного интервала или на его границе, называют не экстремумом, а оптимумом. Оптимум — более об­щее понятие, чем экстремум. Экстремум есть не у всех функций, а в оптимизационных задачах оптимум есть всегда. Оптимум может быть локальным и глобальным.

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

Оптимальное решение x*∈Dназывается точкой локального минимума (локальным решением), если Vx ∈d(x*, ε), истинно высказывание Q(x*) ≤ Q(x), здесь d(x*, є)— є-окрестность точ­ки х. Оптимальное значение x* ∈Dназывается точкой гло­бального минимума (глобальным решением), если ни в одной другой точке области допустимых решений функция Q(x)не принимает меньших значений Q(x*) ≤ Q(x), Vx ∈D.Следова­тельно, глобальный минимум — это наименьший из всех локаль­ных минимумов. Тогда кеазиоптимальное решение — это одно из множества решений, попадающих в локальный экстремум, близкий к глобальному.

Экономичность математической модели характеризуют за­тратами вычислительных ресурсов ЭВМ при ее реализации.

Ос­новными из таких ресурсов являются время Tmи объем исполь­зуемой памяти ЭВМ: Vm = V0∏ + V⅛, где Vo∏— объем опера­тивной памяти; УВн — объем внешней памяти. Отметим, что так как УВн Vo∏, то при анализе затрат памяти в большинстве случаев оценку можно вести по объему внешней памяти УВн. Математическая модель считается тем экономичнее, чем меньше значения Tmи Vm. Величину Tmопределяют как усредненное число операций Ω, выполняемых при однократном обращении к модели. Величину Vmопределяют в основном числом Bперемен­ных математической модели. Сравнение математических моделей по экономичности состоит в сравнении значений Ω и B.

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

рераспределение соединений между эквивалентными выводами, трассировка в канале, трассировка в коммутационном блоке, раз­деление соединений по слоям — относятся к классу ЛР-полных задач, т. е. временная сложность решения этих подзадач растет по экспоненте.

Обзор и анализ существующих подходов выявил следующее: многими авторами предприняты попытки сведения указанных выше задач к задачам целочисленного программирования. Были получены математические модели задач, к которым применялись стандартные методы оптимизации, такие как методы линейного, нелинейного, динамического программирования и др. [2.7, 2.8, 2.9]. В данной постановке теоретически возможно получения глобального результата. В связи с тем, что стандартные мето­ды оптимизации не исключают возможности полного перебора, данные методы оказываются неприемлемыми для задач реальной размерности (n >IO6, где n— число элементов СБИС).

Одним из мощных методов целочисленного программирова­ния является метод ветвей и границ [2.2, 2.5].

Разработка алгоритма по схеме метода ветвей и границ (МВГ) заключается в решении двух задач — разработке метода ветвления и метода подсчета нижней оценки, которые использу­ются потом в стандартном процессе поиска оптимального реше­ния.

В общем случае процесс поиска оптимального решения по схеме метода ветвей и границ выполняется следующим образом. Пусть на множестве решений Aзадан критерий оптимизации F и пусть цель оптимизации — нахождение минимума F. Процесс поиска заключается в последовательном целенаправленном раз­биении и усечении исходного множества решений A [2.6].

Первоначально множество решений A разбивается по заранее выбранному правилу ветвления (разбиения) на n подмножеств

Рассмотренный процесс реализует структуру поиска в шири­ну. Отрицательным свойством такой структуры является посто­янное расширение фронта поиска Bα.Альтернативой является структура поиска в глубину (рис. 2.2). Особенность его заклю­чается в следующем. Если на шаге α — 1 ветвлению подверглась вершина Af-, то в множество Bαвключаются только вершины Af, полученные в результате ветвления Af-i. После выполнения последнего ветвления будет выбрана вершина Ak, содержащая одно решение.

Проведем от вершины Aк вершине Akпрямой путь по дереву решений. При этом найдено произвольное решение с локальным оптимумом. Затем осуществляется проверка: существует ли на дереве решений вершина Aif, для которой ξ(Af)

<< | >>
Источник: Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с.. 2006

Еще по теме Традиционные методы оптимизации:

  1. ГЛАВА 1. СОСТОЯНИЕ ВОПРОСА ПО РАСЧЕТАМ ЖЕЛЕЗОБЕТОННЫХ ПЛИТ И МЕТОДАМ ОПТИМИЗАЦИИ ЖЕЛЕЗОБЕТОННЫХ КОНСТРУКЦИЙ
  2. ОПТИМИЗАЦИЯ ЖЕЛЕЗОБЕТОННЫХ КОНСТРУКЦИЙ
  3. ОСОБЕННОСТИ ОПТИМИЗАЦИИ ПЛИТ С УЧЕТОМ ЗАПРОЕКТНЫХ ВОЗДЕЙСТВИЙ
  4. ГЛАВА 4. РАЗРАБОТКА АЛГОРИТМА ОПТИМИЗАЦИИ ЖЕЛЕЗОБЕТОННЫХ ПЛИТ
  5. 4.1. ПОСТАНОВКА И АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ ОПТИМИЗАЦИИ
  6. 4.2. ПРИМЕРЫ ОПТИМИЗАЦИИ ЖЕЛЕЗОБЕТОННЫХ ПЛИТ
  7. Анализ методов и устройств трехмерного технического зрения и методов калибровки
  8. Муймаров Кирилл Викторович. ОПТИМИЗАЦИЯ ЖЕЛЕЗОБЕТОННЫХ ПЛИТ С ВЫБОРОМ СТРУКТУР АРМИРОВАНИЯ. Диссертация на соискание ученой степени кандидата технических наук. Брянск - 2019, 2019
  9. 3.2 Метод дифференциальной коноскопии.
  10. 1.2.1 Вариационные методы
  11. Геометрические методы
  12. 3. Понятие и виды методов государственно-управленческой деятельности
  13. Изопериметрический метод
  14. Развитие метода интерполяции по коэффициенту формы
  15. Методы вычисления параметров и сопоставления характерных точек объектов
  16. ПРОБЛЕМЫ РАЗВИТИЯ ГЕОМЕТРИЧЕСКИХ МЕТОДОВ РЕШЕНИЯ ЗАДАЧ ТЕХНИЧЕСКОЙ ТЕОРИИ ПЛАСТИНОК
  17. ИССЛЕДОВАНИЕ МЕТОДОВ И УСТРОЙСТВ ВЫЧИСЛЕНИЯ ТРЕХМЕРНЫХ КООРДИНАТ ОБЪЕКТОВ РАБОЧЕЙ СЦЕНЫ
  18. Расчет железобетонных конструкций методом конечных элементов
  19. Перевод как герменевтический метод понимания текста