PODA ALFA-BETA

INTRODUCCIÓN

Poda alfa-beta surgió como mejora del algoritmo minimax. Este algoritmo es capaz de reducir significativamente el número de nodos evaluados en un árbol de juegos y es una técnica muy usada en juegos entre adversarios como por ejemplo: el ajedrez, tres en raya y otros.

DESARROLLO

¿QUÉ ES PODA ALFA-BETA?

El poda alfa-beta es una mejora del algoritmo minimax, y se puede calcular una decisión mínima correcta y es posible aplicarlo a arboles de cualquier profundidad. Emplea la búsqueda primero en profundidad para considerar los nodos que se encuentran a lo largo del camino.

Existen dos jugadores en:

·         Maximizador

·         Minimizador

Y existen dos valores que son:

·         Alfa

·         Beta

Estos valores ayudan en la búsqueda, lo que mejora la búsqueda y mejorando la velocidad sin que se pierda la información

CARACTERÍSTICAS DE LA PODA ALFA-BETA

·         Omite la expansión de nodos donde los valores no son los mejores.

·         La búsqueda se para en algún nivel y se realizan evaluaciones heurísticas.

·         Si el valor del nodo MAX es decir alfa, es menor que el más alto hasta este momento, entonces omitir nodo.

·         Si el valor nodo MIN es decir, beta es mayor que el nodo más bajo hasta el momento, entonces omitir  nodo.

·         El algoritmo alfa-beta permite una búsqueda más completa.

·         En este algoritmo solo importa el orden y no los valores exactos.

·         Poda alfa-beta nos lleva al resultado final.

·         Alfa-beta es una mejora del algoritmo Minimax que evita revisar aquellos nodos donde la información no es útil en la jugada.

La búsqueda se realiza en profundidad y avanza de forma ordenada y usa la información para podar las ramas.

ESTRUCTURAS DE DATOS

Dos variables que se deben ser recordadas durante la búsqueda:

·         Alfa: limite inferior encontrando hasta ese momento.

·         Beta: limite superior.

·         En los niveles maximizantes MAX, se usa beta para podar.

·         En los niveles MIN, se usa alfa para podar.

·         Alfa-beta es muy usado para busqueda en árboles de juegos.

CONCLUSIÓN

Poda alfa beta es una mejora del algoritmo minimax que evita recorrer todos los nodos del árbol lo cual mejora la velocidad y no se pierde la información. El poda alfa-beta usa dos valores para obtener sus propósitos: alfa y beta.

BIBLIOGRAFÍA

López, B. 2009. Poda Alfa-Beta. (En línea). ME. Consultado, 20 de NOV. 2015. Formato PDF. Disponible en: http://www.itnuevolaredo.edu.mx/takeyas/

Solano, R. 2008. Poda Alfa-Beta. (En línea). EC. Consultado, 20 de nov. 2015. Formato PDF. Disponible en: http://es.slideshare.net/rfsolano/ poda-alfa-beta

Russell S. y P. Norvig Inteligencia Artificial: Un enfoque moderno. 2 ed. España. Pearson. p 188-191.

BÚSQUEDA ENTRE ADVERSARIOS-JUEGOS

INTRODUCCIÓN

Los juegos son entornos donde se desenvuelven dos agentes, cada agente debe considerar las acciones del otro agente que se desenvuelven en entornos competitivos donde los agentes siempre están en conflictos, solo puede haber un ganador y el otro indiscutiblemente será el perdedor, esto da lugar a la búsqueda entre adversarios más conocido como juegos.

DESARROLLO

JUEGOS

La teoría de los juegos es una rama de la economía porque ve un entorno multiagente como un juego donde cada acción realizada genera un impacto significativo.

Los juegos son una clase especializada a la que los teóricos de juegos la llamaban juegos de suma cero, de dos jugadores, etc.

Los primeros juegos fueron: el ajedrez, tres en raya. En todo juego si un jugador de gana el otro pierde, por esta razón los agentes producen una situación de adversarios.

Los juegos ocupan las facultades mentales de la gente, en ocasiones en un grado muy elevado, pero los investigadores indican que la naturaleza de los juegos los hacen un tema interesante.

