La Singularidad Desnuda

Un universo impredecible de pensamientos y cavilaciones sobre ciencia, tecnología y otros conundros

Archivos de la categoría ‘Informática’

Demo del videojuego Chapas 2.0

Publicado por Carlos en Noviembre 10, 2009

Chapas 2.0 es un videojuego que traslada al ordenador uno de los deportes infantiles más cautivadores: las carreras de chapas. El desarrollo del juego está siendo realizado por la Universidad de Extremadura (con el compañero y amigo Paco Fernández -cuyo blog La Biblioteca de Alejandría es de lectura recomendada- al frente), la productora GLOW y el estudio Claroscuro Digital. Ésta es la última demo del juego que han publicado. Habrá que ir buscando un endurecedor digital de uñas, ya que se avecinan grandes carreras.

Publicado en Informática, Juegos | Etiquetado: , | Deja un Comentario »

Navaja de Occam vs Profesor de Occam

Publicado por Carlos en Octubre 23, 2009

Si Occam hubiera sabido que se iba a dar su nombre a un lenguaje para la programación de transputers probablemente habría apreciado que el camino puede ser tanto o más divertido que el destino (y sí, eventualmente podías necesitar un destornillador).

Jorge Cham / PhDComics

Jorge Cham / PhDComics

Publicado en Comic, Programación | Etiquetado: , , , | 1 comentario

Ruptura de simetría en redes de filamentos de actina produce una “cola cometaria” que impulsa a las células

Publicado por Carlos en Octubre 1, 2009

Las células de nuestro organismo son capaces de desplazarse en determinadas circunstancias: durante el desarrollo embrionario, durante la respuesta inmune, etc. Dicho desplazamiento (esto es, el desplazamiento por arrastre; hay otro tipo de desplazamiento basado en el impulso mecánico de flagelos, como en el caso de los espermatozoides) se realiza a través de redes de microfilamentos de actina, una proteína. Un artículo interesante describiendo este proceso es el titulado

realizado por Ananthakrishnan y Ehrlicher, y publicado en el International Journal of Biological Sciences, una revista de acceso abierto. Una de las cuestiones más interesantes en relación a este fenómeno es la ruptura de simetría que finalmente da lugar al movimiento. Cuando se observa el proceso se aprecia cómo se forma una envoltura simétrica de actina, y cómo esta envoltura se “rompe” de manera asimétrica, dando lugar a una especie de cola cometaria que propulsa a la célula, ya sea de manera suave o pulsante. Pulsando sobre la imagen inferior puede verse un vídeo ilustrativo.

Dayel et al. / PLoS Biology

Dayel et al. / PLoS Biology

El vídeo anterior está tomado de un artículo de Mark J. Dayel y colaboradores titulado

recién publicado en PLoS Biology. Dayel et al. han analizado mediante simulaciones y experimentos in vitro como pequeñas microesferas simétricas experimentan esta propulsión. En sus simulaciones una envoltura simétrica de filamentos de actina empieza a crecer en la superficie de la esera hasta que -al alcanzar un grosor del orden del radio de la esfera- se produce una rotura en dicha envoltura, y la esfera emerge de la misma dejando tras de sí una especie de cola cometaria de baja densidad. Hay diversos factores que entran en juego en el proceso: la mayor densidad de la red de filamentos junto a la superficie de la esfera que en el exterior de la envoltura provoca que sean más probables las microrroturas en esta última región. Una rotura de este tipo actúa de semilla para una rotura completa de la envoltura, debido a que la tensión de la red se realimenta positivamente en la zona de la fractura causando un fallo catastrófico en la misma, que se abre como las valvas de un molusco. Pulsando sobre la figura inferior puede verse un espectacular vídeo de una de las simulaciones.

Dayel et al. / PLoS Biology

Dayel et al. / PLoS Biology

Pueden verse más vídeos e ilustraciones en la página web de artículo. Realmente impresionante.

Publicado en Biología, Física, Informática | Etiquetado: , , , , , , | Deja un Comentario »

Prueba Voight-Kampff para parejas

Publicado por Carlos en Septiembre 7, 2009

Si tienes un contacto en cualquier red social o profesional y a la primera ocasión te menciona su marca favorita de cacao en polvo o qué detergente te deja el mejor blanco nuclear, caben dos posibilidades: que seas parte sin saberlo del reality show definitivo, o que tu interlocutor sea una IA comercial. En el primer caso la única posibilidad para averiguarlo es navegar hasta encontrar las paredes de biodomo, pero en el segundo la solución es mucho más simple: un captcha doble. Si Deckard lo hubiera sabido habría ahorrado mucho tiempo.

suspicion

Xkcd.com - Randall Munroe

Publicado en Cine, Comic, Inteligencia Artificial, Internet | Etiquetado: , , , , , | 1 comentario

“Code of the Lifemaker” de James P. Hogan

Publicado por Carlos en Agosto 21, 2009


Code of the Lifemaker es una novela de James P. Hogan, el prolífico –y en los últimos tiempos controvertido– escritor británico. Es fundamentalmente una pieza de ciencia-ficción dura que el autor emplea como vehículo para explorar el rol del individuo en la sociedad, los choques de culturas, así como el conflicto entre ciencia y superstición, todo ello aderezado con acción e intrigas en un apasionante entorno alienígena como telón de fondo.

Decía un celebérrimo director cinematográfico que si en una película no sucede nada interesante en los primeros 30 segundos, el abandonaba la sala. No es fácil trasladar esta idea al mundo literario, ya que hay grandes obras cuyo arranque pone a prueba al lector, pero si algo puede decirse de Code of the Lifemaker es que no adolece de este problema. El prólogo con el que comienza la novela es uno de los hitos de la ciencia-ficción, y ha llegado a ser publicado como pieza separada en antologías de cuentos cortos del autor. Todo comienza hace 1,1 millones de años, en algún sistema estelar situado a 1 000 años luz de la Tierra. Una sonda automatizada de una civilización alienígena llega a un planeta virgen con el objeto de explotar sus recursos mineros. Para ello emplea un patrón de auto-replicación: una plétora de robots de diferentes tipos se afanan en la construcción de una factoría cuyo propósito inicial es la fabricación de robots análogos. Estos robots serán despachados para la construcción de una segunda factoría idéntica a la primera, y así sucesivamente. Tras un cierto número de replicaciones, cada factoría pasa a modo de explotación, extrayendo materia prima del terreno, procesándola y manufacturando las naves de carga en las que los bienes producidos serán devueltos al sistema de origen. El patrón de replicación da lugar a un crecimiento exponencial de los centros de explotación, convirtiendo toda la superficie del planeta en una planta industrial en apenas 50 años. En ese momento, la sonda embarca al contingente principal y procede al siguiente planeta. Desafortunadamente para la sonda (y para la civilización que la construyó, que pereció en el evento) una estrella se vuelve supernova en la proximidad, y el baño de radiación daña profundamente los sistemas y programas de la nave. Cuando 100 000 años después la sonda llega al primer cuerpo celeste en el que puede aterrizar y comienza la rutina de explotación, la situación se descontrola irreversiblemente. La capacidad de auto-replicación se mantiene, pero los fallos en los programas y en los sistemas de producción hacen que finalmente se desencadene un proceso evolutivo: empiezan a surgir robots con ligeras variaciones que compiten por los recursos materiales y por el acceso a las plantas de ensamblaje. Esta presión selectiva provoca la aparición de formas complejas de auto-defensa y replicación efectiva, así como patrones de comportamiento social, especiación y relaciones simbióticas. Una ecología robótica en la que –salvo el componente orgánico– todos los ingredientes de lo que consideramos vida están presentes.

Tras el cautivador prólogo, la novela arranca en un futuro muy próximo al actual (segunda década del s. XXI) y se divide inicialmente en dos hilos de acción. El primero tiene lugar en la Tierra, y se centra en Kart Zambendorf, un mentalista muy hábil. Gracias a dicha habilidad y a la del equipo de colaboradores que le rodea, Zambendorf es capaz de mantener una imagen de autenticidad en sus supuestos poderes ESP, lo que le permite una gran popularidad así como influyentes contactos en la GSEC –General Space Enterprise Corporation– una poderosísima megacorporación. A través precisamente de la GSEC se le plantea la idea de participar en una misión de la NASO (la North Atlantic Space Organization, resultado de la fusión de la ESA, la NASA y la OTAN) a Marte. Su papel sería oficialmente el de experimentar con sus poderes ESP sobre distancias interplanetarias, lo que indirectamente daría cobertura mediática a la misión y permitiría a la GSEC promocionar la futura colonización de Marte. Para sorpresa de Zambendorf, que aceptó la idea pensando que la NASO la descartaría, ésta se muestra favorable a la misma y contacta con Gerold Massey –un afamado psicólogo, ilusionista aficionado, y especializado en desenmascarar a videntes y otros farsantes– para que también forme parte de la misión.

