COMPUTACIÓN EVOLUTIVA (CE) INTRODUCCIÓN

Angel García Baños Escuela de Ingeniería de Sistemas y Computación Universidad del Valle 04 de febrero de 2008

PRESENTACIÓN DEL CURSO

Objetivos ■

Existen problemas tan complejos que no hay ningún algoritmo determinista que los solucione en un tiempo razonable. En ese caso hay multitud de técnicas que se emplean para lograr una solución suficientemente buena, aunque quizás no sea la mejor posible.

■

El objetivo del curso es aprender a emplear técnicas de búsqueda de soluciones a problemas complejos (incluido el diseño automático de software) y basadas en el concepto de la evolución: Algoritmos Genéticos, Programación Genética, Estrategias Evolutivas, Programación 3 AGBEvolutiva, etc.

Objetivos ■

■

Se mostrarán así mismo una variedad de temas anejos, que sirven de plataforma para desarrollar estas técnicas, como los autómatas celulares, la teoría de juegos, los dilemas sociales, las hormigas artificiales y los virus de software. Se presentarán también los aspectos teóricos que justifican estas técnicas, así como los que muestran sus limitaciones.

AGB

4

Contenido del curso ●

INTRODUCCIÓN A LA EVOLUCIÓN. El fracaso de la AI clásica. La complejidad. La naturaleza como inspiradora de sistemas.

●

TÉCNICAS GENERALES (CON PROPIEDADES Y EJEMPLOS): ● ● ● ● ● ● ●

●

SIMULATED ANNEALING (SA). ALGORITMOS GENÉTICOS (GAs). PROGRAMACIÓN GENÉTICA (GP). PROGRAMACIÓN EVOLUTIVA (EP). ESTRATEGIAS EVOLUTIVAS (ES). GRAMÁTICAS EVOLUTIVAS (EG). PROGRAMACIÓN POR EXPRESIÓN DE GENES (GEP).

TÉCNICAS ESPECÍFICAS: ●

● ●

MÁQUINAS AUTOREPLICANTES. Entropía y reproducción. Autómatas celulares. INTRODUCCIÓN A LA TEORÍA DE JUEGOS. El dilema del prisionero. VIRUS (PROGRAMAS AUTOREPLICANTES). AGB

5

Contenido del curso ■

FUNDAMENTOS TEÓRICOS DE LA COMPUTACIÓN EVOLUTIVA: – FUNDAMENTOS / APLICACIONES: ■ TEORIA DE JUEGOS ■ MÁQUINAS AUTOREPLICANTES ■ TEORIA DE LA COMPLEJIDAD ■ CAOS ■ FRACTALES – LIMITACIONES: ■ TEOREMA DE GÖDEL ■ PROBLEMA DE LA PARADA ■ PROBLEMAS NP ■ TEOREMA de NO-FREE-LUNCH

AGB

6

INTRODUCCIÓN

Introducción a la IA ■

Algunas técnicas habituales de Inteligencia Artificial (IA): – – – –

■

Redes neuronales Sistemas Expertos Lógica Difusa Técnicas heurísticas

Algunos lenguajes prometedores para la IA: – LISP – PROLOG

AGB

8

Introducción a la IA ■

Algunos logros de la IA: – – – –

■ ■

Eliza (análisis de lenguaje en un entorno psiquiátrico) SHRDLU (análisis de lenguaje en un entorno geométrico) Deep Blue (ajedrez) Sistemas Expertos en estructuras moleculares (DENDRAL), medicina, prospecciones minerales, etc.

Pero... ¿es ello inteligencia? Test de TURING

AGB

9

Introducción a la IA ■

El “fracaso” de la AI clásica. – Teorema de Gödel: todo sistema axiomático suficientemente complejo: ■ o es incompleto (no se pueden deducir de él todas las verdades, no puede trascenderse, no es inteligente) ■ o mantiene contradicciones internas (se derrumba)

■

Los investigadores se propusieron una meta mas modesta: en vez de AI (Artificial Intelligence), buscar AL (Artificial Life) ... y se encontraron con AI.

AGB

