Inteligencia Artificial II

Búsqueda Local�

Adaptado de: Martin Marchetta�martin.marchetta@ingenieria.uncuyo.edu.ar

Hernán Garrido�carloshernangarrido@gmail.com

Complejidad de los algoritmos de Búsqueda Global

2

Búsqueda local

• Búsqueda global
• Ventaja
• Dadas ciertas condiciones, se pueden garantizar que los algoritmos son completos y óptimos�
• Desventajas
• En su mayoría, su complejidad espacial y temporal es exponencial en el peor caso lo que los hace imprácticos en problemas reales

3

Búsqueda local

• Algoritmos de búsqueda local
• Evalúan y modifican un estado o un conjunto reducido de estados → se mueven entre estados “vecinos”�
• Sirven cuando lo que importa es el estado final y no cómo llegar a él�
• Utilizan menos memoria que los algoritmos sistemáticos (generalmente una cantidad constante)�
• No realizan una exploración sistemática del espacio de estados�
• Permiten manejar espacios de estados muy grandes o incluso infinitos (continuos) y obtener soluciones razonables en tiempos razonables

​

4

Búsqueda local

• Algoritmos de búsqueda local: Estados Vecinos

​

5

Estado actual

Estados vecinos

. . .

Búsqueda local

• Algoritmos de búsqueda local: situaciones típicas

​

6

Búsqueda local

• Algoritmos de búsqueda local:
• Basados en gradiente (sólo para funciones continuas y derivables)
• Newton
• Newton-Rapson
• Muchos otros …
• No basados en gradiente
• Hill climbing (ascenso de cima, steepest ascent)
• Optimización local
• Simulated Annealing (Temple Simulado, Recocido simulado)
• Optimización local
• Basin hopping (Salto entre cuencas, multiple restarts)
• Optimización global no garantizada

​

​

​

7

Búsqueda local

• Hill climbing (ascenso de cima, steepest ascent)
• Cada estado es una solución completa (posiblemente mala o inconsistente)
• Ej: Un schedule completo de asignación de recursos de fabricación para una semana�
• Es un algoritmo iterativo que en cada iteración
• Analiza los vecinos (calcula su costo / valor)
• Se mueve al vecino con menor costo (o mayor valor)
• Si hay más de un vecino en esta situación, elige aleatoriamente�
• También se conoce como Greedy Local Search (búsqueda avara local)�

​

8

Búsqueda local

• Hill climbing (ascenso de cima, steepest ascent)
• Problemas
• Se queda atascado en máximos/mínimos locales
• En mesetas puede quedarse atascado indefinidamente y no saberlo

9

Algoritmo:

1. Analiza los vecinos (calcula su costo / valor)
2. Se mueve al vecino con menor costo (o mayor valor)
3. Si hay más de un vecino en esta situación, elige aleatoriamente

.

Todos los vecinos �son peores

Búsqueda local

• Hill climbing (ascenso de cima, steepest ascent)
• Hay muchas variantes del algoritmo para aliviar estos problemas
• Elegir aleatoriamente entre los vecinos que tienen mejor costo que el estado actual (aunque no sea el mejor de todos los vecinos) → Stochastic Hill Climbing
• Elegir aleatoriamente entre los vecinos hasta que alguno sea mejor que el estado actual → First-choice Hill Climbing
• Hill climbing tradicional con reinicio aleatorio cuando �queda atascado → Random-restart Hill Climbing�
• Es un algoritmo completo?

10

Búsqueda local

• Simulated Annealing (Temple Simulado)
• Problemas de Hill Climbing
• Si nunca se mueve a un estado peor → no es óptimo y posiblemente tampoco completo
• Si hace una caminata aleatoria → es muy ineficiente
• Combinando ambos? → Temple Simulado
• En cada iteración
• Se elige un estado vecino aleatoriamente
• Si el nuevo estado es mejor, se acepta
• Si el nuevo estado es peor, se acepta con probabilidad e^ΔE/T
• T disminuye de acuerdo a un schedule o agenda�(puede ser lineal, exponencial, etc)
• En cada iteración, la probabilidad de aceptar un estado peor se reduce

11

Búsqueda local

• Simulated Annealing (Temple Simulado)
• Ejemplo para maximizar VALUE

​

12

Búsqueda local

• Basin-hopping
• Combina optimización local con perturbaciones aleatorias
• Generalmente se usa para espacios continuos
• Similar a Temple Simulado pero con minimización local
• Se sugiere que el “step size” esté en el rango promedio �de separación entre mínimos (máximos) locales

�

​

13

function basinhopping(f, N, s)�Inputs: f: funcion a minimizar, N: cantidad de saltos, s: step size�� x ← prev-x ← random()� prev-y ← f(x)� for i = 1 to N do� y, x ← minimo(f, x)� if y < prev-y then� prev-x, prev-y ← x, y� else � prev-x, prev-y ← x, y con probabilidad e^Δy/T� x ← prev-x + random(s)

¿Preguntas? �¿Opiniones?