BUSQUEDA LOCAL EN ESPACO CONTINUOS

INTRODUCCION

En esta clase vimos los tipos de busqueda, y tambien vimos que una funcion heurística que evalúa la calidad de la solución, pero que no está necesariamente ligada a un coste y que se usará para podar el espacio de búsqueda (soluciones que no merece la pena explorar).

MARCO TEÓRICO

Búsqueda local en espacios continuos. 

Aun ninguno de los algoritmos descritos puede manejar espacios de estados continuos, la función sucesor en la mayor parte de casos devuelve infinitamente muchos estados! la técnicas de búsqueda local para encontrar soluciones optimas en espacios continuos.

Un modo de evitar problemas continuos es simplemente 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

 

 La forma de como funciona esta búsqueda  es que solo consideran lo que realmente pasa en ese estado y luego al darse cuenta de su entorno toma nuevas acciones ya que en otras busque necesitan tener una visión general del problema para así poder realizar una acción.

 

 

 

 

 

 

 

ALGORITMO DE BUSQUEDA LOCAL Y PROBLEMA DE OPTIMIZACION

INTRODUCCION

En esta clases nos dimos cuenta que en la búsqueda local (BL), se empieza de una configuración inicial (generalmente aleatoria) y se hacen pequeños cambios (a través de operadores) hasta alcanzar un estado desde el cual no se puede alcanzar ningún estado mejor. Las técnicas de BL son propensas a encontrar óptimos locales que no son la mejor solución posible. El óptimo global es generalmente imposible de alcanzar en un tiempo limitado, por el tamaño del espacio de soluciones.

MARCO TEORICO

Algoritmos de búsqueda local y problemas de optimización

Los algoritmos de búsqueda local funcionan con un solo estado actual (más que múltiples caminos) y generalmente se mueve solo a los vecinos del estado. Típicamente, los caminos seguidos por la búsqueda no se retienen. Aunque los algoritmos de búsqueda local no son sistemáticos, tienen dos ventajas claves: usan muy poca memoria (por lo general una cantidad constante) y pueden encontrar a menudo soluciones razonables en espacios de estados grandes o infinitos (continuos) para los cuales son inadecuados los algoritmos sistemáticos.

Además de encontrar los objetivos, los algoritmos de búsqueda local son útiles para resolver problemas de optimización puros, en los cuales el objetivo es encontrar el mejor estado según una función objetivo Muchos problemas de optimización no encajan en el modelo <estándar> de búsqueda.

Para entender la búsqueda local, encontraremos muy útil considerar la forma o el paisaje del espacio de estados. El paisaje tiene <posición> (definido por el estado) y <elevación> (definido por el valor de la función de coste heurística o función objetivo). Si la elevación corresponde al costo, entonces el objetivo es encontrar el valle más bajo (un mínimo global); si la elevación corresponde a una función objetivo, entonces el objetivo es encontrar el pico más alto (un máximo global) (Puedes convertir uno en el otro solamente al insertar un signo menos.) Los algoritmos de búsqueda local exploran este paisaje. Un algoritmo de búsqueda local completo siempre encuentra un objetivo si existe; un algoritmo optimo siempre encuentran un mínimo/máximo global.

 

 Búsqueda de Ascensión de Colinas

 El algoritmo de búsqueda de ascensión de colinas es simplemente un bucle que continuamente se mueve en dirección del valor creciente, es decir cuesta arriba. Termina cuando alcanza <un pico> en donde ningún vecino tiene un valor más alto. El algoritmo no mantiene un árbol de búsqueda, sino una estructura de datos del nodo actual que necesita solo el registro del estado y su valor de función objetivo. La ascensión de colinas no mira delante más allá de los vecinos inmediatos del estado actual.

Búsqueda de Temple Simulado. 

Un algoritmo de ascensión de colinas que nunca hace movimientos <cuesta abajo> hacia estados con un valor inferior (o coste más alto) garantiza ser incompleto, porque puede estancarse en un máximo local. En contraste, un camino puramente aleatorio, es decir moviéndose a un sucesor elegido uniformemente aleatorio de un conjunto de sucesores, es completo, pero sumamente ineficaz. Por lo tanto, parece razonable intentar combinar la ascensión de colinas con un camino aleatorio de algún modo que produzca tanta eficacia como completitud.

El bucle interno del algoritmo del temple simulado es bastante similar a la ascensión de colinas. En vez de escoger el mejor movimiento, sin embargo, escoge un movimiento aleatorio. Si el movimiento mejora la situación, es siempre aceptado. Por otra parte, el algoritmo acepta el movimiento con una probabilidad menor que uno. La probabilidad se disminuye exponencialmente con la <maldad> de movimiento (la cantidad ΔE por la que se empeora la evaluación). La probabilidad también disminuye cuando <la temperatura> T baja: los <malos> movimientos son más probables al comienzo cuando la temperatura es alta, y se hacen más improbables cuando T disminuye. Uno puede demostrar que si el esquema disminuye Tbastante despacio, el algoritmo encontrara un óptimo global con probabilidad cerca de uno.

 Búsqueda por Haz Local