Enterados de la composición de la tripulación (formada por un equipo multidisciplinar de científicos, muy diferente del que el perfil de la misión sugiere), la GSEC intenta desactivar a Massey desde el más alto nivel, lo que despierta el recelo de Zambendorf. Tanto más cuando al llegar a la estación en órbita en los días anteriores al comienzo del viaje advierten que un importantísimo contingente militar viajará con ellos. Cuando finalmente averigua que el equipamiento de los militares incluye vehículos para desplazarse por superficies heladas y densas atmósferas, todos los cabos quedan atados: esa misión no irá a Marte sino más bien a alguno de los satélites del Sistema Solar exterior. El anuncio público de esa “profecía” fuerza a la NASO y a la GSEC a reconocer abiertamente que el destino final del la misión no es Marte sino Titán. Más aún, se revela que las sondas de exploración que se han acercado al satélite han descubierto lo que parecen ser los restos de fábricas de origen extraterrestre, así como numerosos robots, aunque extrañamente ningún signo de los alienígenas que los construyeron. El posterior análisis de la información recopilada en relación a los tipos de robots detectados, así como a su comportamiento lleva a la sorprendente conclusión de que esas máquinas constiyen la biosfera de Titán. La especie dominante recibe el nombre de taloides, por Talos, el hombre de bronce de la mitología griega, creado por Hefestos y guardián de Creta.

Paralelamente a lo anterior, los acontecimientos se desarrollan en la superficie de Titán, cuyos habitantes se encuentran en un régimen feudal similar al de la Edad Media. El protagonista principal es Thirg, un filósofo que tiene en la duda y en el anhelo de conocimiento su razón de ser. Esto le causa problemas con las estructuras de poder de Kroaxia, su nación, y fundamentalmente con los jerarcas religiosos. La creencia oficial es que el mundo es plano, y que detrás del manto de nubes que perennemente cubre a Titán no hay nada. Se venera asimismo al Creador de Vida, el ser que creó la primera máquina (y que por lo tanto no era una máquina, la única forma de vida conocida para los taloides). Esto no casa con el conocimiento que a través de los viajeros había adquirido Thirg y que le indica que el mundo es en realidad esférico, pues alguno de los viajeros que se aventuró mucho hacia al Este llegó a ciudades que se encontraban al Oeste. Este pensamiento le lleva a conjeturar que si no hay barreras físicas sobre la superficie tampoco puede que las haya en los cielos, y que detrás de las nubes haya otros mundos, quizá habitados también. Estas ideas le llevan al terreno de la herejía, por lo que debe huir de Kroaxia hasta Cartoghia, una pequeña nación cuyo rey ha instaurado una suerte de pensamiento libre, y en la que inventores y filósofos perseguidos en otras naciones buscan refugio.

Avisado por su hermano Groork de la inminencia de su arresto y ayudado por un pequeño grupo de soldados de Cartoghia, Thirg comienza su huida perseguido por un gran contingente de tropas de Kroaxia. El destino quiere que en una zona desértica fronteriza y cuando ya el encuentro con los perseguidores parecía inminente, un módulo de superficie terrestre haga acto de presencia para establecer el primer contacto. Para los taloides este módulo es una criatura viva y desconocida, un gigantesco dragón que baja de los cielos emitiendo una misteriosa luz violeta. El asombro aumenta cuando ven que junto al dragón están los que parecen ser sus sirvientes, unas extrañas criaturas con carcasa flexible en cuyo interior una masa de aspecto gelatinoso brilla con un intenso calor. Ajenos a este encuentro, el ejército de Kroaxia inicia el ataque sobre los fugitivos, lo que provoca la respuesta armada terrestre y la inmediata e irremisible destrucción del contingente kroaxiano. El asombro de los absortos taloides no cesa cuando finalmente comprenden que los que creían sirvientes del dragón son en realidad los visitantes, y que de hecho el dragón no es más que la obra de éstos, seres vivos que no son máquinas, y que son capaces de crear máquinas. ¿Serán los Creadores de Vida?

