1 13/Mar/06 Curso SCAEB UNIA- Sede Antonio Machado Baeza Juan J. Merelo Guervós [email protected] Depto. ATC Universidad de Granada Sistemas Complejos y Algoritmos Evolutivos

2 2 Real como la vida (artificial) misma ¿Qué es un sistema complejo? Emergencia Filo del Caos Autoorganización Vida Artificial Computación evolutiva

3 3 Lo simple y lo complejo The conception of law in relation to perception is not necessary for the conduct of War, because the complex phenomena of War are not so regular, and the regular are not so complex, that we should gain anything more by this conception than by the simple truth. And where a simple conception and language is sufficient, to resort to the complex becomes affected and pedantic (von Clausewitz, “On War”) El concepto de ley en relación con la percepción no es necesario para la dirección de la Guerra, porque los fenómenos complejos de la Guerra no son tan regulares, y los regulares no tan complejos, que podríamos ganar algo más por este concepto que por la simple verdad. Y donde un concepto y lenguaje simple son suficientes, acudir a lo complejo se convierte en afectado y pedante (von Clausewitz, sobre la guerra).

4 4 Un sistema complejo es...

5 5 No, venga, en serio ¿Esto es un sistema complejo?

6 6 Me pido el comodín del público ¿O quizás esto?

7 7 No existe una sola definición Para empezar, es un sistema. Es decir, un conjunto de elementos, con sus atributos e interacciones. No todos los sistemas son complejos. Sólo lo son si están compuestos de muchos elementos simples, que interaccionan entre si, y que dan lugar a un comportamiento colectivo en principio impredecible a partir del comportamiento individual.

8 8 Volvemos a empezar ¿Es esto un sistema complejo?

9 9 Un sistema complejo debe estar lejos del equilibrio Porque lejos del equilibrio suceden cosas interesantes Suelen ser sistemas con intercambio de materia y energía con el exterior Sol sobre la Tierra Conocimiento y materias primas en una economía. ATP y desechos en una célula

10 1010 Hay muchos sistemas fuera del equilibrio Las lenguas reciben influencia unas de otras, y de sus hablantes Los brokers de la bolsa reciben dinero para manejar. Las redes sufren flujos, y son dinámicas Nuevos nodos, nuevos enlaces

11 1 Pero todos están compuestos por átomos Los átomos, o elementos, o individuos,o agentes, son, para una escala determinada, el elemento más simple de un sistema complejo. Átomos/moléculas (en una reacción Belousov- Zabotinsky). Hogares (simulación anasazi). Agentes/brokers (modelo de Bolsa). Predadores/presas.

12 1212 Aunque los átomos no son muy atómicos Los átomos en cada nivel pueden descomponerse a un nivel inferior, pero para un nivel superior, no interesan. Cada hogar tiene individuos, pero para un modelo de civilización. Un agente de Bolsa tiene un hígado, un cerebro, y un bazo, pero no importa para vender y comprar. Los átomos se clasifican en clases, con características comunes y específicas de cada especie.

13 1313 Los átomos buscan parejas Los átomos/agentes interaccionan consigo mismo o con su contenedor Agentes de bolsa venden o compran. Las células absorben ATP y excretan productos de desecho. Las lenguas reciben influencias de otras, y viceversa. Las hormigas dejan caer y huelen feromonas, construyen hormigueros.

14 1414 Pero no lo hacen de forma lineal Las interacciones son no-lineales: como los resultados de las acciones se retroalimentan a quien lo hace, el sistema no se puede describir de forma lineal. Los efectos de una acción se amplifican, o inhiben. Caminos de feromonas dejados por las hormigas. La decisión de un agente de bolsa de vender o comprar lleva a una caida del mercado.

15 1515 Y al final surge algo

16 1616 ¿Qué emerge? Emergencia se refiere a la creación de un comportamiento inesperado o patrón en una simulación, usualmente sorprendente o contra- intuitivo. Débil: una propiedad es emergente si solo se puede lograr simulando el sistema. Fuerte: Proviene de propiedades de las partes. Es diferente de cualquiera de ellas. Tiene influencia en ellas.

17 1717 Para que no quede en el aire, un ejemplo Construcción de hormigueros: emerge a partir de los comportamientos de cada hormiga individual. Cuando se acaba, provoca otros comportamientos: construcción del nido para la reina, recogida de cadáveres, búsqueda de comida. Desarrollo de una persona a partir de un embrión de células indiferenciadas. Creación de ghettos en ciudades.

18 1818 Y todo esto, ¿cómo se come? La herramienta principal de los sistemas complejos es la simulación. Sistemas basados en agentes (AEB, agent based systems) o en individuo. Uso de herramientas de simulación Starlogo Squeak Swarm... Se observan comportamientos emergentes.

