Регулярные методы оптимизации

Метод направленного поиска

 

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

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

Поэтому в данной лекции стохастическое программирование мы не рассматриваем. (Обычно на практике в качестве целевой функции выбирают математическое ожидание целевой функции.)

Метод поочередного изменения параметров (метод покоординатного спуска, подъема, метод Гаусса-Зейделя)

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

Недостатки:

1) обеспечивает получение только локального оптимума и локальной точки типа седла;

2) позволяет оптимизировать только непрерывно изменяющиеся параметры;

3) результаты поиска существенно зависят от удачного выбора первого направления движения, начальной точки;

4) эффективность метода существенно снижается при наличии ограничений.

Метод градиента

 

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

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

Для определения оптимума необходимо при минимизации целевой функции для каждой точки поискa N определить градиент и сделать шаг по направлению антиградиента (т.е. в направлении обратном градиентному).

Использование градиентного метода удобно при практическом опреде­лении численных значений ряда параметров х₁, х₂,..., х_n, которые обеспечивают достижение экстремума функции Q(х₁, х₂,..., х_n). Таким образом, метод удобен для решения статических задач оптимизации. Можно видеть, что применимость этого метода зависит от свойств функ­ции Q: обычно предполагается, что функция непрерывно дифференцируема во всей области изменения х.

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

Вычислительная процедура движения по градиенту может быть органи­зована как дискретная, так и непрерывная. В первом случае вместо частных производных используется их конечно-раз­ностная аппроксимация, а приращении функции, получаемое при заданном малом, но конечном приращении соответствует оптимизирующей перемен­ной, определяется при двукратном вычислении функции. Если функция Q зависит от k переменных, то для определения ее градиента в заданной точке необходимо провести (k+1) вычисление значения функции.

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

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

Следует, однако, отметить, что это условие является необходимым, но не достаточным, и, чтобы убедиться в достижении именно экстремума, а не точки перегиба, требуется проверить вторые производные на нера­венство нулю, причем при Q"(х) > 0 имеем минимум, при Q"(х) < 0 максимум, если Q"(х) = 0, то наличие экстремума определяется по бли­жайшей не равной нулю старшей производной, которая должна быть четной по порядку.

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

Недостатки:

1) необходимо перед каждым рабочим шагом производить довольно сложный предварительный анализ;

2) при наличии ограничений применение метода затрудняется;

3) необходимо определять частные производные целевой функции по оптимизируемым параметрам;

4) невысокая скорость достижения оптимума;

5) трудности в достижении конечной точки (оптимума);

6) большая чувствительность к масштабным преобразованиям.

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

 

Метод наискорейшего спуска (подъема)

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

 

Методы случайного поиска

 

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

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