A primera vista, una búsqueda por haz local con K estados podría parecerse a ejecutar K reinicios aleatorios en paralelo en vez de en secuencia. De hecho, los dos algoritmos son bastantes diferentes. En una búsqueda de reinicio aleatorio, cada proceso de búsqueda se ejecuta independientemente de los demás. En una búsqueda por haz local la información útil es pasada entre los k hilos paralelos de búsqueda. Por ejemplo, si un estado genera varios sucesores buenos y los otros K-1 estados generan sucesores malos, entonces el efecto es que el primer estado dice a los demás, <￡Venid aquí, la hierba es más verde!> El algoritmo rápidamente abandona las búsquedas infructuosas y mueve sus recursos a donde se hace la mayor parte del progreso.

 Algoritmos Genéticos

Un algoritmo genético (o AG) es una variante de la búsqueda de haz estocástica en la que los estados sucesores se generan combinando dos estados padres, más que modificar un solo estado. La analogía a la selección natural es la misma que con la búsqueda de haz estocástica, excepto que ahora tratamos con reproducción sexual más que con la reproducción asexual.

Como en la búsqueda de haz, los AGs comienzan con un conjunto de K estados generados aleatoriamente, llamados población Cada estado, o individuo está representado como una cadena sobre un alfabeto finito (el más común, una cadenas de 0s y 1s).

 CONCLUSIÓN.

 En conclision dieremos los métodos de búsqueda local, como la ascensión de colinas, operan en formulaciones completas de estados, manteniendo solo un número pequeño de no- dos en memoria.

 BIBLIOGRAFÍA

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

 

FUNCION HEURISTICA

INTRODUCCION

En esta clase recibimos  de lo que es una búsqueda heurística que es toda adquisición de información dispone de algún problema para la solución del problema, por lo que explorar los lugares más prometedores en encontrar el estado objetivo, es decir que para esta búsqueda se necesita información detallada sobre el problema para así poder solucionarlo con éxito.

MARCO TEORICO 

FUNCIONES HEURISTICAS.

Una manera de caracterizar la calidad de una heurística es el b* factor de ramificación eficaz. Si el número total de nodos generados por A* para un problema particular es N, y la profundidad de la solución es d. entonces b* es factor de ramificación que un árbol uniforme de profundidad d deberá tener para  contener N + 1 nodos. Así,

N+1=1+b*+ (b*)^2+……….. (b*)^d 

Por lo tanto, las  medidas experimentales de b* sobre un pequeño conjunto de problemas pueden proporcionar una buena guía para la utilidad total de la heurística. Una heurística bien diseñada tendría un valor de b cerca de 1, permitiría resolver problemas bastante grandes. 

 Aprendizaje de heurísticas desde la experiencia

Una función heurística h(n), como se supone, estima el costo de una solución que comienza desde el estado en el nodo n. Los métodos de aprendizaje inductivos trabajan mejor cuando se les suministrar características de un estado que sean relevante para su evaluación, más que sólo la descripción del estado.

A partir de esto, se puede utilizar un algoritmo de aprendizaje inductivo para construir una función h(n) que pueda predecir los costos solución para otros estados que surjan durante la búsqueda. Las técnicas para hacer esto, está basado en la  utilización de  redes neuronales, árboles de decisión. Y otros métodos.

CONCLUSIÓN.

Muchos algoritmos en la inteligencia artificial son heurísticos por naturaleza, o usan reglas heurísticas.

Cuando se usa la palabra heurística en el procesamiento del lenguaje basado en reglas, el reconocimiento de patrones o el procesamiento de imágenes, es usada para referirse a las reglas.

 

CONCLUSIONES

En la sociedad, dentro de las ciencias de la computación, la de la Inteligencia Artificial es una de las áreas que causa más expectación. Que un sistema pueda mejorar su comportamiento sobre la base de la experiencia y que además, tenga una noción de lo que es un error y que pueda evitarlo, resulta muy interesante.  

No obstante, la realización del trabajo, me ha servido para darme cuenta de que la IA no es algo nuevo, lleva décadas de estudio y está en constante evolución. La realidad es que la mayoría de la gente, al hablar de inteligencia artificial tiende a relacionarlo con el mundo de la robótica y, más concretamente a los robots con formas humanas, capaces de relacionarse. Gracias a este trabajo he descubierto que no es así. La robótica existía mucho antes de la inteligencia artificial.  