Tras el contacto inicial, y una vez que se desarrolla un sistema de traducción (los robots se comunican entre sí mediante ultrasonidos), se concierta una reunión con Kleippur, rey de Cartoghia, para transmitirle los deseos de los terrícolas (“lumianos” para los taloides, debido a su intenso brillo infrarrojo): colaboración para explotar las factorías alienígenas, a cambio de tecnología terrestre (por ejemplo, armamento). Kleippur rechaza sin embargo este trato: el desea que los terrestres les proporcionen conocimiento de sus artes de fabricar vida (es decir, que les enseñen a desarrollar tecnología). Un acuerdo de estas características está fuera de lugar tanto para los dirigentes políticos de la Tierra como para GSEC, que espera obtener billones de la explotación de Titán, por lo que la dirección de la misión decide comenzar una aproximación en los mismos términos con Eskenderom, rey de Kroaxia, mucho más receptivo a la idea puesto que ambiciona conquistar toda Robia (nombre que los taloides le dan a Titán). Sin embargo, la jerarquía religiosa es un contrapoder importante que puede comprometer la realización del plan, por lo que se decide neutralizarla buscando un sumo sacerdote más maleable, al que se aupará gracias a los “milagros” de la tecnología terrestre. Ante la perspectiva que se cierne sobre los taloides, Massey y Zambendorf unirán esfuerzos para conseguir que no acaben como meros esclavos de la Tierra.

Tal como comentaba al comienzo, el desarrollo argumental de la novela incide en la relevancia del individuo frente a la masa, y en la importancia del pensamiento crítico y la ciencia frente a la superstición. No es por ello sorprendente que el telón de fondo guarde bastantes similitudes con la Edad Media. A pesar de que esto supone una visión un tanto antropocéntrica de una civilización alienígena, cabe destacar que tanto el escenario físico (Titán) como la naturaleza de los taloides proporcionan constantemente la oportunidad de hacer volar la imaginación. Máxime cuando gran parte de la acción se nos muestra desde el punto de vista de los taloides, para quienes los humanos son extrañas criaturas que necesitan estar permanentemente bañadas en gases corrosivos a alta temperatura, y cuyo mundo es tan caliente que hay océanos de hielo fundido y el metano sólo existe como gas. Para los taloides las máquinas están vivas, los dispositivos electrónicos de los humanos son “vegetales”, y perciben que el anhelo de los humanos es “domesticar” los bosques salvajes.

La ambientación está muy bien conseguida (destaca el habla medievalizada de los personajes), hay intrigas tanto entre los humanos como entre los taloides, y un amplio abanico de personajes que tienen un papel importante en la trama. A pesar de haber sido publicada originalmente en 1983, y obviando un par de anacronismos sin importancia (e.g., todavía existe la Unión Soviética) la novela aguanta impertérrita el paso del tiempo sin perder frescura. En resumen, una muy recomendable novela para todos los amantes de la ciencia-ficción.

Publicado en Ciencia Ficción, Evolución, First Contact, Hard SF, Libros, Vida Artificial | Etiquetado: , , , , , , , | 2 Comentarios »

Computación humana para automatización de diseño electrónico

Publicado por Carlos en Agosto 10, 2009

El artículo que describe el trabajo del que hablábamos hace algo más de una semana sobre la resolución del instancias de SAT mediante un juego está ya disponible online. Se trata de

de Andrew DeOrio y Valeria Bertacco. El artículo es muy corto, sólo dos páginas, y no proporciona muchos más detalles acerca del sistema. Sí menciona algún aspecto de interés, como es el hecho de que la disposición espacial de las cláusulas intenta corresponderse con las variables que la afectan (lamentablemente no entra en detalles sobre cómo  han atacado este extremo, ya que es un problema de optimización geométrica muy interesante).

