I Jornadas de Computación Distribuida Inteligente y Sistemas Complejos.
CETA-CIEMAT, 11-06-2012
Un enfoque “Interdisciplinar” para el estudio y aplicación de las redes complejas
Dr. Francisco Prieto CastrilloCoordinador de Ciencia y Tecnología del CETA-CIEMAT
domingo 10 de junio de 2012
I Jornadas de Computación Distribuida Inteligente y Sistemas Complejos.
CETA-CIEMAT, 11-06-2012
Un enfoque inter-disciplinar
Ingeniería Informática Ciencia
Obje t i vo : que un a l gor i tmo (herramienta) funcione lo mejor posible (menor tiempo y máxima eficiencia)
¿ C u a l e s s o n l a s r a z o n e s fundamentales (no sólo operativas) de que el algoritmo funcione? ¿ D e s c r i b e c o r r e c t a m e n t e e l comportamiento del sistema?
Pulir la herramienta Generar nuevo conocimiento
Dado un algoritmo....Dos enfoques complementarios
domingo 10 de junio de 2012
I Jornadas de Computación Distribuida Inteligente y Sistemas Complejos.
CETA-CIEMAT, 11-06-2012
De la inspiración a la herramienta....
De la herramienta al conocimiento.
The GRID
domingo 10 de junio de 2012
I Jornadas de Computación Distribuida Inteligente y Sistemas Complejos.
CETA-CIEMAT, 11-06-2012
Estabilidad de sistemas no lineales
Grafos aleatorios
Sistemas dinamicos Grafos aleatorios
Teoria del Caos/Bifuración
Ciencia de los sistemas complejos (Complexity Science)
Sincronización
Henri Poincare
Edward N. Lorentz
Laszlo Barabasi
Paul Erdos
Steven Strogatz
Pensamiento Complejo
Epistemología y Humanidades
Edgar Morin
Redes complejas
domingo 10 de junio de 2012
I Jornadas de Computación Distribuida Inteligente y Sistemas Complejos.
CETA-CIEMAT, 11-06-2012domingo 10 de junio de 2012
I Jornadas de Computación Distribuida Inteligente y Sistemas Complejos.
CETA-CIEMAT, 11-06-2012
Modelos simples. Alta complejidad
(Prieto & Lourenço, 2005)
Poincaré Surface of Section
Un sistema simple..... Esconde gran complejidad
CAOS: Un equilibrio entre azar y estructura donde la sensibilidad a las condiciones de contorno es extrema
Perl, Juergen “On chaotic behaviour of some np-complete problems. Graph-Theoretic Concepts in Computer Science. Springer, (1998)
Caos
NP-Completo
domingo 10 de junio de 2012
I Jornadas de Computación Distribuida Inteligente y Sistemas Complejos.
CETA-CIEMAT, 11-06-2012
En Ingeniería informática / Optimización
En Sistemas/redes complejos
Los grafos suelen ser dirigidos con un coste asociado en las aristas
Los grafos suelen ser no dirigidos y sin coste en las aristas (aunque hay modelos de todo tipo)
El objetivo es encontrar un camíno mínimo o max/min una función de los caminos
El objetivo es estudiar las propiedades estadísticas de un ensemble de grafos del que cada grafo es una realización.
Lo que nos “conecta” son los grafos.....
Ejemplos: El problema del viajante, problema del enrutamiento, Dijkstra SP, corte máximo en grafos, etc
Ejemplos: Estudiar la distribución de grados de un grafo, evolución de un grafo mediante link preferencial, centrlidad, etc.
Hines et al 2010
TSP
domingo 10 de junio de 2012
I Jornadas de Computación Distribuida Inteligente y Sistemas Complejos.
CETA-CIEMAT, 11-06-2012
Lo que nos “conecta” son los grafos.....
Modelo de Erdos & Renyi Modelo de Watts & Strogatz Modelo de Barabasi & Albert
E ⊂ P2(V )
V = {vi : i ∈ IV }{ Aij =�
1 (vi, vj) ∈ E0 (vi, vj /∈ E)
Matriz de adyacencianodos
aristas E ⊂ V × V{ no dirigidodirigido
G = (V,E, W ) W: matriz pesos
P2(V ) = {S ⊂ V : card(S) = 2}
domingo 10 de junio de 2012
I Jornadas de Computación Distribuida Inteligente y Sistemas Complejos.
CETA-CIEMAT, 11-06-2012
De agentes, abejas y sincronización: La inteligencia de “enjambre”
En computer science
En sistemas complejos
Emergencia: Un comportamiento cualitativamente distinto del sistema a partir de la cooperación de agentes/partes no esperable a partir de la información local
Swarm Intelligence o “inteligencia de enjambre”
Agent Based Modelling (ABM)
Agentes(entidades
que cooperan)
{ ReactivosDistributed Artificial Intelligence (DAI)Pro-activosSociales
domingo 10 de junio de 2012
I Jornadas de Computación Distribuida Inteligente y Sistemas Complejos.
CETA-CIEMAT, 11-06-2012
Un ejemplo de agentes: redes de computadoras y aplicaciones P2P
Cliente/servidor Hybrido P2P
El cliente sólo precisa conocer a su server El cliente/agente tiene un diccionario de todos los demás
El cliente sólo interactúa a través de su serverLos agentes interaccionas entre sí directamente
Decentralización
domingo 10 de junio de 2012
I Jornadas de Computación Distribuida Inteligente y Sistemas Complejos.
CETA-CIEMAT, 11-06-2012
Heurísticas“Procedimientos simples, a menudo basados en el sentido común que se supone que obtendrán una buena solución (no necesariamente óptima) a problemas difíciles de un modo sencillo y rápido”. (Zanakis et al.,1981)
Meta-heurísticas“Las metaheurísticas son una clase de métodos aproximados que están diseñados para resolver problemas difíciles de optimización combinatoria en los que los heurísticos clásicos no son efectivos. Las metaheurísticas proporcionan un marco general para crear nuevos algoritmos híbridos combinando diferentes conceptos derivados de la inteligencia artificial, la evolución biológica y los mecanismo estadísticos.” (J.P. Kelly et al, 1996)
En optimización se habla de....
domingo 10 de junio de 2012
I Jornadas de Computación Distribuida Inteligente y Sistemas Complejos.
CETA-CIEMAT, 11-06-2012
Toby S. Cubitt, Jens Eisert, and Michael M. WolfExtracting dynamical equations from experimental data is NP hard. Physical Review Letters, (Accepted, Feb 2012)
Heurísticas
Metaheurísticas
Ruido/excursión aleatoria
Algoritmo
Intensificación
Diversificación
Ingeniería Informática Sistemas Complejos
Ecuación/mapa/analogía
C o m p o r t a m i e n t o gobal, emergencia y auto-organización
Algoritmo “enriquecido”
Mín/Max energía/entropía/etc
Búsqueda gobal
Búsqueda local
Algunos vínculos entre algoritmia y complejidad...
domingo 10 de junio de 2012
I Jornadas de Computación Distribuida Inteligente y Sistemas Complejos.
CETA-CIEMAT, 11-06-2012
Un ejemplo de inter-relación: Small-World/Decentralized Search
J. Kleinberg, “The small-world phenomenon and decentralized search,” SIAM News, vol. 37, no. 3, pp. 1–2, 2004.
soluciones
excursión aleatoria
domingo 10 de junio de 2012
I Jornadas de Computación Distribuida Inteligente y Sistemas Complejos.
CETA-CIEMAT, 11-06-2012
Nombre Método
ACO Ant Colony Optimization
ABC Artificial Bee Colony
AMP Adaptive Memory Programming
AT Asynchronous Teams
CA Cellular Automata
PA Preferential Attachment
SW Small-World
EA Evolutionary Algorithms
EDA Estimation Distribution Algorithms
FANS Fuzzy Adaptive Neighborhood Search
GA Genetic Algorithms
GHC Generalized High-Climbing algorithms
GLS Guided Local Search
GRASP Greedy Adaptive Randomized Search Procedure
HC Heuristic Concentration
ILS Iterated Local Search
MA Memetic Algorithms
MSM Multi-Start Methods
NM Noising Methods
PR Path Relinking
POPMUSIC Partial Optimization Metaheuristic Under Special Intensification Condition
SA Simulated Annealing
SI Swarm Intelligence
SS Scatter Search
SSA Search Space Analysis
TAM Threshold Accepting Methods
TS Tabu Search
VNS Variable Neighborhood Search
Meta-heurísticas m
ás conocidasH
emos
usa
do...
domingo 10 de junio de 2012
I Jornadas de Computación Distribuida Inteligente y Sistemas Complejos.
CETA-CIEMAT, 11-06-2012
¿Para qué lo hemos usado?
1) Computando en redes complejas
2) Computando con redes complejas
domingo 10 de junio de 2012
I Jornadas de Computación Distribuida Inteligente y Sistemas Complejos.
CETA-CIEMAT, 11-06-2012
Barabási. The physics of the Web. Physics World (2001) vol. 14 (7) pp. 33–38
+
Prieto et al IJCNS, 2011
domingo 10 de junio de 2012
I Jornadas de Computación Distribuida Inteligente y Sistemas Complejos.
CETA-CIEMAT, 11-06-2012
Computando en redes complejas
domingo 10 de junio de 2012
I Jornadas de Computación Distribuida Inteligente y Sistemas Complejos.
CETA-CIEMAT, 11-06-2012
AVG DEGREE: 5.03AvgCC: 0.11AVG DIST: 4.24
BROKER
CE
COMM. NODE
α = 2.87
Prieto et al IJCNS, 2011Prieto et al FISES, 2011
domingo 10 de junio de 2012
I Jornadas de Computación Distribuida Inteligente y Sistemas Complejos.
CETA-CIEMAT, 11-06-2012
Computando con redes complejas
Botón-‐Fernández, M., Prieto Castrillo, F., Vega-‐Rodríguez, M.A. ICCSA’11
Botón et al, 2012
Conexión popularidad-eficiencia
cluster de computadores
domingo 10 de junio de 2012
I Jornadas de Computación Distribuida Inteligente y Sistemas Complejos.
CETA-CIEMAT, 11-06-2012
¿Un país de “expertos” o una colaboración de equipos trans/inter-disciplinar?
Bah!!! Yo lo sé todo de la pata izquierda de
la mosca
Perdona. ¿qué es una mosca?
!!!Colaboremos!!!
Soy el mayor experto en la pata derecha de
la mosca
Jejeje
domingo 10 de junio de 2012
I Jornadas de Computación Distribuida Inteligente y Sistemas Complejos.
CETA-CIEMAT, 11-06-2012
¡¡¡Gracias por su atención!!!
“Las mentes son como los paracaídas. Funcionan mejor cuando están abiertas”. Lord Thomas Dewar
domingo 10 de junio de 2012