Según leo en barrapunto, Roger Penrose acaba de visitar España para presentar su nuevo libro "El Camino de la realidad" (Ed. Debate). Se trata de un libro de unas 1500 páginas en las que el autor presenta la historia completa de las matemáticas y la física, además de presentar algunas ideas personales como que antes del Big Bang hubo una fase previa. En elmundo.es publican una breve entrevista.
He ido esta misma tarde al Corte Inglés que hay debajo de mi lugar de trabajo a ver si lo tenían. Aún no había llegado, pero me sorprendió que en las estanterías de divulgación científica, donde habitualmente no hay nadie, estaban cuatro o cinco personas preguntando a una vendedora precisamente sobre este libro.
Cuando lo tenga en mi poder y pueda leerlo os pondré mis subjetivas opiniones.
Hoy, como el último día, os voy a poner otro pequeño ejercicio mental; pero en esta ocasión no permito ninguna fórmula en la solución, quiero respuestas razonadas. Se trata de un clásico que muchos conocereis (bueno, muchos es un decir, dado el número de lectores, jeje). ¡Vamos allá!
Somos el participante finalista de un concurso de televisión. Existen tres puertas numeradas como 1, 2 y 3. Detrás de una de ellas se oculta el Gran Premio, mientras que las otras dos están vacías. Inicialmente escogemos una de ellas, pero el presentador del programa, para darle emoción, abre una de las otras dos puertas y como era de esperar... está vacía.
Así que sólo queda nuestra puerta y una de las otras. El presentador con ánimo de ponernos incluso más nerviosos, nos da la oportunidad de cambiar nuestra puerta por la que queda sin abrir o quedarnos como estamos. La pregunta ahora es ¿Deberíamos cambiar, quedarnos con la que tenemos o realmente da igual?
Hoy os voy a proponer un curioso problema matemático que he leído hoy.
Supongamos que la Tierra es perfectamente esférica y lisa, y que tenemos una cuerda lo suficientemente larga como para rodear a la Tierra por el Ecuador, a nivel del suelo. Si quisiéramos rodearla igualmente por el Ecuador, pero a 1 metro de altura, ¿qué longitud habría que añadirle a la cuerda?
EDITADO: Teneis la solución en los comentarios gracias a Dardo.
Retomando el tema del otro día, que sirvió como introducción a los algoritmos genéticos, vamos a ver hoy por fin como funcionan realmente. Para ello resolveremos un problema muy sencillo pero muy ilustrativo del funcionamiento.
Tenemos una figura como la de la imagen de la derecha. Nuestro objetivo es colorearla usando únicamente tres colores (rojo, verde y azul) de forma que dos cuadrados contiguos no tengan el mismo color. Para esta figura en concreto existen 310 combinaciones posibles (aproximandamente 60 mil). Probar todas las combinaciones hasta encontrar con la mejor no supondría mucho reto a un ordenador de hoy en día, pero si en vez de tener 10 rectángulos la imagen estuviese compuesta por 200, el número de combinaciones posibles crecería hasta 3200, es decir, un 1 seguido de 95 ceros, lo cual haría que la exploración bruta de la mejor solución fuese impracticable.
Paso 1: Modelización matemática del problema
Como comentabamos el último día, un algoritmo genético se puede aplicar siempre las soluciones de un problema se puedan codificar numéricamente y siempre que dispongamos de un medio para decidir si una solución es mejor o peor que otra.
En el ejemplo del mapa podemos decir que una solución es mejor cuántas menos áreas del mismo color estén conectadas, así si todo el mapa fuera de un único color (el peor de los casos) el número de conexiones sería de 19, mientras que el óptimo buscado sería aquel con cero áreas conectadas compartiendo color. En principio no sabemos si esta configuración óptima existe, por lo que tras aplicar el algoritmo un número determinado de generaciones tendremos que quedarnos con la mejor solución encontrada.
Para codificar las posibles soluciones primero numeraremos las celdas de la imagen, tal como se muestra en la figura 2. Representaremos la solución como la secuencia de los colores siguiendo ese orden. Por ejemplo, para la imagen de la figura 3 tendriamos la siguiente secuencia: RVRAARVVRA. Su puntuación sería 3, ya que exiten tres pares de celdas conectadas con el mismo color.
El siguiente paso es codificar esos tres colores en binario. El hecho de que sean tres, y no dos o cuatro plantea un problema adicional, ya que para etiquetar en binario los tres colores hacen falta por lo menos 2 bits, pero con 2 bits obtenemos etiquetas sin adjudicar. Por ejemplo podriamos codificar como:
R = 00
V = 01
A = 10
?? = 11
Pero aun nos queda la etiqueta 11 sin aplicar a ningún color. Al diseñar un algoritmo genético es deseable que esto no ocurra, ya que algunos miembros generados aleatoriamente, cruzados o mutados podrían resultar inválidos. Por supuesto existen varias soluciones pero a la hora de codificar en binario nuestros "individuos" conviene que sean válidos con cualquier combinación de bits, y que todas las cadenas de bits tengan la misma longitud. El segundo problema no aparece en nuestro caso.
Como este artículo pretende ser más explicativo que riguroso, optaré por continuar usando los dígitos R, V y A en vez de cadenas binarias.
Paso 2: Configuración del algoritmo
Existen una serie de parámetros de configuración del algoritmo genético. Estos parámetros pueden tener valores muy dispersos dependiendo de a qué problema nos enfrentemos. La única forma de conseguir los correctos la da la experiencia y el prueba y error.
Paso 3: Ejecución del algoritmo. ¡Manos a la obra!
| Nº | Individuo | Puntuación |
|---|---|---|
| 1 | VAVRRRRRVA | 5 |
| 2 | VRARRVAVAA | 5 |
| 3 | VVRVARRRRA | 7 |
| 4 | RVVRAVAVVV | 8 |
| 5 | VVVRRVARRA | 9 |
| 6 | AAVAAAVARA | 11 |
Examinando la primera población, generada aleatoriamente, observamos que los individuos no son muy buenos; en el mejor de los casos se obtiene una puntuación de 5, esto es, una figura con 5 regiones conectadas (Figura 4).
Selección
Una vez que tenemos la población inicial, debemos escoger los mejores individuos para cruzarlos. En nuestro caso cogeremos a los tres mejores, pero podría ser cualquier numero de ellos. Al igual que en otros parámetros, coger un número excesivo poducirá una siguiente generación más variada, pero a la que le costará más converger.
Cruce
Para hacer el cruce se unen por parejas, y se mezclan la mitad de los bits de un individuo con la mitad del otro. La forma de escoger los bits que aporta cada uno puede cambiar de un algoritmo a otro. Nosotros cogeremos las 5 primeras letras de un progenitor y las 5 siguientes del otro, pero podríamos haber cogido, por ejemplo, las que ocupan una posición par de uno y las que ocupan posición impar del otro. Como nos interesa que la siguiente generación esté compuesta también de seis individuos cruzaremos los 3 individuos todos con todos por la derecha y por la izquierda, de forma que obtengamos la siguiente generación con el mismo número de individuos que la anterior.
1 + 2 = VAVRR RRRVA + VRARR VAVAA = VAVRRVAVAA
1 + 3 = VAVRR RRRVA + VVRVA RRRRA = VAVRRRRRRA
2 + 1 = VRARR VAVAA + VAVRR RRRVA = VRARRRRRVA
2 + 3 = VRARR VAVAA + VVRVA RRRRA = VRARRRRRRA
3 + 1 = VVRVA RRRRA + VAVRR RRRVA = VVRVARRRVA
3 + 2 = VVRVA RRRRA + VRARR VAVAA = VVRVAVAVAA
En la Figura 5 se puede apreciar gráficamente el resultado del primer cruce.
Mutación
VAVRRVAVAA --> (mutación) --> VVVRRVAVAA
VRARRRRRRA --> (mutación) --> VRARRRRRVA
Después de esto se junta de nuevo a los individuos mutados con la nueva generación y ya tenemos la siguiente generación, cuyas puntuaciones son las siguientes:
| Nº | Individuo | Puntuación |
|---|---|---|
| 1 | VVRVARRRVA | 5 |
| 2 | VVVRRVAVAA | 7 |
| 3 | VRARRRRRVA | 7 |
| 4 | VRARRRRRVA | 7 |
| 5 | VVRVAVAVAA | 7 |
| 6 | VAVRRRRRRA | 8 |
Vaya, parece que no hemos avanzado mucho. La selección, al igual que el la vida real, es un proceso largo y gradual, y es muy poco probable que una generación sea automáticamente superior a la anterior. Veremos que en algunas ocasiones las generaciones posteriores son peores que las anteriores, pero a la larga es cuando se obtienen resultados.
Una vez preparada la nueva generación, repetiremos de nuevo los pasos selección, cruce y mutación, para obtener la tercera generación, y así sucesivamente, hasta encontrar el individuo óptimo (si sabemos cual es) o hasta que creamos que el algoritmo ha convergido a una buena solución.
Paso 3: Resultados
Si seguimos ejecutando el algoritmo anterior, generación tras generación, finalmente llegaremos al mejor individuo en la generación número 26. Esta es la población de dicha generación:
| Nº | Individuo | Puntuación |
|---|---|---|
| 1 | VRARAVRVRA | 0 |
| 2 | VRA;RAVRRVA | 1 |
| 3 | VRARAVRRVA | 1 |
| 4 | VRARAVRRRA | 1 |
| 5 | VRARAVRRRA | 1 |
| 6 | VRARAVRRVA | 1 |
Como se puede observar, no sólo tenemos un individuo que cumple con nuestras espectativas, sino que la población en su conjunto ha mejorado notablemente. Además, los individuos son muy parecidos unos con otros, el algoritmo converge. En la Figura 6, se muestra al individuo de puntuación 0 que efectivamente no tiene todas las celdas contiguas del mismo color.
¿Qué ha ocurrido en el transcurso del resto de generaciones? Sería muy largo escribir aquí una a una todas las generaciones y los pasos seguidos, pero podemos hacernos una idea con la gráfica siguiente, en la que se muestra la puntuación del mejor individuo de cada generación y la puntuación media de los individuos de cada generación.
Si a alguien le interesa, para el experimento he desarrollado un programa en Java como implementación del algoritmo genético. Lo colgaré por aquí en los próximos días.
Muy a menudo uno se encuentra con problemas que no es capaz de resolver, o si es capaz, no dispone del tiempo suficiente. Tenemos por naturaleza la tendencia a buscar la mejor solución de todas, pero sin embargo a veces basta con conformarse con una lo suficientemente buena. Para esto surgieron los métodos heurísticos, y los algoritmos genéticos son uno de ellos.
Antes de explicar la heurística, la algoritmia y la genética, expondré un ejemplo sencillo. Supongamos que queremos comprarnos un coche y buscamos aquel que ofrezca la mejor calidad/precio. Sabemos distinguir claramente un coche más caro que otro, por su precio, y en cierta medida alguien entendido puede distinguir la calidad de dos coches en un buen número de detalles, la potencia, la capacidad, si tiene CD, el número de airbags, el ruido y muchos más.
Para resolver el problema damos un valor a cada una de estas características, de forma que podamos decidir matemáticamente si un coche es mejor que otro, según nuestro criterio (no todo el mundo tendría el mismo). Por ejemplo podríamos partir de cero y sumar 100 al valor por cada Airbag, 200 si incluye radio, 500 si trae CD y 900 si tiene MP3; podríamos sumar también los CV multiplicados por algún valor, etc. Para un coche dado, a su precio le llamamos P y a su calidad C. De esta forma, estamos buscando el coche con el mejor C/P (mayor calidad al menor precio). Acabamos de hacer un modelo matemático de nuestro problema.
Ahora lo único que tendríamos que hacer es observar todos los coches del mercado y quedarnos con aquel cuyo valor para C/P sea más alto . ¿Fácil, no? Pues supongamos que no tuviéramos tiempo para revisar todo el mercado automovilístico. Sólo tenemos tres días para elegir un coche y no podemos ver más de 6 coches al día. ¿Qué hacer? Una buena solución sería ver 18 coches cualesquiera en tres días y quedarnos con el mejor de ellos. No sería mala idea, pero quizá las haya mejores. Por ejemplo podríamos ver el primer día un coche de cada marca, de 6 marcas distintas, y anotar las dos marcas que han dado mejor C/P. El segundo día iríamos a ver 3 modelos de cada una de las dos mejores marcas, hacemos la media de los C/P de cada marca y anotamos la marca que mejor puntuación haya obtenido. Por último, el tercer día vamos a ver otros 6 nuevos modelos pero sólo de la mejor marca. Al final hemos visto 18 coches igualmente, y nos quedaremos con el que mejor C/P haya obtenido en cualquiera de los tres días. El resultado por lo general será mejor, aunque en algún caso particular aislado obtiviéramos un resultado peor que en el primer método.
Las dos posibilidades son métodos heurísticos. Esto es, métodos que intentan llegar a la mejor solución posible a través de la búsqueda y exploración de soluciones posibles. En la práctica se emplean cuando la complejidad del problema no permite resolverlo de una forma racional. La palabra heurística se deriva del griego euriskein, que significa hallar, encontrar.
Un algoritmo genético es un método heurístico que emplea toda la potencia de la teoría de la evolución para resolver problemas, obteniendo una solución más próxima a la mejor, cuando no podemos explorar todas las posibles soluciones para llegar a la mejor. Ahora viene lo entretenido del artículo. ¿Cómo se lleva a cabo un algoritmo genético? ¿Qué clases de problemas resuelve?
Primero contestaré a la segunda pregunta. Un algoritmo genético es capaz de resolver cualquier problema cuyas soluciones puedan codificarse numéricamente, y en los que podamos decidir, entre dos posibles soluciones, cual de las dos es mejor. Asombrosamente esto podría aplicarse para cualquier problema que se nos pudiese ocurrir, sólo que no es tan sencillo codificar según que tipo de soluciones (como por ejemplo las distintas posibles soluciones a la pregunta ¿Qué pieza musical clásica acompaña mejor en una cena romántica?).
Una vez que tengamos modelizado el problema se aplica el algoritmo genético. Existen numerosas variantes de los algoritmos genéticos y formas de configurarlos. El funcionamiento de un algoritmo genético consiste, al igual que en la naturaleza, en aplicar una y otra vez estos pasos tan naturales:
Después se repite un número determinado de veces la selección, cruce y mutación. Tras un número lo suficientemente grande de iteraciones podremos estar bastante seguros de que la población final será mejor que inicial, o al menos así ocurre en la naturaleza darwiniana.
El próximo día explicaré más en detalle en qué consisten estos pasos y la magia que hay tras ellos. Creo que por hoy ya os he aburrido bastante
Lejos de ser mínimamente riguroso, hoy voy a escribir sobre el vacío. Un breve resumen histórico y algunas impresiones personales sobre lo que considero uno de los elementos más poéticos del universo.
¿Qué es el vacío? Es difícil de definir, aunque se trata de un concepto realmente simple. Si le preguntamos a nuestra amiga la Wikipedia, nos dice algo así como:
En Física se denomina así al espacio donde hay ausencia de materia. Surgiría como consecuencia de la disgregación de ésta, compuesta por unidades existenciales solapadas entre sí que experimentan un impulso de separación, o voluntad hacia su ser pleno; si no consiguen liberarse de ese solapamiento se debe al empuje de las unidades adyacentes (el cual, en su conjunto, es responsable de la expansión del Universo, más allá de los límites de la existencia); y no por una supuesta fuerza atractiva. Por extensión se suelen denominar vacío, también, los espacios cuya densidad de aire y partículas es muy baja, como, por ejemplo, el espacio interestelar o vacío interestelar.
A mí se me antoja una definición un poco fría, aunque bastante exacta. Sin embargo, la idea de vacío es bastante reciente, aunque cueste creerlo; ocurre algo parecido a la gravedad, que ahora nos parece un concepto muy simple, pero que hasta que en el siglo XVII a Newton no le cayera la famosa manzana en la cabeza, nadie se había dado cuenta.
Empezando por los antiguos griegos, el vacío, o "no ser", para ellos no sólo no existía, sino que su ausencia les causaba auténticos quebraderos de cabeza. El "no ser" por definición y como su propio nombre indica, no podía ser (existir). Si todo era "ser", ¿como era posible el movimiento? Llevado a la vida cotidiana viene a ser algo como un vagón de metro, que cuanto más lleno va, más nos cuesta movernos. Si suponemos que el vagón está completamente lleno, ¿cómo podríamos apenas pestañear?
Mucho más tarde Descartes y sus contemporáneos se enfrentaban a un problema parecido. Para ellos la materia era continua y tenía extensión. Lo primero significa que no pensaban que estuviera formada por átomos, sino que formaba un todo homogéneo que ocupaba el espacio. Un trozo de arcilla, por ejemplo, podría partirse en dos una y otra vez con un cuchillo infinitamente afilado. Por muy pequeño que fuera el trozo, siempre se podría cortar en dos o más trozos menores. La segunda caracterista, la extensión, significa que el espacio mismo está hecho de materia. El volumen es materia, y sin materia no tendría sentido hablar de un metro cúbico y un litro. Las propias dimensiones existen porque la materia las ocupa. Para Descartes, existía un espacio no ocupado por la materia, pero sólo en las matemáticas
Algo más tarde, Newton ya sugería una idea de vacío parecida a la que tenemos ahora, separado de la materia. El vacío ocuparía la mayor parte del espacio, mientras que la materia sólo una pequeña parte de él. Aunque no todos sus contemporáneos pensaban del mismo modo y había gran debate sobre el tema.
Ya en el sigo XIX, cuando se descubrió la naturaleza ondulatoria de la luz, el concepto de vacío se comenzó a tambalear. La luz es una onda electromagnética. Podemos ver ondas formarse en el agua o sentir las ondas sonoras que hacen vibrar el aire hasta nuestros oídos; también podemos ver ondas en la cuerda de un arco de tiro o en las cuerdas de una guitarra. Las olas son ondas que se forman en el mar y las vibraciones de los terremotos también son ondas. Todas las ondas tienen algo en común: se transmiten a través de un medio; es mas, se podría decir que las ondas son deformaciones rítmicas del propio medio. No tendría sentido pensar en las olas del mar sin agua, en un terremoto sin tierra o en una cuerda vibrante sin cuerda. Si la luz era una onda, necesitaría un medio para propagarse.
Es entonces cuando surge la idea del éter. El éter debía ser increíblemente denso para que la luz pudiera vibrar a la velocidad que lo hace. Se tendría que mover a velocidad constante y podría tenerse en cuenta como punto de referencia absoluto del movimiento, lo que supondría una ruptura con la relatividad de Galileo. El éter era una idea para salir del paso ante el problema de la luz, y planteaba más problemas de los que solucionaba. Por ejemplo, si el éter era tan denso, tendría que producir un rozamiento sobre la Tierra (y los otros planetas), haciendo que ésta llegase a detenerse, pero eso no parecía ocurrir.
La idea del éter se vino abajo con la llegada de Albert Einstein. El científico alemán asumió que si el éter era indetectable de ninguna manera y no interaccionaba con nada, podíamos prescindir de él y asumir que la luz tiene la capacidad de viajar por el vacío. Una idea muy positivista pero que fue aceptada por la mayoría. La luz se sustenta por sí misma y es su propio medio.
La idea del vacío clásico de Newton, o algo muy parecido, se mantuvo aún unas décadas más, pero en los últimos años del siglo XX, y hasta la actualidad, con la llegada de la teoría cuántica y el modelo estándar, el concepto de vacío ha cambiado considerablemente.
Actualmente se piensa que el vacío es un hervor continuo de partículas y antipartículas que se generan espontáneamente y se vuelven a aniquilar un instante después. Recordemos que por cada partícula fundamental existe una antipartícula igual, pero de signo contrario. Cuando una partícula y su antipartícula se encuentran, se aniquilan mutuamente dando lugar a energía. Entonces, en el vacío, se están generando y destruyendo continuamente pares de partícula y antipartícula. ¿De dónde surge semejante idea? No parece algo intuitivo o real, pero existen varias teorías que la respaldan; la principal razón, a mi entender, es el principio de incertidumbre de Heisenberg. Este principio nos dice que no se puede conocer a ciencia cierta la cantidad de energía que hay en un punto determinado del espacio. Si tomamos el vacío en el concepto clásico, la temperatura del vacío sería el cero absoluto, o lo que es lo mismo, la ausencia total de energía. Esto contradice el principio de Heisenberg y por lo tanto ¡incluso el vacío debe tener una temperatura superior al cero absoluto! y para que eso ocurra debe contener partículas, que se crean y se destruyen constantemente.
La idea de un vacío burbujeante de partículas me parece casi tan poética como la de un vacío completamente vacío, y en parte le da algo de razón a aquellos primeros griegos que penaban que el "no ser" no podía ser. Sin embargo, me cuesta creer que sea un modelo definitivo. Por ejemplo, ¿qué existe entre esas partículas virtuales? Quizá el espacio esté realmente cuantizado como lo están la materia y la energía, y sea una futura base para una nueva teoría del vacío.
Enlaces de interés
Hoy vamos a ver un objeto muy peculiar. Se trata de la cinta de Möbius, que recibe el nombre de su descubridor, el astrónomo del siglo XIX A.F. Möbius.
Su construcción es increiblemente sencilla: se coge una tira de papel y se pega un extremo con el otro, haciendo un giro de forma que una cara quede pegada en la opuesta, como se muestra en la foto. Esta aberración geométrica tiene algunas propiedades bastante curiosas:
Para empezar, tiene una sóla cara. La mejor forma de comprobarlo es intentar pintar una cara de un color y la otra de otro. Cuando hayas terminado de pintar la primera cara, ¡descubrirás que toda la cinta está pintada de ese color!
Otra propiedad es que es "no orientable". Esto quiere decir que si tomamos una figura formada por dos flechas perpendiculares y la desplazamos por la cinta, al volver al punto de partida se habrá invertido la flecha horizontal, apuntando al lado opuesto. Algunos físicos sugieren que el universo podría tener una propiedad de este tipo, de forma que un zurdo que recorriese todo el universo hasta volver al punto de partida, se convertiría en diestro, al igual que un diestro en zurdo. Es más, ¡Tendría el corazón en el lado derecho!
La última propiedad, y para mí la más interesante, es que si coges unas tijeras y comienzas a cortar la cinta a lo largo por el centro, cuando vuelvas al punto de partida no tendrás dos cintas, sino una sola, la mitad de ancha y el doble de larga, y también de Möbius. Es más, si en vez de recortar por el centro, recortamos por un tercio de la cinta, ¡lo que obtendremos serán dos cintas enlazadas! Haz la prueba tú mismo
Ningún blog que se precie puede comenzar con un mensaje que no sea de bienvenida.
Siempre he sido de los que opinan que hay demasiados blog en el mundo. Demasiada
gente con muchas ganas de escribir y nada interesante que decir. Demasiados blog y sitios web que no aportan nada que no se pudiese conseguir en otros sitios antes, o simplemente que no aportan nada. Si te has dado por aludido te he de dar mi más sincera enhorabuena, eres uno más entre la multitud. Yo también abrí una vez una web, una con foro inclusive, que no tarde mucho en cerrar al ver que no interesaba a nadie.
Por supuesto no pienso que este blog vaya a ser muy distinto a muchos otros que hay sobre cualquier otro tema... o sobre ninguno en absoluto, o todos a la vez. Sólo espero que las personas que por algún avatar del destino tenga la desgracia de caer en estas páginas, no se lleven un mal sabor de boca, una sensación de haber estado perdiendo el tiempo. Mi objetivo principal es que resulte una página de entretenimiento, pero un entretenimiento activo, que haga pensar al lector.
Los temas a tratar serán variados, pero en un mismo entorno, irán desde pequeños acertijos, a las grandes cuestiones de la humanidad; pasando por la física, las matemáticas, la biología, la psicología, e incluso un poco, muy poquito, de filosofía. Temas de los que quizás nunca hayas oído hablar, de los que oíste en la escuela y no llegaste a comprender su profundidad, y temas que siempre te han rondado la cabeza, pero nunca les has prestado mucha atención.
Por último, y espero que este sea el mensaje más largo de todos los que llegue a escribir, sólo anotar que el nombre del blog, está en consonancia directa con el libro "La nueva mente del emperador" de Roger Penrose. Personalmente fue el primer libro de divulgación científica que leí y, a pesar de haber leído bastantes desde aquel, ninguno me ha gustado tanto.
Bueno, después de esta "pequeña" introducción de bienvenida, espero que haya quedado alguien que no haya salido corriendo después de leer palabras como física, matemáticas o filosofía.
Un saludo,
WinterN