10

Introducción a la IA ■

Cuales son las características de un problema de IA: – Si está resuelto, ya no es de IA :) :) :) – Problema directo: dada una entrada y un algoritmo que responda en un tiempo razonable (P), averiguar la salida. Ejemplo: 8 = x + 3; – Problema de IA: dada una entrada y una salida deseada, averiguar el algoritmo. Pero una vez encontrado, el problema se vuelve directo. El proceso de búsqueda del algoritmo si es de IA. Ejemplo: Ajedrez.

■

Problemas clásicos de IA: – Knapsack – Viajero, etc. AGB

11

Evolución biológica ■ ■ ■ ■

La evolución de las especies (Darwin) La supervivencia del más apto (Darwin) Equilibrio puntuado (Jay Gould). Neodarwinismo (Hamilton, Richard Dawkins ==> “El gen egoísta”)

■ ■ ■

Pero nosotros vamos a emplear cosas parecidas a la biología aunque no exactamente iguales: “SISTEMAS BIOINSPIRADOS”

AGB

12

Evolución biológica ■

■ ■

Las características profundas de diversos entornos son muy similares, por lo que muy frecuentemente la evolución lleva al mismo resultado en ellos. Por ejemplo, el ojo ha sido inventado mas de 40 veces de forma independiente (moluscos, artrópodos, vertebrados...). Lo mismo puede decirse de la invención del vuelo. También las etologías (comportamiento) son profundamente convergentes: muchos animales se inflan para aparentar mas tamaño cuando sufren alguna agresión. AGB

13

Evolución biológica ■

Sin embargo, la evolución biológica no parece perseguir ninguna finalidad. De hecho, hay avances y retrocesos. – Caso típico: el caballo. – Y también los peces mamíferos: proceden de peces que salieron a tierra y luego se volvieron a regresar al agua (ballena, delfín...).

■

La evolución biológica ni siquiera tiende a buscar siempre una mayor complejidad. Parece un paseo aleatorio.

AGB

14

Evolución biológica ■

Actualmente se entiende que la evolución ha operado en todos los niveles: ■ ■ ■ ■ ■ ■ ■ ■

■

■

??? Químico Moleculas gigantes (ARN, and) Celular Organismos pluricelulares Cerebro (inteligencia) Sociedades (hormigas, humanos) ???

Hay teorías más especulativas, que suponen que todo el universo es resultado de la evolución. Libro: John Maynard Smith “Ocho hitos de la 15 AGB evolución”.

Teoría de la complejidad ■

■ ■

Usaremos técnicas evolutivas cuando no se conoce un algoritmo eficiente que resuelva el problema dado. Ello ocurre con problemas complejos. Pero ¿cómo caracterizar estos problemas? ¿Que es la complejidad? ¿Como medirla?

AGB

16

Teoría de la complejidad ■

■

Como ingenieros estamos acostumbrados a buscar soluciones aplicando métodos estructurados (procedural, OO), donde unos “ladrillos” básicos se apilan para formar una “pared”, varias de ellas construyen una “casa”, etc. El mundo real no es estructurado: – – – – – –

Biología. Sistemas económicos. Sistemas sociales. Pero también: Química (reacciones reloj) Física (gravedad clásica con 3 cuerpos). AGB

17

Teoría de la complejidad ■

Nuevas herramientas matemáticas para abordar la complejidad: – Teoría de la complejidad, teoría general de sistemas, sistemas dinámicos, sistemas no-lineales, vida artificial... – Teoría del caos – Fractales

AGB

18

Citas acerca de la complejidad ■

Occam: “Si dos fórmulas de distinta longitud explican un mismo fenómeno con igual mérito, la mas corta es la verdadera”.

■

Whitehead: “La ciencia debe buscar las explicaciones mas simples a los fenómenos mas complejos”.

■

Sackman: “Los diseñadores muy buenos de software producen las estructuras mas rápidas, pequeñas, simples y limpias y con menor esfuerzo”.

AGB

19

Citas acerca de la complejidad ■

■

