ПОИСК Статьи Чертежи Таблицы Методы одномерной оптимизации из "Основы автоматизированного проектирования " К методам одномерной оптимизации относятся методы дихотомического деления, золотого сечения, чисел Фибоначчи, полиномиальной аппроксимации и ряд их модификаций. [c.159] Пусть задан отрезок [А, В], на котором имеется один минимум (в общем случае нечетное число минимумов). Согласно методу дихотомического деления (рис. 4.3, а) отрезок делят пополам и в точках, отстоящих от центра С отрезка на величину допустимой погрешности рассчитывают значения целевой функции F( + д)ч F( - д). Если окажется, что F( + q) F( - q), то минимум находится на отрезке [ЛС], если F( + q) F( - q), то минимум — на [С,5], если F + q) = F( - q) — иа [С - q, С + q]. Таким образом, на следующем шаге вместо отрезка [А, В] нужно исследовать суженный отрезок [А,С], [С, В] или [С - q,С + q]. Шаги повторяются, пока длина отрезка не уменьшится до значения погрешности q. Таким образом, требуется не более N шагов, где N— ближайшее к log В -A)/q) целое значение, но на каждом шаге целевую функцию следует вычислять дважды. [c.159] В соответствии с методом золотого сечения (рис. 4.3, б) внутри отрезка [А, В] выделяют две промежуточные точки С, и D, на расстоянии s = aL от его конечных точек, где Z, = В - А — длина отрезка. Затем вычисляют значения целевой функции F(x) в точках С, и Если F( ) F(D ), то минимум находится на отрезке [A,DJ, если F( ,) F(D,)), то — на отрезке [С,, В], если F( j) = F(Dj) — на отрезке [С,, D,]. Следовательно, вместо отрезка [А,В] теперь можно рассматривать отрезок [A,D , [С,, 5] или [С , DJ, т. е. длина отрезка уменьшилась не менее чем в Ы Ь - aL) = 1/(1 - а) раз. Если подобрать значение а так, что в полученном отрезке меньшей длины одна из промежуточных точек совпадет с промежуточной точкой от предыдущего шага, т. е. в случае выбора отрезка [А, точка совпадет с точкой Ср а в случае выбора отрезка [С,, 5] точка — с точкой ),, то это позволит сократить число вычислений целевой функции на всех шагах (кроме первого) в 2 раза. [c.159] Условие получения такого значения а формулируется следующим образом (1 - 2a)Zj = откуда с учетом того, что /Z, = 1/(1 - а), имеем а = 0,382. Это значение и назьшают золотым сечением. [c.159] Таким образом, требуется не более N шагов и Ж+ 1 вычисление целевой функции, где iV можно рассчитать, используя соотношение В-А) Е = (1 - a)N при заданной погрешности определения экстремума. [c.160] Согласно методу чисел Фибоначчи, используют числа Фибоначчи последовательность которых образуется по правилу при Rg = R =l, т. е. ряд чисел Фибоначчи имеет вид 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144. .. Метод аналогичен методу золотого сечения с тем отличием, что коэффициент а равен отношению R.JR., начальное значение i определяется из условия, что / .должно быть наименьшим числом Фибоначчи, превышающим величину В -А) Е, где Е — заданная допустимая погрешность определения экстремума. Так, если (В-А)/Е = 100, то начальное значение i = 12, поскольку R= 144, и а = 55/144 = 0,3819, на следующем шаге будет а = 34/89 = 0,3820 и т. д. [c.160] Вернуться к основной статье