Методы оптимизации - Харчистов Б.Ф.

41

Метод Фибоначчи

Метод Фибоначчи является наилучшим (в смысле максимального уменьшения длины отрезка локализации) среди активных методов поиска.

Согласно методу Фибоначчи, на первом шаге (первой итерации) проводятся два вычисления значений f(x) в точках x1(1) и x2(1) (причем x1(1) < x2(1) ), расположенных симметрично относительно середины отрезка ∆0 = [a, b]. По результатам вычислений одна из частей отрезка ([a, x1(1) ] либо [x2(1) , b] ) отбрасывается, при этом одна из точек (соответственно x2(1) либо x1(1) ) уже проведен-

ных вычислений остается внутри отрезка ∆2 ≡ ∆(1) . На каждом

последующем шаге (последующей итерации) точка очередного вычисления выбирается симметрично оставшейся точки. Таким образом, на первой итерации проводятся два вычисления значений f(x), на каждой последующей − одно вычисление. Поэтому при заданном количестве вычислений N будет выполнено N −1 шагов (итераций).

числа Фибоначчи, определяемые следующим образом:

F0 = F1 = 1, Fk = Fk −1 + Fk − 2 , k = 2,3,....

Условием окончания вычислений является выполнение заданного количества вычислений N.

Итак, алгоритм поиска минимума унимодальной функции методом Фибоначчи заключается в следующем.

1. Задается N, определяются числа Фибоначчи Fk, k = 0, N +1, выбирается ε из условия

ε< b − a .

FN +1

Полагается j=1.

Результаты вычислений заносим в табл. 4.4.

44

Таблица 4.4

Примечание. Знаком * помечаем точки xi( j ) , i=1,2, вычис-

ляемые на j-й итерации.

Поскольку j=N−1=3, то вычисления завершаются.

Точка минимума локализована на отрезке ∆4 = [1,44; 1,88],

Метод золотого сечения

Недостатком наиболее эффективного метода Фибоначчи является то, что должно быть задано количество вычислений N. Метод золотого сечения почти столь же эффективен, как и метод Фибоначчи, но при этом не зависит от N. Алгоритм поиска по методу золотого сечения определяется тем же правилом симметрии, что и алгоритм по методу Фибоначчи: на первой итерации выбираются две точки, расположенные симметрично относительно середины исходного отрезка; на каждой последующей итерации выбирается одна точка, расположенная симметрично оставшейся точки. Разница заключается в выборе точек. Метод золотого сечения основан на делении отрезка локализации «золотым сечением», т.е. таком делении, когда отношение большей части отрезка ко всему отрезку равно отношению меньшей части к большей

A C B

46

функции f (x) = x4 − 6x2 +10 , заданной на отрезке ∆=[1,3], при

N=4.

Решение.

В данном случае будут выполнены N −1 = 3 итерации. Результаты вычислений заносим в табл. 4.5.

Таблица 4.5

f (x) = x2 −3x + 2, заданной на отрезке ∆ = [0, 4] , при N=8, ε = 0,1. 3. Определить методом Фибоначчи минимум функции f (x) = x2 −3x + 2, заданной на отрезке ∆ = [0, 4], при N=4, ε = 0,2 . 4. Определить методом золотого сечения минимум функ-

ции f (x) = x2 −3x + 2, заданной на отрезке ∆ = [0, 4] , при N=4.

47

5. ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ МНОГОЭКСТРЕМАЛЬНЫХ ФУНКЦИЙ

На практическом занятии рассматриваются методы отыскания глобального минимума функций одной переменной. Предполагается, что заданы исходный отрезок ∆ = [a, b] и коли-

чество вычислений N значений функции f (x) . Требуется опре-

делить оценки точки глобального минимума x* и величины минимума f * = f (x*) .

Простейшим методом глобальной оптимизации является так называемое сканирование (метод перебора), которое состоит в

последовательном переборе точек xi ∆, i = 1, N . В простейшем случае точки выбираются равномерно. При этом исходный отре-

минимума и величины глобального минимума, полученные после

iвычислений;

α− любое число, не принадлежащее исходному отрезку [a,b],

т.е. α [a,b] ;

β− число, заведомо большее f * , т.е. β > f * .

Алгоритм поиска глобального минимума методом сканирования заключается в следующем.

1. Задаются N, α и β ; полагается x0* = α, f0* = β, i = 1.

2.Вычисляются xi и f (xi ) .

3.Полагается

4. Проверяется условие окончания вычислений i=N.

Если оно выполняется, то полагается x* x*N , f * fN* и

вычисления завершаются.

Если условие не выполняется, то полагается i=i+1 и осуществляется переход к п.2.

Пример. Определить с помощью сканирования минимум

Поскольку i=10=N, то вычисления завершаются.

Ответ: x* 2,25, f * −1,62 .

Модификацией сканирования с целью уменьшения коли-

чества вычислений является поиск (сканирование) с уточнением.

В этом случае процедура равномерного сканирования выполняется n раз.

На 1-м этапе осуществляется сканирование во всей зоне поиска (на всем отрезке) ∆(0) = [a(0) ≡ a, b(0) ≡ b] . При этом вы-

∆(1) = [a(1) , b(1) ] , границы которого определяются следующим об-