Inteligencia artificial IV: Algoritmos genéticos

Hay una clase de problemas en los que la dificultad consiste en encontrar la mejor solución. El ejemplo típico es el problema del viajante: si tenemos un conjunto de ciudades y una serie de caminos que llevan de unas a otras, el problema consiste en indicarle a un viajante cual es el camino más corto que pasa por todas las ciudades.

Matemáticamente se ha estudiado muchísimo, y no se ha encontrado un algoritmo que resuleva este problema en un tiempo razonable. Este es un ejemplo de problema en el que se puede aplicar un algoritmo genético.

Los algoritmos genéticos no son más que una estrategia de programación que intenta imitar la selección natural. Cada generación es un conjunto de soluciones (no óptimas, ya que entonces tendríamos la solución deseada). Se empieza con unas cuantas soluciones del problema aleatorias (en el caso del problema del viajante, rutas escogidas de cualquier manera). Entonces, se obtiene la siguiente generación a partir de los mejores individuos (es decir, combinando las rutas más cortas obtendríamos otras creadas a partir de ellas). Los mejores individuos se combinan muchas veces. Los peores, se utilizan poco o se descartan.

Además, para calcular las siguientes generaciones, también se introducen mutaciones (es decir, cambios inesperados y normalmente bastante malos en cuanto a encontrar la solución) que sirven para no estancarse en soluciones que parecen óptimas pero que en realidad no lo son.

A base de calcular unas cuantas generaciones, se llega a soluciones cada vez mejores. A pesar de que es muy difícil resolver el problema exactamente por este método, las soluciones obtenidas son bastante buenas. Este método presenta la ventaja de que es muy general ya que se puede aplicar a una gran cantidad de problemas.

Como es más fácil entender las cosas viéndolas, puede que este vídeo sea muy clarificador:

(Las opciones de la derecha son diversos tipos de algoritmos genéticos distintos, con más o menos mutaciones).

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *