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

3.1 Поисковая оптимизация.

Поисковая оптимизация заключается в определении малой окрестности оптимальной точки в допустимой области X_Д пространства управляющих параметров на основе расчета целевой функции и функций – ограничений в ряде точек этого пространства.

Общая схема вычислений при поисковой оптимизации:

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

Методы поиска экстремума можно классифицировать по следующим признакам:

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

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

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

В методах нулевого порядка производные не используются. В методах 1-го порядка используются производные F(X), составляющие вектор-градиент F ^‘(X), поэтому их еще называют градиентными методами. В методах 2-го порядка используются вторые производные.

Примеры методов нулевого порядка: метод Гаусса-Зейделя.

Примеры методов первого порядка (градиентных методов): метод крутого восхождения (метод Бокса-Уилсона).

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

К методам второго порядка относятся методы Ньютона-Рафсона, метод сопряженных направлений, и наиболее эффективный из них: метод Давидона – Флетчера – Пауэлла, который использует как идеи метода Ньютона–Рафсона, так и свойство сопряжённых направлений. Указанные методы являются мощными оптимизационными процедурами, но достаточно сложны в реализации.

3.2 Методы дискретной оптимизации.

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

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

Транспортная задача. Имеется m поставщиков некоторого определенного продукта и n пунктов его потребления. Для каждого пункта производства задан объем производства, а для каждого пункта потребления – объем потребления. Также заданы затраты на перевозку единицы продукта от i-го пункта производства к j-му пункту потребления. Требуется составить план перевозок таким образом, что бы он: а) не превышал предел производительности поставщиков, б) полностью обеспечивал всех производителей, и) давал минимум суммарных затрат на перевозку.

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

Задача о коммивояжёре. Имеется n+1 город, причем номером 0 обозначен исходный город, выехав из которого, коммивояжер должен побывать по одному разу в каждом из n городов и вернуться в исходный город с номером 0. Расстояния между любыми городами известны. Требуется установить порядок объезда городов, при котором суммарный путь, пройденный коммивояжером, будет минимальным.

К данной задаче, например, можно свести задачу о размещении компонентов на печатной плате.

Существует достаточное множество численных методов решения дискретных задач, отметим основные из них.

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

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

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