La leyenda de los "predictores" perfectos

En una mañana cualquiera, aún no habría podido ponerme a trabajar en serio, pero aquél día sólo llevaba media hora sentado en mi mesa y había podido leer todos los emails pendientes, contestarlos, planificarme la jornada e incluso había empezado a trabajar en el código del programa que tenía entre manos. Un día normal mi compañera Sofía me habría entretenido contándome alguna batallita nocturna tras haber derribado alguna web "enemiga" (defacement lo llama ella), pero esa mañana estaba especialmente silenciosa y, pese a ir de alternativa por la vida, ahí estaba con su ipod enchufado a sus orejas. Gaznápiro, mi jefe, había pasado por delante de nuestras mesas como una exhalación, con la cabeza gacha y con un montón de papeles bajo el brazo. Mal presagio sin duda. Es la calma que precede a la tempestad. Cuando Gaznápiro llega tan temprano al trabajo acompañado de tantos papeles (ya podría comprarse una carpeta el hombre) es señal de que tiene que preparar una reunión con la plana mayor, de la que suele salir bastante cabreado. Evidentemente, tiene que desfogar con alguien y parece que, además de informáticos, somos buenos esparrings, porque nada más salir de esas reuniones la emprende, metafóricamente hablando, con nosotros.
Pero lo más extraño de todo era que el Sr. Lego aún no había aparecido por allí, y eso que suele ser el primero en llegar cada mañana. Puntual como un reloj suizo. Fue pensar en ello y aparecer por la puerta de la oficina. Traía el hombre mala cara esa mañana y unas ojeras bastante pronunciadas.
Buenos días Sr. Lego ¿mala noche? -dije.
Pues sí -respondió- he dormido regular. El crío, que anda con dolores de estómago y se pasa la noche llora que te llora, el pobre. Y encima escuchando la radio en el coche me entero de que han bajado las acciones de Microsol, justo ahora que acababa de comprar algunas por probar esto de la bolsa. Afortunadamente no invertí mucho, pero mira que tengo mala pata. Ojalá hubiera algún programa que te dijera en qué empresa hay que invertir para ganar dinero.
¡Ojalá! -dije. Pero me temo que todavía no lo han inventado. Aun así hay bastante gente investigando en ese campo, y por lo que sé, algunos programas no lo hacen mucho peor que brokers profesionales.
Evidentemente, acababa de captar la atención del Sr. Lego porque había dejado de mirar los valóres de bolsa para mirarme a mí.
Bueno -continué- el otro día leí algo sobre que habían desarrollado un programa que usando algoritmos genéticos era capaz de hacer mejor papel que la mayoría de los inversores humanos en el mercado de futuros.
¿Algoritmos genéticos? -preguntó el Sr. Lego.
Sí, es una de las ramas de la Inteligencia Artificial que se está explorando con más interés en la actualidad, y además tiene un campo de aplicación bastante amplio.
Pues no tenía ni idea -reconoció el Sr. Lego. ¿Cómo funcionan los algoritmos genéticos?
Verá usted Sr. Lego, no es fácil explicar cómo funcionan en pocas palabras, pero le voy a contar la leyenda de los "predictores" perfectos y verá como lo entiende rápidamente.

