jueves, 20 de marzo de 2008

Construyendo la realidad

Construyendo la realidad

Jeff Hawkins,

Jeff Hawkins, creador de la agenda electrónica Palm, es uno de los triunfadores de la electrónica de Silicon Valley. Los fondos obtenidos con sus inventos le permitieron fundar el Redwood Neuroscience Institute, donde investiga su gran pasión: cómo funciona el cerebro humano desde la perspectiva de un sistema informático, no desde el paradigma neurológico tradicional. Su libro “On Intelligence” expone las teorías que hasta ahora ha ido estableciendo.

Eduard Punset
El día que se tenga éxito produciendo lo que tu sugieres en este libro sobre máquinas inteligentes posiblemente será el día más feliz de mi vida, porque ya estoy cansado de que se diga que somos los únicos reyes del universo y los que estamos mejores construidos, etc.
Es decir que por primera vez acabarás con la historia de que los ordenadores son completamente diferentes de los cerebros, y vas a construir una máquina que realmente funciona como un cerebro.

Jeff Hawkins
En realidad hago dos cosas, la primera es comprender cómo funciona el cerebro, y no todo el cerebro sino sólo el neocórtex y algunas cosas relacionadas con él. Queremos saber qué hace y como lo hace. Una vez que sepamos qué es el cerebro y cómo funciona podemos construir una máquina que funciona de manera similar, con unos principios parecidos. Mi libro trata del córtex, y hablo de cómo construir máquinas con los mismos principios... cuando estaba escribiendo el libro no sabía cómo hacerlo, pero ahora sí lo que sabemos.

Eduard Punset
Caramba, y serás capaz de reproducir –bueno, dices que desde que has escrito el libro has progresado mucho- de mostrar en una capa cortical (cortical sheet) estas máquinas inteligentes.

Jeff Hawkins
Sí. Déjame hacer una distinción que hago muy cuidadosamente en el libro. Lo que estamos haciendo es un neocórtex, no estamos intentando crear humanos, porque los humanos tienen muchas más cosas: tienen el cuerpo físico, tienen emociones, aspiraciones y muchas cosas que van más allá del neocórtex. El neocórtex es la parte del cerebro que piensa, es la parte inteligente, y desde que escribí el libro hemos progresado mucho. Junto con otro científico, Deleep George, hemos redactado una fórmula matemática para expresar lo que el neocórtex está haciendo, cómo ponerlo en un marco matemático, y con él hemos empezado a hacerlo y a construir los sistemas. Y en realidad lo estamos haciendo, hemos empezado con el sistema de visión, y tenemos sistemas que funcionan mucho mejor que cualquier cosa que se haya hecho antes, y lo hace de esta manera, lo hace de la forma en que lo hace un humano. Estamos construyendo una herramienta de software, o una serie de herramientas, que permiten construir neocórtex pero en software. No es un ordenador, sino que es un algoritmo que funciona en un ordenador, y lo captura todo igual que lo hace el neocórtex. Y podremos construir máquinas que serán inteligentes, aunque tu dirás que no son como los humanos. No podremos sentarnos y tomarnos un café con ellas, pero podrán pensar cosas, comprender y percibir el mundo como lo hacemos tu y yo.

Eduard Punset
Porque se comportarán de la misma manera que lo hace el córtex

Jeff Hawkins
Es como el córtex, puede sentir cosas y podrá decir: sé lo que es esto; y también tendrá expectativas de futuro, y podrá predecir: después de decir “sé lo que es esto” hará una predicción de lo que sucederá.

Eduard Punset
Tu dices dos cosas increíbles, primero dices que no importa tanto el sentido, ya sea la vista, el oído o el tacto, ya que al final en el neocórtex todo se convierte en la misma cosa, las mismas señales, y esto me lo vas a explicar; y la segunda cosa es que dices que para ser inteligente tienes que ser capaz de predecir, y eso es lo que hace el neocórtex, ya que puede predecir cosas, porque almacena lo que tu denominas “patrones de observación” (observational patterns). Es verdad que el cerebro primero observa patrones, los almacena y gracias a el almacenamiento puede hacer predicciones. Y tu dices que si puedes hacer predicciones eres inteligente.

Jeff Hawkins
Si se hacen de la forma correcta, sí. Pero vayamos a la primera parte de la pregunta. Que el córtex hace todo lo que hace utilizando el mismo método, el mismo algoritmo, es un descubrimiento increíble. Lo propuso por primera vez, hace 25 años, en Inglaterra, un señor llamado Mauntcastle, y dijo que aunque el neocórtex se parece a una servilleta grande, y las distintas partes hacen cosas diferentes (hay partes que son la vista, o el oído, o la música, o las matemáticas), si se analizan las células y su estructura son casi idénticas en todas partes. Lo que Mountcastle propuso es que era idéntico en todas las partes y aunque es difícil de creer es así. He preguntado a muchos neurocientíficos si creían en esto o no, y la mitad no lo creen y la mitad sí, y si se les pregunta por qué no se lo creen, dicen que porque es difícil de creer. Pero es el descubrimiento más importante hecho sobre el cerebro y explica cómo funciona y que es todo igual. Si fueras un cerebro y analizaras las señales que entran --entran por las fibras nerviosas del cerebro llamadas axones--, las que entran por los ojos son idénticas a las que entran por los oídos, o por la piel. No hay ningún sonido, o visión u tacto que entre en el cerebro, ya que en cuanto entran en el cerebro son todas unos patrones y son idénticos. La percepción del mundo es muy diferente, pero tiene que ver con la naturaleza del patrón, no tiene nada que ver con el mecanismo en si, porque es el mismo.

