Post on 23-Mar-2020
Jesica Rivero Espinosa
jrivero@inf.uc3m.es
VI Jornadas MAVIR: Tecnologías de Acceso a la Información: Estado actual y retos
Jornadas académicas
2
Motivación
Propuesta ◦ Fundamentos Básicos
◦ Evolución
Evaluación del Algoritmo
Conclusiones y Líneas Futuras
2
3
Una de las aplicaciones más importantes actualmente: Redes Sociales.
Útil para establecer colaboraciones entre investigadores y compañías
Cadena de personas para establecerlas.
Grafos y Algoritmos de Búsqueda de Caminos
PROBLEMA: No hay algoritmos que traten el tamaño de estos grafos usando su topología con un bajo tiempo de respuesta y adaptables.
3
4
Búsqueda en grafos vastos + tiempo de respuesta bajo
Preprocesado Global
No Adaptable
Adaptable + tiempo de respuesta bajo
Grafos Pequeños
4
5 5
ACO
6
ACO
7
ACO
8
ACO
9
ACO
10
ACO
11 11
ACO
12 12
ACO
13 13
ACO
14 14
ACO
15 15
ACO
16
Objetivos: • Evitar pérdidas • Reducir tiempo de repuesta
16
SoSACO
17 17
18
Selección de los Nodos Comida (F = {fi})
Nodos con alta relevancia, distribución/partición, frecuencia de tránsito, alto grado.
O(fi) = m
18
19
Difusión del Olor a Comida (S = {si}, |S| = |F|, si ⊆ N)
Proceso Iterativo: O(ni)’ = O(nj) - k·wij Si O(ni)’ ≥ u y O(ni)’ > O(ni). Fin: No hay más nodos con posible olor mayor que u.
19
20
Búsqueda del Camino: ACO
Dos Colonias: Si extremos ∉ F, o ambos ∈ F: Inicio-Fin y Fin-Inicio
Si algún extremo ∈ F: nodo∉F fi
Selección del siguiente nodo basada en la feromona
p(ni, nj) = τij/∑l∈NodosVálidos (τil)
Si se encuentra un si llegar a fi comprobar si camino almacenar camino parcial continuar búsqueda
Actualización de feromona:
◦ Local: τij(t) = τij(t-1) + cte/(1000·wij)
◦ Global: Enlace en camino: τij(t) = τij(t-1)·(1-ρ) + cte/longCamino
Enlace no en camino: τij(t) = τij(t-1)·(1-ρ)
Cuando finaliza búsqueda Difusión Radial de Olor
Si cambios en el grafo la búsqueda no se interrumpe
20
21
Cuatro Fases: 1. Grafo Vasto Estático Un Nodo Comida
2. Grafo Vasto Estático Varios Nodos Comida
3. Grafo Vasto Dinámico Varios Nodos Comida
4. Grafo Vasto Estático Varios Nodos Comida y Preprocesado
Evaluación en cada fase: ◦ Grafo genérico aunque con alto índice de agrupamiento
◦ 200.000 nodos y 600.000 enlaces
◦ Parámetros bajo estudio: Tiempo de respuesta, Coste del Camino, Tasa de Éxito, Tiempo de Difusión
21
22 22
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
23 23
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
24 24
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
25 25
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
26 26
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
27 27
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
28 28
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
29 29
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
30 30
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
31 31
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
32 32
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
33 33
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
34 34
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
35 35
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
36 36
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
37 37
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
38 38
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
39 39
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
40 40
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
41 41
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
42 42
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
43 43
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
2. Grafo Vasto Estático Varios Nodos Comida ◦ Uso de u
◦ Comprobación de Olor cuando se alcanza Nodo Comida
44 44
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Tipo de Actualización de Feromona
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Actuación cuando se alcanza Olor
2. Grafo Vasto Estático Varios Nodos Comida ◦ Uso de u
◦ Comprobación de Olor cuando se alcanza Nodo Comida
U = {ui} Mientras que no se encuentre
olor ≥ ui
45 45
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Tipo de Actualización de Feromona
◦ Actuación cuando se alcanza Olor
2. Grafo Vasto Estático Varios Nodos Comida ◦ Uso de u
◦ Comprobación de Olor cuando se alcanza Nodo Comida 3. Grafo Vasto Dinámico Varios Nodos Comida ◦ Comportamiento Áreas de Olor
◦ Efecto de los cambios en las hormigas
46 46
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Tipo de Actualización de Feromona
◦ Actuación cuando se alcanza Olor
2. Grafo Vasto Estático Varios Nodos Comida ◦ Uso de u
◦ Comprobación de Olor cuando se alcanza Nodo Comida 3. Grafo Vasto Dinámico Varios Nodos Comida ◦ Comportamiento Áreas de Olor
◦ Efecto de los cambios en las hormigas
47 47
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Tipo de Actualización de Feromona
◦ Actuación cuando se alcanza Olor
2. Grafo Vasto Estático Varios Nodos Comida ◦ Uso de u
◦ Comprobación de Olor cuando se alcanza Nodo Comida 3. Grafo Vasto Dinámico Varios Nodos Comida ◦ Comportamiento Áreas de Olor
◦ Efecto de los cambios en las hormigas
48 48
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Tipo de Actualización de Feromona
◦ Actuación cuando se alcanza Olor
2. Grafo Vasto Estático Varios Nodos Comida ◦ Uso de u
◦ Comprobación de Olor cuando se alcanza Nodo Comida 3. Grafo Vasto Dinámico Varios Nodos Comida ◦ Comportamiento Áreas de Olor
◦ Efecto de los cambios en las hormigas
49 49
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Tipo de Actualización de Feromona
◦ Actuación cuando se alcanza Olor
2. Grafo Vasto Estático Varios Nodos Comida ◦ Uso de u
◦ Comprobación de Olor cuando se alcanza Nodo Comida 3. Grafo Vasto Dinámico Varios Nodos Comida ◦ Comportamiento Áreas de Olor
◦ Efecto de los cambios en las hormigas
50 50
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Tipo de Actualización de Feromona
◦ Actuación cuando se alcanza Olor
2. Grafo Vasto Estático Varios Nodos Comida ◦ Uso de u
◦ Comprobación de Olor cuando se alcanza Nodo Comida 3. Grafo Vasto Dinámico Varios Nodos Comida ◦ Comportamiento Áreas de Olor
◦ Efecto de los cambios en las hormigas
51 51
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Tipo de Actualización de Feromona
◦ Actuación cuando se alcanza Olor
2. Grafo Vasto Estático Varios Nodos Comida ◦ Uso de u
◦ Comprobación de Olor cuando se alcanza Nodo Comida 3. Grafo Vasto Dinámico Varios Nodos Comida ◦ Comportamiento Áreas de Olor
◦ Efecto de los cambios en las hormigas
52 52
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Tipo de Actualización de Feromona
◦ Actuación cuando se alcanza Olor
2. Grafo Vasto Estático Varios Nodos Comida ◦ Uso de u
◦ Comprobación de Olor cuando se alcanza Nodo Comida 3. Grafo Vasto Dinámico Varios Nodos Comida ◦ Comportamiento Áreas de Olor
◦ Efecto de los cambios en las hormigas
53 53
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Tipo de Actualización de Feromona
◦ Actuación cuando se alcanza Olor
2. Grafo Vasto Estático Varios Nodos Comida ◦ Uso de u
◦ Comprobación de Olor cuando se alcanza Nodo Comida 3. Grafo Vasto Dinámico Varios Nodos Comida ◦ Comportamiento Áreas de Olor
◦ Efecto de los cambios en las hormigas
54 54
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Tipo de Actualización de Feromona
◦ Actuación cuando se alcanza Olor
2. Grafo Vasto Estático Varios Nodos Comida ◦ Uso de u
◦ Comprobación de Olor cuando se alcanza Nodo Comida 3. Grafo Vasto Dinámico Varios Nodos Comida ◦ Comportamiento Áreas de Olor
◦ Efecto de los cambios en las hormigas
55 55
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Tipo de Actualización de Feromona
◦ Actuación cuando se alcanza Olor
2. Grafo Vasto Estático Varios Nodos Comida ◦ Uso de u
◦ Comprobación de Olor cuando se alcanza Nodo Comida 3. Grafo Vasto Dinámico Varios Nodos Comida ◦ Comportamiento Áreas de Olor
◦ Efecto de los cambios en las hormigas
56 56
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Tipo de Actualización de Feromona
◦ Actuación cuando se alcanza Olor
2. Grafo Vasto Estático Varios Nodos Comida ◦ Uso de u
◦ Comprobación de Olor cuando se alcanza Nodo Comida 3. Grafo Vasto Dinámico Varios Nodos Comida ◦ Comportamiento Áreas de Olor
◦ Efecto de los cambios en las hormigas
57
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Tipo de Actualización de Feromona
◦ Actuación cuando se alcanza Olor
2. Grafo Vasto Estático Varios Nodos Comida ◦ Uso de u
◦ Comprobación de Olor cuando se alcanza Nodo Comida 3. Grafo Vasto Dinámico Varios Nodos Comida ◦ Comportamiento Áreas de Olor
◦ Efecto de los cambios en las hormigas 4. Grafo Vasto Estático Varios Nodos Comida y Preprocesado
◦ Algoritmo de mantenimiento
57
58
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Tipo de Actualización de Feromona
◦ Actuación cuando se alcanza Olor
2. Grafo Vasto Estático Varios Nodos Comida ◦ Uso de u
◦ Comprobación de Olor cuando se alcanza Nodo Comida 3. Grafo Vasto Dinámico Varios Nodos Comida ◦ Comportamiento Áreas de Olor
◦ Efecto de los cambios en las hormigas 4. Grafo Vasto Estático Varios Nodos Comida y Preprocesado
◦ Algoritmo de mantenimiento
58
59
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Tipo de Actualización de Feromona
◦ Actuación cuando se alcanza Olor
2. Grafo Vasto Estático Varios Nodos Comida ◦ Uso de u
◦ Comprobación de Olor cuando se alcanza Nodo Comida 3. Grafo Vasto Dinámico Varios Nodos Comida ◦ Comportamiento Áreas de Olor
◦ Efecto de los cambios en las hormigas 4. Grafo Vasto Estático Varios Nodos Comida y Preprocesado
◦ Algoritmo de mantenimiento
59
60
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Tipo de Actualización de Feromona
◦ Actuación cuando se alcanza Olor
2. Grafo Vasto Estático Varios Nodos Comida ◦ Uso de u
◦ Comprobación de Olor cuando se alcanza Nodo Comida 3. Grafo Vasto Dinámico Varios Nodos Comida ◦ Comportamiento Áreas de Olor
◦ Efecto de los cambios en las hormigas 4. Grafo Vasto Estático Varios Nodos Comida y Preprocesado
◦ Algoritmo de mantenimiento
60
61
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Tipo de Actualización de Feromona
◦ Actuación cuando se alcanza Olor
2. Grafo Vasto Estático Varios Nodos Comida ◦ Uso de u
◦ Comprobación de Olor cuando se alcanza Nodo Comida 3. Grafo Vasto Dinámico Varios Nodos Comida ◦ Comportamiento Áreas de Olor
◦ Efecto de los cambios en las hormigas 4. Grafo Vasto Estático Varios Nodos Comida y Preprocesado
◦ Algoritmo de mantenimiento
61
62
1. Grafo Vasto Estático Un Nodo Comida ◦ Valor de u
◦ Lista Tabú
◦ Subdivisión de Colonias
◦ Tipo de Actualización de Feromona
◦ Actuación cuando se alcanza Olor
2. Grafo Vasto Estático Varios Nodos Comida ◦ Uso de u
◦ Comprobación de Olor cuando se alcanza Nodo Comida 3. Grafo Vasto Dinámico Varios Nodos Comida ◦ Comportamiento Áreas de Olor
◦ Efecto de los cambios en las hormigas 4. Grafo Vasto Estático Varios Nodos Comida y Preprocesado
◦ Algoritmo de mantenimiento
62
63
Slashdot 02/2009: 82.168 nodos y 948.464 enlaces
Parámetros bajo estudio: ◦ Tiempo de respuesta
◦ Coste del Camino
◦ Tasa de Éxito
Comparativa:
◦ ACO
◦ Dijkstra
10.000 servicios
Mejor servicio con 15 sec de espera
Parameter Value
tthreshold 600 sec
#ants 500
ρ 0.6
m 1.000.000
k 100%
u 999.999
63
64
Dijkstra ACO
(1)
SoSACO
(2)
SoSACO
(3)
SoSACO
(4)
SoSACO
Coste 4,51 387,49 5,89 5,12 - 4,56
Tiempo (seg) 563,39 253,32 2,15 1,63 - 1,91
Tasa de Éxito 100% 90,6% 100% 100% 99,6% 100%
64
(1) SoSACO Grafo Estático con Un Nodo Comida
(2) SoSACO Grafo Estático con Varios Nodos Comida (9 Nodos
Comida)
(3) SoSACO Grafo Dinámico con Varios Nodos Comida (9 Nodos
Comida y 1 cambio/segundo)
(4) SoSACO Grafo Estático con Varios Nodos Comida (9 Nodos
Comida) + Preprocesado
65
SoSACO: ACO + Nodos Comida + Olor
Reducción del tiempo de respuesta del algoritmo.
Obtención de costes de caminos próximos a los óptimos.
Aumento en la tasa de éxito.
Adaptación a los cambios que se puedan producir en el grafo.
65
66
Incluir la fase 4 en el dinamismo.
Dinamismo completo: cambios estructurales + cambios en los costes de los nodos/enlaces.
Incorporar aprendizaje automático para la elección de los nodos comida, así como del umbral del olor.
Cambiar inicialización de las hormigas sustitutas de las afectadas por cambios.
Umbral de disipación del olor.
66
Jesica Rivero Espinosa
jrivero@inf.uc3m.es
VI Jornadas MAVIR: Tecnologías de Acceso a la Información: Estado actual y retos
Jornadas académicas