Cuenta la leyenda que en un mundo paralelo al nuestro vivían unos seres llamados predictores. En ese mundo todo era digital y estaba formado por ceros y unos. Todo se comportaba de forma binaria. Encendido/apagado, activo/inactivo, abierto/cerrado, etc… Los predictores no eran una excepción, y se alimentaban de cifras binarias. La comida de los predictores llegaba en forma de impulsos desde no se sabe dónde, el caso es que cada segundo llegaba un impulso que los predictores debían asimilar y digerir. Esos impulsos podían corresponder a un cero o un uno y siempre llegaban formando el mismo patrón que se repetía una y otra vez: 1101001011.
El Sr. Lego me estaba mirando con cara de incredulidad como pensando "No puede estar contándome semejante tontería", así que me apresuré a continuar antes de que me cortara en seco.
El problema es que los predictores necesitaban emitir una señal idéntica a la que recibían para poder digerirla. Los predictores emitían cada segundo, de forma sincronizada con la llegada de comida, una señal. La señal que emitían los predictores estaba codificada en su ADN en forma de secuencia fija de 10 bits. Cada predictor tenía una secuencia diferente, por lo que algunos, dependiendo del grado de similitud entre la secuencia de su ADN y la del patrón de llegada de comida se alimentaban mejor que otros.
Es decir, si un predictor tenía la secuencia 1001011001 en su ADN (recordemos que el patrón de llegada de alimentos es 1101001011), este comerá 7 de cada 10 veces que recibe comida, ya que hay 3 cifras que son diferentes entre los dos patrones.
O sea, que habrá predictores que estén mejor alimentados que otros ¿no? -dijo el Sr. Lego.
Efectivamente, son predictores mejor adaptados al mundo y, por lo tanto, con mayor probabilidad de sobrevivir y procrear.
El Sr. Lego sonrió: Así que los predictores también tienen hijos.
Realmente, Sr. Lego, son seres hermafroditas y muy promiscuos. Cada pocos segundos sienten la necesidad de unirse a otro predictor. Cada vez que dos predictores tienen relaciones tienen exactamente dos hijos (uno cada uno). Afortunadamente, cada vez que nace un predictor otro se desintegra y de esta forma la población se mantiene estable.
Qué bonita historia de Amor… -se mofó el Sr. Lego.

Verá Sr. Lego, lo más impresionante de esta historia es que tras algunas generaciones de predictores, el ADN de la mayoría de la población era capaz de predecir al 100% el patrón de llegada de alimento. Un hecho increíble. La población entera había evolucionado en su conjunto para adaptarse al medio. Es por ello que llamamos a esta historia la leyenda de los predictores perfectos.
Vaya, esto se parece bastante a la selección natural de la que hablaba Darwin -dijo el Sr. Lego. Sobreviven los más adaptados y con el tiempo los peor adaptados desaparecen.
Efectivamente, pero ¿sabe cuál es el mecanismo que consiguió que toda la población convergiera hacia un ADN perfecto? El secreto estaba en que los mejores adaptados también tenían más posibilidades de reproducirse y, por ende, de transmitir su ADN de mejor calidad.
Como la vida misma -bromeó el Sr. Lego. Lo que no entiendo es qué tiene que ver todo esto con un algoritmo capaz de predecir el comportamiento de la bolsa.

Bueno Sr. Lego, una vez establecida la analogía con el mundo de los predictores vamos a entrar en materia y a ver como funciona un algoritmo genético o evolutivo, como prefiero llamarlo.
En una población completa, llamaremos individuo a cada uno de sus componentes. Al ADN de cada predictor lo llamaremos gen y a cada bit que lo compone lo llamaremos cromosoma.
La población inicial tiene que ser lo suficientemente grande como para tener cierta riqueza genética, así que lo primero que hay que hacer es generar una población grande y con ADNs aleatorios.
Todo algoritmo genético consta de cuatro fases: Selección, cruce, mutación y extinción.

La selección consiste en escoger los mejores individuos para que procreen. Sin embargo, en pro de la diversidad genética no conviene quedarse estrictamente con los mejores. Es preferible asignar una probabilidad de ser seleccionado a cada individuo según su nivel de adaptación. Por ejemplo, un predictor que acierta 8 veces con su secuencia de ADN tiene que tener un 50% más de probabilidad de ser seleccionado para procrear que un predictor con 4 aciertos.
En cualquier caso, un predictor con mal ADN tiene que tener alguna probabilidad de procrear, aunque sea baja, ya que uno de sus hijos podría aportar una gran mejora a la población.
El nivel de adaptación al medio de cada predictor nos lo dará la llamada función de adaptación, que es una función que nos indica cómo de bien adaptado está el individuo. En el caso de los predictores, la función de adaptación nos devolvería el número de bits del ADN del predictor que coinciden con el patrón de llegada de comida.