Eduard Punset
Y entonces una pregunta me viene a la mente. Sí esto es así, las máquinas inteligentes del futuro no hace falta que informen de lo que informan los sentidos tradicionales humanos, puede que estén afinadas para informar de otras cosas, que no tienen nada que ver con estos sentidos a los que estamos acostumbrados.

Jeff Hawkins
Exactamente, es algo muy importante en los descubrimientos de la naturaleza y es un método muy poderoso, que viene a decir: “si me das cualquier dato sensorial, construiré el modelo que lo causó”. Si estudiamos a los mamíferos, y pensamos en los humanos, tenemos vista, oído, olfato, tacto y gusto, pero también otros sentidos como el del propio cuerpo, que en realidad es de la posición del cuerpo; y otros animales, como los roedores, tienen los bigotes, que en realidad es un sentido completamente diferente que va al córtex, que lo procesa.

Eduard Punset
Y las abejas...

Jeff Hawkins
Las abejas no tienen córtex, sólo los mamíferos lo tienen, pero tienes razón ya que cuando construyamos las máquinas, en el futuro, funcionarán con el mismo principio: no hará falta que tengan oídos y ojos, sino que podrán funcionar con cualquier tipo de sensor, cosas simples como el sonar o el radar, e incluso sentidos más exóticos. He escrito en el libro que si se tiene un país y se piensa en las estaciones metereológicas que hay distribuidas por toda la geografía, es lo mismo que la retina del ojo, que va recogiendo todos los puntos de luz... pues lo mismo sucedería con las estaciones metereológicas, cuyas mediciones se podrían entrar en un sistema que “vería” el tiempo metereológico de la misma manera en que tu y yo vemos la luz. O sea que se podrían tener sentidos exóticos y funcionaría así.

Eduard Punset
Pero Jeff, ¿cómo nos comunicaríamos? Porque si hay diferentes sentidos, ¿cómo nos comunicaremos con estas máquinas que funcionan con diferentes sentidos de los que conocemos?

Jeff Hawkins
No es muy difícil. Imagínate lo siguiente: hay personas que no tienen todos los sentidos. Helen Keller es una mujer muy conocida y no podía ni ver ni oír, sólo tenía tacto, y sin embargo construyó un modelo del mundo que no es muy distinto del tuyo o el mío. No tenía unos sentidos distintos a los nuestros, sólo tenía uno y consiguió construir un modelo que se podía comunicar con nosotros. Nosotros estamos pensando en máquinas que se construirán de esta forma, y será muy fácil comunicarse con ellas. Evidentemente no tendremos una conversación como ésta, no se trata de esto, pero a los modelos, como por ejemplo el del tiempo metereológico, etc. será posible interrogarlos. Por ejemplo, les podremos preguntar ¿qué has descubierto? O ¿en qué estás pensando?

Eduard Punset
Cuando haces predicciones probablemente usas la capacidad metafórica de relacionar una cosa con la otra y decir que esto me permite hacer una predicción porque lo he visto, etc. ¿Es esto creatividad? O déjame que lo diga de otra manera: ¿qué es la creatividad?

Jeff Hawkins
Es creatividad, pero déjame que lo ponga en perspectiva. Cuando se hace una predicción, durante cada momento de la vida en que se está despierto no se es consciente de estar haciéndola. Cuando pongo una mano en algún sitio, tengo expectativas de cómo se sentirá y dónde y como lo sentiré. Nunca he estado en exactamente esta situación con anterioridad, y nunca me he sentado hablando contigo antes, de forma que todo esto es nuevo, y nunca he visto este papel antes, pero si lo toco tengo una expectativa de lo que hará: se puede quemar, puede volver, tiene un cierto tacto... y se que estoy haciendo predicciones porque lo conozco, porque si fuera diferente, como cristal o como gelatina o como algo frío diría: caramba, qué sorprendente. Es decir que el cerebro hace esto todo el tiempo y no nos damos cuenta. La segunda cosa que es sorprendente es que las entradas al cerebro siempre son nuevas, son únicas, suceden una vez y no se repiten nunca más, me puedes ver 100 veces y cada vez es un modelo distinto, porque o me he movido un poco, o porque la luz ha cambiado, es decir que se hacen predicciones sobre cosas nuevas todo el tiempo; este es un trozo de papel nuevo que nunca he visto antes y tengo una predicción sobre él. Nunca he tocado esta silla con anterioridad y tengo predicciones, los espectadores están oyendo y viéndome y tienen predicciones sobre lo que voy a decir. O sea que se hacen nuevas predicciones sobre situaciones novedosas, y esta es la esencia de la creatividad, pero se hacen a distintos niveles, no vemos esto como ser creativo. Yo no creo que estoy siendo increíblemente creativo cuando toco esta hoja de papel, o cuando anticipo lo que dirás, pero es lo mismo: en el córtex hacemos esto a niveles inferiores y superiores. Los niveles superiores son aquellos a los que llamamos creatividad: tenemos un nuevo problema que no he visto antes, quizá es un problema científico, se hace una predicción que es la hipótesis sobre la causa y por lo tanto se hace una predicción de lo que sucederá después. Es decir que se tiene un experimento que se va a probar y hacemos predicciones, y a un nivel superior creemos que es creatividad, pero es lo mismo, utilizamos información que tenemos del pasado y decimos que esto es algo similar. Un matemático puede decir: esta ecuación es similar a otra en la que trabajé hace 5 años, y si parece similar voy a utilizar una metodología similar a ver si puedo solucionarla.

Eduard Punset
Pero si todos los cerebros son creativos, ¿por qué algunas personas son más creativas que otras?

