1 Carlos Reynoso UNIVERSIDAD DE BUENOS AIRES http://carlosreynoso.com.arModelos complejos y caóticos Algoritmo genético – Gramáticas – Caos determinista Carlos Reynoso UNIVERSIDAD DE BUENOS AIRES

2 Objetivos Introducir algunas manifestaciones y herramientas de la teoría de la complejidad y el caos Pensamiento profundamente contrario al sentido común Que opera casi siempre en forma proporcional o lineal El todo es diferente a la suma de las partes Caso del agua La complejidad surge a partir de elementos muy simples Nada que ver con el azar, ni (necesariamente) con la numerosidad

3 Agenda El problema del cerebroHeurísticas naturales – Algoritmo genético Gramáticas complejas Aplicaciones en ciencias sociales Si hay tiempo: Caos determinista Conclusiones Referencias

4 Problema: Ilusiones ópticas

5 Problema: Ilusiones ópticas

6 Ilusiones ópticas © M. Bach & J. L. Hinton, 2005

7 Aristoteles, “De Somnis” – Robert Adams, 1834Persistencia Aristoteles, “De Somnis” – Robert Adams, 1834

8

9

10 Giros contrarios Instituto Max Planck de Cibernética Biológica, Alemania

11 Cerebro La visión sólo usa los ojos como artefactos periféricosVisión continua a pesar de la retícula (retina = red) Eficacia evolutiva de las suposiciones en el procesamiento de información ¿Cómo pudo constituirse algo tan complejo en sólo 7 mil millones de años? Una complejidad tan grande requiere un método de resolución poderoso Este método es una dinámica de cambio Selección natural

12 Modalidades Nombre global: Computación evolutiva1. Algoritmo genético (John Holland) Representaciones lineales (binarias), crossover, mutación 2. Estrategia evolutiva (Rechenberg-Schwefel) Representaciones reales lineales Operadores: mutaciones gaussianas, combinaciones de vectores de progenitores 3. Programación genética (John Koza) Representaciones arboladas recursivas, LISP 4. Memética (Richard Dawkins, Daniel Dennett) Memes No crossover, mutación al azar

13 ¿Qué métodos de búsqueda* usan los antropólogos?*O resolución de problemas, exploración, inducción, aprendizaje, etc... (Gregory Bateson) Análisis caso por caso (Modelo mecánico) Método aleatorio o estocástico (Modelo estadístico) Ninguno (Modelo hermenéutico)

14 Otra pregunta ¿Qué modelo de cambio genuino hay que no sea evolutivo?*Algoritmos adaptativos Replicación Mutación Combinación Selección ¿Qué cosa o idea hay que no cambie de ese modo? “No hay nada de biológico en la selección natural” *Hasta hace poco había otro, pero no está pasando por un buen momento.

15 Algoritmos evolutivosSe pueden aplicar a problemas en los cuales las estrategias clásicas fallan. El espacio de búsqueda puede ser inmenso. La función de destino puede ser ruidosa, no lineal, no diferenciable, discontinua, multimodal, de alta dimensionalidad y puede estar sujeta a múltiples clases de restricciones.

16 Espacio de fases

17 Algoritmo genético John Holland, 1960s“Los organismos vivientes son consumados resolvedores de problemas” Adaptation in natural and artificial systems, 1975

18 ¿W. o G. Bateson?

19 Algoritmo genético Población de solucionesSerie de caracteres (cromosomas) Caracter (gen, rasgo) Reproducción sexual y cross-over Mutación Ciclo: 1. Generar población 2. Evaluar adecuación 3. Los mejores se reproducen, los peores se extinguen 4. Aplicar mutaciones 5. Actualizar población 6. Volver a 2

20 Cross-over La riqueza no está en el azar, sino en la diversidadEjemplo: Match – William Langdon, UCL ALGORITMOGENETICOENPOSADAS 2726 = 16,423,203,268,260,700,000,000,000,000,000,000,000 1017 = 100,000,000,000,000,000 FACU.TXT

21 GA Viewer

