La Singularidad Desnuda

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

Posts Tagged ‘Programación Genética’

Evolución de Algoritmos Cuánticos

Posted by 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.

Anuncios

Posted in Computación Evolutiva, Física | Etiquetado: , , | Comentarios desactivados en Evolución de Algoritmos Cuánticos

Guía de Campo de la Programación Genética

Posted by Carlos en abril 9, 2008

La programación genética es uno de los cuatro paradigmas principales de la computación evolutiva. Básicamente consiste en el empleo de un enfoque evolutivo para la generación de programas que resuelven una cierta tarea. Tradicionalmente, estos programas se representan mediante árboles sintácticos a través de los que es posible expresar funciones complejas e incluso programas, dependiendo del conjunto de símbolos disponible (no es extraño en cualquier caso encontrar también representaciones lineales de programas, o representaciones basadas en grafos). Para construir dichos árboles es preciso especificar el conjunto de símbolos terminales que se emplearán como hojas de los árboles (variables, constantes, etc.), así como los símbolos no terminales (funciones básicas) que se emplearán en los nodos internos, y si es preciso las reglas sintácticas y semánticas de indican qué árboles son correctos.

Genetic Programming Tree

A partir de ahí, se emplean los mecanismos de selección, reproducción y reemplazo para hacer evolucionar una población de programas en pos de la solución de un cierto problema (ya sea de tipo supervisado, en el que se desea producir una cierta salida conocida ante ciertas entradas, o no supervisado, en el que típicamente se desea un cierto comportamiento de un sistema controlado por el programa, pero no se dispone explícitamente de las salidas precisas que hay que producir para ello). Lo mejor de todo es que este enfoque funciona, y es posible resolver satisfactoriamente problemas de diferente índole (clasificación, síntesis de circuitos, control de sistemas, etc.). A modo de muestra, pinchando en la imagen inferior se puede acceder a un applet de java que emplea programación genética para realizar regresión simbólica, esto es, encontrar la curva que mejor se ajusta a unos datos sin conocer no ya los parámetros de la misma (eso sería simple regresión numérica), sino la propia forma funcional de ésta (que puede ser sumamente compleja).

Symbolic Regression with Genetic Programming

Hay disponibles diferentes libros de texto o colecciones de artículos más o menos avanzados sobre el tema, y desde hace unas semanas una guía de campo introductoria. Los autores de esa guía son Riccardo Poli, William B. Langdon (ganador por cierto este año de la tercera edición del premio a la contribución sobresaliente a la computación evolutiva, ex aequo con Marc Schoenauer; Poli y Wolfgang Banzhaf lo ganaron el año pasado, y Jennifer Willies antes que ellos), y Nicholas McPhee, y durante la conferencia de hace dos semanas acudieron con una caja de ejemplares que fueron regalando a cambio de la voluntá (y que firmaron a quien quiso). Quien esté interesado en el área puede encontrar interesante que el libro está bajo una licencia CC y puede bajarse gratuitamente de aquí.

Posted in Computación Evolutiva, Libros | Etiquetado: , | 1 Comment »