La teoría de la evolución en informática

¿Puede un algoritmo mejorarse a sí mismo?

Bueno, es una pregunta realmente difícil de responder. Ya vimos el concepto de redes neuronales en el post de Cómo aprenden las máquinas, las cuales son excelentes para reconocer patrones y son capaces de entrenarse a sí mismas para dar mejores resultados.

En este caso vamos a conocer otro tipo de sistemas que se utilizan para solucionar problemas que tienen muchas posibles soluciones pero no todas son igual de buenas. Hablamos de los algoritmos genéticos los cuales son muy utilizados para resolver problemas de optimización. Estos algoritmos no son especialmente nuevos, pues llevan desde los años 70 siendo objeto de discusión, pero son particularmente interesantes, pues se basan en el concepto de la evolución biológica comunmente conocida como selección natural.

Seguro que Charles Darwin estaría orgulloso de estos algoritmos.

— Bien, entonces… ¿estos algoritmos pueden mejorarse a sí mismos?

Más o menos. No es el algoritmo en sí el que se cambia, pero sí que permite mejorar la solución proporcionada conforme avanza el tiempo.

En la naturaleza y según el mecanismo de la selección natural los seres vivos se adaptan al entorno gracias a las características heredadas de sus progenitores, y dentro de los individuos de una especie en una generación determinada las probabilidades de supervivencia son proporcionales al rendimiento de esas características.

El funcionamiento de estos algoritmos pretende simular ese comportamiento. Enfrentaremos a nuestro algoritmo genético a un escenario para el que no ha sido preparado. Buscaremos entonces el mejor individuo (como analogía de la mejor solución) que sepa desenvolverse eficazmente en este escenario. Para esto partiremos de una selección aleatoria de individuos, los pondremos a prueba en este escenario y una vez obtengamos los resultados seleccionaremos un conjunto de ellos, donde los que han mostrado mejores resultados tienen más probabilidades de ser elegidos. Combinaremos los individuos seleccionados mediante las técnicas de cruce y mutación, dando lugar a una nueva generación de individuos, los cuales pueden ser potencialmente mejores a la anterior generación. Repetiremos este proceso tantas veces como necesitemos.

Para poder realizar esto necesitaremos lo siguiente:

• Un cromosoma: La representación de cada individuo en forma de cadena, donde cada símbolo de esta cadena se llama gen. Si la cadena es de dígitos binarios lo llamaremos genotipo.
• Una función de fitness: Cómo evaluar el rendimiento de una solución.
• Los operadores genéticos: Cómo realizar la selección, el cruce y la mutación de los individuos.

Nótese que, dada la naturaleza probabilística de estos algoritmos, habrá individuos que se repitan y otros que no aparezcan. Así pues, no tendremos asegurada la solución más óptima para un problema, pero sí que obtendremos una solución bastante buena en un momento determinado. Las mejoras que nos proporciona cada generación siguen un incremento logarítmico, de forma que llegaremos a un punto en el que necesitaremos muchas iteraciones para lograr una pequeña mejora de la solución. El coste de este proceso dependerá en su mayoría del tiempo que se tarde en probar y evaluar cada solución.

Posiblemente estés un poco confuso con todo esto, así que lo mejor para asimilarlo es mediante un ejemplo. El ejemplo que he seleccionado es un simulador donde buscaremos encontrar la criatura que se mueva más rápido y por tanto logre una mayor distancia en un tiempo determinado. Te dejo las 4 partes aquí (están en inglés):

Parte 1

Parte 2

Parte 3

Parte 4

Puedes probarlo tú mismo aquí:

Tienes el código escrito en Processing disponible en la misma página.

Además, por si te parece poco, estos algoritmos pueden combinarse con las redes neuronales, permitiendo enfrentar el mismo algoritmo genético a escenarios diferentes y obtener mejores resultados a la hora de mejorar los pesos de una red neuronal. Podemos ver esto en un ejemplo, utilizando un algoritmo genético y una red neuronal para hacer que un ordenador aprenda a jugar al mítico dinosaurio de Chrome cuando no hay conexión a Internet. En este caso el escenario es diferente porque en cada ejecución de este juego la distribución del nivel es diferente. También nos ofrece una sencilla explicación sobre redes neuronales y algoritmos genéticos, no tiene desperdicio:

Está en portugués, pero para lo que no se entienda tiene subtítulos en inglés.

Por supuesto, también tienes el código disponible aquí .

Fascinante, ¿verdad?