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.
