Download Avances en Complejidad y Caos

Modelos complejos y caóticos
Algoritmo genético – Gramáticas – Caos determinista
Carlos Reynoso
UNIVERSIDAD DE BUENOS AIRES
http://carlosreynoso.com.ar
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
Agenda
•
•
•
•
•
•
•
El problema del cerebro
Heurísticas naturales – Algoritmo genético
Gramáticas complejas
Aplicaciones en ciencias sociales
Si hay tiempo: Caos determinista
Conclusiones
Referencias
Problema: Ilusiones ópticas
Problema: Ilusiones ópticas
Ilusiones ópticas
Persistencia
Aristoteles, “De Somnis” – Robert Adams, 1834
Giros contrarios
Instituto Max Planck de Cibernética Biológica, Alemania
Cerebro
• La visión sólo usa los ojos como artefactos
periféricos
– Visió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
Modalidades
• Nombre global: Computación evolutiva
• 1. 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
¿Qué métodos de búsqueda* usan
los antropólogos?
•
*O resolución de problemas, exploración,
inducción, aprendizaje, etc... (Gregory
Bateson)
1. Análisis caso por caso (Modelo mecánico)
2. Método aleatorio o estocástico (Modelo
estadístico)
3. Ninguno (Modelo hermenéutico)
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.
Algoritmos evolutivos
• Se 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.
Espacio de fases
Algoritmo genético
• John Holland, 1960s
• “Los organismos vivientes
son consumados
resolvedores de problemas”
• Adaptation in natural and
artificial systems, 1975
¿W. o G.
Bateson?
Algoritmo genético
•
•
•
•
•
•
Población de soluciones
Serie 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
Cross-over
• La riqueza no está en el azar, sino en la
diversidad
Ejemplo: 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
GA Viewer
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
Aplicaciones
• Robert Reynolds (Kent Flannery, John Holland)
– Modelos de conducta, toma de decisiones de cazadoresrecolectores 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
Robert Reynolds
• Voto y promoción
• Conocimiento situacional y normativo
• AC se utiliza en computación como algoritmo de
optimización
Redes sociales
• Mursel Tasgin, Haluk
Bingol (İstanbul, 2005)
• GACD: Detección de
comunidades en redes
sociales complejas
– Performance
comparable a GirvanNewman, Radicchi,
Reinhard-Bornholdt o
Wu-Huberman
– Funciona mucho mejor
en redes inmensas
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)
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
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
Bill Sellers
• Primatólogo computacional
• Evolución de costo metabólico de
homínidos fósiles
• Evolución de escenarios de predadorespresas
• Simulación de locomoción
• Generación de imágenes modélicas de
soluciones de máxima performance
Locomoción
Groucho
Reconstrucción de Lucy
• Robin 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
Reynoso - Jezierski
• Resolvedor de problemas arqueológicos
mediante AG – CAA Visby, 2001
Melero, Torres, León
• Universidad de Granada, 2003
• Reconstrucción interactiva de vasijas ibéricas*
*Cita Reynoso-Jezierski 2001
Clasificación automática
• Chaouki 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
Aplicaciones en música
• Al Biles – GenJam
T 1:30
Aplicaciones
• Eduardo Reck Miranda
• Universidad 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
Otros diseños
•
•
•
•
•
•
•
Peter Bentley
Creación en artes visuales y música
AG + redes neuronales
Idem Cardalda & Johnson
EvoWorkshops: EvoMUSART
Modelos de Agentes + AG (NetLogo)
Simulaciones visuales complejas
ABM Music
Diseño evolutivo
ACCAD – Diseño evolucionario interactivo
Karl Sims – Arte genético
Karl Sims – Arte genético
Herramientas
Kandid
Conclusiones
• Conjunto de técnicas independientes de objeto
– No 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
Complejidad gramatical
Sistemas-L
Carlos Reynoso
UNIVERSIDAD DE BUENOS AIRES
[email protected]
Sistemas-L
• Aristid Lindenmaier – Sistemas-L, ca. 1968
Sistemas-L
• Gramáticas recursivas de crecimiento
• Smith, Prusinkiewicz: gráficos de tortuga
Axioma:
Reglas:
Profundidad
0
1
2
3
B
B F-[B]+B
F FF
Cadena resultante
B
F[-B]+B
FF[-F[-B]+B]+F[-B]+B
FFFF[-FF[-F[-B]+B]+F[-B]+B]+FF[-F[-B]+B]+F[-B]+B
Comando
F
G
+
[
]
|
Acción
Dibujar hacia adelante un número determinado de
posiciones
Mover la tortuga hacia atrás un número de posiciones, sin dibujar
Girar la tortuga hacia la derecha un ángulo determinado. Si se especifica un número entero antes del
signo, la tortuga realiza el giro esa cantidad de veces.
Idem, hacia la izquierda
Guardar la posición y ángulo actual para uso ulterior en una pila de estados guardados
Eliminar el último estado guardado en la pila y restaurar la última posición y ángulo guardados
Mover la tortuga hacia adelante una longitud computada, dibujando una línea desde la posición anterior hasta la nueva – En algunas aplicaciones, girar
90° o 180°
Fractree
Aplicaciones antropológicas
Gift Siromoney
[1932-1988]
• 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
Kolam – Sistemas-L
Lyndyhop
Kolam tamil
Kolam tamil
Casos culturales
• Ron Eglash –
African fractals,
1999 – Cruces
etíopes
L-Systems, arquitectura,
asentamientos y paisajes
Simulación de ciudades
(CityEngine)
Simulación de ciudades
(CityEngine)
Modelo de Pompeya
(Müller - CityEngine)
5:13
Aplicaciones en música
• Prusinkiewicz, Hanan, Siromoney – Música
karnática, 1986
• Stefanie Mason, Michael Saffle – Música y LSystems, 1994
• David Sharp – LMUSe, 1995-1998
• John Belcher, James Murrel – Teorías rítmicas
africanas
• Goodall y Watson – Lsys2MIDI, 1998
• Luke DuBois – Jit.linden, 2003
Aplicaciones en música (2/2)
• Stelios Manousakis – Musical L-Systems (tesis),
2006
• Peter Worth, Susan Stepney – Growing music
Visions of Chaos
Si queda tiempo...
Caos determinista
Caos – Ecuación logística
• x = k * x (1 – x)
• x entre 0 y 1
• k entre 0 y 4
Ecuación
Fractales
Innumerables algoritmos adicionales
• Redes 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
Conclusiones
•
•
•
•
•
Métodos independientes de objeto
Elaboraciones 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
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.
¿Preguntas?