Jeff Hawkins
Vale, todo el mundo es creativo, y hay personas que son más creativas que otras en ciertas áreas. Se puede decir que yo soy más creativo que tu en ciertas tareas, y es posible que tu lo seas en otras. Yo creo que es parte del clásico debate naturaleza / entorno. Claramente una parte es aquello a lo que se ha estado expuesto, si no he estado expuesto a una serie de cosas no sabré hacer predicciones para eso; si me pones delante un nuevo idioma al que nunca con anterioridad he estado expuesto, para mi no tendrá ningún sentido, y no seré capaz de hacer predicciones de lo que se está hablando, o lo que se dirá después, o lo que hará alguien, etc. Es decir que se tiene que estar expuesto a los modelos para poder ser creativo, y cuanto más altos son los niveles más creativo se es: si he estado muchos años estudiando física, se puede ser muy creativo en física. La segunda cosa es que hay diferencias entre los cerebros humanos, sabemos que hay mucha variabilidad en los cerebros humanos, y las áreas dedicadas a tareas diferentes cambian mucho. Un hecho increíble es que si se toma el área visual del cerebro humano, que es el área más grande del neocórtex, varía en una factor de 3 entre distintas personas, es decir que es posible que una persona tenga una área tres veces más grande que otra. Todos pueden ver, pero una tendrá una visión más exacta, pero esto no se sabe: yo no puedo decir que tengo una visión más exacta que la tuya, no lo sé. Y de la misma manera hay personas que tienen un cerebro que es mejor para unas tareas determinadas. Pero no quiero predecir ni quién ni como, es algo natural.

Eduard Punset
Es cierto que si dañas el córtex de una rata hay cosas que pasarán de forma diferente, pero no muchas; sin embargo, si se destruye el córtex de un humano se paraliza por completo ¿no?

Jeff Hawkins
Esto es por la evolución del córtex porque el córtex empezó realmente con los mamíferos, y los no mamíferos no tienen córtex, pero todos los mamíferos lo tienen. Y en una rata el córtex es muy pequeño, quizá tiene el tamaño de un sello de correos, o algo así, y no juega un papel dominante en la vida de la rata. La rata tiene un cerebro primitivo como el de un reptil y un pequeño córtex, es decir que es de una cierta ayuda pero no es dominante, y como tu has dicho puedes extirpar el córtex de una rata y ella sigue moviéndose y tiene una apariencia casi normal. En los humanos, y en la progresión evolutiva, el córtex juega un papel muy dominante en la vida y tiene un tamaño enorme: de 1000 centímetros cuadrados. Y es muy importante, o sea que si se extrae el córtex de un humano es posible que respire y digiera alimentos pero nada más.

Eduard Punset
Porque realmente el córtex suplantó de alguna manera...

Jeff Hawkins
Sí, el córtex creció físicamente de una manera increíble alrededor del cerebro y tiene una fuerza dominante, aunque por supuesto no lo controla todo. Por ejemplo, si te digo que dejes de respirar es posible que lo hagas, pero la parte primitiva del cerebro en un cierto punto dirá que hay que respirar, ya que no se puede estar sin respirar, o sea que no lo controla todo, pero sí casi todo.

Eduard Punset
O sea que este comportamiento en la mayoría de los animales, y desde luego en los no mamíferos, obedece al cerebro primitivo, y en los humanos tenemos esta especie de monstruo que crece en el cerebro y ha suplantado muchas de sus funciones.

Jeff Hawkins
Teníamos el cerebro primitivo, el de un cocodrilo o de un reptil o lo que fuera, pero al caminar, por ejemplo, la mayoría del control motor, que es el que hace que se muevan las piernas, no viene del córtex sino de partes del cerebro primitivo; sin embargo en los humanos, con la excepción de unos movimientos básicos, el habla, el movimiento de las manos, la interacción social, casi todo lo que hacemos, todo está controlado por el córtex. Seguimos teniendo esta parte primitiva, todavía está ahí y el mejor ejemplo es que al aprender a montar en bicicleta...

Eduard Punset
No tiene nada que ver con el córtex...

Jeff Hawkins
No mucho, la mayoría de la gente no sabe cómo montan en bicicleta y es por eso que se caen, porque el córtex no tiene mucho que ver y el cerebro primitivo sí. Resulta que cuando se quiere ir a la izquierda hay que ir primero a la derecha para que la bicicleta se incline y se pueda hacer una curva a la izquierda. Si cuando se quiere ir a la izquierda se gira el manillar inmediatamente te caes, y esto es algo que el córtex no controla, y hay alguna historia similar, pero todo lo demás lo sabe hacer el córtex.

Eduard Punset
Has mencionado la evolución y pensemos en la célula, primero... estoy pensando en la predicción que significa inteligencia. La célula, o todos los organismos vivos, me imagino que hacen una cierta predicción: la célula, las plantas y las neuronas. Y si es así, la pregunta obvia que la audiencia haría es: ¿los animales son inteligentes?

