|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Многомерная безусловная оптимизация
Многомерная оптимизация заключается в поиске экстремума функции нескольких (n) переменных Z= f(X) = f(x1, x2,..., xn). Для решения такой задачи применяются аналогично одномерной оптимизации аналитический метод, численные методы и методы случайного поиска. Аналитический метод основывается на 1-х и 2-х частных производных по оптимизируемым параметрам: ¶ Z/¶ xi = 0 }, . Решение системы уравнений ¶ Z/¶ xi = 0 }, дает оптимальное решение Xп, если оно существует. Вид экстремума определяется значением определителя D матрицы Гессе , , . Если решение существует в точке Xп и в этой точке D > 0, то оптимизируемая функция имеет минимум, а иначе максимум. Среди численных методов различают методы нулевого порядка и градиентные (1-го и 2-го порядка). Первые основаны только на вычислениях значений оптимизируемой функции. Вторые используют частные производные соответствующего порядка. Эффективность процедуры поиска оптимума – возможность отыскания решения и сходимость к решению по скорости зависят от применяемого метода и вида функции. Наиболее известны следующие методы нулевого порядка: координатного спуска – поочередная оптимизация параметров вдоль осей одним из известных одномерных методов (одна из реализаций – метод Гаусса-Зейделя на основе шагового метода); спирального координатного спуска; вращающихся координат (метод Розенброка); конфигураций; Хука-Дживса с поиском по образцу; параллельных касательных (метод Пауэлла); Нелдера-Мида – поиска по деформируемому многограннику за счет его отражения, растяжения и сжатия и др.
1 Пуск
Ввод a, b, e a и b – начальные значения нижней и верхней границ интервала поиска экстремума; e – относительная точность поиска h, L, aш ,bш h –относительный шаг поиска; L – граничное число неудачных попыток; aш и bш – соответственно коэффициенты уменьшения шага поиска и определения шкалы поиска
s = (b - a)/ bш
xт = (a+ b)/ 2 xт – текущая расчетная точка xп= xт xп – текущее (начальное) приближение к решению
Z = f(xт)
7 на минимум 11 15 Zп = Z Zп > Z Да xп = xт: Zп= Z
15,18 k = 0 12 8
k = k + 1 xт = xп+ s h (2 r -1) 13 Да 13 k <= L
10 9 Z = f(xт) 14 Нет
h = h aш
18 Да 8 xп, Zп, h h >= e aш
Нет
Вывод xп, Zп
Останов
Рисунок 3.11 – Алгоритм одномерного случайного поиска с пересчетом
Наиболее известными являются такие градиентные методы как наискорейшего спуска и Давидона-Флетчера-Пауэлла (ДФП) с использованием кубической интерполяции. Для случайного поиска применяются метод с пересчетом, метод с парными пробами, метод по наилучшей пробе и др. Эффективная оптимизационная процедура должна успешно решать тестовые задачи, которыми могут быть: функция Розенброка Хп = (1;1);
функция Пауэлла
Хп = (0;0;0;0);
двумерная экспоненциальная функция: , при k = 1 Хп = (1;10).
Одним из методов нулевого порядка – метод координатного спирального спуска. Основывается на поочередном приближении к решению с текущим значением шага по всем оптимизируемым переменным. Если с текущим шагом в данном направлении оптимизация вызывает "ухудшение" целевой функции, то шаг уменьшается и направление поиска меняется на противоположное. Коэффициент aш рекомендуется принимать равным 0.25 – 0.40. Решение продолжается до тех пор, пока шаг по модулю не станет равным или менее заданной точности решения. Алгоритм метода координатного спирального спуска приведен ниже. Метод координатного спуска недостаточно эффективен для поверхностей с "оврагами", так как в этом случае получение решения с требуемой точностью не гарантировано. Это вызвано тем, что в случае "оврага", повернутого относительно осей, попытка продвижения в любом направлении может вызывать "ухудшение" целевой функции. В то же время продвижение вдоль "оврага" может давать "улучшение" целевой функции. Для таких случаев необходимо применять другие методы, например, метод Розенброка или метод Пауэлла.
Метод вращающихся координат (метод Розенброка) имеет следующий алгоритм (рисунок 3.13): 1) принимается начальное (текущее) приближение к решению – точка Xп1 и начальный (текущий) шаг поиска; 2) находится одним из известных методов при текущем значении шага следующее приближение – точка Xп2; 3) по линии Xп1 - Xп2 принимается новое направление поиска (производят поворот осей); 4) модифицируется шаг поиска и вдоль новых осей Z1 и Z2 находится следующее текущее приближение; 5) если результат с заданной точностью получен, то решение закончено или иначе по последнему и предпоследнему приближениям находится новое направление поиска и делается переход на пункт 4. Для выполнения поворота осей используют ортогонализацию по Граму-Шмидту. Пуск 2 Ввод m, h, aш, e m – число оптимизируемых переменных; h – начальный шаг поиска; aш– коэффициент уменьшения шага поиска; e – точность поиска 3 xп i – начальные (текущие) приближения к решению Ввод xп i,
4 Z = f(Xп)
5 12 10 Вывод xпi, Z, h
6 11 Нет abs(h) > e xпi = xпi + h Да 12 7 Zп = Z h = –aш h
8 Z = f (X) 5 13 Вывод xпi, xп m =xп m -h, Zп, e на min Нет 9 Да 14 Zп > Z Останов
Рисунок 3.12 – Алгоритм координатного спирального спуска Рисунок 3.13 – Графическая интерпретация метода Розенброка
Метод Пауэлла основан на определении направлений поиска путем проведения касательных к изолиниям (изоповерхностям), параллельных друг другу. Линия, соединяющая точки касания определяет текущее направление поиска Z1. Графическое представление метода приведено на рисунке 3.14.
Рисунок 3.14 – Графическая интерпретация метода Пауэлла
Итерационные процессы оптимизации, в которых направление поиска на каждом шаге совпадает с антиградиентом функции, называются градиентными методами. Отличаются способами выбора величины шагов поиска. Метод наискорейшего спуска – один из методов с переменным шагом (рисунок 3.15). Шаг выбирается с учетом степени изменения функции в направлении поиска: Hi = h Si Gi, где i – номер переменной; Hi – шаг поиска; h – относительный шаг поиска; Si – шкальность изменения переменных; Gi – значение антиградиента функции по хi. Шаг Hi остается постоянным до тех пор, пока значение функции убывает (растет).
Рисунок 3.15 – Графическая интерпретация метода наискорейшего спуска
Шкальность определяется зависимостью Si = (xн – xв)i bш , где xн, xв – соответственно принятая нижняя и верхняя граница интервала поиска; bш – коэффициент, определяющий шкальность по переменным. Имеется ряд методов оптимизации на основе случайного поиска. Ниже приведен алгоритм метода случайного поиска с пересчетом. В алгоритме приняты обозначения: r – псевдослучайные числа в интервале от 0 до 1.0; Si – шкальность изменения xi; Xт = {xтi} – текущее значение X; Xп = {xпi} – текущее приближение к решению X.
Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.012 сек.) |