Con todo, lo más relevante del artículo sean las referencias a la escalabilidad (que ya anticipamos el otro día como uno de los cuellos de botella del enfoque). Al parecer, la idea básica es que cada nivel sea una visión local de una parte del problema completo, visión que se irá ampliando al ir aumentando de dificultad. En instancias de gran tamaño sugieren emplear un enfoque multi-jugador en el que cada participante juega sobre una parte del problema. Obviamente hay interrelaciones entre estas partes (si modificamos una variable podemos alterar el estado de una cláusula de otro tablero), por lo que la división debería hacerse de manera astuta de forma que estas interrelaciones sean mínimas. La mala noticia es que tendríamos entonces un problema de corte mínimo en grafos, que es NP-hard si se introducen restricciones sobre el número de interrelaciones entre subconjuntos.

Publicado en Complejidad, Juegos, Optimización Combinatoria | Etiquetado: , , , , | 1 comentario

Resuelve problemas NP-completos mientras juegas

Publicado por Carlos en Julio 29, 2009

La clase NP -de la que ya hemos hablado en alguna ocasión- abarca aquellos problemas de decisión que pueden resolverse en tiempo polinómico no determinista, o lo que es lo mismo, aquellos problemas para los que es posible verificar en tiempo polinómico la validez de una solución dada. Esta clase ha sido tradicionalmente empleada como sucedáneo de la idea de intratabilidad computacional. No se trata de la mejor caracterización, ni siquiera de la más apropiada, puesto que admite mucha patología y en ocasiones tiene un impacto práctico limitado, pero eso será tema de algún futuro post. Sea como fuere, es común que allá donde nos enfrentemos a un problema NP-hard se emplee este hecho como justificación para el empleo de algún tipo de (meta)heurística.

Nuestra comprensión sobre cómo aplicar metaheurísticas para resolver problemas específicos ha avanzado enormemente en la última década. Una de las claves está en ser capaces de explotar conocimiento del problema durante el proceso de búsqueda. Técnicas tales como los algoritmos meméticos se basan fundamentalmente en esta idea. Evidentemente no se trata de algo trivial de conseguir, y aquí es donde es posible que la mente humana eche una mano y no en la ingeniería del proceso sino contribuyendo capacidad de búsqueda pura y dura. No se trata por supuesto de cálculo numérico ni de búsqueda sistemática, sino de explotar algunas de las cualidades que nuestros cerebros han ido desarrollando durante millones de años de evolución: estrategia y procesamiento visual.

La capacidad de extraer información de un torrente de datos visuales es una de nuestras grandes bazas. Estamos programados para buscar orden en el caos, patrones en el ruido blanco, formas conocidas en el desorden. Áreas tales como la minería de datos visual intentan explotar precisamente esta característica. Por otra parte nuestra visión estratégica, la capacidad de trazar planes y seleccionar heurísticamente las ramificaciones más relevantes es también bien conocida en el ámbito -por ejemplo- de los juegos de tablero. Es precisamente en este área en el que investigadores de la Universidad de Michigan han intentado aunar ambas capacidades y dirigirlas hacia la resolución de problemas NP-completos. Andrew DeOrio y Valeria Bertacco, del departamento de ingeniería eléctrica e informática de la citada universidad, han desarrollado un entorno en el que se pueden resolver instancias del problema de la satisfacibilidad lógica mediante un juego lejanamente relacionado con el clásico lights off.

FunSAT - Pulsa sobre la imagen para jugar

FunSAT - Pulsa sobre la imagen para jugar

En el tablero tenemos una matriz de burbujas que representan las cláusulas de la instancia del problema (esto es, las restricciones que debemos satisfacer). Estas cláusulas dependen de un conjunto de variables, representadas como rectángulos en los bordes del tablero. Pulsando sobre éstos podemos fijar una cierta variable a cierto/falso o dejarla indefinida. De resultas de cualquiera de estas acciones algunas cláusulas pasarán a estar satisfechas (lo que se indicará mediante el color verde) o insatisfecha (un tono grisáceo, tanto más oscuro cuantas menos variables que puedan afectar a dicha cláusula nos queden sin asignar). El tamaño de cada burbuja indica el número de variables que intervienen en ella (se puede jugar también a 3-SAT, variante clásica en la que todas las cláusulas tienen 3 variables involucradas).

Lo interesante es que las instancias de SAT que se plantean en este juego corresponden supuestamente a problemas de diseño VLSI.  El análisis de lo que el juego puede dar de sí lo han publicado en un artículo titulado

  • Human computing for EDA