Jeff Hawkins
Esta es una respuesta compleja, aunque intentaré hacerla sencilla. Cualquier comportamiento del animal depende de tener un cierto modelo del mundo que hace las predicciones, para eso están los modelos. Una planta hace predicciones porque sube hacia el tejado en busca de la luz, y envía las raíces hacia abajo en busca del agua. Esto no es pensar, las plantas no tienen una conversación y no dicen dónde voy a poner las raíces para buscar agua, pero sí que es predicción. La definición de la inteligencia es construir un modelo del mundo y hacer predicciones. Hay una gama: desde lo más simple, como los animales unicelulares o las plantas, etc. hasta los más sofisticados que son los humanos. Y a un nivel muy elevado se hace lo mismo, lo que se tiene que pensar con los mamíferos es que hemos desarrollado un sistema para hacer esto durante la vida, es decir que aprendemos mucho durante nuestra vida. Casi todo lo que sabemos del mundo, sobre los programas de TV, o ciencia, o sillas, o lo que sea, no nacimos sabiendo eso, lo hemos aprendido; y la planta no es así, no aprende nada durante su vida, pero nosotros lo aprendemos todo durante la vida. Y el córtex tiene una forma muy genérica de hacer esto: puede aprender casi todo; anteriormente en la genética se tenía que aprender de forma evolutiva, pero nosotros podemos aprender casi todo durante la vida. A un cierto nivel las plantas son inteligentes, pero es un nivel muy mínimo, no se puede decir que tengan un nivel ideal de inteligencia. Pero cuando hablamos de mamíferos, de la rata, ¿es inteligente? Claro que lo es. No es tan inteligente como nosotros, ni puede comprender el mundo como nosotros, no puede aprender lo mismo, pero por definición puede hacer predicciones y tiene un mundo de percepciones, por lo tanto la rata es mínimamente inteligente. No sirve de mucho poner unas marcas de inteligencia: éste animal es inteligente y éste no lo es, todo es una gama que va desde los humanos hasta el organismo más simple.

Eduard Punset
Cuando te oigo hablar sobre la creatividad me da tanto miedo... porque pienso: caramba, es posible que mi creatividad me pierda, que me lleve a algún sitio que...

Jeff Hawkins
Déjame que te explique otro término que utilizamos: las creencias. Cuando el cerebro está expuesto al mundo, construye un modelo del mundo, y ese modelo es básicamente cómo funciona el mundo, y esto genera unas creencias. Todos los seres humanos compartimos algunas creencias. Compartimos unas creencias sobre el sol, sobre la gravedad, sobre alimentos, sobre el agua y sobre rutinas de cada día. Pero cuando vamos subiendo en ideas abstractas en la jerarquía del córtex las creencias difieren, formamos creencias distintas, cada religión tiene un conjunto diferente de creencias, y no todas pueden ser correctas. También podemos formar creencias falsas que a veces denominamos estereotipos, pero es muy fácil para los humanos crear las falsas creencias. El algoritmo que nos ha llevado a conocer el mundo y nos permite hacer predicciones, y ser creativos, puede formar creencias falsas del mundo, y por lo tanto puede crear predicciones falsas y llevarnos a hacer cosas malas. Y aquí es donde se produce la mayor parte de los conflictos del mundo, y es porque todos tenemos un conjunto diferente de creencias en la parte superior, mientras que todos compartimos las básicas: los hombres y las mujeres hacemos lo mismo, pero es en la parte superior donde tenemos creencias fundamentalmente diferentes sobre cómo funciona el mundo.

Eduard Punset
Vamos a volver a las máquinas, a las máquinas inteligentes. La gente todavía tiene miedo a las máquinas inteligentes: ¿por qué?

Jeff Hawkins
Tiene historia: cuando se construyo la máquina de vapor se le tenía miedo, era como un milagro, una máquina que se mueve como un cuerpo, y eso da miedo. Cuando se inventó el ordenador, se pensó que iba a sobrepasar el comportamiento humano, y esto no sucedió; la gente tiene el mismo miedo de las máquinas inteligentes, creen que serán igual que los humanos. Es como de ciencia ficción y como si fueran un robot, como R2-D2 en Star Wars o algo así. Creen que será como un robot humano, pero no será así, las máquinas inteligentes tienen una apariencia muy aburrida y es posible que sean como ordenadores pero puede que estén pensando o que sientan el mundo: tampoco tendrán hambre, o querer tener sexo, o protegerse a si mismas, o querer reproducirse a si mismas, de la misma manera que los ordenadores no son así, ni las máquinas de vapor tampoco lo son. La gente se pone nerviosa porque se está recreando la humanidad, pero yo creo que es un error, y en realidad no tengo ningún deseo de hacerlo; sin embargo, entender cómo funciona el contexto y recrearlo creo que traerá grandes beneficios, que será muy bueno.

Eduard Punset
¿Cómo cuál? ¿Qué hacen las máquinas inteligentes? Trabajan más rápidamente que el cerebro, esto es seguro.

Jeff Hawkins
Trabajan más rápidamente que el cerebro y pueden ser más grandes y más inteligentes que el cerebro. Pero déjame que ponga en dos categorías lo que pueden hacer las máquinas inteligentes. La primera categoría es la obvia pero un poco más aburrida. Las máquinas pueden hacer lo que hacen los humanos, se pueden construir máquinas que conduzcan coches, o que miren las cámaras de seguridad para vigilar lo que sucede; se pueden construir máquinas que hagan traducción automática de idiomas, etc.: cosas que pueden hacer los humanos, pero que no son realmente interesantes. Hay una serie de cosas que tradicionalmente el mundo de la inteligencia artificial ha intentado hacer. Para mí lo que es más interesante de construir córtex como los del cerebro es que hagan cosas que los
humanos tienen problemas para hacer, como lo que hemos hablado antes de innovar en nuevos sensores. O, por ejemplo, los humanos no son muy buenos en física o en matemáticas, nos cuesta mucho y necesitamos mucho tiempo para ser buenos en eso, y creo que podemos construir máquinas que puedan ser realmente excelentes. Lo que es interesante, y de hecho es lo que motiva todo el trabajo que hago, es construir una máquina que nos ayude a entender cómo funciona todo el mundo, que responda a grandes preguntas como son la naturaleza del tiempo y el espacio, o de dónde viene el universo y a dónde va. Estas son para mi preguntas muy interesantes, y creo que construyendo unas máquinas muy inteligentes que se concentren en estos problemas –faltan algunos años para que suceda pero estoy seguro que sucederá– seremos capaces de tener un entendimiento mayor del mundo y de lo que realmente sucede aquí, y eliminar algunas de las creencias falsas.

sábado, 8 de marzo de 2008

Genetic programming

Genetic programming

Genetic programming (GP) is an evolutionary algorithm based methodology inspired by biological evolution to find computer programs that perform a user-defined task. It is a specialization of genetic algorithms where each individual is a computer program. Therefore it is a machine learning technique used to optimize a population of computer programs according to a fitness landscape determined by a program's ability to perform a given computational task. The roots of GP begin with the evolutionary algorithms first utilized by Nils Aall Barricelli in 1954 as applied to evolutionary simulations but evolutionary algorithms became widely recognized as optimization methods as a result of the work of Ingo Rechenberg in the 1960s and early 1970s - his group was able to solve complex engineering problems through evolution strategies (1971 PhD thesis and resulting 1973 book). Also highly influential was the work of John Holland in the early 1970s, and particularly his 1975 book. The first results on the GP methodology were reported by Stephen F. Smith (1980)[1] and Nichael L. Cramer (1985),[2]. In 1981 Forsyth reported the evolution of small programs in forensic science for the UK police. John R. Koza is a main proponent of GP and has pioneered the application of genetic programming in various complex optimization and search problems [3].

GP is very computationally intensive and so in the 1990s it was mainly used to solve relatively simple problems. But more recently, thanks to improvements in GP technology and to the exponential growth in CPU power, GP produced many novel and outstanding results in areas such as quantum computing, electronic design, game playing, sorting, searching and many more.[4] These results include the replication or development of several post-year-2000 inventions. GP has also been applied to evolvable hardware as well as computer programs. There are several GP patents listed in the web site [5].

Developing a theory for GP has been very difficult and so in the 1990s GP was considered a sort of outcast among search techniques. But after a series of breakthroughs in the early 2000s, the theory of GP has had a formidable and rapid development. So much so that it has been possible to build exact probabilistic models of GP (schema theories and Markov chain models).[citation needed]

Contents

[hide]

Chromosome representation

A function represented as a tree structure
A function represented as a tree structure


GP evolves computer programs, traditionally represented in memory as tree structures. Trees can be easily evaluated in a recursive manner. Every tree node has an operator function and every terminal node has an operand, making mathematical expressions easy to evolve and evaluate. Thus traditionally GP favors the use of programming languages that naturally embody tree structures (for example, Lisp; other functional programming languages are also suitable).

Non-tree representations have been suggested and successfully implemented, such as the simpler linear genetic programming which suits the more traditional imperative languages [see, for example, Banzhaf et al. (1998)]. The commercial GP software Discipulus,[6] uses AIM, automatic induction of binary machine code[7] to achieve better performance.[8] MicroGP[9] uses a representation similar to linear GP to generate programs that fully exploit the syntax of a given assembly language.

Genetic operators

Crossover

The main operators used in evolutionary algorithms such as GP are crossover and mutation. Crossover is applied on an individual by simply switching one of its nodes with another node from another individual in the population. With a tree-based representation, replacing a node means replacing the whole branch. This adds greater effectiveness to the crossover operator. The expressions resulting from crossover are very much different from their initial parents.

The following code suggests a simple implementation of individual deformation using crossover:

individual. Children[randomChildIndex] = otherIndividual.Children[randomChildIndex];

Mutation

Mutation affects an individual in the population. It can replace a whole node in the selected individual, or it can replace just the node's information. To maintain integrity, operations must be fail-safe or the type of information the node holds must be taken into account. For example, mutation must be aware of binary operation nodes, or the operator must be able to handle missing values.

A simple piece of code:

individual. Information = randomInformation;

or

individual = generateNewIndividual;

Meta-Genetic Programming

Meta-Genetic Programming is the proposed meta learning technique of evolving a genetic programming system using genetic programming itself. [10]. It suggests that chromosomes, crossover, and mutation were themselves evolved, therefore like their real life counterparts should be allowed to change on their own rather than being determined by a human programmer. Meta-GP was proposed by Jürgen Schmidhuber in 1987 [11]; it is a recursive but terminating algorithm, allowing it to avoid infinite recursion.

Critics of this idea often say this approach is overly broad in scope. However, it might be possible to constrain the fitness criterion onto a general class of results, and so obtain an evolved GP that would more efficiently produce results for sub-classes. This might take the form of a Meta evolved GP for producing human walking algorithms which is then used to evolve human running, jumping, etc. The fitness criterion applied to the Meta GP would simply be one of efficiency.

For general problem classes there may be no way to show that Meta GP will reliably produce results more efficiently than a created algorithm other than exhaustion. The same holds for standard GP and other search algorithms, of course.


Otra referencia Util ( tut GP)


Genetic programming is a branch of genetic algorithms. The main difference between genetic programming and genetic algorithms is the representation of the solution. Genetic programming creates computer programs in the lisp or scheme computer languages as the solution. Genetic algorithms create a string of numbers that represent the solution. Genetic programming, uses four steps to solve problems:
1) Generate an initial population of random compositions of the functions and terminals of the problem (computer programs).

2) Execute each program in the population and assign it a fitness value according to how well it solves the problem.

3) Create a new population of computer programs.
i) Copy the best existing programs
ii) Create new computer programs by mutation.
iii) Create new computer programs by crossover(sexual reproduction).

4) The best computer program that appeared in any generation, the best-so-far solution, is designated as the result of genetic programming [Koza 1992].


Figure 1: genetic programming Flowchart.



