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!

¿Qué números jugar en el Melate para ganar?

Los concursos de azar en general -si efectivamente no hay influencia externa- son un ejemplo perfecto de lo que es la probabilidad. El ser humano se ha preguntado muchas veces sobre qué tan probable es que ocurra un evento en particular, por ejemplo, el tirar una moneda al aire y ver si cae de un lado o el otro. Y se supone que en el mundo de los grandes números, cuando se hacen millones y millones de intentos, la probabilidad de que caiga una moneda de un lado o del otro es del 50%.

Pero esto es el mundo ideal. Hoy, hablando con un par de estudiantes de mi curso de Proceso Digital de Imágenes, discutíamos una idea para hacer más eficiente el algoritmo de búsqueda de la mejor imagen para colocarla en el fotomosaico que tienen que crear. Un alumno de China, Yuguo (yo le digo "Hugo"), junto con Diego, en donde este último halló una idea interesante usando árboles k-dimensionales (), hablábamos de qué enfoque había que usar para la tarea mencionada. A Yuguo se le ocurrió usar un método en donde no encuentra necesariamente la mejor imagen en el fotomosaico, sino un aproximado. Su comentario fue: si hay en un salón tres alumnos de más de 1.80 m. ¿por qué tengo que revisar a cada uno de ellos en su estatura? Digamos que eso -como piensa mi estudiante- es perder el tiempo. Entonces nos indicó a Diego y a mí que busca "el más probable", lo que significa -de acuerdo al algoritmo que parece seguir- tiene alguna manera de buscar en una zona del espacio de búsqueda, ignorando lo demás. Así, encuentra una imagen aceptablemente buena aunque como el mismo Yuguo dijo, "no es la imagen óptima". Le pedí pues que documentara su algoritmo para estudiarlo.

Pues bien, todo lo anterior fue el preámbulo para cuando Yuguo me comentó: "yo creo que la probabilidad está en la cabeza nada más". Y en parte tiene razón. La realidad es que la probabilidad de que caiga una moneda en un intento es exactamente igual a la que tendrá aunque se hayan tirado antes mil millones de veces la moneda. Vamos, no importa que haya salido el mismo lado de la moneda en mil millones de tiros (poco probable, muy poco), el siguiente intento tiene la misma probabilidad de salir "sol" o "águila" (cara o cruz, pues).

Y entonces hablamos de los concursos donde el azar existe. Comentamos el problema del Melate y les comenté que la cantidad de concursos llega a apenas a menos de 4000. Estos no son los grandes números en donde, si es un concurso totalmente azaroso, el porcentaje de que salga un número es 1/56. Así de simple. Pero resulta que hay muchos números que han salido con frecuencias diversas. Este es el resultado que me entrega el software:

Frecuencias/Números (de mayor a menor) con 7 números.

507 veces - 32
505 veces - 12
503 veces - 37
497 veces - 13
495 veces - 20
492 veces - 5
488 veces - 36
487 veces - 16,33
485 veces - 2,7
484 veces - 15,28
483 veces - 11,19,25
482 veces - 30
481 veces - 1,18
475 veces - 14,29
473 veces - 9
471 veces - 8
470 veces - 6
469 veces - 17
466 veces - 3,27
464 veces - 4,39
463 veces - 21,38
462 veces - 22,24
458 veces - 26
456 veces - 31,34
451 veces - 10
444 veces - 35
432 veces - 23
406 veces - 40
385 veces - 43
380 veces - 44
373 veces - 42
350 veces - 41
229 veces - 45
228 veces - 47
212 veces - 46
192 veces - 49
189 veces - 48
175 veces - 51
173 veces - 50
161 veces - 56
154 veces - 52
151 veces - 55
150 veces - 54
135 veces - 53

Si consideramos esta tabla, veremos que números como el 32, el 12, el 37, el 13, el 20 y el 5 han salido con mucho más frecuencia que el 53, 54, 55, 52, 51, 48, 10 entre otros.

