Лекция №14 Методы оптимизации параметров систем автоматизации



Скачать 121.19 Kb.
Дата12.11.2016
Размер121.19 Kb.
Лекция № 14

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


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

а) в зависимости от наличия ограничений на поиск экстремума различают методы безусловной и условной оптимизации;

б) в зависимости от количества управляемых параметров – методы одномерного и многомерного поиска;

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

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

Задачи оптимизации параметров технических систем, как правило, являются многопараметрическими и имеют ограничения на внутренние и выходные параметры (то есть относятся к классу задач многомерного условного поиска) –



. (1)

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


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

где - функция штрафа.

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

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

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

Для учета ограничений-равенств () используется квадратичная функция штрафа –



, (3)

где - параметр штрафа для i-й функции ограничения в m-м цикле поиска; М – число функций ограничений-равенств.

Задача поиска безусловного экстремума целевой функции обычно решается многократно (не менее 3-5 раз) с различными значениями , пока результаты поиска на смежных циклах (m-1) и m не окажутся достаточно близкими. В каждом цикле поиска минимума , о новый цикл совершается при

, (4)

где - приращение вектора параметров штрафа.

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

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

В методе внешней точки применяют:

- функцию квадрата срезки, (5)

где L – число функций ограничений-неравенств, имеет тот же смысл, что и в случае ограничений-равенств

и функцию полубесконечного барьера - , (6)

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

В методе внутренней точки используют:

- логарифмическую функцию - (7)

или обратную функцию - . (8)

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

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

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

, (9)

где - постоянные весовые коэффициенты, не зависящие от номера m цикла поиска;



- элементы векторов параметров метода множителей: .

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



; . (10)

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


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

1. Задание начальных значений и параметров алгоритма: начальной точки поиска ; начального вектора параметров штрафа ; вектора приращений параметров штрафа ; параметров окончания процедуры безусловной оптимизации в каждом цикле поиска и (зависят от выбранного метода оптимизации); параметра окончания работы алгоритма .

2. Определение значения целевой функции .

3. Поиск управляемых параметров , доставляющих минимум (максимум) целевой функции при фиксированном векторе параметров штрафа (или - в методе множителей Лагранжа).

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

5. По формуле (4) определяют (или по формулам (10) - ) и переходят к этапу 2.

Для контроля за сходимостью метода множителей Лагранжа используют последовательности ; ; ; ; ; , получаемые по окончании каждого цикла поиска. Условием прекращения поиска является неизменность значений по крайней мере одной из перечисленных последовательностей при переходе от одного цикла к другому.
Третий этап рассмотренного алгоритма заключается в поиске безусловного экстремума с использованием любого из известных методов безусловной оптимизации.
К методам многомерного поиска нулевого порядка относятся:

- метод покоординатного поиска;

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

- метод вращающихся координат;

- метод сопряженных направлений;

- метод деформируемого многогранника.

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

В методе покоординатного спуска (метод Гаусса-Зейделя) направление движения к экстремуму выбирается поочередно вдоль каждой из координатных осей управляемых параметров . Предположим, что осуществляется поиск минимума . Из выбранной начальной точки поиска выполняется пробный шаг в положительном направлении одной из координатных осей (обычно вдоль оси первого управляемого параметра). Если , то это направление принимается для осуществления дальнейшего пошагового поиска экстремума - . В противном случае движение осуществляется в отрицательном направлении. Движение в выбранном направлении изменения выполняется до тех пор, пока целевая функция улучшается - . При его нарушении возвращаются в предыдущую точку и совершается движение вдоль следующей координатной оси . После осуществления спусков вдоль осей всех управляемых параметров завершается 1 цикл и организуется новый цикл. Если на очередном цикле поиска движение оказалось невозможным ни по одной оси, то уменьшается шаг поиска. Условием окончания поиска является – , . (11)

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


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

,

где h – шаг поиска, - случайный вектор, определяющий направление поиска (для его получения используют n значений равномерно распределенной в интервале [-1,1] случайной величины ).

Алгоритм его применения аналогичен методу покоординатного спуска. Если выбранное направление не улучшает целевую функцию, то проверяется противоположное направление поиска - . Если и оно не имеет успеха, то выбирается новый вектор случайного направления поиска. Поиск прекращается после выполнения заданного числа L неудачных попыток улучшения целевой функции. По аналогии с методом покоординатного спуска в алгоритме может быть предусмотрено уменьшение величины шага после L неудачных попыток. Тогда условием окончания поиска будет условие (11).
К методам многомерного поиска первого порядка относятся:

- метод градиента;

- метод наискорейшего спуска;

- метод сопряженных градиентов;

- метод переменной метрики.

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



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

Движение в пространстве управляемых параметров осуществляется по выражению –



, где - шаг поиска, - единичный вектор направления поиска на (k+1) шаге, характеризующий направление градиента в точке .

При минимизации вектор должен иметь направление, противоположное направлению вектора градиента - ,

где - норма вектора градиента, вычисленная в точке .

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

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

; , где - малая положительная величина.

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


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

, (12)

где - текущая отображающая точка; - единичный вектор направления поиска.

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

.

Интерполяционный полином представляет собой квадратичную функцию –



. (13)

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



.

Для определения подставим в (13) -



.

Вычислив производную по переменной h и приравняв ее к нулю, получим , удовлетворяющее условию (12), то есть величину оптимального шага в направлении -



.

Следует помнить, что приемлемая оценка возможна в том случае, если унимодальна на рассматриваемом интервале изменения h.

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

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


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

Формула оптимизационного метода Ньютона базируется на разложении целевой функции в окрестности точки в ряд Тейлора (известное вам из прошлой лекции) и имеет вид –

,

где - обращенная матрица Гессе.

Условие окончания поиска имеет вид, аналогичный методу градиента - .

Для того, чтобы обеспечивался спуск по поверхности отклика к минимуму целевой функции необходимо выполнение неравенства



.

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






Тарасик В.П. Математическое моделирование технических систем: Учебник для вузов. – Мн.: ДизайнПРО, 1997. – 640 с.


База данных защищена авторским правом ©bezogr.ru 2016
обратиться к администрации

    Главная страница