Fitness Function
The most difficult and most important concept of genetic programming is the fitness function. The fitness function determines how well a program is able to solve the problem. It varies greatly from one type of program to the next. For example, if one were to create a genetic program to set the time of a clock, the fitness function would simply be the amount of time that the clock is wrong. Unfortunately, few problems have such an easy fitness function; most cases require a slight modification of the problem in order to find the fitness.


Gun Firing Program
A more complicated example consists of training a genetic program to fire a gun to hit a moving target. The fitness function is the distance that the bullet is off from the target. The program has to learn to take into account a number of variables, such as wind velocity, type of gun used, distance to the target, height of the target, velocity and acceleration of the target. This problem represents the type of problem for which genetic programs are best. It is a simple fitness function with a large number of variables.

Water Sprinkler System
Consider a program to control the flow of water through a system of water sprinklers. The fitness function is the correct amount of water evenly distributed over the surface. Unfortunately, there is no one variable encompassing this measurement. Thus, the problem must be modified to find a numerical fitness. One possible solution is placing water-collecting measuring devices at certain intervals on the surface. The fitness could then be the standard deviation in water level from all the measuring devices. Another possible fitness measure could be the difference between the lowest measured water level and the ideal amount of water; however, this number would not account in any way the water marks at other measuring devices, which may not be at the ideal mark.

Maze Solving Program
If one were to create a program to find the solution to a maze, first, the program would have to be trained with several known mazes. The ideal solution from the start to finish of the maze would be described by a path of dots. The fitness in this case would be the number of dots the program is able to find. In order to prevent the program from wandering around the maze too long, a time limit is implemented along with the fitness function.


Functions and Terminals
The terminal and function sets are also important components of genetic programming. The terminal and function sets are the alphabet of the programs to be made. The terminal set consists of the variables and constants of the programs. In the maze example, the terminal set would contain three commands: forward, right and left. The function set consists of the functions of the program. In the maze example the function set would contain: If "dot" then do x else do y. In the gun firing program is the terminal set would be composed of the different variables of the problem. Some of these variables could be the velocities and accelerations of the gun, the bullet and target. The functions are several mathematical functions, such as addition, subtraction, division, multiplication and other more complex functions.

Crossover Operation
Two primary operations exist for modifying structures in genetic programming. The most important one is the crossover operation. In the crossover operation, two solutions are sexually combined to form two new solutions or offspring. The parents are chosen from the population by a function of the fitness of the solutions. Three methods exist for selecting the solutions for the crossover operation.

The first method uses probability based on the fitness of the solution. If is the fitness of the solution Si and

is the total sum of all the members of the population, then the probability that the solution Si will be copied to the next generation is [Koza 1992]:


Another method for selecting the solution to be copied is tournament selection. Typically the genetic program chooses two solutions random. The solution with the higher fitness will win. This method simulates biological mating patterns in which, two members of the same sex compete to mate with a third one of a different sex. Finally, the third method is done by rank. In rank selection, selection is based on the rank, (not the numerical value) of the fitness values of the solutions of the population [Koza 1992].

The creation of the offsprings from the crossover operation is accomplish by deleting the crossover fragment of the first parent and then inserting the crossover fragment of the second parent. The second offspring is produced in a symmetric manner. For example consider the two S-expressions in Figure 2, written in a modified scheme programming language and represented in a tree.


Figure 2: Crossover operation for genetic programming. The bold selections on both parents are swapped to create the offspring or children. (The child on the right is the parse tree representation for the quadratic equation.)



Figure 3: This figure illustrates one of the main advantages of genetic programming over genetic algorithms. In genetic programming identical parents can yield different offspring, while in genetic algorithms identical parents would yield identical offspring. The bold selections indicate the subtrees to be swapped.


An important improvement that genetic programming displays over genetic algorithms is its ability to create two new solutions from the same solution. In the Figure 3 the same parent is used twice to create two new children.

Mutation
Mutation is another important feature of genetic programming. Two types of mutations are possible. In the first kind a function can only replace a function or a terminal can only replace a terminal. In the second kind an entire subtree can replace another subtree. Figure 4 explains the concept of mutation:


Figure 4: Two different types of mutations. The top parse tree is the original agent. The bottom left parse tree illustrates a mutation of a single terminal (2) for another single terminal (a). It also illustrates a mutation of a single function (-) for another single function (+). The parse tree on the bottom right illustrates a the replacement of a subtree by another subtree.



Summary
Genetic programming is much more powerful than genetic algorithms. The output of the genetic algorithm is a quantity, while the output of the genetic programming is a another computer program. In essence, this is the beginning of computer programs that program themselves.

Genetic programming works best for several types of problems. The first type is where there is no ideal solution, (for example, a program that drives a car). There is no one solution to driving a car. Some solutions drive safely at the expense of time, while others drive fast at a high safety risk. Therefore, driving a car consists of making compromises of speed versus safety, as well as many other variables. In this case genetic programming will find a solution that attempts to compromise and be the most efficient solution from a large list of variables.

Furthermore, genetic programming is useful in finding solutions where the variables are constantly changing. In the previous car example, the program will find one solution for a smooth concrete highway, while it will find a totally different solution for a rough unpaved road.


REFERENCES

Koza, John R. 1992. Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: The MIT Press.

Cramer, Nichael Lynn: "A Representation for the Adaptive Generation of Simple Sequential Programs", Proceedings, International Conference on Genetic Algorithms and their Applications, July 1985 [CMU], pp183-187.


martes, 30 de octubre de 2007

Tema de Tesis / Modelos de Transporte

Modelos de Transporte

El tema de investigación es:
"La interacción entre modelos de equilibrio simultaneo y modelos microscópicos de transporte"

