PDF de programación - 2 BH3 Busqueda local

Búsqueda Local

Búsqueda Local

Introducción

A veces el camino para llegar a la solución no nos importa, buscamos
en el espacio de soluciones
Queremos la mejor de entre las soluciones posibles alcanzable en un
tiempo razonable (el óptimo es imposible)
Tenemos una función que nos evalúa la calidad de la solución, pero
que no esta ligada a ningún coste necesariamente
La búsqueda se realiza desde una solución inicial que intentamos
mejorar modificándola (operadores)
Los operadores nos mueven entre soluciones vecinas

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

1 / 33

Búsqueda Local

Búsqueda Local

Introducción

La función heurística:

Aproxima la calidad de una solución (no representa un coste)
Hemos de optimizarla (maximizarla o minimizarla)
Combinará los elementos del problema y sus restricciones
(posiblemente con diferentes pesos)
No hay ninguna restricción sobre como ha de ser la función, solo ha de
representar las relaciones de calidad entre las soluciones
Puede tomar valores positivos o negativos

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

2 / 33

Búsqueda Local

Búsqueda Local

Introducción

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

3 / 33

Funcion ObjetivoEspacio de SolucionesSolucion actualBúsqueda Local

Búsqueda Local

Introducción

El tamaño del espacio de soluciones por lo general no permite obtener
el óptimo
Los algoritmos no pueden hacer una exploración sistemáticaProblems
La función heurística se usará para podar el espacio de búsqueda
(soluciones que no merece la pena explorar)
No se suele guardar historia del camino recorrido (el gasto de
memoria es mínimo)
La falta total de memoria puede suponer un problema (bucles)

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

4 / 33

Escalada (Hill climbing)

Búsqueda Local

Hill Climbing

Escalada simple

Se busca cualquier operación que suponga una mejora respecto al padre

Escalada por máxima pendiente (steepest-ascent hill climbing,
gradient search)

Se selecciona el mejor movimiento (no el primero de ellos) que suponga
mejora respecto al estado actual

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

5 / 33

Hill Climbing

Búsqueda Local

Hill Climbing

Algoritmo: Hill Climbing
Actual ← Estado_inicial
fin ← falso
mientras no fin hacer

Hijos ← generar_sucesores(Actual)
Hijos ← ordenar_y_eliminar_peores(Hijos, Actual)
si no vacio?(Hijos) entonces

sino

Actual ← Escoger_mejor(Hijos)
fin ← cierto

fin

fin

Sólo se consideran los descendientes cuya función de estimación es mejor que
la del padre (poda del espacio de búsqueda)
Se puede usar una pila y guardar los hijos mejores que el padre para hacer
backtracking, pero por lo general es prohibitivo
Es posible que el algoritmo no encuentre una solución aunque la haya
c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

6 / 33

Hill climbing

Búsqueda Local

Hill Climbing

Las características de la función heurística y la solución inicial
determinan el éxito y rapidez de la búsqueda
La estrategia del algoritmo hace que la búsqueda pueda acabar en un
punto donde la solución sólo sea la óptima aparentemente
Problemas

Máximo local: Ningún vecino tiene mejor coste
Meseta: Todos los vecinos son iguales
Cresta: La pendiente de la función sube y baja (efecto escalón)

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

7 / 33

Hill climbing

Búsqueda Local

Hill Climbing

Posibles soluciones

Reiniciar la búsqueda en otro punto buscando mejorar la solución
actual (Random Restarting Hill Climbing)
Hacer backtracking a un nodo anterior y seguir el proceso en otra
dirección (solo posible limitando la memoria para hacer el backtracking,
Beam Search)
Aplicar dos o más operaciones antes de decidir el camino
Hacer HC en paralelo (p.ej. Dividir el espacio de búsqueda en regiones
y explorar las más prometedoras, posiblemente compartiendo
información)

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

8 / 33

Hill Climbing - Ejemplo - Knapsack problem

Búsqueda Local

Hill Climbing

BY: $\ C Dake

Solución: Cualquier combinación de objetos en la mochila
Solución Inicial: Mochila vacía
Operadores: Meter y sacar objetos de la mochila
Valori
Pesoi

Función heurística: maxP

i Valori o maxP

i

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

9 / 33

Hill Climbing - Ejemplo - Knapsack problem

Búsqueda Local

Hill Climbing

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

10 / 33

8€/5Kg7€/6Kg6€/4Kg2€/1Kg3€/1Kg12€/10KgSol Inicial...7€/6Kgh(n)=78€/5Kgh(n)=812€/10Kgh(n)=1216KgHill Climbing - Ejemplo - Knapsack problem

Búsqueda Local

Hill Climbing

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

11 / 33

8€/5Kg7€/6Kg6€/4Kg2€/1Kg3€/1Kg12€/10Kg...7€/6Kgh(n)=198€/5Kgh(n)=2012€/10Kgh(n)=1812€/10Kg12€/10Kg12€/10Kg6€/4KgHill Climbing - Ejemplo - Knapsack problem

Búsqueda Local

Hill Climbing

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

12 / 33

