Revolución IA

La Inteligencia Artificial está llamada a protagonizar la próxima Revolución tecnológica

Inicio

Sobre Revolucionia

Temas

Para saber más

Contacto

Algoritmos para búsqueda heurística

Fernando P.    26/01/2018

Temas:  Fundamentos

Básicamente, existen dos aproximaciones a la hora de tratar de resolver problemas mediante técnicas de búsqueda de soluciones. Se trata de los algoritmos para búsqueda sistemática y los algoritmos para búsqueda heurística. La diferencia entre ambas aproximaciones reside en la forma de considerar y manejar la información disponible sobre el problema. Ya hemos hablado de forma general sobre ambas clases de algoritmos.

Habiendo descrito ya varios algoritmos para búsqueda sistemática, basándonos en algunas ideas de este tipo de algoritmos, vamos a ver cómo podemos mejorar la búsqueda sistemática incorporando información adicional que nos permita tomar un poco de riesgo a cambio de mejorar el rendimiento de un algoritmo normal de búsqueda sistemática.

Motivación de la búsqueda heurística
En general, los algoritmos para búsqueda sistemática tienen problemas de rendimiento, sobre todo si se trata de problemas en los que interesa localizar una solución óptima. Hay problemas que se adaptan bien a algunos algoritmos concretos, pero no es el caso general.

No se puede decir que con los algoritmos que conocemos para búsqueda sistemática sea posible atacar cualquier problema. Con problemas muy grandes es posible que ninguno de estos algoritmos pueda localizar soluciones satisfactorias.

Se nos plantea, entonces, la cuestión relativa a ver si podemos, de alguna forma, mejorar los algoritmos para búsqueda sistemática en su aplicación a problemas grandes. Y esta es la motivación que da lugar a la idea de búsqueda heurística.

En la búsqueda heurística vamos a tratar de usar información extra sobre el problema. Información que puede ser incompleta o inexacta, al contrario de la información que tenemos sobre la estructura del problema (estados, acciones y costes), que se supone que es completa y exacta.

La idea es usar esa información extra, asumiendo un riesgo derivado de su posible incompletitud o inexactitud, para afinar el proceso de selección de nodos a expandir en el árbol de búsqueda correspondiente al problema.

A veces, también se conoce a la búsqueda heurística como búsqueda informada en referencia a esa información extra que vamos a usar, que puede ser información de largo alcance sobre la estructura general del problema, en contraposición a la búsqueda sistemática o ciega, que sólo usa información local relativa a las acciones a tomar en cada estado del problema (nodo del árbol de búsqueda).

Búsqueda por lo mejor
La búsqueda heurística opera usando un algoritmo genérico que vamos a denominar algoritmo de búsqueda por lo mejor. Se trata de una instancia del algoritmo general para construir árboles de búsqueda, de la misma forma que lo son cada uno de los algoritmos vistos para búsqueda sistemática.

En este sentido no hay mucha novedad respecto a lo visto en los algoritmos para búsqueda sistemática. El concepto de árbol de búsqueda sigue siendo la base de todo el proceso y las diferencias entre unos y otros algoritmos se refieren a la forma en la que se va construyendo ese árbol a base de expandir nodos en la frontera del mismo.

Función de evaluación
El núcleo del algoritmo de búsqueda por lo mejor consiste en una función  f(n)  que vamos a denominar función de evaluación y que, para cada nodo de la frontera, nos va a proporcionar una estimación del coste asociado a expandir ese nodo. El nodo que se elegirá para ser expandido será el de menor valor en la función de evaluación.

La forma exacta de la función de evaluación va a depender de cada problema y de la información extra que podamos conseguir sobre el mismo. No es algo que se pueda describir a priori, aunque sí que existen algunas situaciones generales que se pueden aplicar en ciertos problemas.

Por ejemplo, dado un nodo en la frontera del árbol de búsqueda, hacemos que la función de evaluación en ese nodo sea igual al coste desde el origen hasta ese nodo, tenemos que el algoritmo de búsqueda por lo mejor es idéntico al algoritmo para búsqueda con coste uniforme.

Función heurística
El concepto de función de evaluación es muy genérico, para dejar la puerta abierta a implementaciones arbitrariamente complejas del algoritmo de búsqueda por lo mejor.

Pero, en la práctica, la forma más común de función de evaluación incluirá un término  h(n)  denominado función heurística que no va a ser tan genérica.

Usaremos la función heurística para obtener una estimación del coste asociado a llegar hasta un nodo destino partiendo del nodo  n. Si estas estimaciones son relativamente fiables, la idea de expandir el nodo cuya estimación de coste sea la más baja tiene sentido y, en promedio, esta forma de proceder tendrá tendencia a proporcionar buenas soluciones sin necesidad de explorar todo el árbol de búsqueda.

En general, vamos a suponer que una función heurística es no negativa y que su valor es cero sólo para nodos destino en el árbol de búsqueda.

La función heurística será la encargada de codificar toda la información incompleta o inexacta que tengamos sobre el problema y en el resto de términos, hasta completar la función de evaluación, se puede codificar información exacta derivada de la estructura conocida del problema.

Será la función de evaluación la que guíe la expansión del árbol de búsqueda en el algoritmo de búsqueda por lo mejor. Pero en un contexto esencialmente heurístico será la función heurística el término principal de la función de evaluación y será la que verdaderamente guíe el proceso de expansión del árbol de búsqueda.

Los algoritmos para búsqueda heurística son extensiones del concepto general de árboles de búsqueda a las que se añade información extra incompleta o inexacta con intención de acelerar el proceso normal de búsqueda sistemática.

Para saber más:

• AI: A modern Approach

Libro de Stuart Russell y Peter Norvig que trata todas las técnicas de Inteligencia Artificial. No hace demasiado énfasis en cuestiones conectivistas (redes neuronales artificiales) y contiene abundante material del resto de técnicas. El capítulo 3 contiene una discusión detallada sobre la búsqueda heurística.