19. Глобальная оптимизация (Дима)

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

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

20. Классификация алгоритмов оптимизации (Дима)

Методы оптимизации классифицируют по ряду признаков.

В зависимости от числа управляемых параметров различают:

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

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

Реальные задачи в САПР многомерны, методы одномерной оптимизации играют вспомогательную роль на отдельных этапах многомерного поиска.

По наличию или отсутствию ограничений выделяют:

• методы условной оптимизации;

• методы безусловной оптимизации.

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

В зависимости от числа экстремумов различают задачи:

• одноэкстремальные (локальные);

• многоэкстремальные (глобальные).

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

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

• задачи оптимизации, сводящиеся к задачам нелинейного программирования с соответствующими методами их решения.

Методы оптимизации классифицируют в соответствии с задачами оптимизации:

• локальные методы, сходящиеся к какому-нибудь локальному экстремуму целевой функции. В случае унимодальной целевой функции этот экстремум единственен и будет глобальным максимумом/минимумом;

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

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

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

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

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

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

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

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

Метаэвристические алгоритмы рассматривают целевую функцию как «чёрный ящик». Единственное действие, которое они могут совершить с ней - это аппликация, т. е. её вычисление для конкретного решения. Таким образом, для работы метаэвристического алгоритма требуется лишь возможность получения значения целевой функции.