¿Por qué ocurre esto? Hay dos posibles razones: la primera es que la ley de la probabilidad, en este caso 1/56, se aplica a los grandes números, a hacer estos sorteos millones y millones de veces y aún así, no sé qué signifique exactamente "los grandes números", es decir, en qué momento llego a esa cifra... La segunda es que efectivamente, como Yuguo me decía, la probabilidad es un constructo humano y es una observación que queremos suponer que en general es cierta, aunque esto ocurre en el mundo ideal y no en el mundo real, en el que vivimos y en donde la diferencia de pesos (aunque sean décimas de gramo) de las bolitas que se ponen en el sorteo, puede hacer la diferencia que muestre las razones por qué el 10 sale una tercera parte de lo que sale el 12, por ejemplo.

Entonces, si hay que establecer un criterio, si pensamos que en estos "grandes números", las probabilidades eventualmente se igualarán, podemos pensar que menos de 4000 concursos (desde 1984), no caen ni remotamente en esta ley de los grandes números y por ende, pensar que los números que no han salido ahora sí saldrán con más frecuencia, es simplemente creer que estamos en el mundo ideal de la probabilidad.

Así pues, ¿quiere ganar el Melate? Desde luego que tendrá que tener un golpe de suerte porque como indicamos al principio del artículo, si es al azar realmente cada número debería tener 1/56 de posibilidades de salir (aunque pensándolo bien, el primer número tiene 1/56 chances de salir, el segundo 1/55, el tercero 1/54, etcétera). Pero en términos generales, los concursos ocurren en el mundo real y aunque sí, los números por salir son "igualmente probables" (en el mundo ideal), en el real se notan preferencias debido a la "imperfección de la realidad". Consecuentemente, la mejor apuesta debe ser a los números más frecuentes.

Desde luego -y antes de que alguien venga a reclamarle que no ganó el Melate- esto es meramente una especulación que busca ser educada, es decir, basándose en hechos. Y vuelvo a elaborar: las pelotitas del concurso real pueden no tener estrictamente el mismo peso y una diferencia de décimas de gramo entre una y otra pudiese hacer que una esfera saliese más veces que las otras, aunque evidentemente, no puedo afirmar que esto ocurra por esta razón.

¿Sirve para algo orar? (segunda parte)

Hace unos días se generó una alarma por la llegada del huracán "Patricia" el cual, se decía, era el huracán más fuerte de toda la historia de la humanidad. Patricia iba a pasar por el territorio mexicano y el gobierno estaba haciendo todo lo posible por tomar las previsiones necesarias. Se reunió el gabinete para discutir las medidas. Se usaron las redes sociales para informar a la población. Los noticieros no hablaban de otra cosa y como fondo tenía unas imágenes de un huracán gigantesco y devastador. En Facebook se publicaban imágenes de la Estación Espacial Internacional que parecían impactantes. Bueno, la cosa parecía gravísima.

Pero nada pasó. Patricia tocó tierra y por arte de magia se degrado a tormenta tropical. Las peores previsiones fueron aparentemente infundadas. Esto, desafortunadamente, dio pie a dudar de la promoción mediática con la que "inundó" el gobierno sus acciones. Hubo el "sospechosismo" ya habitual en el mexicano y se empezó a pensar que ni era tan grave el problema y que tampoco era Patricia el huracán más mortífero de la historia.

Enrique Peña Nieto destacó la fe del pueblo de México en sí mismo y su unidad, que se unió con cadenas de oraciones e incluso solidaridad, con creación espontánea de centros de acopio para afrontar la llegada del huracán Patricia, que en buena medida permitieron superar esta crisis.