22 Aplicaciones Arqueología Antropología sociocultural Arte & Diseño Música**Si no se puede componer música o pintar, pongan en duda el método

23 Aplicaciones Robert Reynolds (Kent Flannery, John Holland)Modelos de conducta, toma de decisiones de cazadores-recolectores en Oaxaca Algoritmo cultural: Consiste en Un espacio de población Un espacio de creencias culturales Nivel individual Nivel ontológico – Almacén de las experiencias acumuladas Un protocolo de interacción que vincula a ambos

24 Robert Reynolds Voto y promoción Conocimiento situacional y normativoAC se utiliza en computación como algoritmo de optimización

25 Redes sociales Mursel Tasgin, Haluk Bingol (İstanbul, 2005)GACD: Detección de comunidades en redes sociales complejas Performance comparable a Girvan-Newman, Radicchi, Reinhard-Bornholdt o Wu-Huberman Funciona mucho mejor en redes inmensas

26 Redes sociales Floortje Alkemade, Carolina Castaldi (Utrecht y Groningen, 2005) Difusión de novedades en redes sociales – Planificación de programas de marketing orientado – Alternativa a modelos epidemiológicos (Sperber) Linton Freeman (UC at Irvine) Identificación de grupos en redes Bruce Edmonds (U. Manchester) Aplicación de AG a la simulación social (JASSS)

27 Arqueología Dimitros Kontogiorgos (Sheffield), Alexandros Leontitsis (Patras) Estimación del peso de microartefactos por minimización con AG (2005) Journal of Archaeological Science, 32(8) Aplicación a artefactos neolíticos del sitio de Paliambela, Aretusa, norte de Grecia

28 Arqueología Luciano Silva, Olga Bellón, Paulo Gotardo (Paraná), Kim Boyer (Ohio) Obtención de imágenes arqueológicas tridimensionales a partir de 2D con AG 2003 Conference on Computer Vision and Pattern Recognition A diferencia de ICP (iteración de punto más cercano) el AG no converge en mínimos subóptimos y no requiere pre-alineamiento Combinan AG con otras técnicas, como hill climbing o simulación de templado

29 Bill Sellers Primatólogo computacionalEvolución de costo metabólico de homínidos fósiles Evolución de escenarios de predadores-presas Simulación de locomoción Generación de imágenes modélicas de soluciones de máxima performance

30 Locomoción Groucho

31 Reconstrucción de LucyRobin Crompton, Univ Liverpool (2005) Lucy (Australopithecus afarensis) – Estructura corporal muy distinta a H. sapiens Estrategia de ingeniería reversa: Qué clase de locomoción ciertas partes del cuerpo están mejor diseñadas para sostener Modelos de los pies + AG para desarrollar movimiento óptimo Los movimientos desarrollados (similares a los nuestros) coinciden con las huellas fósiles de Laetoli

32

33

34 Reynoso - Jezierski Resolvedor de problemas arqueológicos mediante AG – CAA Visby, 2001

35 Melero, Torres, León Universidad de Granada, 2003Reconstrucción interactiva de vasijas ibéricas* *Cita Reynoso-Jezierski 2001

36 Clasificación automáticaChaouki Maiza, Véronique Gaildrat, 2005* SIAMA: Sistema de imaginería y análisis de mobiliario arqueológico Programa CLAPS – Búsqueda de posición de fragmento en la vasija Sitios galo-romanos de La Graufesenque y Montans 40 mil fragmentos digitalizados *Cita Reynoso-Jezierski 2001

37 Aplicaciones en músicaAl Biles – GenJam T 1:30

38

39 Aplicaciones Eduardo Reck MirandaUniversidad de Plymouth, UK – Editor del Leonardo Music Journal (MIT) Estudio de los componentes cognitivos que rigen la comunicación sonora Síntesis con autómatas celulares y AG

40 Otros diseños Peter Bentley Creación en artes visuales y músicaAG + redes neuronales Idem Cardalda & Johnson EvoWorkshops: EvoMUSART Modelos de Agentes + AG (NetLogo) Simulaciones visuales complejas ABM Music

41 Diseño evolutivo

42 ACCAD – Diseño evolucionario interactivo

