Es sorprendente lo que puede dar de sí un golpe de inspiración extralaboral en horas de trabajo.
En mi caso, mi inspirador ha sido Richard Dawkins, leyendo uno de sus libros, "El relojero ciego". Este libro habla de evolución natural darwiniana, explicándola y justificándola con ejemplos de seres vivos, y respondiendo a críticas de otros autores a la evolución.
En uno de sus apartados, Dawkins se hizo un pequeño programa informático para jugar a ver la evolución de lo que llama "bioforma", o forma de vida, bastante simple. Él crea árboles fractales, donde los genes que definen el aspecto del árbol pueden variar ligeramente.
La idea es partir de una bioforma, y mostrar una posible descendencia en la que se ha variado un gen ligeramente. La selección natural, en este caso, no es tan natural, ya que el propio Dawkins elige en cada paso qué forma de vida sobrevive y puede dar descendencia. Partiendo de un mismo punto, consigue bioformas muy vistosas como ilustra en su libro.
La idea me pareció muy atractiva, y decidí hacer algo parecido. Dawkins tenía un ordenador de 64Kb con BASIC (uno de los primeros lenguajes de programación de alto nivel). Yo tengo un buen PC y el Mathematica. No creo que compense la cabeza y los conocimientos de Dawkins, pero se hace lo que se puede.
La ventaja del sistema utilizado por Dawkins es que se puede ver la bioforma "desarrollada", es decir, de forma gráfica. Es mucho más vistoso, sobretodo para enseñar a los amigos. Pero tiene una pega: hacer un algoritmo que elija una de las mutaciones es mucho más complicado, porque a ver qué parámetros eliges para que la bioforma sea "bonita". Dawkins las elegía manualmente una a una.
Así que yo he optado por algo más sencillo y automatizable. Mis bioformas en realidad son bionúmeros. Voy a suponer que cada ente es en realidad, una lista de números, como un vector. Se podría decir que son los genes, definidos por la secuencia numérica.
De esta forma, es más fácil elegir quién sobrevive. Basta con aplicar alguna función a cada mutación y escoger un hijo basándonos en un criterio matemático.
En mi caso, he empezado con una muy simple: la supervivencia viene dada por la suma de los valores absolutos de cada número del gen. Cuanto más baja sea esta suma, mejor sobrevive.
En este caso existiría un único gen "perfecto", formado todo por ceros. Además, cualquier mutación en un gen haría que la función de supervivencia subiera o bajara.
Por tanto el proceso es el que sigue:
- Se elige una secuencia de genes al azar, como una secuencia numérica de cualquier longitud (50 en mi caso), con valores entre -10 y 10.
- Se crean n hijos, cada uno con una mutación. La mutación consiste en sumar o restar un pequeño valor (entre 0 y 1) a uno cualquiera de sus genes (pero sólo a uno).
- De entre todos los hijos, calculamos su función de supervivencia y nos quedamos con el mejor.
- Se repite el proceso todas las veces que se quiera.
Si entre mis lectores hay algún ingeniero, físico, matemático, etc. un poco avispado, habrá visto lo que significa matemáticamente este planteamiento. Se trata de una optimización numérica. Hay un objetivo final, y partiendo de un punto cualquiera, se van haciendo pequeñas mejoras hasta acercarnos (o alcanzar) el objetivo. Así que en realidad he desarrollado un método de optimización numérica basado en algoritmos genéticos, más o menos, que en cualquier caso, no es nada nuevo. Pero lo que me interesa es el camino y no el objetivo.
Suponiendo 50 genes aleatorios entre -10 y 10, con 5 hijos por generación y escogiendo siempre el hijo más cerca a mi objetivo, se puede ver la evolución aquí:
El eje vertical está en escala logarítimica de tal forma que puede verse cómo se acerca la secuencia a la secuencia "ideal" (cuanto más baja es la línea, más cerca está). Converge hacia cierto valor pero no baja más. Ninguna secuencia de mutaciones se acerca, incluso entre los mejores hijos. Al final, hay mutaciones que se alejan.
Si se aumenta el número de hijos, al haber más donde elegir, la convergencia se hace más rápida y más estable, ya que será más fácil encontrar una mutación mejor.
Aquí puede verse en rojo la evolución con 25 hijos, y en azul la anterior, con 5 hijos por generación. Claramente, con 25 hijos se mejorarían los genes.
Otra característica es que me quedo siempre con el mejor hijo. Esto es un poco artificial, porque dudo mucho que en la evolución real las pequeñas diferencias entre hermanos hagan que sólo uno sobreviva. La selección natural determinará que en un conjunto muy grande de hermanos, los que estén mejor preparados tenderán a sobrevivir más, pero será una tendencia, no un absoluto.
Así que metí un pequeño cambio en el programa. En esta ocasión, el mejor hijo tendrá un 50% de probabilidades de ser elegido. El segundo mejor hijo un 30% y el tercero un 20%.
La cosa cambia un poco, como se puede ver:
En marrón se ve cómo evolucionan 5 hijos, pero sin seleccionarse siempre la mejor mutación, sólo alguna de las mejores.
Con la función de supervivencia que he cogido (la suma de los valores absolutos de cada gen), se tienen dos consecuencias. En primer lugar, como ya he comentado, existe una combinación de genes perfecta, y cualquier otra es peor, con lo que el objetivo final está claro. Por otro lado, cada gen es independiente del resto, ya que al final se suman todos.
Para intentar cambiar estos dos factores, probé con otra función objetivo: en primer lugar calculo la diferencia de un gen con el anterior, y después, sumo estas diferencias.
¿Cómo cambia la cosa? En esta situación, hay infinitas combinaciones de genes ideales. En concreto, cuando todos los genes
valen lo mismo, pero no necesariamente cero, simplemente todos iguales. En ese caso, las diferencias con el anterior valdrán cero, y la suma de las diferencias será también cero.
El otro factor que cambia es el de la independencia de los genes. Al considerarse la resta entre dos genes consecutivos, cuando varía un gen, cambian en realidad las relaciones entre dos genes. Puede darse la situación de que se sumen ambas diferencias (y quedaría el doble) o que se resten, con lo que el resultado no cambiaría, aunque cambie el gen. Espero no haberlo liado mucho :D. El caso es que algunos cambios van en buen camino, pero no son cuantificables hasta que se alcanza cierto valor.
Pero veamos cómo converge ahora una evolución cualquiera en esta situación:
En esta situación, converge peor. Más despacio (ahora hay 2000 generaciones en el gráfico en vez de 500) y más lejos del objetivo.
Pero además, se puede ver otra curiosidad. En el caso anterior, las series evolutivas convergían siempre a un valor mínimo, y se quedaban ahí oscilando un poco para arriba o para abajo. Pero en esta situación no sucede esto. Por ejemplo, aquí se pueden ver 5 evoluciones distintas a partir de los mismos genes iniciales:
No es que no se estabilice nunca, sino que se estabiliza en torno a valores distintos en cada evolución, dando saltos puntuales. Partiendo de un mismo origen, se llega a soluciones distintas.
Recuperando lo que he comentado anteriormente de que este modelo corresponde a una optimización numérica, se puede explicar este comportamiento.
En una optimización se pueden buscar mínimos locales o globales. En este caso, el algoritmo está buscando mínimos locales. Se puede ver el símil de buscar el punto más profundo en un cartón de una huevera. Si uno cambia su posición sobre la huevera sólo ligeramente (una mutación), podrá bajar o subir por la curva de la huevera. Al caer en un hoyo, nos estaremos moviendo todo el rato por el fondo de uno de los agujeros.
Sin embargo, es posible que haya otro agujero mejor en la huevera. Se necesitaría subir todo el agujero y caer en otro (una gran mutación, o una serie de malas mutaciones) para poder encontrarlo.
Curiosamente Dawkins comenta este caso como algo que realmente pasa en la vida real. Por ejemplo, los ojos de los pulpos y de los humanos son distintos. Ambos ojos evolucionaron de forma independiente, y dieron soluciones parecidas (a problemas similares, soluciones similares). Sin embargo los ojos de los pulpos son superiores a los nuestros en algunos aspectos.
Nuestros ojos podrían evolucionar hasta conseguir mejorar los aspectos en los que falla (respecto a los pulpos), pero eso requeriría un camino intermedio peor y no se llega a ese cambio ya que los cambios son pequeños, generación a generación, y los cambios a peor tienden a descartarse. Así que parece que no se van a cambiar.
Estoy abierto a cualquier sugerencia para nuevas funciones objetivos o nuevos cambios que alguien tenga curiosidad por probar.
No tengo problemas en dar el código fuente (algo caótico) para Mathematica 6.
Y hasta aquí la paja mental del mes (que es más o menos lo que actualizo el blog, una vez al mes).
Un saludo.
PD. Le agradecería a mi meneador anónimo un buen meneo, que lo voy necesitando ;)
