Jugando al Melate con algoritmos genéticos

Hoy, gracias a la ciencia, hemos podido resolver un número enorme de problemas que nos afectan. Hemos entendido por ejemplo, algunas características de los sismos y por ello hemos podido tomar acciones para protegernos. Y esto es sólo una muestra porque la ciencia en general ha trabajado en un sinfín de frentes y se han resuelto problemas que permiten que la vida sea más fácil de vivirla.

Hay problemas, sin embargo, que no aceptan una solución definitiva y que en el mejor de los casos sólo podemos hallar una solución aproximadamente buena. Este tipo de problemas en teoría de la computación se les llaman NP (nondeterministic polynomial time) y su importancia reside en que hay muchos problemas de búsqueda y optimización en donde no hay una solución final. Lo más que podemos tener son aproximaciones. Por ejemplo, el problema del agente viajero, el cual trata de responder a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿Cuál es la ruta más corta posible que el agente viajero puede usar para visitar cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen? No existe solución completa y final a este problema y quien lo encuentre bien podría hacer mucho dinero, pues su solución podría permitir implementarla en las empresas de mensajería y así optimizar sus viajes.  

Otro problema NP es el de la mochila, el cual dice: Dado un conjunto de artículos, cada uno con un peso y un valor, determine qué artículos incluir en la colección para que el peso total sea menor o igual a un límite dado y el valor total sea lo más grande posible. Este tipo de problemas suelen plantearse de muchas maneras, por ejemplo: imagine que tiene una mochila y encuentra una cueva con una serie de objetos de metales preciosos. El problema es que sólo puede llevarse lo que pueda entrar en su mochila. ¿Cómo hacer para llevarse el máximo valor posible (dadas las condiciones iniciales)? Es otro problema que no tiene una solución final y definitiva. La ciencia ha buscado incansablemente maneras de aproximarse al máximo en este particular problema.

Y el tema de la mochila es una mera analogía a muchos problemas de máximos y mínimos que encontramos en el mundo real. De hecho, pensando en esto, el problema de la mochila puede ser usado para intentar hallar los números del Melate a los cuales apostar para tener más chances de ganar. De hecho, en el artículo pasado hablamos de un software que escribí para hallar los números del Melate que aparecen con más frecuencia que otros. La razón para que no salgan con la misma probabilidad esos números es que el azar real, en la tómbola que se usa, hace que quizás –sólo quizás– las diferencias mínimas en el peso de las bolitas (décimas o centésimas de gramos), bien podría hacer que la probabilidad no fuese exactamente de cada número 1/56. Puede ser también que todo esto sea una construcción mental y que simplemente no hay suficientes concursos realizados para que se cumpla la ley de los grandes números, la cual es en realidad un teorema de la estadística que nos dice que el promedio de una muestra (pequeña), tomada al azar de un universo (de gran tamaño), tenderá a estar cerca de la media de dicho universo. 

Como sea, el problema de la mochila puede programarse como un algoritmo genético, un sistema ideado por el biólogo teórico John Holland en los años 70s del siglo pasado, en donde se realizan una serie de pasos en un programa a partir de la evolución biológica y su base genética. Estos algoritmos hacen evolucionar una población de individuos (simulando sus condiciones a través de “cromososmas y genes”), sometiéndola a acciones aleatorias, semejantes a las que actúan en la evolución biológica (mutaciones y recombinaciones genéticas), así como también a una selección. Se usa una función de “aptitud” (fitness) para establecer qué individuos son mejores que otros. Esto se hace ejecutando repetitivamente el algoritmo genético hasta que se llega a una buena solución o cuando se exceden los recursos de la máquina que está haciendo el proceso. De acuerdo con esto, se decide cuáles son los individuos más adaptados, que sobreviven, y cuáles son los menos aptos, que son descartados.

Entonces, si tenemos el cálculo del porcentaje de veces que salen los números en el histórico del Melate, bien podemos pensar que este porcentaje habla del éxito de esos números para “sobrevivir”, para ser los más “aptos”. Si consideramos que tenemos que elegir 7 números (donde el último es el adicional), basándonos en el porcentaje en el que han salido en los anteriores 1777 concursos, bien podemos pensar que es el equivalente a elegir los objetos más valiosos hallados en una cueva para meterlos en nuestra mochila y llevarnos la mayor riqueza posible dadas las condiciones iniciales planteadas.

Hay en Internet muchos programas y aplicaciones que juegan con el algoritmo genético. Desde luego que dada las condiciones azarosas del concurso del Melate, diferentes programas pueden dar diferentes soluciones. Sin embargo, para ayudarles un poco a mis cuatro lectores, les pondré la lista de números (columna izquierda) y el porcentaje calculado del número de sorteos en el que ha salido cada número (columna derecha):