1.- ¿Que es un modelo de transporte?
2.- ¿Que es modelo de equilibrio simultaneo?
3.- ¿Que es modelo microscópico de transporte?
4.- ¿Cuales son las similitudes y diferencias?

Hipótesis de Trabajo:

"Es posible el desarrollo de un modelo de interacción entre modelos de datos agregados y modelos de simulación de comportamiento microscópico en el área del transporte urbano, que permita identificar los puntos de conflicto e intervenir sobre ellos."

El campo de trabajo:

a.- Espacio físico:
Un sector de la ciudad de Santiago, sobre el eje de la avenida Alameda, en un punto de alta densidad de uso, p.e. Plaza Italia, Santa Rosa, Estación Central o Las Rejas.
(Se considerará como área de modelamiento a las vías y al espacio público peatonal.)

b.- Movimientos a ser observados:
Movimientos vehiculares particulares y públicos.
Metro / Buses / Colectivos y Taxis
Movimientos peatonales ( interconexión / transbordo / espera ).

Objetivos del modelo:

a.- Análisis del comportamiento del peatón al hacer uso del espacio público, en relación con los medios de transporte tanto públicos como privados.

b.- Predicción de zonas de congestión y saturación, que causen colapsos en el sistema de transporte.

c.- Evaluación de reconfiguración del espacio público con el fin de optimizar el uso por parte del peatón, en momentos de congestión y saturación.

el, ¿como?

La lógica (utópica..) , de funcionamiento del sistema corresponderá a la siguiente:
  • El sistema desarrollado recibirá desde el modelo de transporte los datos agregados de origen destino esperados para una zona.
  • Mediante una aplicación SIG (sistema de información geográfica), se "mapearan" estos datos, es decir, se vincularán con posiciones en el plano.
  • Se definirá un campo de movimiento (espacio público) en el SIG, mediante la sobreposición sucesiva de "buffers" asociados a diferentes entidades (predios, ejes de calles, plazas, etc,). Y mediante operaciones booleanas se obtendrá un cobertura correspondiente al área en estudio.
  • Es este espacio de movimiento, se crearán a partir de los datos de entrada, ACTORES (peatones), los que mediante programación basada en agentes ( o autómatas celulares), se desplazarán por el espacio.
  • Se utilizará una interfaz de entrada para los parámetros de comportamiento de los actores (o agentes).
  • Mediante la variación de parámetros o la alteración de las condiciones de espacio (SIG) , se generarán escenarios de uso del espacio público en diferentes condiciones, y se evaluarán alternativas de configuración de éste para situaciones de saturación.
  • Se comparará la experiencia realizada con datos empíricos es los puntos críticos de la ciudad.

lunes, 22 de octubre de 2007

CATA de Siete!!



Catalina ya tiene siete meses!




miércoles, 10 de octubre de 2007

NPeame este problema!!

Para explicar esto ...
1.- Imagina una secuencia de puntos en el espacio, supongamos de momento un espacio bidimensional, osea una superficie.
2.- Iniciemos la tarea con 2 puntos. Encontrar el camino mas corto entre ellos es obvio, no?
3.- Aumentemos la cantidad de puntos, digamos 4, distribuídos aleatoriamente. Para encontrar el camino mas corto basta con ser un buen observador y de ser necesario una regla para medir el largo total de la linea dibujada. Algunas opciones:


Al ser solo cuatro puntos resulta relativamente facil estimar las opciones, basta con partir de 1 y experimentar, (y que la hipotenusa es mas corta que la suma de los catetos..). Pero si quisieramos estar seguros de que el camino elegido es el mas corto, deberiamos medir todas las opciones. ¿Cuantas son?.


Si partimos desde cada punto, tendremos cuatro inicios, siendo en todos los casos las siguientes opciones solo tres, ya que el primer punto está seleccionado, y luego dos, y por último sólo el punto que queda. Por lo tanto: Si tenemos 4 puntos, el total de opciones correponde a 4 x 3 x 2 x 1 , o 4! (factorial), y las opciones de circuito corresponderán a n-1! (siendo n = el número de puntos por los cuales se debe pasar), es decir 3! = 6.

Es decir 24 alternativas de recorrido por estos cuatro puntos, algunas de las cuales se enmarcan en un mismo ciclo partiendo desde otro de los tres puntos disponibles. Y ya que cada ciclo se compone de 4 lineas, y que el total de lineas posibles de utilizar al realizar un circuito corresponde a 6, tenemos solo 3 ciclos posibles no redundantes, (nos olvidaremos de esto por el momento).


http://www.tsp.gatech.edu/methods/opt/subtour.htm


4.- Aumentemos los puntos a 10!!, que hacemos? Una opcion es comenzar por cualquiera y elegir el mas cercano cada vez y luego unirlo. Pero como saber que es la mejor opcion? Para estar seguros deberíamos partir de todos los puntos repitiendo el proceso antes nombrado y obtener un largo total para cada uno...lo cual puede ser un poco lento. Las opciones de recorridos corresponderían a 10!, es decir 3.628.800 posibles recorridos! Aún es posible calcularlo pero se deberá optar por un sistema diferente: identificar lo circuitos redundantes para así limitar la cantidad de mediciones. Sin embargo si demoráramos 1 segundo en medir la distancia entre cada punto al revisar el recorrido, nos tomaría 60.480 minutos, es decir 1008 horas, es decir 42 días.

http://www.tsp.gatech.edu/methods/opt/subtour.htm

Parece una cantidad enorme de tiempo para solucionar un problema para el cual una solución "posible" es muy fácil de descubrir. Una solucion "optima" nos tomará 42 días!!!


