Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Методы одномерной оптимизации




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

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, равный ACCB, и наконец, на отрезке AB откладывают отрезок AE, равный AD. Тогда

 

Рассмотрим для простоты отрезок [0,1] единичной длины.

Ясно, что на отрезке имеется две таких точки и , они симметричны относительно концов. Точка производит золотое сечение отрезка [A,C], а точка производит золотое сечение отрезка [B,D]. Положим |AB|= x. Тогда |BD|=1-x. В соответствии с определением точки «золотого сечения» имеем: . Решив эту пропорцию, получим .

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

Согласно методу чисел Фибоначчи, используют числа Фибоначчи , последовательность которых образуется по правилу при , т.е. ряд чисел Фибоначчи имеет вид 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,... Метод аналогичен методу золотого сечения с тем отличием, что коэффициент «а» равен отношению , начальное значение определяется из условия, что должно быть наименьшим числом Фибоначчи, превышающим величину , где — заданная допустимая погрешность определения экстремума. Так, если , то начальное значение , поскольку , и , на следующем шаге будет и т.д.

Метод полиномиальной аппроксимации: 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).

В результате:

-при =14 алгоритм Фибоначчи почти в 3 раз эффективнее алгоритма деления пополам.

-при =14 алгоритм золотого сечения примерно на 40 процентов эффективнее алгоритма Фибоначчи.

http://optimizaciya-sapr.narod.ru/map.html

 

 

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...