8€/5Kg7€/6Kg6€/4Kg2€/1Kg3€/1Kg12€/10Kgh(n)=228€/5Kg12€/10Kgh(n)=2312€/10Kg12€/10Kg3€/1Kg8€/5Kg8€/5Kg2€/1KgSol Final8€/5Kg7€/6Kg6€/4Kg3€/1KgÓptimoh(n)=24Otros algoritmos de búsqueda local

Búsqueda Local

Otros Algoritmos

Se han planteado otros algorimos inspirados en analogías físicas y
biológicas:

Simulated annealing: Hill-climbing estocástico inspirado en el proceso
de enfriamiento de metales
Algoritmos genéticos: Hill-climbing paralelo inspirado en los
mecanismos de selección natural
Ambos mecanismos se aplican a problemas reales con bastante éxito

Pero también Particle Swarm Optimization, Ant Colony Optimization,
Intelligent Water Drop, Gravitational search algorithm, ...

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

13 / 33

Simulated Annealing

Búsqueda Local

Simulated Annealing

Es un algoritmo de Hill-Climbing estocástico (elegimos un sucesor de
entre todos los posibles según una distribución de probabilidad, el
sucesor podría ser peor)
Hacemos paseos aleatorios por el espacio de soluciones
Inspirado en el proceso físico de enfriamiento controlado
(cristalización, templado de metales)
Se calienta un metal/disolución a alta temperatura y se enfría
progresivamente de manera controlada
Si el enfriamiento es adecuado se obtiene la estructura de menor
energía (mínimo global)

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

14 / 33

Simulated Annealing

Búsqueda Local

Simulated Annealing

BY: $\ C DoITPoMS, University of Cambridge

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

15 / 33

Simulated Annealing - Metodología

Búsqueda Local

Simulated Annealing

Debemos identificar los elementos del problema con los del problema
físico
Temperatura, parámetro de control
Energía, calidad de la solución f (n)
Función de aceptación, permite decidir si escoger un nodo sucesor
F(∆f , T ), función de la temperatura y la diferencia de calidad entre la
solución actual y la solución candidata
A menor temperatura menor probabilidad de elegir sucesores peores

Estrategia de enfriamiento, número de iteraciones a realizar, como
bajar la temperatura y cuantos sucesores explorar para cada paso de
temperatura

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

16 / 33

Simulated annealing - Algoritmo Básico

Búsqueda Local

Simulated Annealing

Algoritmo: Simulated Annealing
Partimos de una temperatura inicial
mientras la temperatura no sea cero hacer

// Paseo aleatorio por el espacio de soluciones
para un numero prefijado de iteraciones hacer

Enuevo ← Genera_sucesor_al_azar(Eactual)
∆E ← f (Eactual) − f (Enuevo)
si ∆E > 0 entonces
Eactual ← Enuevo
con probabilidad e∆E /T: Eactual ← Enuevo

sino

fin

fin
Disminuimos la temperatura

fin

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

17 / 33

Simulated Annealing

Búsqueda Local

Simulated Annealing

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

18 / 33

Hill ClimbingSimulated AnnealingEspacio de SolucionesFunción ObjetivoSimulated Annealing - Aplicación

Búsqueda Local

Simulated Annealing

Adaptable a problemas de optimización combinatoria (configuración
óptima de elementos) y continua (punto óptimo en un espacio
N-dimensional)
Indicado para problemas grandes en los que el óptimo esta rodeado de
muchos óptimos locales
Indicado para problemas en los que encontrar una heurística
discriminante es difícil (una elección aleatoria es tan buena como otra
cualquiera)
Aplicaciones: TSP, Diseño de circuitos VLSI
Problemas: Determinar los valores de los parámetros requiere
experimentación

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

19 / 33

Simulated annealing - Ejemplo - TSP

Búsqueda Local

Simulated Annealing

Viajante de comercio (TSP): Espacio de búsqueda N!
Definimos posibles transformaciones de una solución (operadores):
Inversiones, traslaciones, intercambios
Definimos la función de energía (Suma de distancia entre ciudades,
según el orden de la solución)

E =

(xi − xi+1)2 + (yi − yi+1)2 +

q
(xN − x1)2 + (yN − y1)2

q

nX

i=1

Definimos una temperatura inicial (experimentación)
Determinamos cuantas iteraciones hacemos para cada temperatura y
como disminuimos la temperatura

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

20 / 33

Simulated annealing - Ejemplo - TSP

Búsqueda Local

Simulated Annealing

c b e a (LSI-FIB-UPC)

Inteligencia Artificial

Curso 2011/2012

21 / 33

1234512345Swap(2,3)12345Swap(5,3)12345h(n)=100h(n)=105h(n)=120h(n)=98Swap(4,3)Swap(2,3)12345h(n)=9012345Swap(3,3)h(n)=10112345Swap(2,5)h(n)=99OKOKOKKOKOKOSoluciónIt1It2It3It4It5It6Algoritmos Genéticos

Búsqueda Local

Algoritmos Genéticos

Inspirado en el mecanismo de selección natural

Los seres vivos se adaptan al entorno gracias a las características
heredadas de sus progenitores
Las posibilidades de supervivencia y reproducción son proporcionales a
la bondad de esas características
La combinació