АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. II. Методы непрямого остеосинтеза.
  2. II. Рыночные методы.
  3. III. Методы искусственной физико-химической детоксикации.
  4. III. Параметрические методы.
  5. IV. Современные методы синтеза неорганических материалов с заданной структурой
  6. А. Механические методы
  7. Автоматизированные методы
  8. Автоматизированные методы анализа устной речи
  9. Адаптивные методы прогнозирования
  10. Административно-правовые методы государственного управления
  11. Административно-правовые методы государственного управления
  12. АДМИНИСТРАТИВНО-ПРАВОВЫЕ МЕТОДЫ УПРАВЛЕНИЯ

 

К методам одномерной оптимизации относятся методы дихотомического деления, золотого сечения, чисел Фибоначчи, полиномиальной аппроксимации и ряд их модификаций.

Пусть задан отрезок [А,В], на котором имеется один минимум (в общем случае нечетное число минимумов). Согласно методу дихотомического деления (рис. 7.20,а) отрезок делят пополам и в точках, отстоящих от центра С отрезка на величину допустимой погрешности q, рассчитывают значения целевой функции F(C+q) и F(C-q). Если окажется, что F(C+q)>F(C-q), то минимум находится на отрезке [А,С], если F(C+q)<F(C-q), то минимум – на [С,В], если F(C+q) = F(C-q) – на [C-q,C+q]. Таким образом, на следующем шаге вместо отрезка [А,В] нужно исследовать суженный отрезок [А,С], [С,В] или [C-q,C+q]. Шаги повторяются, пока длина отрезка не уменьшится до величины погрешности q. Таким образом, требуется не более N шагов, где N – ближайшее к log((B-A)/ q) целое значение, но на каждом шаге целевую функцию следует вычислять дважды.

Рисунок 7.20 – Одномерная оптимизация

а – дихотомическое деление, б – золотое сечение

По методу золотого сечения (рис. 4.3,6) внутри отрезка [А,В] выделяют две промежуточные точки С1 и Dl на расстоянии s = aL от его конечных точек, где L = В-А – длина отрезка. Затем вычисляют значения целевой функции F(x) в точках С1 и Dl. Если F(С1) < F(Dl), то минимум находится на отрезке [A,D1], если F(С1) > F(Dl), то – на отрезке 1,B], если F(С1) = F(Dl) – на отрезке 1 Dl]. Следовательно, вместо отрезка [А,В] теперь можно рассматривать отрезок [A,D1], [С1,B] или 1 Dl], т.е. длина отрезка уменьшилась не менее чем в L/(L-aL)=1/(1-a) раз. Если подобрать значение а так, что в полученном отрезке меньшей длины одна из промежуточных точек совпадет с промежуточной точкой от предыдущего шага, т.е. в случае выбора отрезка [A,D1] точка D2 совпадет с точкой С1, а в случае выбора отрезка 1,B] точка С2 – с точкой D2 то это позволит сократить число вычислений целевой функции на всех шагах (кроме первого) в 2 раза.

Условие получения такого значения а формулируется следующим образом (1-2a)Lk = aLk-1, откуда с учетом того, что Lk/Lk-1 =1/(1- a), имеем а = 0,382. Это значение и называют золотым сечением.

Таким образом, требуется не более N шагов и N+1 вычисление целевой функции, где N можно рассчитать, используя соотношение (В-А)/Е=(1-а)N заданной погрешности Е определения экстремума.

Согласно методу чисел Фибоначчи, используют числа Фибоначчи Ri, последовательность которых образуется по правилу Ri+2=Ri+1+Ri при R0=R1= 1, т.е. ряд чисел Фибоначчи имеет вид 1,1,2, 3, 5, 8, 13, 21, 34, 55, 89, 144.... Метод аналогичен методу золотого сечения с тем отличием, что коэф­фициент а равен отношению Ri-2/Ri, начальное значение i определяется из условия, что R, ; должно быть наименьшим числом Фибоначчи, превышающим величину (В-А)1Е, где Е – заданная допустимая погрешность определения экстремума. Так, если (В-А)/Е= 100, то начальное значение i= 12, поскольку R1= 144, и а = 55/144 = 0,3819, на следующем шаге будет а = 34/89 = 0,3820 и т.д.

По методу полиномиальной аппроксимации при аппроксимации F(x) квадратичным полиномом

Р(х) = а0 + а1х + а2x2 (7.41)

выбирают промежуточную точку С и в точках А, В, С вычисляют значения целевой функции. Далее решают систему из трех алгебраических уравнений, полученных подстановкой в (7.41) значений А,В, С вместо х и вычисленных значений функции вместо Р(х). В результате становятся известными значения коэффициентов ak в (7.41) и, исходя из условия dP(x)/dx= 0, определяют экстремальную точку Э полинома. Например, если точка С выбрана в середине отрезка [А,В], то Э=С+(C-A)(F(A)-F(B))/(2(F(A)-2F(C)+F(B))).

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)