Búsqueda local en espacios continuos

Búsqueda local en espacios continuos

En el Capítulo 2, explicamos la diferencia entre entornos discretos y continuos, señalando que la mayor parte de los entornos del mundo real son continuos. Aún ninguno de los algoritmos descritos puede manejar espacios de estados continuos, £la función sucesor en la mayor parte de casos devuelve infinitamente muchos estados! Esta sección proporciona una muy breve introducción a técnicas de búsqueda local para encontrar soluciones óptimas en espacios continuos. La literatura sobre este tema es enorme; muchas de las técnicas básicas se originaron en el siglo xvn, después del desarrollo de cálculo Newton y Leibniz13. Encontraremos usos para estas técnicas en varios lugares del libro, incluso en los capítulos sobre aprendizaje, visión y robótica. En resumen, cualquier cosa que trata con el mundo real.

Comencemos con un ejemplo. Supongamos que queremos colocar tres nuevos aeropuertos en cualquier lugar de Rumania, de forma tal que la suma de las distancias al cuadrado de cada ciudad sobre el mapa (Figura 3.2) a su aeropuerto más cercano sea mínima Entonces el espacio de estados está definido por las coordenadas de los aeropuertos:

(*,, y¡), {x2, y2), y (x¡, y ). Es un espacio seis-dimensional, también decimos que los estados están definidos por seis variables (en general, los estados están definidos por un vector «-dimensional de variables, x). Moverse sobre este espacio se corresponde a movimientos de uno o varios de los aeropuertos sobre el mapa La función objetivo f(xv yu x2, y2, x2, y j es relativamente fácil calcularla para cualquier estado particular una vez que tenemos las ciudades más cercanas, pero bastante complicado anotar en general.

Un modo de evitar problemas continuos es simplemente discretizar la vecindad de cada estado. Por ejemplo, podemos movernos sólo sobre un aeropuerto a la vez, en la dirección x o y en una cantidad fija ±& Con seis variables, nos da 12 sucesores para cada estado. Podemos aplicar entonces cualquiera de los algoritmos de búsqueda local descritos anteriormente. Uno puede aplicar también la ascensión de colinas estocástica y el temple simulado directamente, sin discretizar el espacio. Estos algoritmos eligen a los sucesores aleatoriamente, que pueden hacerse por la generación de vectores aleatorios de longitud 5.

Hay muchos métodos que intentan usar el gp-adiorfe del paisaje para encontrar un máximo. El gradiente de la función objetivo es un vector V/que nos da la magnitud y la dirección de la inclinación más escarpada. Para nuestro problema, tenemos