Задача оптимизации в конструировании

5. Метод Фибоначчи
Этот метод является более эффективным по сходимости, чем метод дихотомии, и обладает наибольшей скоростью сходимости для класса непрерывных функций. В нем, как и в методе «золотого сечения», на каждом шаге производится только одно определение целевой функции, а в методе дихотомии два. Но в этом методе требуется заранее выбрать число испытаний N.
Метод основан на использовании чисел Фибоначчи для нахождения точек, в которых определяется целевая функция F(х).
Числа Фибоначчи образуют последовательность целых чисел так, что Ф_N = Ф_{N -1} + Ф_{N -2} при N  2. Ф₀ = Ф₁ = 1.
Первые 15 чисел Фибоначчи.

N	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
ФN	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610

В основу схемы поиска экстремума положены два исходных соотношения

L_{N -2} = L_{N -1} + L_N, при N  3, и
Первое из них связывает длины трех соседних (по номерам) интервалов неопределенности. Второе требует, чтобы процесс поиска экстремума всегда завершался одинаково: симметричным размещением двух последних точек (х_{N -1} и х_N) на интервале L_{N -1}.
Координаты точек, в которых определяются целевые функции, находятся по формулам:


где r – номер шага (r = 0, 1, 2, 3, …, N –3);
l_r = (b_r – a_r) – длина интервала неопределенности на r-ом шаге;
a_r, b_r – начало и конец r-го интервала неопределенности.
Алгоритм метода является итерационной процедурой, включающей следующие этапы.
На первом этапе, который соответствует первому шагу поиска (r = 0) симметрично от концов начального интервала неопределенности (а и b) проводится пара испытаний в точках и , определяемых N-ом и (N –1) числами Фибоначчи. Получаем

В этих точках определяется целевая функция и в зависимости от ее значений выбирается новый (суженный) интервал неопределенности.

Второй этап включает в себя (N –3) итерационных шагов. На каждом r-ом шаге в интервале неопределенности l_r, полученном на предыдущем шаге, рассматривается новая пара испытаний .
Особенностью данного алгоритма поисковой оптимизации является то, что из двух точек и , рассматриваемых на (r+1)-м шаге, одна всегда будет совпадать с одной из точек предыдущего шага ( или ), в которой уже было проведено испытание.
Третий этап характерен тем, что после проведения (N –1)-го испытания необходимо решить, по какую сторону от точки х, находящейся внутри интервала неопределенности l_{N -1}, лежит точка истинного экстремума. Для этого последнее N-е испытание проводится вблизи от точки предыдущего испытания в точке (х – ) или (х + ), что позволяет определить апостериорный (послеопытный) интервал неопределенности l_N.
На рис. 4.22 приведена схема поиска экстремума по методу Фибоначчи (второй и третий этапы).
В заключение данного раздела проведем сравнение методов «золотого сечения» и Фибоначчи.
Метод Фибоначчи более эффективен по сходимости, т.е. по достижению необходимого сужения интервала неопределенности при одинаковом числе определений целевой функции.
Но его недостатки:

1. 
   Заранее заданное число испытаний, которое нельзя менять в процессе сужения интервала неопределенности, и если после N испытаний не получена нужная точность определения оптимума, то все приходится начинать сначала, задавшись большим N..
   
2. 
   При применении ЭВМ необходимо запоминать (или каждый раз вычислять) числа Фибоначчи.
   

Рисунок 4.22.

Метод «золотого сечения» не требует заранее заданного числа испытаний. Для него требуется сравнительно небольшой объем памяти ЭВМ, и он прост в реализации.

С точки зрения эффективности метод «золотого сечения» занимает промежуточное положение между методами дихотомии и Фибоначчи.
На практике иногда комбинируют оба метода: первые шаги делают по методу «золотого сечения», а затем, когда оптимум достаточно близок, фиксируют число N и переходят к методу Фибоначчи.