Schumacher: “Si el ingeniero falla en estudiar metainformática, o, peor aún, si permanece inconsciente del hecho de que hay límites a la aplicabilidad de la computación, es probable que caiga en una clase de error similar a la de ciertos teólogos medievales que intentaban establecer cuestiones de física por medio de citas bíblicas”. Bunge: “El técnico no puede evitar el contagio filosófico, ya que maneja ideas que presuponen conceptos filosóficos: hace filosofía sin saberlo. Y, puesto que la hace, mejor sería que la hiciese bien. Para eso tendría que aprender algo de filosofía”. AGB

20

¿Que es la Vida Artificial? ■

En el mundo en que vivimos, muchas veces la complejidad surge espontáneamente, a partir de sistemas muy simples. A ello se le llama: – Comportamiento emergente: al interactuar entre si entidades similares con comportamiento muy simple, puede surgir un comportamiento mucho mas complejo que no estaba programado en las entidades simples (hormigas, dilemas sociales, etc).

■

El todo es mas que la suma de las partes. – Fin del REDUCCIONISMO (Descartes). – Aparición del HOLISMO (no debe interpretarse como algo mágico: simplemente, los fenómenos no-lineales dan lugar a comportamientos difíciles de predecir). AGB

21

VIDA es INTELIGENCIA

■

■

Vida es adaptación al entorno ⇒ APRENDIZAJE

■

Por ello, Vida es Inteligencia.

■

La inteligencia NO es una cuestión de TODO o NADA sino gradual: piedra, martillo, computador, delfín, persona...

■

La inteligencia se basa en poder predecir el futuro (APRENDIZAJE), anticiparlo, adaptarse y sobrevivir.

■

El universo es bastante predecible (el sol sale periódicamente...). Los organismos vivos intentan predecirlo para sacar ventaja de él. Si el universo fuera completamente incorrelado no habría vida.

Por evolución emergieron estructuras complejas autoorganizadas, capaces de reproducirse. Cosas vivas. Y después por evolución se fueron haciendo más inteligentes, es decir, capaces de predecir mejor suAGB entorno, su futuro, etc.

22

La teoría de la evolución ■

También evoluciona la teoría de la evolución: – Darwinismo = selección del más adaptado. ■ ■ ■ ■

Competencia. Lucha (gana el más fuerte). La naturaleza son garras y dientes chorreando sangre. El mundo es cruel pues lo domina el más fuerte.

– Neodarwinismo = Darwinismo + Teoría de juegos ■

■

■

La competencia sigue existiendo, pero ahora nos damos cuenta que la cooperación es mucho más importante. Sobreviven los que se apoyan mútuamente cooperando entre sí. Y crean nuevas estructuras (células eucariotas, seres multicelulares, grupos sociales, económicos y culturales...). El mundo lo fabrica y domina el más inteligente.

AGB

23

Condiciones para que haya EVOLUCIÓN (Natural o Artificial) ■

Sistemas evolutivos: – Población (conjunto) de entes – que se reproducen (sexual o asexualmente) – con variabilidad (surgen diferencias debidas a la reproducción sexual o a mutaciones) – sometidos a una presión selectiva (usualmente, comparten un recurso vital escaso)

AGB

24

Condiciones para que haya EVOLUCIÓN (Natural o Artificial) ■

¿Por qué se necesita variabilidad? – Si todos los entes son iguales, hay estancamiento. Las teorías actuales evolutivas hablan de equilibrios puntuados (la evolución no es continua, sino a saltos). Actualmente estamos en un punto de “estancamiento”.

■

¿Como se consigue la variabilidad? – Reproducción sexual: los hijos son heredan de ambos padres y, por tanto, son distintos a ambos. – Mutación: fallos de los mecanismos de reproducción. Aleatorios. Usualmente produce peores individuos.

AGB

25

Sistemas que evolucionan ■

Sistemas biológicos: ■ ■ ■ ■ ■

■ ■ ■

célula órgano individuo población ecosistema

Sistemas químicos prebióticos Sistemas sociales La ciencia

AGB

26

Sistemas que evolucionan ■

