busqueda local

Busqueda local.ppt

Guía
Búsqueda local
Introducción a problemas
Formulación del problema como
búsqueda local
Algoritmo de escalada de la colina
Algoritmo de enfriamiento simulado
Algoritmode búsqueda tabú

Búsqueda Local
Basado en:
How to solve it. Modern Heuristics
Michalewicks & Fogel

2

1

Búsqueda local

Búsqueda local

Los métodos de búsqueda anteriores:
Exploranespacio de estados y buscan
sistemáticamente las opciones
Mantienen una o mas rutas en memoria
y guardan que alternativas han sido
consideradas y cuales no
Solución: Ruta del estado inicial alobjetivo

En algunos problemas la ruta es
irrelevante, únicamente importa el estado
objetivo o final
Ejemplos
8 reinas
Diseño de circuitos
Calendarizacion de actividades
Optimización de unared
Problema de satisfacibilidad
Problema del cartero
Programación no lineal

3

Búsqueda local

Búsqueda local

Cuando la ruta es irrelevante y
únicamente nos importa el estado
objetivo ofinal debemos considerar los
algoritmos de búsqueda local

Ventajas
Uso de memoria limitada
Encuentran soluciones razonables en
espacio de estados mas complejos, por
ejemplo estados continuosSon buenos para resolver problemas de
optimización (buscar de acuerdo a la
función de evaluación)
5

Paquete Didactico - IA

4

6

Busqueda local.ppt

Búsqueda local

Introducción aproblemas
Los problemas del mundo real son difíciles de
resolver por:

Espacio de estados
x: Estados
y: Función objetivo
Si y corresponde al costo, hay que
encontrar el punto mas bajo (mínimoglobal)
Si hay que encontrar el punto máximo,
se busca el máximo global

El numero de posibles soluciones es tan grande
que no se permite una búsqueda exhaustiva
Tenemos que simplificar elproblema y luego esta
solución simplificada no es tan útil
La función de evaluación tiene ruido o varia con el
tiempo
Las posibles soluciones tienen muchas
restricciones
7

Introducción a...