9.2: Búsqueda de algoritmos

La figura\(\PageIndex{1}\) muestra una porción de las tierras baldías de Dakota del Sur, un paisaje árido que incluye muchas crestas estrechas formadas a través de la erosión. Supongamos que desea subir al punto más alto de esta cresta. Debido a que el camino más corto hasta la cima no es obvio, podrías adoptar la siguiente regla simple: mira a tu alrededor y da un paso en la dirección que tenga el mayor cambio de elevación, para luego repetir hasta que no sea posible más paso. La ruta que sigues es el resultado de una búsqueda sistemática que utiliza un algoritmo de búsqueda. Por supuesto que hay tantas rutas posibles como puntos de partida, tres ejemplos de los cuales se muestran en la Figura\(\PageIndex{1}\). Tenga en cuenta que algunas rutas no alcanzan el punto más alto, lo que llamamos el óptimo global. En cambio, muchas rutas terminan en un óptimo local desde el cual es imposible seguir moviéndose.

Figura\(\PageIndex{1}\). Encontrar el punto más alto en una cresta usando un algoritmo de búsqueda es un método útil para ubicar el óptimo en una superficie de respuesta. El camino en el extremo derecho alcanza el punto más alto, o el óptimo global. Los otros dos caminos llegan al optima local. Los algoritmos de búsqueda tienen nombres: el que aquí se describe es el método de ascenso más empinado.

Podemos utilizar un algoritmo de búsqueda sistemática para localizar la respuesta óptima. Comenzamos por seleccionar un conjunto inicial de niveles de factores y medir la respuesta. A continuación, aplicamos las reglas de nuestro algoritmo de búsqueda para determinar un nuevo conjunto de niveles factoriales y medir su respuesta, continuando con este proceso hasta alcanzar una respuesta óptima. Antes de considerar dos algoritmos de búsqueda comunes, consideremos cómo evaluamos un algoritmo de búsqueda.

Eficacia y Eficiencia

Un algoritmo de búsqueda se caracteriza por su efectividad y su eficiencia. Para ser efectivo, un algoritmo de búsqueda debe encontrar el óptimo global de la superficie de respuesta, o al menos llegar a un punto cercano al óptimo global. Un algoritmo de búsqueda puede no encontrar el óptimo global por varias razones, incluyendo un algoritmo mal diseñado, incertidumbre en la medición de la respuesta y la presencia de optima local. Consideremos cada uno de estos problemas potenciales.

Un algoritmo mal diseñado puede terminar prematuramente la búsqueda antes de que alcance el óptimo global de la superficie de respuesta. Como se muestra en la Figura\(\PageIndex{2}\), cuando subes a una cresta que se inclina hacia el noreste, es probable que un algoritmo la falle si limita tus pasos solo hacia el norte, sur, este u oeste. Un algoritmo que no pueda responder a un cambio en la dirección del ascenso más empinado no es un algoritmo efectivo.

Figura\(\PageIndex{2}\). Ejemplo que muestra cómo un algoritmo de búsqueda mal diseñado, limitado a moverse solo hacia el norte, sur, este u oeste, puede fallar en encontrar el óptimo global de una superficie de respuesta.

Todas las mediciones contienen incertidumbre, o ruido, que afecta nuestra capacidad para caracterizar la señal subyacente. Cuando el ruido es mayor que el cambio local en la señal, entonces es probable que un algoritmo de búsqueda termine antes de que alcance el óptimo global. La figura\(\PageIndex{3}\), que proporciona una vista diferente de la figura\(\PageIndex{1}\), nos muestra que el terreno relativamente plano que conduce a la cresta está muy desgastado y muy desigual. Debido a que la variación en la altura local (el ruido) excede la pendiente (la señal), nuestro algoritmo de búsqueda termina la primera vez que nos acercamos a una superficie local menos erosionada que es más alta que las superficies inmediatamente circundantes.

Figura\(\PageIndex{3}\). Otra vista de la cresta en la Figura\(\PageIndex{1}\) que muestra el terreno desgastado que conduce a la cresta. La varilla amarilla en la parte inferior de la figura, que marca el rastro, es de unos 18 pulgadas de altura.

Finalmente, una superficie de respuesta puede contener varios óptimos locales, solo uno de los cuales es el óptimo global. Si comenzamos la búsqueda cerca de un óptimo local, es posible que nuestro algoritmo de búsqueda nunca llegue al óptimo global. La cresta en Figura\(\PageIndex{1}\), por ejemplo, tiene muchos picos. Sólo aquellas búsquedas que comiencen en el extremo derecho llegarán al punto más alto de la cresta. Idealmente, un algoritmo de búsqueda debería alcanzar el óptimo global independientemente de dónde comience.

Un algoritmo de búsqueda siempre alcanza un óptimo. Nuestro problema, por supuesto, es que no sabemos si es el óptimo global. Un método para evaluar la efectividad de un algoritmo de búsqueda es utilizar varios conjuntos de niveles de factores iniciales, encontrar la respuesta óptima para cada uno y comparar los resultados. Si llegamos a o cerca de la misma respuesta óptima después de comenzar desde ubicaciones muy diferentes en la superficie de respuesta, entonces estamos más seguros de que es el óptimo global.

La eficiencia es la segunda característica deseable de un algoritmo de búsqueda. Un algoritmo eficiente se mueve desde el conjunto inicial de niveles de factores a la respuesta óptima en los pocos pasos posibles. Al buscar el punto más alto en la cresta en la Figura\(\PageIndex{3}\), podemos aumentar la velocidad a la que nos acercamos al óptimo dando pasos más grandes. Sin embargo, si el tamaño del paso es demasiado grande, la diferencia entre el óptimo experimental y el óptimo verdadero puede ser inaceptablemente grande. Una solución es ajustar el tamaño del paso durante la búsqueda, usando pasos más grandes al principio y pasos más pequeños a medida que nos acercamos al óptimo global.