![Page 1: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/1.jpg)
Búsqueda local: hill-climbing
Blanca A. Vargas Govea * [email protected] * Agosto 21, 2012
Inteligencia Computacional
http://blancavg.com/tc3023/
![Page 2: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/2.jpg)
2
Métodos anteriores
A
B I
C G
D E F F H
H
La solución es una secuencia de accionesA-I-G-H
![Page 3: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/3.jpg)
3
Búsqueda local
A B C
G
D
E F H
En vez de explorar los caminos se evalúan y modifican uno o más estados
Los algoritmos son adecuados para problemas en los que importa el estado meta, no el camino
A C B
G
D
E F H
A C B
G
D
E F H
A B C
G
D
E F H
![Page 4: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/4.jpg)
4
Búsqueda local
A B C
G
D
E F H
Los caminos no se almacenan
El movimiento es hacia vecinos del estado
A C B
G
D
E F H
A C B
G
D
E F H
A B C
G
D
E F H
Generación yevaluación devecinos
![Page 5: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/5.jpg)
5
Algoritmo Hill climbing
simple
Selecciona la primer acción que mejora el estado actual
![Page 6: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/6.jpg)
6
Algoritmo Hill climbing
steepest ascent
Evalúa a todos los vecinos y se mueve en la dirección en donde el valor aumenta (“cuesta arriba”)
Termina cuando alcanza un pico donde ningún vecino tiene mayor valor
![Page 7: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/7.jpg)
7
Algoritmo Hill climbing
steepest ascent
● No mantiene un árbol de búsqueda● La estructura de datos del nodo actual solamente registra el estado y el valor de la función objetivo
● Si hay vecinos empatados, la estrategia más simple es seleccionar de forma aleatoria
![Page 8: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/8.jpg)
8
Algoritmo Hill climbing
steepest ascent
estado_actual = estado_inicialloop
Generar sucesores del estado_actualObtener el sucesor con el valor más altoif valor(sucesor) < valor(estado_actual)then
return estado_actualelse
estado_actual = sucesor
![Page 9: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/9.jpg)
9
Algoritmo Hill climbing
máximolocal
máximoglobal máximo
local
máximoglobal
Solución: óptimo local Solución: óptimo global
espacio de estadosespacio de estados
funciónobjetivo
funciónobjetivo
![Page 10: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/10.jpg)
10
Panorama – espacio de stados
Valor de la función objetivo
Posibles objetivos:● Minimizar costo● Maximizar el valor de la función
El estado inicial es importante
![Page 11: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/11.jpg)
11
Algoritmo Hill climbing
Razones de estancamiento
● Máximo local. Pico más alto que cualquier vecino pero menor al óptimo global.
● Cresta. Secuencia de máximos locales.
● Meseta. Área plana del espacio de estados (plano, hombro).
En cada caso, el algoritmo llega a un punto en el cual no puede alcanzar una mejor solución
![Page 12: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/12.jpg)
12
Algoritmo Hill climbing
Saliendo de mesetas
● Se llega a una meseta cuando el vecino mejor evaluado tiene el mismo valor que el estado actual.
● Idea: movimientos laterales esperando que encuentre un mejor vecino.
● Riesgo: que no existan y se entre en un ciclo infinito.
● Posible solución: limitar el no. de movimientos laterales.
hombro
máximo localplano
![Page 13: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/13.jpg)
13
Ejemplo 1: acomoda los bloques
Considera las 5 figuras geométricas de tamaño 1,2,3,4 y 5:
1
2
3
4
5
Se da el estado inicial y el estado meta. Solamente se puede mover la pieza de arriba y usar 2 stacks adicionales.
![Page 14: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/14.jpg)
14
Ejemplo 1- heurística 1
+1 por cada figura que esté sobre la figura correcta. El estado meta vale +5.-1 por cada figura que esté en la figura incorrecta.
![Page 15: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/15.jpg)
15
Ejemplo 1- heurística 1
1
2
3
4
5
Estado meta Estado inicial
1+1+1+1+1 = 5 -1+1+1+1-1 = 1
1
2
3
4
5
![Page 16: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/16.jpg)
16
Ejemplo 1- heurística 1
+1+1+1-1+1 = 3
Movimiento 1
Mejor evaluación queel estado inicial. Reem-plaza al estado actual.
1
2
3
4 5
Movimiento 2a
1
2
3
4 5
1+1-1+1-1 = 1
Menor al estado actual
![Page 17: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/17.jpg)
17
Ejemplo 1- heurística 1
+1+1+1-1+1 = 3
Movimiento 1
Mejor evaluación queel estado inicial. Reem-plaza al estado actual.
1
2
3
4 5
Movimiento 2b
12
3
4 5
1+1-1-1+1 = 1
Menor al estado actual
Para 2a y 2b laevaluación es menorque el estado inicial.
El movimiento 1 es el mejor.Se llega a un óptimo local
![Page 18: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/18.jpg)
18
Ejemplo 1- heurística 2
+n por cada figura que esté en un grupo correcto de n figuras. El estado meta tiene el valor de 10.-n por cada figura que esté en un grupo incorrecto de n figuras.
![Page 19: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/19.jpg)
19
Ejemplo 1- heurística 2
1
2
3
4
5
Estado meta Estado inicial
4 está sobre 1 pieza correcta = 13 está sobre 2 piezas correctas = 22 está sobre 3 piezas correctas = 31 está sobre 4 piezas correctas = 4
1
2
3
4
5
10
3 está sobre 1 pieza incorrecta = -12 está sobre 2 piezas incorrectas = -21 está sobre 3 piezas incorrectas = -35 está sobre 4 piezas incorrectas = -4
-10
![Page 20: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/20.jpg)
20
Ejemplo 1- heurística 2
3 está sobre 1 pieza incorrecta = -12 está sobre 2 piezas incorrectas = -21 está sobre 3 piezas incorrectas = -3
-1-2-3 = -6
Mejor evaluación queel estado inicial. Reem-plaza al estado actual.
1
2
3
4 5
Movimiento 1
Movimiento 2a
1
2
3
4 5
-1-2 = -3
Mayor al estado actual
![Page 21: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/21.jpg)
21
Ejemplo 1- heurística 2
3 está sobre 1 pieza incorrecta = -12 está sobre 2 piezas incorrectas = -21 está sobre 3 piezas incorrectas = -3
-1-2-3 = -6
Mejor evaluación queel estado inicial. Reem-plaza al estado actual.
1
2
3
4 5
Movimiento 1
Movimiento 2b
12
3
4 5
-2-1-1 = -4
Mayor al estado actual
Se evita el óptimo local
![Page 22: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/22.jpg)
22
Ejemplo 2 - 8 puzzle
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 2
3 4 5
6 7 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 5
6 7 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 5
6 7 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 2
3 4 5
6 7 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 5
6 7 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 7 5
6 8
1 4 2
3 5
6 7 8
1 2
3 4 5
6 7 8
1 2
3 4 5
6 7 8
1 2
3 4 5
6 7 8
Estado inicial Estado meta
h=4
h=0
h=4 h=2
h=3
Reemplaza
h=1 h=3 h=3
Reemplaza
h=0 h=2
En este caso, HC es exitoso
![Page 23: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/23.jpg)
23
Ejemplo 3: agente viajero
Agente viajero. Traveling Salesman Problem (TSP).Dado un conjunto de n ciudades y el costo del viaje entre cada par, el problema es encontrar la forma menos costosa de visitarlas todas, sin repetición y regresar al punto de partida.
BA
C
B
DE
F
4
5
2
1
3
1
2
4
3
1
2
34
12
Pueden usarse distintos opera-dores. El más simple: intercam-biar el orden en que dosciudades son visitadas.
![Page 24: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/24.jpg)
24
Ejemplo 3: agente viajero. Óptimo local.
Estado inicial
BA
C
B
DE
F
4
5
2
1
3
1
2
4
3
1
2
34
12
ABCDEF (16)
ACBDEF (17)ABDCEF (17)ABCEDF (19)ABCDFE (15) reemplaza
ABCDFE (15)
ACBDFE (16)ABDCFE (17)ABCFDE (20)Ninguno es mejor.
Óptimo local: ABCDFE
![Page 25: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/25.jpg)
25
Ejemplo 3: agente viajero. Óptimo global.
Si consideramos que cualquier par de ciudades puede intercambiarse al mismo tiempo:
ABCDEF (16)
ACBDEF (17)ADCBEF (11)AECDBF (15)AFCDEB (19)ABDCEF (16)ABEDCF (19)ABCEDF (17)ABCFED (16)ABCDFE (15)
Óptimo global: ADCBFE
ADCBEF (11)
ACDBEF (15)AECBDF (17)ADBCEF (13)ADFBEC (14)ADCFEB (14)AFCBED (16)ADEBCF (16)ADCEBF (12)ADCBFE (10)
Al reemplazar y continuar, nohay otro menor
![Page 26: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/26.jpg)
26
Variantes
Stochastic hill: no examina a todos los vecinos, selecciona aleatoriamente a uno y con base en la mejora decide si revisa otro o se queda con ése.
Random restart hill climbing: realiza series de búsqueda hill climbing a partir de estados iniciales generados aleatoriamente hasta que se encuentra la meta.
![Page 27: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/27.jpg)
27
Ventajas/desventajas de Hill Climbing
Ventajas
● Fácil de implementar, poca memoria● Fácil para obtener una solución aproximada
Desventajas
● El diseño de la función de evaluación puede ser difícil
● Si el no. de movimientos es muy grande puede ser ineficiente
● Si el no. de movimientos es pequeño puede estancarse fácilmente
![Page 28: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/28.jpg)
28
Familia de algoritmos de búsqueda local
Recocido simulado
Algoritmos genéticos
http://www.frankfurt-consulting.de/img/SimAnn.jpg
http://www.flickr.com/photos/42156072@N00/47457221/
![Page 29: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/29.jpg)
29
Ejercicio: resolver usando Hill Climbing
Problema de los misioneros y caníbales.3 misioneros y 3 caníbales están en la orilla izquiera de un río. Los 6 quieren cruzar el río. Un bote está disponible pero el bote solamente puede llevar 2 personas a la vez. Además, los misioneros no deben ser menos (en número) que los caníbales en ningún momento.
![Page 30: Inteligencia Computacional - Blanca A. Vargas Goveablancavg.com/tc3023ic/ic5.pdf · 23 Ejemplo 3: agente viajero Agente viajero. Traveling Salesman Problem (TSP). Dado un conjunto](https://reader035.vdocumento.com/reader035/viewer/2022062505/5bacf3a609d3f23f0d8c5d95/html5/thumbnails/30.jpg)
30
Russell, S., y Norvig, P. (2003). Artificial intelligence: A modern approach(2nd edition ed.). Prentice-Hall, Englewood Cliffs, NJ.
Grosan C., y Abraham A. (2011) Intelligent Systems: A Modern Approach. Intelligent Systems Reference Library, Volume 17. Springer.
Referencias