19 1919 El filo del caos La emergencia puede suceder a cualquier nivel ¿Cuando? Al filo del caos. Zona entre orden (estático, no hay ninguna sorpresa) y caos (dinámico, imposible de predecir). Se pueden predecir, pero las no-linealidades harán que sean peores según avanza el tiempo. Fluctuaciones pueden llevar a caos, a orden, o dejarlo seguir en el filo. La complejidad no es una característica, sino un estado.

20 2020 En el filo del caos está la diversión Un sistema en el filo del caos genera la máxima cantidad de información (diversidad) Cualquier resultado es, en su mayor parte, inesperado. La productividad de un sistema tal será superior.

21 2121 Naturaleza al borde del caos En ecología: la hipótesis de perturbaciones intermedias dice que los ecosistemas con máxima biodiversidad están en zonas con perturbaciones intermedias. Desierto: Cambios de temperatura demasiado altos Clima mediterráneo: demasiado cambio estacional. Pluviselva: justico, como la bofetá de Carrasco.

22 2 Por favor, ¿para ir al borde del caos? Por co-adaptación: diferentes agentes, que intentan optimizar su fitness, pueden llegar al borde del caos a través de mecanismos de cooperación y competición Los productos de un segmento del mercado coevolucionan. Carrera armamentística en la naturaleza. Experimentos con el dilema del prisionero iterado.

23 2323 Posibles resultados del filo del caos Ley de los retornos crecientes (Brian Arthur) accidentes congelados. Beta vs. VHS. QWERTY vs. AZERTY. Conducción en el lado izquierdo. Sentido de las agujas del reloj. Situación de segundas residencias.

24 2424 Simulando el borde del caos Usando autómatas celulares Wolfram: classificación en ACs tipo I a IV Langton AC I&II: Orden AC III: Caos AC IV: Borde del caos Probabilidad de supervivencia en la siguiente generación = =.273

25 2525 Organizándose uno mismo La autoorganización es una propiedad emergente. Creación de orden en un sistema sin intervención de una fuerza central. El orden no es estático, sino dinámico. Criticalidad auto-organizada: La probabilidad de cambio en un sistema es inversamente proporcional a su tamaño.

26 2626 ¿Criticalidad autoorganizada? Propuesta por Per Bak Da lugar a leyes de potencias: las avalanchas de mayor tamaño son mucho menos probables que las más pequeñas La evolución sucede al filo del caos: Pequeños sucesos de especiación producen diversidad; grandes llevan a la extinción. Los tamaños de las extinciones siguen una ley de potencias (Ricard Solé) Pequeños cambios incrementan la diversidad, grandes lo destruyen.

27 2727 Auto-generación Autopoiesis (Varela). Modelo para el origen de la vida Cierre Uno mismo Anticipación Modelo del mundo

28 2828 Sistemas autoorganizados para todos Sistema inmunitario de los mamíferos superiores Uno mismo contra lo otro: uno, bueno, lo otro, malo Modelado por Forrest y Mitchell usando algoritmos evolutivos. Embajadores del cerebro en el flujo sanguíneo

29 2929 Y más arriba también Consciencia (Daniel Dennet) Reproducirse. Encontrar comida. Mantener la integridad. Sentido de uno mismo.

30 3030 Separación es inevitable Autoorganización, modelos del mundo y la especifidad lleva a la creación de nichos La Naturaleza aborrece el vacío Cada nicho está ocupado por una sola specie Los animales se alimentan de una forma determinada. Las compañías se especializan en un segmento de mercado. Las series de televisión buscan un target. Comunidades científicas o en Internet

31 3131 ¿Dónde está la chicha? Aplicaciones comerciales de sistemas autoorganizativos. La inteligencia está en los agentes, no hay un gobierno centralizado. Radio autoorganizada frente a radio regulada Vuelo libre frente a vuelo controlado. Satélites autoorganizados.

32 3232 Todo está unido a todo Los sistemas auto-organizativos se describen en un marco conexionista (J. Doyne Farmer). Los nodos están unidos por aristas con un peso. Algunos nodos actúan como entradas, otros como salidas. La adaptation normalmente significa cambio de pesos, o añadir nuevos nodos, o nuevas conexiones.

33 3 Complejidad Complejo: Entretejido, como una tela o red Complicado: plegado muchas veces, como una pajarita de papel. Complejo no es complicado: los sistemas complejos consisten en muchas partes que interaccionan, adaptándose al mismo tiempo. Una catedral es complicada.

34 3434 De lo simple a lo complejo ¿Qué hace la Evolución? ¿Optimiza? ¿Va de lo simple a lo complejo? ¿Mejora? La evolución es cambio, y actúa sobre sistemas complejos.

35 3535 Evolución En la Naturaleza Mercados Universos inflacionarios evolutivos Evolución memética

36 3636 La evolución no tiene que ver con los sustratos sino con interfaces y la supervivencia del más adecuado

37 3737 Los imitadores de Darwin Inspirado por la evolución y su base molecular, para resolver problemas de ingeniería Procesos que actúan sobre poblaciones de cromosomas Mutación y entrecruzamiento. Selección natural: supervivencia del más adecuado. La adecuación se incremente con el tiempo.

