• Author / Uploaded
• Vicky Párraga

Citation preview

ESCUELA SUPERIOR POLITÉCNICA AGROPECUARIA DE MANABÍ “MANUEL FÉLIX LÓPEZ”

CARRERA INFORMÁTICA PERIODO MAR – AGO/2015

SEMESTRE SÉPTIMO

INTELIGENCIA ARTIFICIAL II TEMA: BUSQUEDA LOCAL EN ESPACIOS CONTINUOS

AUTORA: MARÍA VICTORIA PÁRRAGA MERO

FACILITADORA: ING. HIRAIDA SANTANA CEDEÑO

MISIÓN Formación de profesionales íntegros que conjuguen ciencia, tecnología y valores en su accionar, comprometidos con la sociedad en el manejo adecuado de programas y herramientas computacionales de última generación.

VISIÓN Ser referente en la formación de profesionales de prestigio en el desarrollo de aplicaciones informáticas y soluciones de hardware.

CALCETA, JUNIO 2015

INTRODUCCIÓN La semana del 8 al 12 de junio, se continuó con el trabajo grupal realizado la semana anterior, las temáticas tratadas fueron: los algoritmos de búsqueda local y problemas de optimización y búsqueda local en espacios continuos. En este apartado trataremos sobre la búsqueda local en espacios continuos. Esta búsqueda surge a raíz de ciertas dificultades que presentan los algoritmos anteriormente descritos, ya que estos han sido diseñados para manejarse un ambiente discreto, he ahí donde nace la necesidad de crear otros métodos de búsquedas que no solo se manejen en este espacio sino también en aquellos que cambian constantemente, aunque en la actualidad no se ha estudiado en este portafolio un algoritmo que pueda trabajar en ambos ambientes, estudiaremos la búsqueda local en espacios continuos que es parte de la solución a la problemática anteriormente expuesta.

MARCO TEÓRICO Para poder avanzar es necesario recordad primeramente cual es la diferencia entre los entornos discretos y continuos. ENTORNOS DISCRETOS: en estos entornos se presentan un conjunto de pasos infinitos, un ejemplo claro es el ajedrez, en el cual con un conjunto de movimientos se puede terminar la partida. ENTORNOS CONTINUOS: los entornos continuos son aquellos en los cuales se van a realizar un conjunto de pasos o acciones no secuenciales, es decir infinito puesto que depende las diferentes acciones y percepciones del agente. Con las definiciones expuestas anteriormente podemos concluir que la mayor parte de los entornos del mundo real son continuos, y ninguno de los algoritmos descritos hasta el momento puede manejarse en este tipo de entornos. Este apartado proporcionará una breve introducción a técnicas de búsqueda local para encontrar soluciones óptimas en espacios continuos.

La función sucesor en la mayor parte de casos devuelve infinitamente muchos estados, la búsqueda Local es una solución a este inconveniente, puesto que mediante esta se buscará hasta llegar a la solución óptima en espacios continuos. Diferentes investigaciones muestran el ejemplo de colocar tres aeropuertos en Rumania minimizando su distancia a las ciudades.

FIGURA 1. Mapa de las carreteras de Rumania.

Entonces tendríamos una interpretación de la siguiente manera: Estados: están definidos por las coordenadas de los 3 aeropuertos: (x1,y1) (x2,y2) (x3,y3) Función objetivo: f(x1, y1, x2, y2, x3, y3)=distancia de todas las ciudades a su aeropuerto más cercano.

TECNICAS DE BUSQUEDA LOCAL Y ESPACIOS CONTINUOS

El gradiente de la función objetivo es un vector.

Este vector contiene la magnitud y dirección de la inclinación más escarpada

Este gradiente evalúa la respuesta con pequeños incrementos y decrecimientos en cada coordenada Aquí es necesario evaluar los valores de alfa (α) que es una constante pequeña

Amplia la dirección de gradiente actual, va duplicando los valores de

(α).

Esto lo hace hasta el punto de crear nuevos estados.

Es un algoritmo eficaz, utiliza una técnica general para encontrar la solución de la ecuación de la forma g(x)=0.

Una nueva estimación para la raíz x. Para mejorar este método se implemento la matriz Hesiana, debido a el costo elevado de los espacios dimensionales

OPTIMIZACION CON RESTRICCIONES 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 presencia de restricciones reduce la región en la cual buscamos el óptimo. En la mayor parte de los problemas de toma de decisiones están presentes ligaduras entre las variables o limitaciones en las mismas. La categoría más conocida es la de los problemas de programación lineal.

CONCLUSION Como se mencionó en la introducción, existen algoritmos que han sido desarrollados para resolver problemas en espacios discretos, pero la realidad exige que existan algoritmos que se ajusten al mundo real el cual está compuesto en su gran mayoría por espacios continuos, si bien es cierto la búsqueda local en espacios continuos es una manera de resolver este problema, resulta difícil de entender su mecanismo si no se posee conocimiento de cálculo multivariante y aritmética vectorial. Lo ideal en un agente seria que manejara estos dos tipos de ambientes tanto el continuo y discreto y a su vez este agente debería poseer los algoritmos de búsqueda para ambos casos. Un tema destacable de la búsqueda es espacios continuos es la optimización de restricciones, la cual posee características que hacen que tenga varias aplicaciones en el mundo real, así como se explicó anteriormente un claro ejemplo de su utilización es la programación lineal.

BIBLIOGRAFÍA Bañares, J. 2013. Inteligencia Artificial: Búsqueda Local. (En Línea). EC. Consultado 10 de jun. 2015. Formato PDF. Disponible en: http://webdiis.unizar.es

Díaz, J. 2012. Sistemas Inteligentes: Búsqueda Heurística. (En Línea). EC. Consultado 10 de jun. 2015. Formato PDF. Disponible en: http://www.aic.uniovi.es/ssii/SSII-T3-BusquedaII.pdf

Prada, C. 2008. Optimización con restricciones. (En Línea). EC. Consultado 10 de jun. 2015. Formato PDF. Disponible en: http://www.isa.cie.uva.es/~prada/KKT.pdf

Russell, S y Norvig, P. 2004. Inteligencia Artificial un enfoque moderno. 2ed. Pearson Educación S.A. Madrid, ES.