que presentarán en la próxima Design Automation Conference, que se celebra en San Francisco en estos días. El artículo aún no está disponible, por lo que se puede añadir poco más a lo ya comentado. Esperaremos a leerlo para ver cuál es el planteamiento a largo plazo del invento, que a priori diríase que adolece de un problema de escalabilidad. Y es que el ser humano es extraordinario, pero dentro de un límite.

Publicado en Complejidad, Juegos, Optimización Combinatoria | Etiquetado: , , , | 2 Comentarios »

Realidad Virtual y Vida Artificial: de la Biomecánica a la Inteligencia

Publicado por Carlos en Julio 14, 2009

Las charlas plenarias de las conferencias suelen navegar por la procelosa frontera que separa el tema central de la reunión con otros temas relacionados (y en ocasiones transcurren directamente al otro lado de la frontera). Suele ser una buena política, ya que en las zonas de confluencia las cosas se ponen divertidas, y de hecho este ha sido el caso de la primera de las charlas invitadas que hemos disfrutado. El orador era Demitri Terzopoulos, que estuvo involucrado en los comités de programa de estos saraos tiempo ha pero que nunca ha llegado a aplicar computación evolutiva a su área de trabajo. Era pues un gran desconocido a priori para el grueso de la audiencia -salvedad hecha de los que trabajan en visión por computador- a pesar de tener un currículo investigador talla XXL, y hay que decir que después de su charla los allí presentes recordaremos bien su nombre, pues fue una hora y media extremadamente interesante y entretenida.

El título de su charla fue “Artificial Life Simulation of Humans and Lower Animals: From Biomechanics to Intelligence”, y durante la misma intentó explicarnos algunas de las claves de la emergente fusión entre realidad virtual y vida artificial, cuyo objetivo final es la construcción de agentes biomiméticos autónomos. En sus diapositivas iniciales nos mostró lo que no es uno de dichos agentes, como por ejemplo los dinosaurios de Parque Jurásico, o los protagonistas de Toy Story por citar un par de ejemplos. Las cosas empezaron a calentarse un poco con los ejércitos de El Señor de los Anillos, que podríamos englobar dentro de la categoría de enjambres (animar manualmente cada uno de los miles de personajes en el ejercito es inasumible, por lo que cada uno de ellos está dotado de un sistema simple basado en reglas para determinar su comportamiento). En este punto fue donde nos presentó los diferentes niveles en los que hay que intervenir para construir un sistema biomimético autónomo, y que se organizan jerárquicamente como sigue:

Niveles para la simulación de un sistema biomimético. Credit: Demitri Terzopoulos

Niveles para la simulación de un sistema biomimético. Credit: Demitri Terzopoulos

La ilustración inicial de estas ideas corrió a cargo de una fauna submarina sintética que el propio Demitri desarrolló con sus colaboradores. El nivel más bajo de la jerarquía estaba definido en este caso por un armazón de cada uno de los peces, construido a partir de partículas unidas mediante una combinación de muelle y amortiguador. Algunos de los segmentos del pez hacen las veces de músculos, y en ellos la longitud natural del muelle puede modificarse a voluntad. El modelo resultante queda descrito por una colección de ecuaciones diferenciales que determinan la respuesta dinámica al movimiento del pez en el medio líquido. La locomoción del pez se optimizó mediante una técnica de búsqueda local (no entró en muchos detalles al respecto) para que resultara en el movimiento más fluido y energéticamente económico. En este punto, el movimiento de natación de peces y morenas resultante era extremadamente realista.

Para simular la percepción, los peces estaban dotados de sensores visuales que permitían cubrir un cierto ángulo en la dirección de orientación de la criatura. La información así obtenida era procesada según técnicas estándar de visión por computador, para proporcionar la entrada al siguiente nivel, el comportamiento. Éste es esencialmente reactivo, y está determinado por una red neuronal que determina la acción correspondiente a un determinado estímulo. Para la simulación de los animales marinos se incluyó un registro de memoria con capacidad unidad. Esto permite que el animal desarrolle un comportamiento básico -seguir un objeto, alimentarse, ..- que pueda ser interrumpido cuando por ejemplo se entre en modo huida al detectar un depredador, y luego reanudado cuando cese el peligro.

