4.5 Espacios de Busqueda

Cuando se resuelve un problema, se busca la mejor solución entre un conjunto de posibles soluciones. Al conjunto de todas las posibles soluciones a un problema concreto se llama espacio de búsqueda. Cada punto en el espacio de búsqueda representa una posible solución. Cada posible solución se le puede asociar un fitness o un valor que indicará cómo de buena es la solución para el problema. Un algoritmo genético (AG) devolverá la mejor solución de entre todas las posibles que tenga en un momento dado.

Entonces parece que buscar una solución se reduce a buscar un valor extremo (mínimo o máximo) en el espacio de búsqueda. A veces el espacio de búsqueda puede ser bien definido, pero en la mayoría de las ocasiones sólo se conocen algunos puntos en el espacio de búsqueda. Cuando se usa un AG las posibles soluciones generan otras a medida que el genético evoluciona.

La resolución de un problema puede expresarse como la busqueda del extremo de una función Aquí resolvemos ese problema, este es un algorítmo genético que calcula el máximo de una función. La gráfica representa un espacio de busqueda y las líneas verticales son posibles soluciones. La línea roja es el mejor individuo de la población y las verdes el resto.

Pulsa el botón Empezar para que el genético comience, el botón Parar detendrá la ejecución, en el botón Paso a Paso se ejecutará un único paso creando una nueva población y el botón Reiniciar creará una nueva población inicial.

El problema estriba en que la búsqueda puede ser muy compleja por diversas razones, como por ejemplo no saber dónde buscar una solución o dónde empezar a buscarla. Existen muchos métodos que se usan para buscar una solución válida, pero no necesariamente obtienen la mejor solución. Algunos de estos métodos son los algoritmos de escalada, backtracking o vuelta atrás, búsqueda a ciegas y los algoritmos genéticos. Las soluciones que encuentran estos tipos de búsqueda suelen ser buenas soluciones, pero no siempre encuentran la óptima.