Методы одномерной оптимизации
Задачи одномерной минимизации представляют собой простейшую математическую модель оптимизации, в которой целевая функция зависит от одной переменной, а допустимым множеством является отрезок вещественной оси: f(x) -> min, x принадлежит [a, b]. Самым слабым требованием на функцию f(x), позволяющим использовать эти методы, является ее унимодальность. Поэтому далее будем считать функцию f(x) унимодальной на отрезке [a, b] т.е. на котором имеется один минимум.
К методам одномерной оптимизации относятся методы равномерного поиска, дихотомического деления, золотого сечения, чисел Фибоначчи, полиномиальной аппроксимации и ряд их модификаций.
Метод перебора или равномерного поиска является простейшим из прямых методов минимизации и состоит в следующем. Разобьем отрезок [a,b] на n равных частей точками деления: xi=a+i(b-a)/n, i=0,...n Вычислив значения F(x) в точках xi, путем сравнения найдем точку xm, где m - это число от 0 до n, такую, что F(xm) = min F(xi) для всех i от 0 до n. Погрешность определения точки минимума xm функции F(x) методом перебора не превосходит величены Eps=(b-a)/n.
Согласно методу дихотомического деления (рис. 3,а) отрезок делят пополам и в точках, отстоящих от центра
Рис. 3. Одномерная минимизация: а — дихотомическое деление; б — золотое сечение Золотое сечение (золотая пропорция) — деление непрерывной величины на две части в таком отношении, при котором меньшая часть так относится к большей, как большая ко всей величине. Отношение большей части к меньшей в этой пропорции выражается квадратичной иррациональностью и, наоборот, отношение меньшей части к большей Геометрическое построение. Золотое сечение отрезка AB можно построить следующим образом: в точке B восстанавливают перпендикуляр к AB, откладывают на нём отрезок BC, равный половине AB, на отрезке AC откладывают отрезок AD, равный AC − CB, и наконец, на отрезке AB откладывают отрезок AE, равный AD. Тогда
Рассмотрим для простоты отрезок [0,1] единичной длины. Ясно, что на отрезке имеется две таких точки Таким образом, требуется не более Согласно методу чисел Фибоначчи, используют числа Фибоначчи Метод полиномиальной аппроксимации: P = a0+a1 x +a2 x2
Выбирают промежуточную точку С на отрезке А,В и записывают значения целевой функции в каждой точке. Далее решают систему из трех АУ, полученных подстановкой P(x) и А, В, С вместо х – получают аi. Исходя из (dP(x)/dx =0) определяют точку экстремума. Сравнение эффективности алгоритмов одномерной условной оптимизации.
Аналитическое решение возможнотолько при условии одномерной унимодальной функции Ф(х) на интервале <а, b>. В качестве критерия используют максимальную длину текущего интервала неопределенности (ТИН) после N испытаний. А) после одной итерации равномерного поиска ТИН уменьшается в N/2 раз W=(b-a)/N/2 Б) при дихотомическом поиске после одной итерации ТИН уменьшается в 2 раза W= (b-a)/2n B) алгоритм Фибоначчи: i-число Фибоначчи, N-шаг. W= (b-a)/i(N). В результате: -при -при http://optimizaciya-sapr.narod.ru/map.html
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|