En la fase de cruce es donde procrean los individuos seleccionados dando lugar a dos hijos. Se llama fase de cruce porque se seleccionan dos individuos y se entrecruzan sus ADNs. El proceso consiste en seleccionar de forma aleatoria un punto de corte del ADN y recombinarlos según el siguiente esquema. Supongamos que el punto de corte ha sido el tercer cromosoma.

Es decir, que del cruce de los padres (arriba) obtenemos dos nuevos hijos (abajo).

La tercera fase, llamada mutación, imita las mutaciones genéticas biológicas. Estas mutaciones no deben ser muy frecuentes (sobre un 1% de probabilidad de que se produzca, aunque se puede jugar con este valor). La mutación consiste en cambiar uno de los cromosomas de forma aleatoria en un gen, es decir, seleccionamos un cromosoma aleatoriamente y si es un cero lo cambiamos a un uno y si es un uno lo transformamos en un cero.

Finalmente nos queda la fase de extinción, donde elegiremos a los dos individuos peor adaptados para eliminarlos.
Todo el proceso se repite hasta que, o bien la población converge (aproximadamente un 95% de la población tiene un valor similar en la función de adaptación) o bien se alcanza un número máximo de iteraciones.
Este sería, grosso modo, el pseudocódigo de un algoritmo genético:

generar población inicial de forma aleatoria
  Mientras(no fin)
   Para tamaño(población)/2 hacer
      seleccionar dos individuos
      cruzar los dos individuos
      mutar con cierta probabilidad los nuevos individuos
      añadir los dos nuevos individuos a la población
      eliminar los dos peores individuos de la población
    fin para
  fin mientras
quedarse con la mejor solución

El señor lego estaba entusiasmado. Parecía haberlo entendido y ya estaba pensando en construir su propio modelo del mundo de los predictores. No tardó más de un par de horas en enviarme el siguiente código.

1. import math
2. import random
4. def initial_population(max_population, num_vars):
5.   # crear población inicial aleatoria
6.   population=[]
7.   for i in range(max_population):
8.     gene=[]
9.     for j in range(num_vars):
10.       if random.random()>0.5:
11.         gene.append(1)
12.       else:
13.         gene.append(0)
14.     population.append(gene[:])
15.   return population
17. def adaptation_function(gene, solution):
18.   # valor de adaptación del gen
19.   cont=0
20.   for i in range(len(gene)):
21.     if (gene[i]==solution[i]):
22.       cont=cont+1
23.   return cont
26. def evaluate_population(population, solution):
27.   # evalua todos los genes de la poblacion
28.   adaptation=[]
29.   for i in range(len(population)):
30.     adaptation.append(adaptation_function(population[i], solution))
31.   return adaptation
34. def selection(population, solution):
35.   adaptation=evaluate_population(population, solution)
36.   # suma de todas las puntuaciones
37.   total=0
38.   for i in range(len(adaptation)):
39.     total=total+adaptation[i]
40.   # escogemos dos elementos
41.   val1=random.randint(0,total)
42.   val2=random.randint(0,total)
43.   sum_sel=0
44.   for i in range(len(adaptation)):
45.     sum_sel=sum_sel+adaptation[i]
46.     if sum_sel>=val1:
47.       gene1=population[i]
48.       break
49.   sum_sel=0
50.   for i in range(len(adaptation)):
51.     sum_sel=sum_sel+adaptation[i]
52.     if sum_sel>=val2:
53.       gene2=population[i]
54.       break
55.   return gene1, gene2
57. def crossover(gene1, gene2):
58.   # cruza 2 genes y obtiene 2 descendientes
59.   new_gene1=[]
60.   new_gene2=[]
61.   cutpoint=random.randint(0, len(gene1))
62.   new_gene1[0:cutpoint]=gene1[0:cutpoint]
63.   new_gene1[cutpoint:]=gene2[cutpoint:]
64.   new_gene2[0:cutpoint]=gene2[0:cutpoint]
65.   new_gene2[cutpoint:]=gene1[cutpoint:]
66.   return new_gene1, new_gene2
68. def mutation(prob, gene):
69.   # muta un gen con una probabilidad prob.
70.   if random.random<prob:
71.     chromosome=random.randint(0, len(gene))
72.     if gene[chromosome]==0:
73.       gene[chromosome]=1
74.     else:
75.       gene[chromosome]=0
76.   return gene
78. def drop_worse_genes(population, solution):
79.   # elimina los dos peores genes
80.   adaptation=evaluate_population(population, solution)
81.   i=adaptation.index(min(adaptation))
82.   del population[i]
83.   del adaptation[i]
84.   i=adaptation.index(min(adaptation))
85.   del population[i]
86.   del adaptation[i]
88. def best_gene(population, solution):
89.   # devuelve el mejor gen de la poblacion
90.   adaptation=evaluate_population(population, solution)
91.   return population[adaptation.index(max(adaptation))]
93. def genetic_algorithm():
94.   max_iter=10
95.   max_population=50
96.   num_vars=10
97.   done=False
98.   solution = initial_population(1, num_vars)[0]
99.   population = initial_population(max_population, num_vars)
101.   iterations=0
102.   while not done:
103.     iterations=iterations+1
104.     for i in range((len(population))/2):
105.       gene1, gene2 = selection(population, solution)
106.       new_gene1, new_gene2 = crossover(gene1, gene2)
107.       new_gene1 = mutation(0.1, new_gene1)
108.       new_gene2 = mutation(0.1, new_gene2)
109.       population.append(new_gene1)
110.       population.append(new_gene2)
111.       drop_worse_genes(population, solution)
113.     if (max_iter<iterations):
114.       done=True
116.   print "Solucion: "+str(solution)
117.   best = best_gene(population, solution)
118.   return best, adaptation_function(best, solution)
122. if __name__ == "__main__":
123.   random.seed()
124.   best_gene = genetic_algorithm()
125.   print "Mejor gen encontrado: "+ str(best_gene[0])
126.   print "Funcion de adaptacion: "+str(best_gene[1])