Los métodos tradicionales en Inteligencia Artificial que permitieron el desarrollo de los primeros sistemas expertos y otras aplicaciones, ha ido de la mano de los avances tecnológicos y las fronteras se han ido expandiendo constantemente cada vez que un logro, considerado imposible en su momento, se vuelve posible gracias a los avances en todo el mundo, generando incluso una nueva mentalidad de trabajo que no reconoce fronteras físicas ni políticas. Por ello, yo soy optimista en relación al futuro siempre que se respeten los límites culturales y éticos. Creando siempre máquinas capaces de ayudar al ser humano, de sustituirlo en tareas desagradables, duraderas, pesadas o como complemento de ocio. 

BIBLIOGAFIA

Stuart J. Russell y Peter Norvig 2010.INTELIGENCIA ARTIFICIAL. Un enfoque moderno. Séptima edición.

TEMA2. BUSQUEDA CON INFORMACION PARCIAL

INTRODUCCION

Su percepción no proporciona ninguna nueva información despues de cada acción. ¿Que pasa cuando el conocimiento de los estados o acciones es incompleto? Encontramos que diversos tipos de incornpletitud conducen a tres ipos de problemas distintos:

1. Problemas sin sensores (también llamados problemas conformados): si el agente no tiene ningún sensor, entonces (por lo que sabe) podría estar eri Lino de los posibles estados iniciales, y cada acción por lo tanto podría conducir a uno de los posibles estados sucesores.
2. Problemas de contingencia: si el entorno es prircialinente observable o si las acciones son inciertas, entonces las percepciones del agente proporcionan nueva informacion despues de cada acción. Cada percepción posible define una contingencia que debe de planearse. A un problema se le llama entre adversarios si la incertidumbre esta causada por las acciones de otro agente.
3. Problemas de exploraciún: cuando se desconocen los estado5 y las acciones del entorno, el agente debe actuar para descubrirlos. Los problemas de exploración pueden verse como un caso extremo de problen-ias de contiilgencia. 

CONCLUSION

Este capitulo ha introducido metodos en los que un agente puede seleccionar acciones en los ambientes deterministas, observables, estaticos y completamente conocidos.

TEMA 1.2 ESTRATREGIAS DE BUSQUEDA NO INFORMADA

También llamadas búsqueda a ciegas el término significa que ellas no tienen información adicional acerca de los estados más allá de la que proporciona la definición del problema. Todo lo que ellas pueden hacer es generar los sucesores y distinguir entre un estado objetivo es “más prometedor” que otro se llama búsqueda informada o búsqueda heurística. La búsqueda no informada tiene las siguientes estrategias:

BUSQUEDA PRIMERO EN ANCHURA

La búsqueda primero en anchura es una estrategia sencilla en la que se expande primero el nodo raíz, a continuación se expanden todos los sensores del nodo raíz, después sus sucesores, etc. La búsqueda primero en anchura se puede implementar llamando a la búsqueda árboles con una frontera vacía que sea una cola primero en entrar primero en salir (FIFO), asegurando que los nodos primeros visitados serán los primeros expandidos. La cola FIFO pone todos los nuevos sensores generados al final de la cola, lo que significa que los nodos más superficiales se expanden antes que los nodos más profundos.

                                          BUSQUEDA PRIMERO EN PROFUNDIDAD

La búsqueda primero en profundidad siempre expande el nodo más profundo en la frontera actual de árbol de búsqueda. La búsqueda procede inmediatamente al nivel más profundo del árbol de búsqueda, donde los nodos no tienen ningún sucesor. Cuando estos nodos se expanden, son quitados de la frontera, entonces la búsqueda retrocede al siguiente nodo más superficial que todavía tenga sucesores inexplorados. Esta estrategia puede implementarse por la búsqueda de árboles con una cola último en entrar primero en salir (LIFO), es común aplicar la búsqueda primero en profundidad con una función recursiva que se llama en cada uno de sus hijos, esta tiene unos requisitos muy sencillos de memoria. Necesita almacenar solo un camino desde la raíz a un nodo hoja, junto con los nodos hermanos restantes no expandidos para cada nodo del camino.

Una variante de la búsqueda primero en profundidad, llamada también búsqueda hacia atrás, utiliza aún menos memoria, en esta solo se genera un sucesor a la vez; cada nodo parcialmente expandido recuerda que sucesor se expande a continuación. El inconveniente de la búsqueda primero en profundidad es que puede hacer una elección equivocada y obtener un camino muy largo aun cuando una elección diferente llevaría a una solución cerca de la raíz del árbol de búsqueda. (Russell, Norving, 2008).

CONCULUSION

la búsqueda una de las operaciones más sencillas y elementales en cualquier estructura de datos, se han estandarizado el uso de estos algoritmos para ello, por lo que se conocen como algoritmos de búsqueda. Sin embargo, es importante resaltar que pueden utilizarse para muchísimas otras operaciones con grafos que no necesariamente incluyan la búsqueda de algún elemento dentro del grafo.