49 13.77379619

29 13.77379619

54 13.77379619

52 13.71780515

5 13.54983203

50 13.43784994

12 13.3818589

56 13.3818589

43 13.32586786

21 13.26987682

19 13.21388578

40 13.21388578

1 13.04591265

18 13.04591265

15 12.87793953

26 12.87793953

10 12.76595745

24 12.76595745

45 12.76595745

25 12.65397536

33 12.65397536

2 12.59798432

13 12.59798432

17 12.59798432

28 12.59798432

44 12.59798432

48 12.59798432

51 12.59798432

36 12.54199328

3 12.4300112

39 12.4300112

6 12.37402016

32 12.31802912

42 12.31802912

16 12.26203807

46 12.20604703

55 12.20604703

20 12.09406495

8 11.92609183

30 11.92609183

37 11.92609183

47 11.92609183

4 1.87010078

14 11.87010078

34 11.87010078

35 11.87010078

53 11.87010078

38 11.81410974

27 11.7581187

23 11.70212766

9 11.64613662

22 11.64613662

31 11.59014558

7 11.53415454

11     11.53415454

41 11.42217245

Ahora hay que hacer la tarea de buscar qué aplicaciones de algoritmos genéticos pueden hallar en Internet y poner los datos como el sistema que hayan encontrado les exija para que pueda procesarlos. Para darles una idea de los resultados que puede entregar el algoritmo genético, yo usé el programa de Gary Darby, Branch and Bound Algorithm, que aparece en su página www.DelhiForFun.org. Este fue el resultado que el sistema halló: 49, 29, 54, 52, 5, 50 y 12. Ojo, no sé cuál es el número adicional de todos estos y además, considerando los porcentajes, el 12 podría cambiarse por el 56, por ejemplo.

Cabe decir que de nuevo, este trabajo no garantiza que se hará el lector millonario de la noche a la mañana. Simplemente les dará una aproximación que quizás sea mejor que apostar azarosamente a los siete números (o quizás no). Mi sugerencia es que si consideran que todo esto tiene algún sentido y quieren probar suerte, háganlo sistemáticamente cada semana. Es muy, pero muy poco probable, que se ganen el Melate con una primera apuesta al sistema. Si me preguntan, yo apostaría esos mismos números semana a semana por varios meses. En cualquier caso me deslindo de cualquier responsabilidad mía sobre las acciones, apuestas y gastos que tomen los lectores de este artículo. Yo solamente intento usar las herramientas de la ciencia para poder jugar con más chances que si se hace azarosamente. ¡Qué conste!

La gran idea del algoritmo genético (y un libro gratis)

John Henry Holland fue un científico norteamericano, profesor de psicología, ingeniería eléctrica y de computación. Fue el pionero de lo que a la postre se llamaría "algoritmos genéticos". Holland, desde pequeño, se preguntó cómo es que los organismos se hacían cada vez mejores. Muchos años después, ya teniendo un doctorado, salió con la idea de algo que eventualmente se llamó el "algoritmo genético", partiendo de la base de que todo ocurre por las interacciones locales entre individuos, y entre estos lo que les rodea. Probablemente un libro que tuvo una gran influencia en el científico fue "La teoría genética de la selección natural", del evolucionista R.A. Fischer. Ahí Holland aprendió que la evolución es una forma de adaptación mucho más poderosa que el aprendizaje simple y a partir de ahí, desarrolló programas para demostrar su idea.

Holland se planteó dos objetivos:

• Imitar de alguna manera los procesos de adaptación de los sistemas naturales
• Diseñar programas, sistemas que podríamos llamara artificiales, que tengan los mecanismos de los sistemas naturales estudiados

El algoritmo genético busca hacer evolucionar una población de individuos, sometiéndola a acciones azarosas, parecidas a las que actúan en la evolución biológica (mutaciones y recombinaciones genéticas), así como también a una selección de acuerdo con algún criterio -probablemente la parte más difícil- en función del cual se decide qué individuos son los mejor adaptados, que sobreviven, y cuáles los menos aptos, que son descartados.

De acuerdo a la Wikipedia:

Un algoritmo genético puede presentar diversas variaciones, dependiendo de cómo se aplican los operadores genéticos (cruzamiento, mutación), de cómo se realiza la selección y de cómo se decide el reemplazo de los individuos para formar la nueva población. En general, el pseudocódigo consiste de los siguientes pasos:

• Inicialización: Se genera aleatoriamente la población inicial, que está constituida por un conjunto de cromosomas los cuales representan las posibles soluciones del problema. En caso de no hacerlo aleatoriamente, es importante garantizar que dentro de la población inicial, se tenga la diversidad estructural de estas soluciones para tener una representación de la mayor parte de la población posible o al menos evitar la convergencia prematura.
• Evaluación: A cada uno de los cromosomas de esta población se aplicará la función de aptitud para saber cómo de "buena" es la solución que se está codificando.
• Condición de término: El AG se deberá detener cuando se alcance la solución óptima, pero ésta generalmente se desconoce, por lo que se deben utilizar otros criterios de detención. Normalmente se usan dos criterios: correr el AG un número máximo de iteraciones (generaciones) o detenerlo cuando no haya cambios en la población. Mientras no se cumpla la condición de término se hace lo siguiente:

• Selección Después de saber la aptitud de cada cromosoma se procede a elegir los cromosomas que serán cruzados en la siguiente generación. Los cromosomas con mejor aptitud tienen mayor probabilidad de ser seleccionados.
• Recombinación o Cruzamiento La recombinación es el principal operador genético, representa la reproducción sexual, opera sobre dos cromosomas a la vez para generar dos descendientes donde se combinan las características de ambos cromosomas padres.
• Mutación modifica al azar parte del cromosoma de los individuos, y permite alcanzar zonas del espacio de búsqueda que no estaban cubiertas por los individuos de la población actual.
• Reemplazo una vez aplicados los operadores genéticos, se seleccionan los mejores individuos para conformar la población de la generación siguiente

John Hollander

Pero ¿cómo aplicar esto en el mundo real de un programa? El siguiente ejemplo, aunque trivial, nos puede ayudar a entender esto.

Dados los dígitos del 0 al 9, y los operadores +,-,* y /, hallar una secuencia que represente un número objetivo. >Los operadores se aplicarán de izquierda a derecha como se van leyendo.

Por ejemplo, dado el número objetivo 23, la secuencia 6+5*4/2+1 sería una posible solución. Si se busca el 75.5, entonces 5/2+9*7-5 sería una posible solución. Nótese que los operadores se aplican de izquierda a derecha y no usando precedencia de operadores.

Teniendo el problema definido, pasamos a codificarlo. Como queremos hacerlo a partir de un algoritmo genético, nuestros cromosomas serán una cadena de bits. Podemos representar los números y sus operadores así:

0: 0000
1: 0001
2: 0010
3: 0011
4: 0100
5: 0101
6: 0110
7: 0111
8: 1000
9: 1001
+: 1010
-: 1011
*: 1100
/: 1101

Los genes 1110 y 1111 no se usan y serán ignorados si son detectados en el algoritmo.

Para la solución '6+5*4/2+1' podemos representar esto como:

0110 1010 0101 1100 0100 1101 0010 1010 0001
6 + 5 * 4 / 2 + 1

Estos son los genes que forman el cromosoma 011010100101110001001101001010100001, que es la solución.

Cabe decir que si hallamos la cadena:

0010 0010 1010 1110 1011 0111 0010
2 2 + ?? - 7 2

estaríamos realmente representando la operación 2 + 7.

Llegamos pues a la parte más difícil, la de hallar una función de aptitud (fitness), la cual se acerque lo más posible al resultado que queremos (el número objetivo). En este proyecto usaremos una puntuación de aptitud que es inversamente proporcional a la diferencia entre la solución y el valor decodificado que representa el cromosoma hallado. Si por ejemplo, el número objetivo es 42, el cromosoma 011010100101110001001101001010100001 tiene una puntuación de aptitud de 1/(42-23) o 1/19. Si la solución se adhiere al valor objetivo, podrías encontrar algo como 1/(42-42), lo cual nos daría una división entre cero. Podemos desde luego considerar este caso para no caer en un error y que el sistema se detenga.

Otro punto importante es el de tener que usar todos los genes en el cromosoma que dé el resultado. Así, si el número objetivo es 42, + 6 * 7 / 2 no da el resultado correcto aunque contenga la subcadena 6 * 7.

Para entender las ideas, no hay mejor idea que intentarlas, siguiendo la máxima adjudicada a Benjamín Franklin: Si me lo dices lo olvido, si me lo enseñas lo recuerdo, si me involucras aprendo. Sin embargo, si se desea experimentar, se puede descargar el código en C, Java o Delphi y ver cómo fue programado (ver referencias).

Como un bono a quien haya llegado hasta este punto, hace tiempo escribí un libro sobre Vida Artificial, recursión y temas afines. En algún momento se explora el algoritmo genético. El libro se puede comprar en formato Kindle por menos de 6 dólares y si lo hacen, se los agradecería. Sin embargo, lo pongo a disposición gratuita por siete días a los primeros 100 lectores que quieran descargarlo, lo que ocurra primero. Este es el enlace.

Referencias:

AI-Junkie 
Wikipedia 
Código en Delphi 
Código en Java 
Código en C