Inteligencia Artificial II
temas importantes y basico sobre la inteligencia artificial
martes, 2 de febrero de 2016
lunes, 1 de febrero de 2016
jueves, 21 de enero de 2016
lunes, 30 de noviembre de 2015
ALGORITMO MINIMAX
INTRODUCCION.
Este episodio nos centraremos en el Algoritmo
Minimax, el cual es un algoritmo de decisión para minimizar la pérdida máxima
aplicada en juegos de adversarios es decir de información completa, cada jugador
conoce el estado del otro al momento de realizar el siguiente movimiento .
MARCO TEORICO.
En teoría de juegos, Minimax es un método de decisión para minimizar la
pérdida máxima esperada en juegos con adversario y con información perfecta.
Este cálculo se hace de forma recursiva. El funcionamiento de Minimax puede
resumirse como elegir el mejor movimiento para ti mismo suponiendo que tu
contrincante escogerá el peor para ti.
FUNCIONAMIENTO DEL
ALGORITMO MINIMAX
1. Generación del árbol de juego. Se generarán todos los nodos hasta
llegar a un estado terminal o determinando una profundidad concreta.
Vamos aplicando el algoritmo por un número fijo de iteraciones hasta
alcanzar una determinada profundidad. En estas aplicaciones la profundidad
suele ser el número de movimientos o los incluso el resultado de aplicar
diversos pasos de planificación en un juego de estrategia.
2. Cálculo de los valores de la función de utilidad para cada nodo
terminal.
Para cada resultado final, cómo de beneficioso me resulta si estamos en MAX
o cuanto me perjudicará si estamos en MIN.
·
El
maximizador busca movimientos que lo conduzcan al mayor número positivo
·
El
minimizador busca movimientos que lo conduzcan al menor número negativo
3. Calcular el valor de los nodos superiores a partir del valor de los
inferiores. Alternativamente se elegirán los valores mínimos y máximos
representando los movimientos del jugador y del oponente, de ahí el nombre de
Minimax.
4. Elegir la jugada valorando los valores que han llegado al nivel superior.
El algoritmo explorará los nodos del árbol asignándoles un valor numérico
mediante una función de utilidad, empezando por los nodos terminales y subiendo
hacia la raíz. La función de utilidad como se ha comentado, definirá lo buena
que es la posición para un jugador cuando la alcanza.
Versiones más avanzadas como el minimax con poda alfa beta hacen
que se reduzca considerablemente el número de nodos a visitar por lo que el
tiempo de cálculo se reduce ampliamente.
Y para terminar comentar un ejemplo cásico, el tres en raya (juego
del gato, tatetí, triqui, tres en gallo, michi, la vieja o tic tac toe). Se
trata de hacer una fila de tres para ganar y evitar que el oponente la haga
antes que tu.
Al aplicar el algoritmo, se suceden una serie de estados que se resumen en
la fotografía. Un estado -1 significa que MAX gana, 0 empate o -1 pierde.
CONCLUSION.
El Minimax es un algoritmo
entre dos jugadores la funcion principal es elegir el mejor camino para ti
mismo ya que el oponente elegirá el peor para ti
BIBLIOGRAFÍA.
Russell, S. y Norvig, P. 2004. INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO.
PEARSON EDUCACION. 2 ed. Madrid.
Algoritmo Minimax Consultado, 23 de Nov. 2015. Formato HTML.
Disponible
http://razonartificial.com/2010/08/algoritmo-minimax-un-jugador-incansable/
sábado, 28 de noviembre de 2015
BUSQUEDA ENTRE ADVERSARIO
INTRODUCION
Dentro de un entorno multiagente
competitivo los objetivos de los agentes se encuentran en conflictos
ocasionando una búsqueda entre adversarios, también conocidas como
juegos.
Lo cual se va a detallar en esta ocasión
para tener en cuenta como se desempeñan los agentes en estados en el que
participan más de un agente
MARCO
TEORICO
JUEGOS.
Los juegos proporcionan una tarea estructurada en la que es muy fácil
medir el éxito o el fracaso. En comparación con otras aplicaciones de
inteligencia artificial, por ejemplo comprensión del lenguaje, los juegos no
necesitan grandes cantidades de conocimiento.
Los juegos en IA se enfoca a que un agente enfrente a otro y cumplir un
determinado objetivo, en si ganar, cuando un agente gana el juego implica a que
el otro lo pierda por lo que se dice que resultado siempre será 0, ya que el
ganador contara con +1 y el perdedor -1 al sumar ambos valores el resultado
será 0 y en el caso de empate no hay puntos para ninguno resultando 0.
DECISIONES ÓPTIMAS EN
JUEGOS.
Se toma en cuenta quien inicia y quien le sigue en un juego, a lo cual se
le denomina MAX al que inicia y MIN al otro jugador, pero para que aquellos
tomen una decisión en el transcurso del juego depende de estos factores:
ESTRATEGIAS ÓPTIMAS.
En un problema de búsqueda normal, la solución óptima sería una secuencia
de movimientos que conducen a un estado objetivo (un estado terminal que es
ganador). En un juego, por otra parte el agente debe estar pendiente de las
acciones que realiza su rival y cómo influyen en el entorno, ya que las
decisiones de este dependen del otro.
Para considerar una estrategia óptima se debe analizar a cada uno de los
agentes implicados (MIN y MAX), para determinar que se debe realizar en cierto
momento.
CONCLUSION
Como se adjunta
anteriormente se debe de tener muy en cuenta las estrategias que se pueden
tomar para llegar a ganar, es decir conseguir el objetivo.
Para asegurar el objetivo
se debe tomar las decisiones adecuadas y tener en cuenta lo que el adversario
pueda realizar para cambiar el panorama del entorno. Para lo cual se explicó cómo
funciona el algoritmo minimax que comienza Max tomando el máximo valor para
generar el nodo, de ahí se toma en cuenta el valor Min para desplegar el
siguiente nodo.
BLIBLIOGRAFIA
Russell, S. y Norvig, P. 2004. INTELIGENCIA
ARTIFICIAL. UN ENFOQUE MODERNO. PEARSON EDUCACIÓN. 2 ed. Madrid.
sábado, 14 de noviembre de 2015
BUSQUEDA ONLINE Y AMBIENTES DESCONOCIDOS
INTRODUCCION.
Hoy vamos a conocer los
agentes de búsqueda online y ambiente desconocidos si bien es cierto las busque
trata de recorrer la mejor ruta posible en pocas palabras de optimizar pero que
es la búsqueda online, está búsqueda solo necesita saber los acontecimientos
que realmente sucede sobre un problema a resolver.
MARCO TEORICO.
AGENTES DE BÚSQUEDA ONLINE Y AMBIENTES DESCONOCIDOS
Hasta ahora nos hemos centrado en agentes que usan algoritmos de
búsqueda offline. Ellos calculan una solución completa antes de poner un pie en
el mundo .Y luego ejecutan la solución sin recurrir a sus percepciones. En
contraste, un agente de búsqueda online es una buena idea en dominios dinámicos
o semidinámicos. 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 sólo considere lo que realmente pasa.
Por ejemplo, a un agente que juega al ajedrez se le aconseja que haga su primer
movimiento mucho antes de que se haya resuelto el curso completo del juego.
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 ese 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.
AGENTE DE
BÚSQUEDA EN LÍNEA (ONLINE)
Después de cada acción, un agente online recibe una percepción al
decirle que estado ha alcanzado; de esta información, puede aumentar su mapa
del entorno. El mapa actual se usa para decidir dónde ir después. Esta
intercalación de planificación y acción significa que los algoritmos de búsqueda online son bastantes diferentes
de los algoritmos de búsqueda offline.
Un algoritmo online, por otra parte puede expandir sólo el nodo
que ocupa físicamente. Para evitar viajar atravez de todo el árbol para
expandir el siguiente nodo, parece mejor expandir los nodos en un orden local.
La búsqueda primero en profundidad tiene exactamente esta propiedad, porque el
siguiente nodo a expandir es hijo del nodo anteriormente expandido.
Fig.1. Forma de aprendizaje del agente de búsqueda online
Objetivo del
agente:
Alcanzar un estado objetivo
Minimizando el coste.
Intercalación
planificación-acción:
Después de cada acción, un
agente online recibe una percepción (al decirle el estado que ha alcanzado).
Esta información aumenta su mapa de entorno. El mapa actual se utiliza para
decidir dónde ir.
La búsqueda on-line son necesarias para problemas de exploración.
Los estados deben expandirse teniendo en cuenta la posición física que ocupamos
=> búsqueda en profundidad.
Ejemplo:
Un problema sencillo de un laberinto el agente comienza en S y
debe alcanzar G, pero no sabe nada del entorno.
Búsqueda
off-line:
– Calcula una solución completa antes de poner un pie en el mundo
real.
– Después ejecutan la solución sin recurrir a las percepciones.
Búsqueda
on-line: Intercala el calcula y la acción.
– Toma una acción
– Observa el entorno
– Calcula la siguiente acción.
Usos de la
búsqueda on-line:
– Problemas de exploración, donde el agente desconoce los estados
y acciones.
Problemas de búsqueda en línea (online)
Un problema de búsqueda online puede resolverse solamente por un
agente que ejecute acciones, más que por un proceso puramente computacional.
Asumiremos que el agente
sabe lo siguiente:
· Acciones (). Que
devuelve una lista de acciones permitidas en el estado s;
· Funciones de coste
individual c(s, a, s’). hay que tener en cuenta que no pude usarse hasta que el
agente sepa que s’ es el resultado; y
· Test-Objetivo(s).
CONCLUSION.
Gracias
al estudio de estas búsquedas se puede concluir que su función principal es
analizar lo que realmente sucede en su entorno y así poder calcular la siguiente acción con la ayuda del mapa que
caracteriza a una de ellas.
BIBLIOGRAFÍA.
Russell, S. y Norvig, P. 2004. INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO.
PEARSON EDUCACION. 2 ed. Madrid.
jueves, 5 de noviembre de 2015
ALGORITMO GENETICO
INTRODUCCION.
Esta clase estudiaremos
el algoritmo genético el cual surgió en 1970 por Jhon Holland este algoritmo es
basado en la evaluación biológica ha sido uno de los logros más grande en la
inteligencia artificial.
Los Algoritmos Genéticos
usan una analogía directa con el comportamiento natural. Trabajan con una población
de individuos, cada uno de los cuales representa una solución factible a un
problema dado.
MARCO TEORICO.
DESCRIPCIÓN GENERAL Y
CARACTERÍSTICAS DE LOS ALGORÍTMOS GENÉTICOS
La
idea básica es generar un conjunto con algunas de las posibles soluciones. Cada
una va a ser llamada individuo, y a dicho conjunto se le denominará población.
Cada
individuo tiene una información asociada a él. Tiene asociada una función de
adaptación que determina el grado de adaptación de un individuo. A dicha
información se le denomina código genético.
Las
características de los individuos, sean beneficiosas o no, se van a denominar
fenotipos. La información asociada a un individuo se compone de partes
indivisibles denominados cromosomas.
Características
Son
algoritmos estocásticos, es decir, dos ejecuciones distintas pueden dar dos
soluciones distintas.
v Son
algoritmos de búsqueda múltiple, luego dan varias soluciones.
v
Son los algoritmos que hacen una barrida
mayor al subespacio de posibles soluciones válidas.
v
A diferencia de los otros algoritmos, cuya
convergencia y resultado final son fuertemente dependientes de la posición
inicial, la convergencia del algoritmo genético es poco sensible a la población
inicial si esta se escoge de forma aleatoria y es lo suficientemente grande.
v
Por su grado de penetración casi nulo, la
curva de convergencia asociada al algoritmo presenta una convergencia
excepcionalmente rápida al principio, que casi enseguida se bloquea. Esto de
debe a que el algoritmo genético es excelente descartando subespacios realmente
malos.
v
La optimización es función de la
representación de los datos.
v Es
una búsqueda paramétricamente robusta. Eso quiere decir que sólo si se escoge
realmente mal los parámetros del algoritmo, éste no va a converger.
La
forma más simple de algoritmo genético utiliza tres tipos de operadores:
selección, cruce y mutación.
v Selección o reproducción:
Este operador escoge cromosomas entre la población para efectuar la
reproducción. Cuanto más capaz sea el cromosoma, más veces será seleccionado
para reproducirse.
v Cruce:
Se trata de un operador cuya labor es elegir un lugar, y cambiar las secuencias
antes y después de esa posición entre dos cromosomas, para crear nueva
descendencia (por ejemplo, las cadenas 10010011 y 11111010 pueden cruzarse
después del tercer lugar para producir la descendencia 10011010 y 11110011).
Imita la recombinación biológica entre dos organismos haploides.
v Mutación:
Este operador produce variaciones de modo aleatorio en un cromosoma (por
ejemplo, la cadena 00011100 puede mutar su segunda posición para dar lugar a la
cadena 01011100). La mutación puede darse en cada posición de un bit en una
cadena, con una probabilidad, normalmente muy pequeña (por ejemplo 0.001). Como
se ve, los Algoritmos Genéticos difieren de los métodos tradicionales de
búsqueda y optimización, en cuatro cuestiones esenciales:
ALGUNAS
APLICACIONES DE LOS ALGORITMOS GENÉTICOS
Aunque, como se ha
comentado, el Algoritmo que se utilizó en el apartado anterior es muy simple,
ha servido para que los estudios realizados en torno a él, se hayan aplicado a
diversos problemas y modelos en ingeniaría, y en la ciencia en general. Cabe destacar
entre ellos:
Ø Optimización:
Se trata de un campo especialmente abonado para el uso de los Algoritmos
Genéticos, por las características intrínsecas de estos problemas. No en vano
fueron la fuente de inspiración para los creadores estos algoritmos. Los Algoritmos
Genéticos se han utilizado en numerosas tareas de optimización, incluyendo la
optimización numérica, y los problemas de optimización combinatoria.
Ø Programación automática:
Los Algoritmos Genéticos se han empleado para desarrollar programas para tareas
específicas, y para diseñar otras estructuras computacionales tales como el
autómata celular, y las redes de clasificación.
Ø Aprendizaje máquina:
Los algoritmos genéticos se han utilizado también en muchas de estas
aplicaciones, tales como la predicción del tiempo o la estructura de una
proteína. Han servido asimismo para desarrollar determinados aspectos de sistemas
particulares de aprendizaje, como pueda ser el de los pesos en una red
Ø Economía:
En este caso, se ha hecho uso de estos Algoritmos para modelizar procesos de
innovación, el desarrollo estrategias de puja, y la aparición de mercados económicos.
Ø Sistemas inmunes:
A la hora de modelizar varios aspectos de los sistemas inmunes naturales,
incluyendo la mutación somática durante la vida de un individuo y el descubrimiento
de familias de genes múltiples en tiempo evolutivo, ha resultado útil el empleo
de esta técnica.
Ø Ecología:
En la modelización de fenómenos ecológicos tales como las carreras de armamento
biológico, la coevolución de parásito-huesped, la simbiosis, y el flujo de recursos.
Ø Genética de poblaciones:
En el estudio de preguntas del tipo “¿Bajo qué condiciones será viable
evolutivamente un gene para la recombinación?”
Ø Evolución y aprendizaje: Los Algoritmos Genéticos se han utilizado en el estudio de las
relaciones entre el aprendizaje individual y la evolución de la especie.
Ø Sistemas sociales:
En el estudio de aspectos evolutivos de los sistemas sociales, tales como la
evolución del comportamiento social en colonias de insectos, y la evolución de
la cooperación y la comunicación en sistemas multi-agentes. Aunque esta lista
no es, en modo alguno, exhaustiva, sí transmite la idea de la variedad de
aplicaciones que tienen los Algoritmos Genéticos. Gracias al éxito en estas y otras
áreas, los Algoritmos Genéticos han llegado a ser un campo puntero en la investigación
actual.
CONCLUSION.
Se
puede concluir que los algoritmo genéticos están basado en probabilidades,
entré mayor sea el número de generaciones el resultado será más óptimo en lo
general todo lo que es comparativo es genético.
BIBLIOGRAFÍA.
Russell, S. y Norvig, P. 2004. INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO.
PEARSON EDUCACION. 2 ed. Madrid.
Algoritmo Genético Consultado, 04 de Nov. 2015. Formato PDF.
Disponible http://www.uv.es/asepuma/X/J24C.pdf
Suscribirse a:
Entradas (Atom)