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

При проведении испытаний необходим оптимальный выбор систем, видов, методов и условий испытаний.

Оптимизация (от лат. optimum - наилучшее) - это процесс выбора наилучшего варианта из возможных или приведения системы в наилучшее (оптимальное) состояние.

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

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

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

Главным результатом создания теории оптимального управления является принцип максимума Понтрягина (Л.С. Понтрягин - советский математик, 1908 - 1988), который представляет собой совокупность ряда теорем теории оптимальных процессов, которые устанавливают необходимые условия для построения оптимального закона управления объектом. Принцип максимума позволяет учесть ограничения, налагаемые на изменения переменных.

Все методы оптимизации можно разделить на два основных класса.

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

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

В свою очередь экспериментальные методы можно разделить на две группы.

Первая группа - это поисковые методы, в которых осуществляется последовательное локальное изучение поверхности отклика:

  • - определение по результатам специально спланированного эксперимента направления движения из некоторой точки, в окрестностях которой проводится эксперимент;
  • - организация движения в найденном направлении;

- повторение указанных этапов до достижения точки оптимума.

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

Существует много методов поиска оптимума, рассмотрим лишь основные из них.

Аналитические методы оптимизации

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

Аналитический поиск экстремума целевой непрерывной функции сводится к приравниванию её частных производных нулю.

Метод множителей Лагранжа (J.L. Lagrange - французский математик и механик, 1736 - 1813) используют, когда на переменные наложены ограничения типа равенства.

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

Метод Гаусса-Зейделя (P.L. Seidel - немецкий астроном и математик, 1821 - 1896) заключается в последовательном поиске оптимума поочерёдно по каждой переменной. После завершения перебора всех переменных опять приходится перебирать переменные до тех пор, пока не будет достигнут оптимум. Метод прост в реализации, но его эффективность зависит от порядка чередования переменных.

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

R(x)^>max (a (3.5.1)

где а и b - минимальное и максимальное значения х.

Метод сканирования заключается в последовательном переборе всех значений а<х<Ь с шагом 8 (погрешность решения) с вычислением критерия оптимизации.

Метод деления пополам основан на делении текущего отрезка [а, Ь], где содержится экстремум, на две равные половины и последующем выборе одной из половин, где находится максимум.

Метод золотого сечения основан на делении по правилу золотого сечения отрезка [а, Ь], где содержится максимум, на две неравные части, и последующем выборе отрезка, где находится максимум. Золотое сечение известно из «Начал» Евклида (Еи%Л.єі8исг -древнегреческий математик, III век до н.э.) и заключается в делении отрезка АВ на две части АС и СВ таким образом, что АВ:АС = АС:СВ.

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

Градиентная оптимизация

Эти методы относятся к численным методам поискового типа. Они универсальны, хорошо приспособлены к решению на ЭВМ и в большинстве случаев весьма эффективны при поиске экстремального значения нелинейных функций с ограничениями и без них, а также когда аналитический вид функции вообще не известен. Вследствие этого градиентные (от лат. gradiens, род. падеж gradients - шагающий) методы широко используются на практике. Суть этих методов состоит в том, что последующее приближение функции получается из предыдущего смещением в направлении градиента функции.

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

Этого недостатка лишён метод наискорейшего спуска, суть которого состоит в вычислении градиента и поиска в этом направлении минимума функции.

Метод сопряжённых градиентов на начальных этапах (вдали от оптимума) ведёт себя как метод первого порядка, а в окрестностях оптимума приближается к методам второго порядка.

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

Математическое программирование

Геометрическое программирование основано на теореме о среднем, по которой среднеарифметическое положительных чисел всегда больше или равно их среднегеометрическому.

Геометрическое программирование применимо для минимизации алгебраических выражений вида

F(xj, x2, ... xn) = YjCjPj (X1> X2> - Xn>’ (3.5.2) ЛІ

где Cj - положительные константы;

P(xj,X2, ...xn)= , (3.5.3)

1=1

где al} - действительные числа.

Линейное программирование позволяет найти экстремум в задачах с линейными уравнениями. Одним из основных методов линейного программирования является симплекс-метод (лат. simplex - простой). Симплексом в п-мерном пространстве называют фигуру, содержащую п+ї вершину. На плоскости - это треугольник, в трёхмерном пространстве - тетраэдр и т.д. Вычислительная процедура симплекс-метода состоит в последовательном решении систем алгебраических уравнений. Алгоритм линейного программирования очень удобен для решения на ЭВМ.

Динамическое программирование применяется для многошаговых задач принятия оптимального решения. Метод был предложен Р. Веллманом (R.E. Bellman -американский математик, 1920 - 1984) При этом много-шаговость задачи либо отражает реальное протекание процесса принятия решений во времени, либо вводится в задачу искусственно за счёт расчленения процесса принятия однократного решения на отдельные этапы, шаги. Цель такого представления состоит в сведении исходной задачи, состоящей в нахождении решения как точки в пространстве высокой размерности, к решению на каждом шаге задачи небольшой размерности (и даже одномерной задачи). Недостатком динамического программирования является необходимость выполнения большого числа шагов и относительно большого обьёма ОЗУ для хранения промежуточных вычислений.

Статистическая оптимизация

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

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

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

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

Корреляционный (от позднелат. correlatio -соотношение) анализ основан на обнаружении корреляционной зависимости между случайными величинами или признаками.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >