Fibonacci

En el método de eliminación de regiones de Fibonacci, el intervalo de búsqueda se reduce de acuerdo a la serie de Fibonacci, La propiedad de los números de Fibonacci es que, dados dos números consecutivos Fn−2 y Fn−1, el tercer número se calcula usando la regla de la expresión:

F_n= F_(n-1) + F_(n-2)

Donde, n = 2, 3, 4,...

Los primeros números de Fibonacci son: F_0=1, F_1=1, F_2=2, F_3=3, F_4=5, F_5=8, F_6=13 y así sucesivamente.

Los números de Fibonacci pueden usarse para crear un algoritmo de búsqueda que requiera sólo una evaluación de la función objetivo en cada iteración. El principio de la búsqueda de Fibonacci consiste en que, de dos puntos requeridos para el uso de la propiedad de eliminación de regiones uno es siempre el punto previo y el otro punto es nuevo. Por ende, sólo se requiere una evaluación de la función en cada iteración.

En la iteración k, se eligen dos puntos intermedios, cada uno de los cuales está a una distancia L_k^* de cada extremo del espacio de búsqueda (L=b−a). Cuando la propiedad o criterio de eliminación de regiones elimina una porción del espacio de búsqueda, el espacio de búsqueda restante es L_k^ . Definiendo L_k^* = (F_(n-k+1)^ /F_(n+1)^ )/L y L_k^ = (F_(n-k+2)^ /F_(n+1)^ )/L se puede mostrar que,

L_k^ - L_k^* = L_(k+1)^*

Esto significa que uno de los dos puntos usados en la iteración k se mantiene como uno de los puntos de referencia en la iteración (k + 1).

Es necesario tener en cuenta las siguientes observaciones:

• La función a optimizar debe ser unimodal en el intervalo inicial de búsqueda.

• Este método no puede localizar el óptimo exacto del problema.

• Debe especificarse el número de iteraciones a efectuar o una tolerancia.

Con la búsqueda de Fibonacci, el intervalo se reduce a,

2/F_(n+1) xL

Nótese que debe calcularse la serie de Fibonacci hasta N+1 al usar este método.

...