CvdB

búsqueda de Fibonacci

Definición: Esta búsqueda encuentra el máximo de una función unimodal en un intervalo, [a, b], por la evaluación de los puntos de búsqueda ubicados segun una transformación de la secuencia de Fibonacci, {F_N}.

Los números de Fibonacci son los que satisfacen la definición siguiente: 

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

con las condiciones iniciales 

F_0 = 0
 F_1 = 1.

Tal como se ve en la tabla, la secuencia se acelera mucho después de N = 10 y se vuelve astronómica cerca de N = 50. 

         N    F_N
       ==============
         1      0            
         2      1
         3      1
         4      2
         5      3
         6      5
         7      8
         8     13
         9     21
        10     34
        11     55
        12     89
        22  10946
        52    2.0E10
       102    5.7E20
      ==============

En el caso continuo, empezamos con un cierto intervalo de incertidumbre, [a,b], y reducimos su longitud a 

(b-a)/F_N.

El cociente, g_n = F_(n-1)/F_n, es la clave para las ubicaciones de los puntos a experimentar.

    Este es el método para el caso continuo:
  1. Inicialización. Sea x = a + (1 - g_N)(b-a) y, además, y = a + g_N(b-a). Evaluar f(x) y f(y) y llamar n=N.
  2. Iteración. Si f(x) < f(y), reducir el intervalo a [x, b] (esto es, fijar a=x), decrementar n to n-1, y fijar tanto x = y, como y = g_n. Si f(x) >= f(y), reducir el intervalo a [a, y) (esto es, fijar b=y), decrementar n a n-1, y fijar tanto y = x como x = 1 - g_n.

La búsqueda de Fibonacci minimiza el máximo número de evaluaciones necesarias para reducir el intervalo de incertidumbre a una longitud prescripta. Con 20 evaluaciones se reduce el intervalo unitario [0,1] a 1/10946 (=0,00009136). En el caso de un conjunto finito con sólo 20 evaluaciones, la búsqueda de Fibonacci encuentra el máximo de una función unimodal entre 10946 puntos. Solamente la supera la búsqueda de "lattices" (lattice search).

En el caso de ir creciendo N a valores muy altos, la relación de ubicación (g_N) tiende a un límite que es la conocida relación áurea , por lo cual la búsqueda de Fibonacci se acerca a la más sencilla búsqueda por relación áurea. Se la puede comparar también con la búsqueda dicotómica (que determina dos puntos cercanos a la mitad del intervalo [a,b] y con la comparación de los resultados obtenidos descarta casi la mitad del intervalo de incertidumbre, para iterar redefiniendo [a,b]). Es menos eficiente, segun la siguiente tabla comparativa de métodos de búsqueda.

Para 20 tentativas por aproximaciones sucesivas, la de Fibonacci gana por un orden de magnitud a la segunda mejor. Con mayor número, no hay diferencia práctica entre Fibonacci y relación áurea. 

    Evaluaciones  Fibonacci      Dicotómica      Relación áurea
        N          1/F_N        1/2^|_N/2_|      1/(1.618)^(N-1) 
    ============================================================
        5         0,125            0,25              0,146
       10         0,0112           0,0312            0,0131
       15         0,00101          0,00781           0,00118
       20         0,0000914        0,000976          0,000107 
       25         0,00000824       0,0002441         0,0000096 
    =============================================================

19.may.2000

Pulsar tecla de vuelta

Vuelta a Portada

Glosario de Carlos von der Becke.

1