Jugar juegos fue una de las primeras tareas de la inteligencia artificial, poco después de que las computadoras se hicieran programables. Los juegos son parecidos a la vida real en cierto modo, por ejemplo: en un juego se requiere de la capacidad de tomar decisiones cuando se debe calcular una solución óptima y castigan la ineficiencia   

DECISIONES ÓPTIMAS EN JUEGOS

Puede definirse como una clase de problemas de búsqueda con los siguientes componentes:

·         El estado inicial.

·         Una función sucesor devuelve una lista de movimientos pares o estados.

·         El test terminal determina cuando termina el juego.

·         Una función utilidad.

e   Ejemplo:

CONCLUSIÓN

Los juegos fueron uno de los primeros objetivos de la I.A, tiene la capacidad de ocupar la mentalidad de algunas personas en niveles excesivos lo que no es bien visto. Un juego está conformado por dos agentes donde uno de ellos es el ganador y el otro debe ser el perdedor.

BIBLIOGRAFÍA

Ceccaroni, L. 2008. Búsqueda entre adversarios. (En línea). ES. Consultado,  13 de nov. 2015. Formato PDF. Disponible en: http://www.cs.upc.edu/~luigi/II

Pérez, G. 2011. Búsqueda entre adversarios. (En línea). ES. Consultado,  13 de nov. 2015. Formato PDF. Disponible en: http://es.slideshare.net/gvnyps/

Russell S. y P. Norvig Inteligencia Artificial: Un enfoque moderno. 2 ed. España. Pearson. p 181-182.

AGENTES DE BÚSQUEDA ONLINE Y AMBIENTES DESCONOCIDOS

INTRODUCCIÓN

La busqueda online es una idea necesaria para un problema de explaración. La busqueda online es una idea necesaria para un problema de explaración.

Estos agentes observan el entorno de trabajo y hace un cambio en donde va a trabajar. Un agentes de este tipo es una buena idea para dominios estocasticos.

Los agentes de búsqueda online escogen la major ruta para llegar al objetivo con solo saber los acontecimientos que realmente suceden.

                                                         DESARROLLO            

Un agente de búsqueda online es una buena idea en dominios, es una idea incluso mejor que los dominios estocásticos. Esta búsqueda es una idea necesaria para un problema de exploración donde los estados y las acciones son desconocidos por el agente, y como el agente está en estado de ignorancia debe usar sus acciones como experimentos para determinar que hace después y luego se empieza a intercalar el cálculo y la acción.

AGENTES DE BÚSQUEDA ONLINE

Luego de una acción el agente online recibe una percepción al conocer el estado que ha alcanzado y a partir de esta información puede crear o aumentar su mapa del entorno, dicho mapa se usa para decidir dónde ir después.

El algoritmo online puede expandir sólo el nodo que ocupa físicamente. Para evitar viajar a través de todo el árbol para expandir el siguiente nodo es mejor expandir los nodos en orden local. La búsqueda primero en profundidad tiene exactamente dicha propiedad porque el siguiente nodo a expandir es hijo del nodo anteriormente expandido.

OBJETIVO DEL AGENTE

·         Alcanzar el estado objetivo.

·         Minimizar el coste.

INTERCALACIÓN PLANIFICACIÓN-ACCIÓN

Luego de cada acción el agente online recibe una percepción al decir que el estado se ha alcanzado. Dicha información aumenta el mapa de entorno, y luego ese mismo mapa se usa para decidir hacia dónde ir.

La búsqueda online es necesaria en problemas de exploración. Los estados deben expandirse teniendo en cuenta la posición física que la búsqueda en profundidad.

Búsqueda online: intercala el cálculo y la acción:

·         Tomar una acción.

·         Observar el entorno.

·         Calcular la siguiente acción.

Usos de la búsqueda online:

·         Problemas de exploración donde el agente desconoce los estados y las acciones

Un problema de búsqueda online puede ser resuelta solo por un agente que ejecute acciones más que por un proceso computacional

CONCLUSIÓN

