Непосредственные градиентные методы

Математически, градиент целевой функции Q в точке

выражается в виде формулы Непосредственные градиентные методы ,

(19.1)

где ei – орты осей переменных xi.

При сложных моделях частные производные в (19.1) не смогут быть выяснены аналитически. Исходя из этого производится их приближенное вычисление: придавая всем xi поочередно приращения , вычисляют соответствующие приращения .

1.1. Поиск ответа задачи оптимизации градиентным способом

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

Непосредственные градиентные методы

Рис. 19.1. Поиск оптимума градиентным способом

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

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

Для ускорения поиска оптимума по градиенту используется способ наискорейшего спуска (подъема), иллюстрация которого приведена на рис.19.2.

Непосредственные градиентные методы

Рис. 19.2. Способ наискорейшего спуска (подъема)

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

Поиск по методу «оврагов»

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

Непосредственные градиентные методы

Рис. 19.3. Перемещение по оврагу

Из исходной точки А0 осуществляется перемещение по градиенту Q до точки В0, где целевая функция начинает мало изменяться (приращение за один ход меньше малой величины e). После этого в стороне от А0 выбирается вторая исходная точка А1 и из нее осуществляется перемещение по градиенту Q до точки В1, где Q начинает мало изменяться. Затем делается по прямой В0В1 ход по «оврагу» до точки А2 и т.д.

Способ зигзагообразного поиска

Данный способ используется, в то время, когда перемещение по градиенту целевой функции Q натыкается на границу ограничений и появляется неприятность предстоящего поиска экстремума в допустимой области (см. рис. 19.4).

Непосредственные градиентные методы

Рис. 19.4. Способ зигзагообразного поиска на протяжении границы ограничений

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

Непосредственные градиентные методы

(19.2)

Когда текущая точка поиска опять окажется в допустимой области, перемещение по сменяется на перемещение по направлению градиента Q.

Способ функций штрафа

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

Непосредственные градиентные методы

(19.3)

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

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

Способ случайного поиска

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

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

Непосредственные градиентные методы

Рис. 19.5. Комбинация метода и градиентного метода случайных опробований

Способом случайных проб выбираются исходные точки О1, О2, О3. Находится градиентным способом локальные экстремумы. Сравнивая локальные экстремумы, собирают из них глобальный.

Лекция 18: Многомерная оптимизация (часть 1)


Интересные записи:

Понравилась статья? Поделиться с друзьями: