MMTS_Lectures_M

3. ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ И МЕТОДЫ ИХ РЕШЕНИЯ

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

3.1. Безусловная оптимизация одномерной унимодальной целевой функции

Унимодальной называется функция, имеющая один экстремум.

Задача поиска экстремума сводится к нахождению значения хо, соответствующего максимуму или минимуму f(x).

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

Применение аналитического метода возможно в случае дифференцируемости функции f(x) и находится как f'(x) = 0. Решение полученного уравнения дает оптимальное значение хо. Значение второй производной определяет вид экстремума. Если f''(хо) > 0, то имеем минимум, а если f''(хо) < 0, то максимум (рисунок 3.1).

f(x)

1

2

хо x

f '(x)

2

x

1

f ''(x)

2

x

1

Рисунок 3.1 – Графическая интерпретация поиска экстремума дифференцируемой функции

Из приведенной графической интерпретации метода следует, что функция (1) имеет максимум и функция (2) – минимум.

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

Метод дихотомии (половинного деления) является одним из методов одномерной безусловной оптимизации унимодальной целевой функции. Алгоритм метода основывается на выборе исходного отрезка поиска решения [a, b] и последующем делении текущего отрезка пополам:

1)xc=(b+a)/2;

2)x1 = xc - /2; x2 = xc + /2, где – точность поиска экстремума;

3)если при минимизации f(x1) < f(x2), то b = xс, иначе a = xс;

4)при b - a <= , xопт = ( b + a)/2 и решение получено, иначе на п. 1.

Ниже приведена графическая интерпретация (рисунок 3.2) и один из возможных алгоритмов метода дихотомии (рисунок 3.3).

f(x)

f(x2) f(x1)

Рисунок 3.2 – Графическая интерпретация метода дихотомии

1

Пуск

2

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

Рисунок 3.3 - Схема алгоритма программы по методу дихотомии

62

Метод золотого сечения основан на делении отрезка [a,b] по правилу "золотого" сечения, когда отношение большего отрезка к меньшему const. Такое отношение определяется

выражением (5 -1)/2 ≈ 0.62. При этом методе в отличие от метода дихотомии на каждой итерации требуется расчет только одного значения целевой функции. В результате находится решение xп и соответствующее ему значение целевой функции Zп (рисунки 3.4, 3.5).

На минимум: f(x)

– точность поиска

3

k= (5 -1)/2

4

i = 1

Рисунок 3.5 - Схема алгоритма программы по методу золотого сечения

Метод Фибоначчи основан на делении отрезка [a, b] с использованием чисел Фибоначчи, представляющих ряд, у которого последующее число равно сумме двух предыдущих

(1,1,2,3,5,8 и т.д.).

Шаговые методы основаны на том, что текущему приближению к решению xп на каждом новом шаге дается приращение h как xп=xп+h и вычисляется f(xп). Если новое значение целевой функции "лучше" предыдущего, то переменной x дается новое приращение. Если функция "ухудшилась", то поиск в данном направлении завершен.

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

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

Рисунок 3.6 – Графическая интерпретация метода поразрядного приближения

1

Z = f(xп)

4

Zп =Z

5

xп = xп + h

Рисунок 3.7 – Алгоритм поиска экстремума по методу поразрядного приближения

Метод квадратичной интерполяции-экстраполяции является одним из методов аппроксимации кривыми и базируется на описании целевой функции квадратичной параболой по трем точкам – текущее приближение x1= xп и точки, лежащие от нее слева x0 и справа x2 на удалении h и нахождении экстремума аналитически. Процесс проводится до тех пор, пока предыдущее и последующее приближения различаются более, чем на заданную точность поиска. Алгоритм метода следующий (рисунок 3.8, 3.9):

1) находятся x0 = xп - h ; y0 = f(x0); x1 = xп ; y1 = f(x1); x2 = xп + h; y2 = f(x2);

2)находятся параметры параболы, проходящей через три выбранных точки:

a = (yo- 2y1 + y2) / (2h2);

b = (-yo (2x1 + h) + 4y1 x1 - y2 (2x1 - h)) / (2h2);

3)вычисляется очередное приближение xп на основе аналитической оптимизации

аппроксимирующей функции как xп = - b/( 2a);

4) проверяется условие: abs(xп - x1) < . Если условие выполняется, то оптимум найден и решение закончено, иначе переходим к 1-му пункту алгоритма.

На минимум: f(x)

f(x)=ax2+bx+c

f(xп+h) f(xп-h) f(xп)

Рисунок 3.8 – Графическая интерпретация метода на основе квадратичной аппроксимации

1

Пуск

2

Ввод xп, h, xп – текущее значение приближения к решению; h – параметр интервала

yi= f(xi)

Да

9

Zп= f(xп)

10

Вывод xп, Zп

11

Останов

Рисунок 3.9 – Алгоритм на основе квадратичной аппроксимации

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

Повторение испытаний описывается формулой Бернулли (биноминальным распределением)

P(k) = C kn pk qn-k , k = 0, 1, 2, ..., n,

где k – число благоприятных случаев; n – общее число испытаний;