Los agentes de búsqueda online trabajan en ambientes desconocidos, ellos deben explorar para aprender y con lo aprendido arma un mapa y decide que hacer luego de llegar a una meta. Son parecidos a los bebes que exploran el mundo para conocerlo.

BIBLIOGRAFÍA

Russell S. y P. Norvig Inteligencia Artificial: Un enfoque moderno. 2 ed. España. Pearson. p 138-142.

Mora, M. 2014. Agentes de búsqueda online y ambientes desconocidos. (En línea). ES. Consultado,  12 de oct. 2015. Formato PDF. Disponible en: http://inteligenciartificialmariana.blogspot.com/

ALGORITMOS GENÉTICOS

INTRODUCCIÓN

Los algoritmos genéticos están basados en la biología y en la teoría de evolución planteada por Darwin, en los últimos años se ha vuelto muy popular ya que es una técnica que se basa en los mecanismos que usa la naturaleza para seleccionar. Los individuos que se adaptan a los cambios son los que sobreviven, los cambios hacen referencia a la transformación de los genes y las características más destacadas de los individuos deben ser heredadas a sus descendientes.

DESARROLLO

Definición

Es un algoritmo matemático paralelo que transforma objetos matemáticos usando operaciones modeladas de acuerdo a la teoría de evolución de Darwin que trata sobre la reproducción y supervivencia del individuo más apto.

Este algoritmo está basada en mecanismo de selección natural y genética natural, combinando la supervivencia de los individuos más compatibles con una estructura de información aleatoria donde se intercambia información para construir un algoritmo de búsqueda con capacidades de innovación.

Lo que hace el algoritmo es que en cada generación se crea un conjunto nuevo de criaturas artificiales usando bits y partes del progenitor, esto genera un proceso aleatorio que no es tan simple.

La forma más simple de algoritmos genéticos usa tres tipos de operadores:

Selección o reproducción: se encarga de escger las cormosomas entre la población para efectuar la reproducción, si el cromosomas es más capaz tendrá más oportunidades de ser seleccionado para la reproduccion.

Cruce: se trata de cambiar las secuencias entre la posicion de dos cromosomas para crear una nueva desendencia.

Mutaciones: se producen variaciones de modo aleatorio en el cromosomas, puede mutar en cda posición de un bit en una cadena.

Ventajas

·         Permite trabajar con varias soluciones.

·         Tiene mayor tolerancia en la optimización.

·         Mejor manipulación de parámetros simultáneamente.

·         No requiere de conocimiento específico sobre el problema.

·         Usa algoritmo probabilístico.

Desventajas  

·         Puede tardarse demasiado en llegar a su objetivo.

Debe realizarse con lenguajes que toleren cambios

CONCLUSIÓN

Los algoritmos genéticos están basados en la teoría de Darwin y permiten que una población de individuos evolucione mediante la mutación o recombinaciones genéticas de forma aleatoria.

BIBLIOGRAFÍA

Martínez, M; Palacios, B; Sergio, T; Barreco, F. 2011. Aplicación de algoritmos genéticos a la identificación de la estructura de enlaces en portales web. ES. Revista española de documentación científica. Vol. 2. Pag 233.

Rodríguez, P. 2009. Introducción a los algoritmos genéticos y sus aplicaciones. ES. Consultado, 28 de oct. 2015. Formato PDF. Disponible en: http://www.uv.es/asepuma/X/J24C.pdf

Russell S. y P. Norvig, Inteligencia Artificial: Un enfoque moderno. 2 ed. España. Pearson. p 131-134.

FUNCIONES HEURISTICAS

Tema: Búsqueda informada y exploración  

Fecha: 09 de Octubre de 2015

INTRODUCCIÓN

Existen instancias del problema donde la heurística produce resultados malos o se ejecuta de forma lenta. Esta función es muy común en el mundo real y debe tener alguna información para llegar su destino a través del mejor camino.

DESARROLLO

FUNCIONES HEURÍSTICAS

Los métodos de búsqueda heurística disponen de alguna información sobre la proximidad de cada estado a un estado objetivo, lo que permite explorar en primer lugar los caminos más prometedores.