La humanidad, que exhibe tres niveles de evolución (o quizás mas): – ontogenética (dentro del individuo): la mínima unidad es la neurona. El depósito de conocimiento es todo lo que el individuo conoce de su entorno. – philogenética (el linaje): la mínima unidad son los genes. El depósito es el genoma. – sociogenética (la sociedad): la mínima unidad son las ideas. El depósito es la cultura. Las ideas también se llaman “memes” (término acuñado por Richard Dawkins). ■

HOAX, etc

AGB

27

Somera introducción a los genes biológicos ■ ■

■ ■

■

■

El ADN de los cromosomas está compuesto por una secuencia de 4 nucleótidos llamados A, T, G, C (adenina, timina, guanina y citosina). Cada grupo de 3 nucleótidos forma un codón, que se traducirá a un aminoácido. Los aminoácidos son los bloques constitutivos de las proteínas. Cada proteína tendrá unas propiedades u otras dependiendo de cual sea su estructura tridimensional, lo que a su vez depende de que aminoácidos la componen y en que orden se encuentran. Hay algunos codones que son marcas de finalización. A la secuencia de codones terminada en una marca de finalización se le llama gen. Cada gen codifica una proteína. De modo que la secuencia de codones en el ADN es la que dirige la forma en que se construyen las proteínas, que a su vez determina las formas y funcionalidades del individuo. Al ADN se le llama genotipo, a las formas y funcionalidades del individuo se le llama fenotipo, y al paso del primero al segundo se le llama expresión. Hay un paso intermedio que consiste en sacar una copia (ligeramente distinta, con T --> Uracilo) del DNA,AGB cuyo resultado se llama ARNm. 28

Somera introducción a los genes biológicos ■

Richard Dawkins llama “fenotipo extendido” a características de comportamiento ligadas a un individuo. Por ejemplo: – La forma especial de un nido, asociada al pájaro que lo construyó. – El cambio de comportamiento de un huésped, asociado al parásito.

■

En muchos casos, los comportamientos son algoritmos preprogramados en los genes. Los humanos no somos la excepción a esto.

AGB

29

Somera introducción a los genes biológicos ■

El código genético es (casi) universal en el planeta Tierra: AMINOÁCIDO Alanina Cisteina Ácido Aspártico Ácido Glutámico Fenilalanina Glicina Histidina Isoleucina Lisina Leucina Metionina Asparagina Prolina Glutamina Arginina Serina Treonina Valina Triptofano Tirosina STOP

CODONES del ARNm GCA GCC GCG GCU UGC UGU GAC GAU GAA GAG UUC UUU GGA GGC GGG GGU CAC CAU AUA AUC AUU AAA AAG UUA UUG CUA CUC CUG CUU AUG AAC AAU CCA CCC CCG CCU CAA CAG AGA AGG CGA CGC CGG CGU AGC AGU UCA UCC UCG UCU ACA ACC ACG ACU GUA GUC GUG GUU UGG UAC UAU UAA UAG UGA

AGB

30

Somera introducción a los genes biológicos

AGB

31

Simplificaciones que se introducen en la computación evolutiva ■

Cualquier modelo en computación simplificación de la realidad biológica.

evolutiva

es

una

– En CE vamos a considerar un único cromosoma muy largo, en vez de tener los genes distribuidos por varios cromosomas más pequeños. – A veces, en CE, no hay EXPRESIÓN (el fenotipo es el mismo genotipo). – En CE se supone que un gen produce una característica, mientras que en biología, se sabe que los organismos mas evolucionados exhiben: ■ Pleiotropy (pleiotropía): un solo gen puede producir varias características del fenotipo: los gatos de ojos azules son sordos; los perros sin pelo tienen dientes defectuosos... ■ Polygeny (poligenía): una característica del fenotipo puede ser debida a la interacción de varios genes. AGB

32

Simplificaciones que se introducen en la computación evolutiva

CROMOSOMA

GEN

EXPRESIÓN

if(x > y + z) for(i = 0; i < 100; i++) z += y;

ALELOS de un GEN

GENOTIPO

AGB

FENOTIPO

33