En el ejemplo del mundo submarino no había mucho lugar para el nivel más alto de la pirámide y que entronca plenamente con la inteligencia artificial. En el siguiente ejemplo que abordó -seres humanos sintéticos- sí que era más relevante, aunque no entró en él. Sí describió unos modelos muy interesantes relativos a la simulación de rostros humanos (quien haya visto Final Fantasy recordará el fotorrealismo de algunos de los personajes). Los niveles más bajos de la pirámide se abordan de la misma manera que en el caso de los peces, aunque más arriba se introduce un elemento más interesante: redes bayesianas para la determinación del comportamiento. Resultaba curioso ver cómo un rostro humano sintético era capaz de reaccionar a estímulos visuales, siguiendo la trayectoria de un objeto o mostrando enfado o satisfacción dependiendo de su patrón de movimiento.

La charla terminó con algunas ideas sobre lo que podemos esperar en el futuro. Alguien planteó si quizás en algunos años una versión virtual de Demitri podría dar esa misma charla ante una audiencia igualmente virtual. Él estuvo de acuerdo en que eso será factible, aunque no cree vivir para verlo (hay que decir que no es muy mayor, cuarenta y tantos según mi ojo de buen cubero). Yo soy sin embargo más optimista que él.

Publicado en Aprendizaje Automático, Computación Evolutiva, Inteligencia Artificial, Vida Artificial | Etiquetado: , , , , | 6 Comentarios »

Evolución de Algoritmos Cuánticos

Publicado por Carlos en Julio 10, 2009

Una de sesiones más interesantes de lo que llevamos de conferencia ha sido la referida a evolución de algoritmos cuánticos. El ponente de la misma ha sido Lee Spector (uno de cuyos trabajos sobre inteligencia artificial comentamos aquí in ilo tempore), y durante aproximadamente 2 horas nos desgranó un tutorial sobre algoritmos cuánticos que desembocó en la interrelación de los mismos con la programación genética. Antes de llegar a este último punto, comenzamos recordando uno de los experimentos más clásicos (y no por ello menos sorprendente) de la mecánica cuántica, esto es, el interferómetro de Mach-Zehnder.

Interferómetro de MAch-Zender (credit: Danielmader)

Interferómetro de Mach-Zender (credit: Danielmader)

En este experimento se emplean dos espejos semi-reflectantes (abajo a la izquierda, y arriba a la derecha) que con una probabilidad del 50% dejan pasar un fotón incidente o lo reflejan en dirección perpendicular. La intuición clásica indica que dado que hay dos bifurcaciones, cada una de las cuales es equiprobable, un fotón tendría un 50% de probabilidades de llegar al segundo espejo semi-reflectante por el camino superior y un 50% de hacerlo por el camino inferior. Una vez en el mismo, tendría un 50% de probabilidades de ser reflejado y un 50% de atravesarlo. Sumando el 25% de probabilidad de que el fotón llegue por el camino superior y se refleje y el 25% de que llegue por el camino inferior y atraviese el espejo, llegamos a que un 50% de los fotones llegarían al detector 2. Sin embargo, esta intuición no es correcta ya que la realidad indica que el 100% de los fotones llegan al detector 1. Esto es debido a que al ser reflejado un fotón se produce un cambio de fase de media longitud de onda en el mismo. De resultas del mismo se produce una interferencia destructiva al superponer los estados que desembocan en el detector 2, por lo que ningún fotón puede llegar al mismo. La única posibilidad factible son los caminos que llevan al detector 1.

Este experimento admite una vuelta de tuerca muy interesante: imaginemos que tenemos bombas cuya espoleta se activa en el momento que detectan un fotón. Dada una de estas bombas, podemos saber si funciona correctamente (o por el contrario es defectuosa) simplemente exponiéndola a la luz, aunque obviamente esto conduciría a la pérdida de todas las bombas plenamente funcionales. Un procedimiento más astuto hace uso del montaje anterior, y da lugar a lo que se conoce como comprobador de bombas de Elitzur-Vaidman. Básicamente, sustituimos el reflector inferior derecho por la bomba. Ahora, si la bomba es defectuosa se comportará como un espejo y el sistema será equivalente al anterior, es decir, todos los fotones llegarán al detector 1. Sin embargo, si la bomba funciona correctamente el fotón no puede seguir en estado superpuesto camino superior/camino inferior, ya que la explosión de la bomba supone un proceso de medida, y la función de onda debe colapsar a uno de los dos estados. Por lo tanto, puede pasar que la bomba explote (si el estado al que el fotón colapsa es el camino inferior), o que no lo haga (si el estado es el camino superior). En este segundo caso, al llegar al segundo espejo semi-reflectante no se produce interferencia destructiva, y hay un 50%-50% de posibilidades de que llegue a un detector o al otro. Si llega al detector 2 estamos seguros de que la bomba es buena. En otro caso hay que repetir el experimento hasta que eventualmente la bomba explote, el fotón llegue al detector 2, o tengamos una certeza razonable de que la probabilidad de que la bomba sea defectuosa es despreciable.

