8 FuncionesHeuristicas

Métodos Heurísticos en
Inteligencia Artificial
Javier Ramírez-Rodríguez
Ana Lilia Laureano-Cruces
Universidad Autónoma Metropolitana

Métodos Heurísticos en
Inteligencia Artificial
„

„

Los problemas de Inteligencia Artificial
(IA) generalmente usan un término común
llamado estado.
No hay un algoritmo formal que los
resuelva, i.e., dado un estado inicial no se
puede decir cual es la secuenciade etapas
para llegar a un estado meta.
Met. Heurísticos en IA: Ramírez/Laureano

„

„

„

„

„

La IA estudia especialmente métodos que permiten
resolver problemas en los que no existe el
conocimiento sistemático para plantear una solución
analítica.
Estos métodos tienen la ventaja de poderse aplicar en
una gran diversidad de clases de problemas.
Para llevarlos a cabo efectiva y eficientemente,sobre
dichos métodos se utiliza el conocimiento heurístico
disponible.
Entre menos estados se generen, mejor es el
algoritmo utilizado para llegar al estado meta.
Heurístico: Viene del griego heuriskein que significa
encontrar o descubrir.
Met. Heurísticos en IA: Ramírez/Laureano

„

„

„

En Inteligencia Artificial, heurístico se
describe mejor como método de búsqueda.
La búsqueda heurísticaconsiste en añadir
información, basándose en el espacio
estudiado hasta ese momento, de forma que
se restringe drásticamente esa búsqueda
Muchos problemas de IA se pueden modelar
como una gráfica en donde hay que buscar
recorridos o caminos con ciertas
características.
Met. Heurísticos en IA: Ramírez/Laureano

„

„

Para estos modelos se han desarrollado
muy diversas heurísticas que han dado
muybuenos resultados para encontrar
soluciones aproximadas.
Entre las que se pueden mencionar

algoritmos genéticos, recocido simulado y
en general algoritmos evolutivos.

Met. Heurísticos en IA: Ramírez/Laureano

„

La IA estudia especialmente métodos que permiten resolver
problemas en los que no existe el conocimiento sistemático
para plantear una solución analítica (a lo ancho, en
profundidad, hillclimbing).
„

„

Estos métodos, considerados débiles por realizar procedimientos
de búsqueda no informada, no aprovechan la información
relevante del dominio, suelen ser poco eficientes, pero tienen la
ventaja de poderse aplicar en una gran diversidad de clases de
problemas.
Para llevarlos a cabo efectiva y eficientemente, sobre dichos
métodos se utiliza el conocimiento heurístico disponible.

• Laclave para el enfoque de IA es búsqueda inteligente y
emparejamiento de estados. Entre menos estados se
generen, mejor es el algoritmo utilizado para llegar al
estado meta.
Met. Heurísticos en IA: Ramírez/Laureano

Búsqueda Heurística
„

George Polya: Estudio de métodos y
reglas para descubrimiento e invención.
„

Las heurísticas son formalizadas como reglas
para elegir (búscar) las ramas en elespacio
de estados que son más probables de llegar
a una solución aceptable del problema.

Met. Heurísticos en IA: Ramírez/Laureano

En IA, se emplean heurísticas
en dos casos
„

Un problema puede no contar con solución exacta
debido a ambigüedades inherentes en el problema o
datos disponibles.
„
„

„

Diagnóstico médico
Visión

Un problema puede tener solución exacta, pero el costo
computacionalpor encontrarla puede ser prohibitivo.
„
„
„

Problema del agente viajero
Problema de coloración
Juego de ajedrez

Met. Heurísticos en IA: Ramírez/Laureano

Búsquedas Heurísticas y Sistemas
Expertos
„

Juegos simples son vehículos ideales para explorar el
diseño y comportamiento de algoritmos de búsqueda
heurística debido a que
„
„
„
„

El espacio de búsqueda es suficientemente grande querequiere poda heurística.
Son suficientemente complejos para sugerir una amplia
variedad de evaluaciones heurísticas.
Generalmente admiten representaciones sencillas.
Cada nodo del espacio de estados tiene una representación
común, una heurística puede aplicarse a través del espacio de
estados.

Met. Heurísticos en IA: Ramírez/Laureano

Las Heurísticas
„

„
„
„

„

Atacan la complejidad guiando la...