43 Karl Sims – Arte genético

44 Karl Sims – Arte genético

45 Herramientas

46 Kandid

47 Conclusiones Conjunto de técnicas independientes de objetoNo hay nada de biológico en la selección natural Mejor comprensión de problemas, soluciones, búsqueda, adaptación, aprendizaje, cambio Cualquiera sea el marco teórico y el objeto Se entienden mejor las posibilidades y también los límites Algoritmos y estructuras más ricos y complejos que los de los métodos analíticos o hermenéuticos En el peor escenario, se puede crear arte, o jugar

48 Complejidad gramatical Sistemas-LCarlos Reynoso UNIVERSIDAD DE BUENOS AIRES

49 Sistemas-L Aristid Lindenmaier – Sistemas-L, ca. 1968

50 Sistemas-L Gramáticas recursivas de crecimientoSmith, Prusinkiewicz: gráficos de tortuga Axioma: B Reglas: B F-[B]+B F FF

51 Fractree

52 Aplicaciones antropológicas

53 Gift Siromoney [ ] Matemático, teórico de la información, arqueólogo y etnógrafo ¿Qué procedimientos siguen los artesanos? Picture languages, 1972 – Array languages, 1974 Identificó procedimientos regulares para el diseño de Kolams: Kolam de matriz finita, Kolam de matriz regular, Kolam regular independiente de contexto Los sistemas-L son más simples, pero las ideas de Siromoney fueron avanzadas para su época

54 Kolam – Sistemas-L Lyndyhop

55 Kolam tamil

56 Kolam tamil

57 Casos culturales Ron Eglash – African fractals, 1999 – Cruces etíopes

58 L-Systems, arquitectura, asentamientos y paisajes

59 Simulación de ciudades (CityEngine)

60 Simulación de ciudades (CityEngine)

61

62 Modelo de Pompeya (Müller - CityEngine)5:13

63 Aplicaciones en músicaPrusinkiewicz, Hanan, Siromoney – Música karnática, 1986 Stefanie Mason, Michael Saffle – Música y L-Systems, 1994 David Sharp – LMUSe, John Belcher, James Murrel – Teorías rítmicas africanas Goodall y Watson – Lsys2MIDI, 1998 Luke DuBois – Jit.linden, 2003

64 Aplicaciones en música (2/2)Stelios Manousakis – Musical L-Systems (tesis), 2006 Peter Worth, Susan Stepney – Growing music Visions of Chaos

65 Si queda tiempo... Caos determinista

66 Caos – Ecuación logísticax = k * x (1 – x) x entre 0 y 1 k entre 0 y 4 Ecuación Fractales

67 Innumerables algoritmos adicionalesRedes independientes de escala Las distribuciones normales son excepcionales Distribución 1/f, seis grados de separación,, necesidad de determinar como funcionan las redes en la vida real Autómatas celulares Surgimiento del orden a partir del desorden – Auto-organización, emergencia Criticalidad auto-organizada, transiciones de fase, clases de universalidad Modelos basados en agentes – Sociedades artificiales Modelos para determinar consecuencias de afirmaciones sobre las sociedades reales Fractales – Dimensión fractal Estudios de pánico, dinámica de la auto-organización, ola mexicana

68 Conclusiones Métodos independientes de objetoElaboraciones transdisciplinarias Clases de universalidad Infinidad de herramientas No es una teoría, sino un conjunto de elementos de juicio independientes del marco teórico Carácter crítico del conocimiento complejo

69 Referencias Reynoso, Carlos – Complejidad y caos: Una exploración antropológica. Buenos Aires, SB Ediciones, 2006 Grupo Anthropokaos – Exploraciones en antropología de la complejidad. Idem, 2007. Eglash, Ron – African fractals. New Brunswick, Rutgers University Press, 1999. Eve, Raymond, Sara Horsfall & Mary Lee. Chaos, complexity and sociology. Myth, models, and theories. Thousand Oaks, Sage, 1997. Watts, Duncan. Six degrees. The science of a connected age. Londres, Random House, 2004.

70 ¿Preguntas?