Y de inmediato surgieron las críticas, totalmente justificadas, pues asignarle a la divinidad el habernos salvado, previas cadenas de oraciones, es regresar al oscurantismo. Para empezar, si existiese tal divinidad, ¿por qué nos mandó un huracán? Pero más allá de eso, habría que tomar una actitud más científica. ¿Pueden las cadenas de oraciones hacer un cambio? ¿Qué hay de quienes rezan para ayudar a quien está enfermo, o a quien tienen que intervenir quirúrgicamente? ¿Será posible que las oraciones produzcan una diferencia?

Si nos remitimos a la mecánica cuántica, sabemos que el observar un experimento afecta los resultados de éste. Y si esto pasa en partículas subatómicas, ¿no pasará en los eventos cotidianos? ¿Cómo podríamos probar que esto ocurre o bien que es un simple mito que se ha eternizado de generación en generación?

No soy el primero que ha pensado en esto. Hay muchos estudios que demuestran que no hay efecto en el rezar o al menos, siquiera un pequeño efecto. Por ejemplo, en 14 estudios del 2006 se concluyó que no hubo un efecto discernible. Sin embargo, en el 2007, en 7 de 17 estudios tuvieron un efecto pequeño pero significativo en esto de orar por alguien. No obstante esto, se hizo notar que los estudios más rigurosos no mostraron nada significativo en sus resultados.

Hay estudios que datan de 1872, donde el científico victoriano Francis Galton hizo el primer análisis estadístico. No halló que rezar sirviese para algo. Más de 100 años después, Byrd -en 1988- usó a 393 pacientes de la unidad del área de coronarias del Hospital General de San Francisco. Los hallazgos de Byrd pueden resumirse en que parece haber un efecto y que éste es benéfico para los enfermos. La reacción de la comunidad científica fue mixta. Algunos dudaron de su rigor para el trabajo realizado. Otros concluyeron que esto no tenía ningún pero.

Harris, en 1999, decidió replicar los hallazgos de Byrd pero en condiciones experimentales más estrictas, donde notó que los resultados del este investigador no fueron totalmente ciegos y concluyó, después de un trabajo muy cuidadoso, que no era posible repetir los resultados de Byrd y que además, los resultados favorables podían explicarse por probabilidad.

Hay otros estudios, pero el consenso general indica que no parece servir de nada orar. Sin embargo, considerando esto, decidí realizar mi propio experimento. Escribí un programa simple que busca hallar si el concentrarse en un número pudiese cambiar el resultado de la elección azarosa del 0 al 9 en la computadora. El mecanismo funciona así:

• Se le pide un número al usuario (del 0 al 9)
• Se le da un tiempo determinado para que se concentre (rece), pidiendo que ese número es el que eligirá la computadora al azar
• Al terminarse el tiempo, el sistema arroja el número elegido al azar y lo despliega (en rojo si la elección del usuario no fue la de la máquina y en verde si el usuario acertó al número elegido al azar)
• El sistema lleva una bitácora de experimentos realizados para estudiarse posteriormente.

Si existe una correlación entre el número que pide el usuario que salga contra el que salió, podríamos pensar que hay un elemento más allá de la simple estadística. En términos de probabilidad, un usuario podría acertar 1 de cada 10 intentos. Quizás acertar 2 de 10 sea relativamente significativo pero 6 o 7 de 10 veces sería ya para pensarse.

¿Podría ser este un experimento para probar si sirve orar? No estoy muy seguro. Claramente el algoritmo pseudo-azaroso de la máquina podría ser el primer pero. No obstante esto, podemos empezar a probar si de alguna manera algún usuario se concentra lo suficiente y logra vencer a la probabilidad del evento.

A quien le interese el programa, puede pedírmelo a morsa@la-morsa.com y se lo mandaré por correo electrónico.


Referencias:

Wikipedia 

Problema lógico probabilístico