Dándole otra vuelta más de tuerca al sistema, podemos sustituir la bomba por un computador que ejecutará un algoritmo y producirá o no un fotón de salida. Nuevamente, inspeccionando los detectores podemos determinar cuál sería la salida del algoritmo, sin necesariamente ejecutarlo. Este montaje fue propuesto por Onus Hosten et al. en un artículo titulado

publicado en Nature (véase también este comunicado de prensa). Toda esta discusión constituyó un punto de entrada para ilustrar el concepto de superposición de estados y -tras una breve disgresión sobre la mente humana, la consciencia y su computabilidad- entrar en la noción de qubits y puertas lógicas cuánticas.Estas últimas las vimos a través de su notación matricial. Por ejemplo, si tenemos un qubit con valor \alpha|0\rangle + \beta|1\rangle, la siguiente matriz representa un NOT:

\left(\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right)

ya que al multiplicarla por el vector columna (\alpha,\beta) obtenemos el vector columna (\beta,\alpha) (puede verse por ejemplo que en el caso clásico en el que \alpha=1, \beta=0 o viceversa se obtiene el resultado complementario). Más interesante es la puerta lógica SNR (square root of NOT):

1/\sqrt{2}\left(\begin{array}{cc} 1 & -1 \\ 1 & 1 \end{array} \right)

Al aplicarla una vez a un qubit que es 1 ó 0 se obtiene una suerte de aleatorización, ya que se pasa a un estado de superposición equiprobable entre ambos valores. Al aplicarla por segunda vez, se obtiene sin embargo el complemento:

\left(\begin{array}{c} 1 \\ 0 \end{array} \right) \Rightarrow \left(\begin{array}{c} 1/\sqrt{2} \\ 1/\sqrt{2} \end{array} \right) \Rightarrow \left(\begin{array}{c} 0 \\ 1 \end{array} \right).

Una de las posibilidades para la aplicación de técnicas de programación genética es tratar de buscar puertas cuánticas ad hoc, mediante la evolución de las matriz que la define. Yendo más allá, se puede pensar en programación genética para combinar puertas lógicas preexistentes y obtener un circuito que desarrolla un cierto propósito buscado. Un ejemplo de esto nos lo dio con un trabajo (que hay que decir ya tiene unos años) en el que se consiguió una solución nueva y eficiente a un problema simple (pero por algo hay que empezar). El trabajo en cuestión es

del propio Lee Spector et al., y que apareció en las actas del CEC 1999. Otras líneas de desarrollo apuntan a la construcción de algoritmos híbridos que combinan elementos clásicos con elementos cuánticos. Un área apasionante sin duda.

Publicado en Computación Evolutiva, Física | Etiquetado: , , | Comentarios desactivados

Montreal, nous sommes ici!

Publicado por Carlos en Julio 8, 2009

Este año la “Gran Cosa Científica” (Prof. Frink dixit) del área de la computación ev olutiva tiene lugar en Montreal (Quebec, Canadá), y para allá que hemos liado el petate y agarrado un avión.

Rue Saint Antoine

El verano por estos lares es como los programas culturales en televisión: todo el mundo ha oído hablar de ellos, pero pocos los disfrutan. Unos suaves 15C y una menos suave lluvia nos ha recibido a nuestra llegada. La sede del congreso está en un lugar céntrico, y desde el que se puede dar una pequeño e interesante paseo.

Notre Dame of Montreal

En cuanto el ritmo de sesiones lo permita, intentaremos seguir explorando le Vieux-Montreal. Stay tuned…

Publicado en Computación Evolutiva, Lugares, Viajar | Etiquetado: , , , | 5 Comentarios »