Excelente Sr. Lego, veo que ha captado perfectamente la idea. De hecho sus predictores se convierten en predictores perfectos tras muy pocas iteraciones. ¡Enhorabuena!
Sí, y me parece que los predictores están muy felices, pero ¿valen para algo más los algoritmos genéticos?
Pues valen para muchas cosas. Son de hecho una metaheurística usada en búsquedas locales.
¿cómo? ¿metaqué? -preguntó el Sr. Lego.
Metaheurística. Es una forma de búsqueda heurística que podemos adaptar a casi cualquier problema que no tenga un algoritmo propio que lo resuelva. Una especie de comodín. Si no sabemos cómo afrontar la solución de un problema podemos usar una metaheurística como pueda ser un algoritmo genético.
Nos vale para problemas de optimización, diseño automático, aprendizaje, predicción, etc…
De hecho, si podemos representar el problema como ristras de números binarios, podemos usar el programa que acaba de hacer para resolverlo. Por ejemplo, si quisiéramos encontrar un valor entero para x que maximice la función f(x)=x^2, sólo tendríamos que crear una población de números binarios, que representarían a sus contrapartidas enteras, y usar como función de adaptación el valor de la propia función X^2 al evaluar el número representado por el ADN. En pocas iteraciones obtendríamos una población que convergería hacia ese valor de X que maximiza la función.
Interesante -dijo el señor Lego. ¿Pero sólo podemos tener genes cuyos cromosomas son ceros y unos?
Para nada -contesté. En el campo de la investigación suelen representarse así ya que con números binarios podemos codificar casi cualquier valor. De hecho, los cromosomas podrían ser cualquier cosa: números, letras, etc…
Eso sí, teniendo en cuenta que hay que elegir una función de adaptación acorde a la representación que usemos para la información.
Bueno, dijo el Sr. Lego. Voy a darle algunas vueltas a todo esto que me has contado para ver como hago un predictor perfecto para los valores de la bolsa.
Desafortunadamente (o afortunadamente) la bolsa no sigue patrones fijos, al menos aparentemente, aunque quizás dé usted con un predictor bursatil que le saque de esta empresa.
Ojalá, contestó el Sr. Lego. Aunque echaría de menos nuestras conversaciones.