Imaginen que están en el programa de Chabelo y han llegado hasta la catafixia. El conductor, amigo de todos los niños, les muestra tres puertas, 1, 2 y 3. Y les indica que en una de ellas hay un buen premio, pero que en las otras dos no hay nada. Les pide Chabelo que digan qué puerta eligen. Si somos sensatos, es claro que da lo mismo elegir cualquiera de ellas. Así, tenemos 1/3 de probabilidades de obtener el premio. Supongamos que elegimos la 1. Entonces Chabelo decide abrir la puerta 3 y mostrarnos que ahí no estaba el premio y entonces nos pregunta a bocajarro: ¿Quieres cambiar de elección, o te quedas con la elección original de la puerta 1? ¿Cuál será la mejor decisión?

Esto es un tema que tiene que ver con teoría de juegos y analizando la respuesta que dan a este tema en el libro "Teoría de juegos. Una introducción matemática a la toma de decisiones", de Amster, Pablo y Juan Pablo Pinasco, FONDO DE CULTURA ECONÓMICA (FCE 2014), me parece que es errónea. Los autores indican que cambiar la elección de la puerta 1 a la 2 cuando el conductor lo propone, incrementa a 2/3 la probabilidad de ganar el premio. ¿Pero es así? El argumento parece simple. Si nos quedamos con la puerta 1, la primera elección, habremos decidido con una probabilidad de 1/3, pero si ya Chabelo destapó la puerta 3 y nosotros cambiamos, estamos con una probabilidad de obtener el premio que es de 2/3. O sea, la mejor decisión es hacer la catafixia de la puerta 1 por la puerta 2. En principio parece lógico lo que dicen los autores del libro, pero hagamos el siguiente cambio. Imaginemos que Chabelo nos pide que PENSEMOS, sin decirle, la elección de la puerta que queremos abrir. Y asumamos por un momento que Chabelo abre una puerta que no elegimos y que además, no tiene el premio. Si Chabelo nos pide cambiar la elección QUE PENSAMOS, estamos hablando sobre simplemente elegir entre dos puertas y la probabilidad de ganar es de 1/2, porque nunca le dijimos qué puerta habíamos elegido inicialmente.

Dicho de otra manera, ¿Por qué el hecho de informar sobre qué puerta elegimos cambia las probabilidades? Entiendo que originalmente la apuesta es de 1/3, pero al abrir la puerta 3 el conductor, y mostrarnos que no tiene nada, entonces la apuesta se reduce a acertar en un 50% Digamos que es un espejismo pensar que seguimos hablando de 1/3 por puerta, porque ya Chabelo nos hizo ver que en una no existe el premio y al eliminarla, ¿cuál es la probabilidad de que el premio esté en la puerta 1 o 2? 50%, no 1/3 o 2/3.

¿Pero ustedes qué opinan? ¡Que empiecen los juegos del hambre!... No, digo, la discusión...

Sólo por saber

Hoy, a eso de las 2:30 pm moría de hambre y decidí salir a comer cerca de casa. Como hoy no circula mi coche, caminé hasta el centro comercial, que queda a unos 7 kms (máximo) de donde vivo. En el trayecto, mientras discurría qué iba a zampar (las morsas no comen, zampan), si un kilo de pescado fresco o quizás una buena ración de moluscos, hallé en el piso doscientos pesos. Sí, creo que esta es la segunda vez que me encuentro dinero en el piso. Hace como un año encontré cuatrocientos pesos después de correr una carrera de 10 kms en la UNAM, en un parque ecológico que está relativamente cerca. Con eso compramos Pilar y yo un pastel para comer como postre ese día.

Considerando que fue un acto de suerte, pensé que quizás debiese continuar la racha y me compré un "melático", es decir, aposté al sorteo MeLate del domingo, con números totalmente al azar. A ver si la racha de fortuna sigue o se detuvo después de hacerme de los doscientos pesos que pagaron las tres bolsas de camarones que de rigor una morsa come por día.

Quiero imaginar que la mayoría de nosotros alguna vez se ha encontrado dinero. Pero... ¿es así? ¿Qué me dicen mis cuatro fieles lectores?