5.- Digamos que los puntos son ahora 50, que hacemos ? como podemos obtener la solucion en un tiempo razonable, (es decir en menos que la edad del universo...) El número total de recorridos posibles es 50!, es decir: 3,041 x 1064 ( por 10 elevado a 64). Si hacemos el mismo cálculo de tiempo anterior, es decir 1 segundo por medición, el resultado sería: 5,069 x 1062 minutos, 8,448 x 1060 horas, 3,520 x 1059 dias, 9,644 x 1056 años !! Parece bastante no?,


El proyecto WMAP de la NASA estimó la edad del Universo en:
(13.7 ± 0,2) × 109 años.




... primero, debemos demorar menos en medir, es decir ¡usar un computador que mida!, por lo tanto podríamos demorar un nanosegundo en medir cada distancia... sorprendentemente esto no cambia mucho el problema, solo se consigue bajar el número de años en un par de ordenes de magnitud, pero de todos modos, el tiempo es demasiado.


Este es un buen problema,
Obtener una solucion, no necesariamente la mejor, solo una posible y válida, es muy facil. Pero obtener la mejor solucion puede requerir de un tiempo gigantesco. Esto es lo que se llama el problema del vendedor viajero (TSP, Traveling Salesman Problem), y es un problema que requiere de soluciones no convencionales en cuanto a matemáticas.
http://www.tsp.gatech.edu/

Es lo que se llamaría: "problema NP hard"

A problem is NP-hard if an algorithm for solving it can be translated into one for solving any NP-problem (nondeterministic polynomial time) problem. NP-hard therefore means "at least as hard as any NP-problem," although it might, in fact, be harder.

DATO !!! : revise

http://fbim.fh-regensburg.de/~saj39122/jfroehl/diplom/e-index.html

(redes neuronales aprendiendo plano de union minimo)

OPCION:
Optimización mediante procesos Heurísticos, esto es, mediante procesos de aproximación iterativa (es decir mediante intentos sucesivos). Esto nos permite buscar en el universo de soluciones posibles una buena (no necesariamente la mejor)

conceptos:
(voy a completar esto...)
a.- Optimo local / Optimo Global
b.- Convergencia en la optimización
c.- Algoritmos de búsqueda Heurística
d.- Algoritmos Genéticos
e.- Algoritmos de Tabú Search
f.- Algoritmos de Simulated Annealing
g.- Metodos de optimización y las metaforas del pensamiento diseñador en la Arquitectura

desarrollo....

a.- Optimo local / Optimo Global







Imagina que todas las medidas de distancia entre todas las posibles combinatorias de los puntos se grafican en un plano, en el que la altura (eje z) representa el largo total, esto correspondería al universo de soluciones en el que buscaremos. Un detalle es que obtener la representacion del universo de soluciones para un problema dado corresponde a obtener todas las soluciones posibles, y en el caso de los problemas NP el tiempo requerido para esto es demasiado. Por lo tanto solo podemos especular sobre las posibilidades de conformacion de este plano.

El optimo global corresponderá al punto mas bajo de este plano (idealmente solo uno), y será este el principal objetivo de busqueda. Las opciones de conformacion de este plano:





- Un valle unico y continuo desde los bordes: esto implica una solucion que puede obtenerse buscando en las cercanías de cualquier solucion y seleccionandola mejor vecina repetidas veces, y cuando no se encuentre una mejor, ya se estará en el fondo (optimo global). Atencion que se deberá cuidar el umbral de busqueda ya que se podrñia generar un salto muy grande en la seleccion del vecino y así oscilar en torno al optimo sin seleccionarlo nunca.

- Una secuencia de valles de diferentes tamaños, distribuidos aleatoriamente entre los cuales uno es el mayor. Esta corresponde a la situación clasica de este tipo de problemas, y cada uno de los valles es lo que se identifica por optimos locales, a los que se llega mediante el proceso de comparación con vecinos, pero de los que es imposible salir ya que esto requeriría seleccionar una solucion peor que la que se tiene durante una secuencia de iteraciones para lograr superar los bordes del valle.

- Una "caja de huevos", la pesadilla de la optimización. Todos los valles son equivalentes, todos son optimos locales y globales al mismo tiempo. Y será imposible saber si hemos llegado a un optimo global por comparación ya que todo sera igual...!!

b.- Convergencia en la optimización



Algo de matemáticas...



...para evaluar un resultado necesitamos sumar el total de lineas que definen el camino a recorrer, para esto debemos obtener la diferencia entre un punto y el siguiente, descompuesto en lso componentes X e Y (las coordenadas cartesianas de cada punto y el cálculo de la distancia euclidiana),




D, corresponde a la distancia total

n, es el número de puntos por los cuales se debe pasar



X e Y, son las coordenadas de cada punto




Esto es lo que se considera la función de evaluación del resultado, es decir la medida de "optimización" conseguida, y el objetivo será que el valor obtenido sea el mínimo.


El grafico anterior correponde a la minimización del resultado en un proceso de optimización, realizado para el curso "Optimizacion en Ingeniería" del magister de informática del DIINF USACH, dictado por el profesor Victor Parada. En este proceso se utilizó la heurística de tabú search, y podemos ver que al inicio el valor disminuye rápidamente, para luego estabilizarse en un valor aproximadoa 190.000, luego de 6300 iteraciones. Luego de esto, el valor baja muy lentamente y se puede detener la búsqueda. Es importante hacer notar que 6300 iteraciones, es probablemente "infinitamente" menor al número total de combinatoria de soluciones al problema, y por lo tanto el tiempo empleado en obtener la solucion fue relativamente poco (menos que la edad del universo entodo caso).

Cata ya tiene 6 meses!!!

Ya tiene 6 meses,




y esta empezando a comer comida solida!!!





Catalinda!!! esta mas grande!!!