38 3838 Los pájaros Darwin se preguntó sobre la variación de especies de pinzón existentes en las Galápagos. Lo explicó mediante dos mecanismos básicos: variaciones aleatorias y supervivencia del más adaptado. Wallace también, más o menos al mismo tiempo.

39 3939 Los repollos Mendel describió la herencia como algo atómico. Von Neumann fue el primero en especular sobre el código genético. Watson y Crick describieron en los años 50, la estructura y función del código ADN (ácido desoxirribonucleico)

40 4040 O séase La evolución procede a través de cambios en el ADN, que dan lugar a diferencias somáticas. Los cambios se conservan si son viables y el propietario se reproduce (fitness > 0). Cambio ⇒ Adaptación ⇒ Supervivencia. La Naturaleza optimiza Localmente, espacial y temporalmente.

41 4141 El algoritmo Los algoritmos evolutivos imitan a la naturaleza trabajando sobre una población de posibles soluciones a un problema, cambiándolas aleatoriamente, combinándolas las unas con las otras, seleccionándolas de acuerdo con lo bien que resuelven el problema. Repítelo varias generaciones. ¡Yastá!

42 4242 Cromosoma my $cromosoma = { _str => '', _fitness => 0}; Se puede usar cualquier estructura de datos Cadenas de bits, vectores de números reales, árboles... El fitness es un número real. Debe ser comparable. $crom=Algorithm::Evolutionary:: Individual::BitString 10

43 4343 Cromosoma Todos los cromosomas (individuos) descienden de Algorithm::Evolutionary::Individual::Base La clase base puede crear cualquier derivada Representada en XML como 1 0

44 4 Mutación my @alphabet = ('a'..'z'); sub mutate { my $chromosome = shift; my $mutationPoint = rand( length( $chromosome->{_str})); substr($chromosome->{_str}, $mutationPoint,1 )= $alphabet[( rand( @alphabet))]; } my @mutador = Algorithm::Evolutionary:: Op::IncMutation;

45 4545 Mutación Todos los operadores (modifican cromosomas) descienden de Algorithm::Evolutionary::Op::Base La clase base puede crear cualquier derivada Representada en XML como

46 4646 Sexo: Crossover Crossover == recombinación 2 o más padres intercambian material.

47 4747 Sexo: Crossover sub crossover { my ($chr1, $chr2) = @_; my $crossoverPoint = int (rand( length( $chr1->{_str}) - 1)); my $range = 1 + int(rand( length( $chr1->{_str}) - $crossoverPoint )); my $str = $chr1->{_str}; substr( $chr1->{_str}, $crossoverPoint, $range, substr( $chr2->{_str}, $crossoverPoint, $range)); substr( $chr2->{_str}, $crossoverPoint, $range, substr( $str, $crossoverPoint, $range )); }

48 4848 Sexo: Crossover my $chr1 = new Algorithm::Evolutionary::Op::Crossover 3; El crossover es un operador binario. En algoritmos evolutivos, se suelen combinar los dos.

49 4949 Lo selecto Ydtvslqflr -> 42 ygrslvihcr -> 44 vfodoqaegj -> 47 rjyaknrqts -> 48 tgiaakugps -> 49 hecdimrhbr -> 49 pexesvqgac -> 52 zxpiipwmhn -> 53 ygrslgiqcr -> 54 cglinjtihl -> 55 jhkdkphbiq -> 57 Ydtvslqflr -> 42 ygrslvihcr -> 44 vfodoqaegj -> 47 rjyaknrqts -> 48 tgiaakugps -> 49 hecdimrhbr -> 49 pexesvqgac -> 52 zxpiipwmhn -> 53 ygrslgiqcr -> 54 Ydtaakqflr tgivslugps

50 5050 La caña de España Ydtvslqflr -> 42 ygrslvihcr -> 44 vfodoqaegj -> 47 rjyaknrqts -> 48 tgiaakugps -> 49 hecdimrhbr -> 49 pexesvqgac -> 52 zxpiipwmhn -> 53 ygrslgiqcr -> 54 cglinjtihl -> 55 jhkdkphbiq -> 57 Ydtvslqflr -> 42 ygrslvihcr -> 44 vfodoqaegj -> 47 rjyaknrqts -> 48 tgiaakugps -> 49 hecdimrhbr -> 49 pexesvqgac -> 52 ygrslvaecr vfodoqihgj Ydtdoqaflr vfovslqegj

51 5151 Tribus genéticas

52 5252 Vida artificial La complejidad es una propiedad de los sistemas vivos. La vida artificial trata, principalmente, de complejidad en los seres vivos. Interacciones huésped-parásito. Redes de genes. Sistemas inmunes. ¡La internet!

53 5353 No hay nada más que añadir O quizás si ¿Preguntas? O quizás si ¿Preguntas?