p – вероятность благоприятного исхода при одном испытании; q – вероятность, противоположная p (q=1-p).

Вероятность, что событие наступит n раз

P(n) = pn ;

что не наступит ни разу

P(0) = (1-p)n ;

наступит хотя бы один раз

P1 =1-p(0) 1 (1-p)n .

Если абсолютную точность поиска решения на участке (b - a) обозначить через ε, то вероятность решения при одном испытании p = ε/(b - a). При этом вероятности Р1 получения решения с заданной точностью ε в зависимости от числа испытаний n при различных p приведены в таблице 3.1.

Таблица 3.1 – Оценка точности поиска

Например, если p = ε /(b - a)=0.01, то вероятность получения решения с точностью ε при числе испытаний n = 100 равна 0.634; при n =200 – 0.866; при n = 500 – 0.993; при n = 1000 – 0.99996, т.е. требуется 10 (b - a) /ε испытаний для надежного решения (Р1> 0.9999) с заданной

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

Имеется большое множество методов оптимизации на основе случайного поиска и их разновидностей. Ниже приведена иллюстрация простейшего метода поиска (рисунок 3.10), состоящая в последовательном формировании на отрезке от a до b случайным образом расчетной точки xт, расчете в ней целевой функции f(xт), сравнении значения функции f(xт) и ранее найденного "лучшего" значения функции f(xп), присвоении xп = xт и f(xп) = f(xт), если текущая точка "лучше". Формирование случайной точки производится по выражению xт = a + r (b-a), где r – случайное число, равномерно распределенное в интервале от 0 до 1.0.

f(x)

f(xт)

f(xп)

Рисунок 3.10 – Графическая интерпретация метода случайного поиска (на минимум)

Более эффективным является метод случайного поиска с пересчетом, алгоритм которого приведен на рисунке 3.11. Принимаемые значения показателей aш, bш, h и L должны находится в определенном соотношении, например, начальные значения могут быть приняты как bш = 2 ; h= bш /5 ; aш = 0.25 ; L=10. Формирование случайной расчетной точки xт (блок 9) производится относительно текущего приближения xп на основе использования случайных чисел r, равномерно распределенных в интервале от 0 до 1.0. Произведение sh определяет отрезок, в пределах которого формируется случайная точка.

3.2. Многомерная безусловная оптимизация

Многомерная оптимизация заключается в поиске экстремума функции нескольких (n)

переменных Z= f(X) = f(x1, x2,..., xn)=min(max) , i 1,n.

{xi}

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

Аналитический метод основывается на 1-х и 2-х частных производных по оптимизируемым переменным:

Решение системы уравнений Z/ xi = 0 }, i 1,n дает оптимальное решение Xп , если оно существует.

Вид экстремума определяется значением определителя det G матрицы Гессе

Если решение существует в точке Xп и в этой точке det G > 0, то оптимизируемая функция имеет минимум, а иначе максимум.

1

17Да

16

Нет

18

Вывод xп , Zп

19

Останов

Рисунок 3.11 – Алгоритм одномерного случайного поиска экстремума с пересчетом

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

Наиболее известны следующие методы нулевого порядка:

координатного спуска – поочередная оптимизация переменных вдоль осей одним из известных одномерных методов (одна из реализаций – метод Гаусса-Зейделя на основе шагового метода);

координатного спирального спуска; вращающихся координат (метод Розенброка); конфигураций; Хука-Дживса с поиском по образцу;

параллельных касательных (метод Пауэлла); Нелдера-Мида – поиска по деформируемому многограннику за счет его отражения,

растяжения и сжатия и др.

Наиболее известными являются такие градиентные методы как наискорейшего спуска и Давидона-Флетчера-Пауэлла (ДФП) с использованием кубической интерполяции.

Для случайного поиска применяются метод с пересчетом, метод с парными пробами, метод по наилучшей пробе и др.

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

функция Розенброка

f(x1 ,x2 ) 100(x2 x12 )2 (1 x1 )2 Хп = (1; 1);

функция Пауэлла

f(X) (x1 10x22)2 5(x3 x4)2 (x2 2x3)4 10(x1 x4)4 Хп = (0; 0; 0; 0);

двумерная экспоненциальная функция :

k

f(x1 ,x2 ) ((e-kx1 -e-kx2 )-(e-k -e-10k ))2 ,

i 1

при k = 1 Хп = (1;10).

Один из методов нулевого порядка – метод координатного спирального спуска основывается на поочередном приближении к решению с текущим значением шага по всем оптимизируемым переменным (рисунок 3.12). Если с текущим шагом в данном направлении поиска по всем переменным происходит "ухудшение" целевой функции, то шаг уменьшается и направление поиска меняется на противоположное. Коэффициент aш рекомендуется принимать равным 0.25 – 0.40. Вычисления продолжаются до тех пор, пока шаг по модулю не станет равным или менее заданной точности решения. Алгоритм метода координатного спирального спуска приведен ниже.

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

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

1

шага поиска; – точность поиска

3

xп i – начальные (текущие) приближения к решению

Ввод xп i, i 1,m

4

Z= f(Xп)