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:
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.
Inicio |
![]() ![]() |
En general, todo el contenido de este sitio web es original, salvo referencias o enlaces a otros sitios web y citas o reproducciones expresamente presentadas como tales. No está permitida la reproducción ni la copia del contenido de este sitio web sin el permiso expreso de la propiedad del mismo. Este sitio web no utiliza cookies ni ningún otro mecanismo para almacenar información en los navegadores de los visitantes ni para realizar seguimiento de los mismos. 2017,2018 Revolucionia.net |
Sobre Revolucionia | ||
Temas | ||
Para saber más | ||
Contacto |