CARACTERÍSTICAS

·         No garantizan que se encuentre una solución, aunque existan soluciones.

·    Si encuentran una solución, no se asegura que ésta tenga las mejor esas propiedades (que sea de longitud mínima o de coste óptimo).

·         En algunas ocasiones (que, en general, no se podrán determinar a prioridad), encontrarán una solución (aceptablemente buena) en un tiempo razonable.

·     En general, los métodos heurísticos son preferibles a los métodos no informados en la  solución de problemas difíciles para los que una búsqueda exhaustiva necesitaría un tiempo demasiado grande. Esto cubre prácticamente la totalidad de los problemas reales que interesan en Inteligencia Artificial.

·      La información del problema concreto que estamos intentando resolver se suele expresar por medio de heurísticas.

El concepto de heurística es difícil de aprehender. Newell, Shaw y Simon en 1963 dieron la siguiente definición: "Un proceso que puede resolver un problema dado, pero que no ofrece ninguna garantía de que lo hará, se llama una heurística para ese problema".

CONCLUSIONES

La función heurística es muy importante porque cuentan con una información acerca del objetivo lo cual hace que se llegue más rápido y más seguro. 

BIBLIOGRAFÍA

Russell S. y P. Norvig, Inteligencia Artificial: Un enfoque moderno. 2 ed. España. Pearson. p 119-121.

Malangón, C. 2010. Búsqueda heurística. (En línea). ES. Consultado,  12 de oct. 2015. Formato PDF. Disponible en: https://www.nebrija.es/~cmalagon/

BÚSQUEDA INFORMADA Y EXPLORACIÓN

Tema: Búsqueda informada y exploración  

Fecha: 09 de Octubre de 2015

INTRODUCCIÓN

La búsqueda utiliza conocimientos específicos del problema, con esto puede encontrar soluciones de una manera eficiente. La información sobre el espacio de estados puede impedir a los algoritmos cometer un error en la oscuridad. La heurística aparece bajo la forma de una función de evaluación basada en la información específica para el dominio o contexto relacionada con el problema.

DESARROLLO

ESTRATEGIA DE BUSQUEDA INFORMADA (HEURÍSTICA)

Utiliza conocimiento específico del problema más allá de la definición del problema en sí mismo y puede encontrar soluciones de una manera más eficiente que una búsqueda no informada.

TIPOS DE BUSQUEDAS INFORMADAS:

·         BÚSQUEDA VORÁZ PRIMERO EL MEJOR.

·         BÚSQUEDA A ESTRELLA.

·         BÚSQUEDA HEURÍSTICA CON MEMORIA ACOTADA.

BUSQUEDA PRIMERO EL MEJOR

El nombre primero el mejor es inexacto, si se supiera cual es el mejor directamente, el nombre sería el correcto.

La búsqueda primero el mejor es un caso particular del algoritmo general de Búsqueda -Árboles o Búsqueda- Grafos en el cual se selecciona un nodo para la expansión basada en una función de evaluación f(n).

f(n)= g(n) + h(n)

f(n): coste más barato estimado de la solución a través de n.

g(n): costo para alcanzar el nodo.

h(n): costo estimado del camino más barato desde n al objetivo.

BUSQUEDA A ESTRELLA

La búsqueda A* permite reducir al mínimo el costo entre de nodo de origen y el nodo objetivo y es la forma más ampliamente conocida de la búsqueda primero el mejor, siendo la búsqueda A* tanto completa como óptima.

CONCLUSIONES

·    La búsqueda informada tiene conocimientos específicos del área donde se va a desenvolver.

·         La función e evaluación estima el coste más barato estimado de la solución.

        

BIOGRAFÍA

Russell S. y P. Norvig, Inteligencia Artificial: Un enfoque moderno. 2 ed. España. Pearson. p 107-115.

Hurtado. L. 2014. Búsqueda Informada y Exploración. (En línea). Consultado,  12 de oct. 2015. Formato PDF. Disponible en https://prezi.com/dhru2d0ur6qe/busqueda-informada-y-exploracion/