BÚSQUEDA LOCAL

Fecha de clases: jueves, 24 de julio de 2014

BÚSQUEDA LOCAL EN ESPACIOS CONTINUOS Y BÚSQUEDA ONLINE Y AMBIENTES DESCONOCIDOS

INTRODUCCIÓN.

El objetivo de esta clase es entender como un agente inteligente hace una búsqueda en espacios continuos o búsqueda online por lo que esta búsqueda solo se basa en lo que está pasando en ese estado para tomar de nuevo otra acción.

BÚSQUEDA LOCAL EN ESPACIOS CONTINUOS.

Un modo de evitar problemas continuos es discretizar la vecindad de cada estado. Podemos aplicar entonces cualquiera de los algoritmos de búsqueda local descritos anteriormente. Uno puede aplicar también la ascensión de colinas estocástica y el temple simulado directamente, sin discretizar el espacio. Estos algoritmos eligen a los sucesores aleatoriamente, que pueden hacerse por la generación de vectores aleatorios de longitud.

Los métodos locales de búsqueda sufren de máximos locales, crestas, y mesetas tanto en espacios de estados continuos como en espacios discretos. Se pueden utilizar el reinicio aleatorio y el temple simulado y son a menudo provechosos. Los espacios continuos dimensionalmente altos son, sin embargo, lugares grandes en los que es fácil perderse.

Un problema de optimización está restringido si las soluciones debieran satisfacer algunas restricciones sobre los valores de cada variable. La dificultad de los problemas de optimización con restricciones depende de la naturaleza de las restricciones y la función objetivo. La categoría más conocida es la de los problemas de programación lineal en los cuales las restricciones deben ser desigualdades lineales formando una región convexa y la función objetiva es también lineal. Los problemas de programación lineal pueden resolverse en tiempo polinomial en el número de variables. También se han estudiado problemas con tipos diferentes de restricciones y funciones objetivo (programación cuadrática, programación

cónica de segundo orden, etcetera).

AGENTES DE BÚSQUEDA ONLINE Y AMBIENTES DESCONOCIDOS

Un agente de búsqueda en línea (online) funciona intercalando el cálculo y la acción: primero toma una acción, entonces observa el entorno y calcula la siguiente acción. La búsqueda online es una buena idea en dominios dinámicos o semidinamicos (dominios donde hay una penalización por holgazanear y por utilizar demasiado tiempo para calcular). La búsqueda online es una idea incluso mejor para dominios estocásticos. En general, una búsqueda offline debería presentar un plan de contingencia exponencialmente grande que considere todos los acontecimientos posibles, mientras que una búsqueda online necesita solo considerar lo que realmente pasa.

La búsqueda online es una idea necesaria para un problema de exploración, donde los estados y las acciones son desconocidos por el agente; un agente en este estado de ignorancia debe usar sus acciones como experimentos para determinar que hacer después, y a partir de ahí debe intercalar el cálculo y la acción.

CONCLUSIÓN.

Estas búsquedas solo consideran lo que realmente pasa en ese estado y después toman nuevas acciones ya que en otras búsquedas necesitan tener una visión general del problema para así poder realizar una acción.

Los agentes efectúan búsquedas para encontrar una solución, en este caso tiene la difícil tarea de realizar una búsqueda online; el agente se mueve en un entorno desconocido en la que hacer una exhausta observación  para luego pasar a realizar el respectivo calculo y en base a esto realizar una acción y en la mayoría de los casos se encuentra una solución óptima.

BIBLIOGRAFÍA

Russell, S. y Norvig, P. 2004. INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. PEARSON EDUCACION. 2 ed. Madrid.