martes, 2 de junio de 2015
MÉTODOS HEURISTICOS
MÉTODOS HEURISTICOS
Métodos de escalada
Se llaman de escalada (o de ascensión a la colina) porque tratan de elegir en cada paso un estado cuyo valor heurístico sea mayor que el del estado activo en ese momento. Se dividen en dos grupos: Los métodos irrevocables, que no preven la vuelta a un lugar del espacio de estados si el camino resulta inadecuado. Los métodos tentativos en los que sí podemos volver hacia atrás si prevemos que el camino elegido no es el más adecuado.
La escalada simple.
Primero el mejor.
Este algoritmo, combina las ventajas de los algoritmos primero en profundidad y primero en amplitud. Sigue un sendero a la vez, pero puede cambiarse a otro sendero que parece más prometedor que el que está siguiendo.
En este sentido, puede considerarse que es un algoritmo que realiza su proceso de búsqueda en un grafo de tipo O, ya que todos sus ramales representan una alternativa de solución. Para su operación, el algoritmo necesita dos listas de nodos y una función heurística que estime los méritos de cada nodo que se genere:
1. ABIERTOS - Es una variable que contiene los nodos que han sido generados. La función heurística ha sido aplicada a ellos, pero todavía no han sido examinados, es decir no se han generado sus sucesores. ABIERTOS puede considerarse como una COLA DE PRIORIDADES en la que los elementos con mayor prioridad son los que tienen los valores más prometedores, dados por la función heurística.
2. CERRADOS - Es una variable que contiene los nodos que han sido examinados. Es necesario tener esta información, para que la búsqueda sea en un grafo y no en un árbol.
3. FUNCIÓN HEURÍSTICA - Permite que el algoritmo busque primero por senderos que son o parecen más prometedores.
Para muchas aplicaciones, es conveniente definir esta función f', como la suma de dos, que se las llamará g y h'. La función g es una medida del costo de llegar desde el nodo inicial al nodo actual. La función h' es una estimación del costo adicional para llegar desde el nodo actual al estado objetivo. Aquí es donde se explota el conocimiento que se dispone sobre el dominio del problema.
Es decir, la función combinada f' representa una estimación del costo de llegar desde el estado inicial hasta el estado objetivo, siguiendo el sendero que ha generado el nodo actual. Si el nodo actual ha generado más de un sendero, el algoritmo deberá dejar registrado sólo el mejor.
Búsqueda avara
Una estrategia simple consiste en reducir al mínimo el costo estimado para lograr una meta. Aunque es posible estimar el costo que implica llegar a una meta desde un estado determinado, no es posible hacerlo con precisión. La función que se utiliza para calcular tales estimados de costo se conoce como función heurística.
A la búsqueda que utiliza una función heurística para escoger qué nodo se expandirá es denominada “búsqueda avara”.
La búsqueda avara y la preferente por profundidad se asemejan por su indicación a utilizar una sola ruta hasta llegar a la meta, pero se atorarán cuando se topen con un callejón sin salida. Esta búsqueda no es óptima y es incompleta.
http://www.angelfire.com/ia3/aisite/bus_heuristica.htm
Métodos de escalada
Se llaman de escalada (o de ascensión a la colina) porque tratan de elegir en cada paso un estado cuyo valor heurístico sea mayor que el del estado activo en ese momento. Se dividen en dos grupos: Los métodos irrevocables, que no preven la vuelta a un lugar del espacio de estados si el camino resulta inadecuado. Los métodos tentativos en los que sí podemos volver hacia atrás si prevemos que el camino elegido no es el más adecuado.
En este método, en el momento es que se encuentra un estado E que es más favorable que el que se está expandiendo, dicho estado E es devuelto sin generar el resto de estados hijos.
La escalada por la máxima pendiente.
En este caso, se generan todos los hijos de un estado, se calculan sus valores heurísticos y se determina uno de los estados de mejor valor heurístico; se compara dicho valor con el de el estado expandido y si es mejor, se devuelve ese estado como expansión.
Este algoritmo, combina las ventajas de los algoritmos primero en profundidad y primero en amplitud. Sigue un sendero a la vez, pero puede cambiarse a otro sendero que parece más prometedor que el que está siguiendo.
En este sentido, puede considerarse que es un algoritmo que realiza su proceso de búsqueda en un grafo de tipo O, ya que todos sus ramales representan una alternativa de solución. Para su operación, el algoritmo necesita dos listas de nodos y una función heurística que estime los méritos de cada nodo que se genere:
1. ABIERTOS - Es una variable que contiene los nodos que han sido generados. La función heurística ha sido aplicada a ellos, pero todavía no han sido examinados, es decir no se han generado sus sucesores. ABIERTOS puede considerarse como una COLA DE PRIORIDADES en la que los elementos con mayor prioridad son los que tienen los valores más prometedores, dados por la función heurística.
2. CERRADOS - Es una variable que contiene los nodos que han sido examinados. Es necesario tener esta información, para que la búsqueda sea en un grafo y no en un árbol.
3. FUNCIÓN HEURÍSTICA - Permite que el algoritmo busque primero por senderos que son o parecen más prometedores.
Para muchas aplicaciones, es conveniente definir esta función f', como la suma de dos, que se las llamará g y h'. La función g es una medida del costo de llegar desde el nodo inicial al nodo actual. La función h' es una estimación del costo adicional para llegar desde el nodo actual al estado objetivo. Aquí es donde se explota el conocimiento que se dispone sobre el dominio del problema.
Es decir, la función combinada f' representa una estimación del costo de llegar desde el estado inicial hasta el estado objetivo, siguiendo el sendero que ha generado el nodo actual. Si el nodo actual ha generado más de un sendero, el algoritmo deberá dejar registrado sólo el mejor.
Búsqueda avara
Una estrategia simple consiste en reducir al mínimo el costo estimado para lograr una meta. Aunque es posible estimar el costo que implica llegar a una meta desde un estado determinado, no es posible hacerlo con precisión. La función que se utiliza para calcular tales estimados de costo se conoce como función heurística.
A la búsqueda que utiliza una función heurística para escoger qué nodo se expandirá es denominada “búsqueda avara”.
La búsqueda avara y la preferente por profundidad se asemejan por su indicación a utilizar una sola ruta hasta llegar a la meta, pero se atorarán cuando se topen con un callejón sin salida. Esta búsqueda no es óptima y es incompleta.
http://www.angelfire.com/ia3/aisite/bus_heuristica.htm
CARACTERÍSTICAS DE LA BÚSQUEDA HEURISTICA
Ø
Supone la existencia de una función de
evaluación que debe medir la distancia estimada al (a un) objetivo (h(n))
Ø
Esta función de evaluación se utiliza para guiar
el proceso haciendo que en cada momento se seleccione el estado o las
operaciones más prometedores
Ø
No siempre se garantiza encontrar una solución
(de existir ésta)
Ø
No siempre se garantiza encontrar la solución
más próxima (la que se encuentra a una distancia, número de operación menor)
Ø
Existen múltiples algoritmos
¿QUE ES LA BÚSQUEDA HEURISTICA?
Búsqueda Heurística
¿QUE ES LA BÚSQUEDA HEURISTICA?
Los métodos de búsqueda heurísticas (del griego heuriskein, que significa encontrar) están orientados a reducir la cantidad de búsqueda requerida para encontrar una solución. Cuando un problema es presentado como un árbol de búsqueda el enfoque heurístico intenta reducir el tamaño del árbol cortando nodos pocos prometedores. Estos métodos se llaman métodos fuertes porque ellos son más poderosos que los estudiados hasta aquí al incorporar conocimiento heurístico o heurística. Hay una contradicción entre generalidad y potencia en el sentido que los métodos débiles son esencialmente aplicables universalmente mientras que los fuertes son menos universales en su aplicabilidad y el conocimiento o heurística usada en un problema dado puede no ser totalmente aplicable o ser inaplicable en otro dominio o tarea.
Feigenbaum y Feldman definen la heurística como sigue: "Una heurística es una regla para engañar, simplificar o para cualquier otra clase de ardid el cual limita drásticamente la búsqueda de soluciones en grandes espacios de estados". En esencia una heurística es simplemente un conjunto de reglas que evalúan la posibilidad de que una búsqueda va en la dirección correcta. Generalmente los métodos de búsqueda heurísticas se basan en maximizar o minimizar algunos aspectos del problema.
Un ejemplo sencillo de heurística es el siguiente:
Un hombre se encuentra en una extensa llanura y tiene sed, en ese momento ha llegado a una pequeña elevación que es la única en esa región y se sube a ella. Desde la elevación el hombre observa el cuadro siguiente:
NORTE: vegetación verde y movimiento de animales
SUR: vegetación amarilla
ESTE: vegetación amarilla
OESTE: vegetación verde
Evidentemente la vegetación verde es un indicio de que hay humedad, luego es muy probable que exista agua en la superficie o subterránea. El movimiento de animales puede indicar que ellos se dirigen allí a beber, lo cual sugiere que el agua está en la superficie. Esta información le dice al hombre que debe dirigirse al norte, constituye una heurística.
La Heurística no garantiza que siempre se tome la dirección de la búsqueda correcta, por eso este enfoque no es óptimo sino suficientemente bueno. Frecuentemente son mejores los métodos heurísticos que los métodos de búsquedas a ciegas. Las desventajas y limitaciones principales de la heurística son:
La flexibilidad inherente de los métodos heurísticos pueden conducir a errores o a manipulaciones fraudulentas.
Ciertas heurísticas se pueden contradecir al aplicarse al mismo problema, lo cual genera confusión y hacen perder credibilidad a los métodos heurísticos.
Soluciones óptimas no son identificadas. Las mejoras locales determinadas por las heurísticas pueden cortar el camino a soluciones mejores por la falta de una perspectiva global. La brecha entre la solución óptima y una generada por heurística puede ser grande.
http://www.monografias.com/trabajos75/busqueda-heuristica/busqueda-heuristica.shtml#ixzz3bxSlAwbO
martes, 12 de mayo de 2015
jueves, 30 de abril de 2015
BÚSQUEDA POR AMPLITUD
Búsqueda en por amplitud o anchura es un algoritmo para recorrer o buscar elementos en un grafo (usado frecuentemente sobre árboles). Intuitivamente, se comienza en la raíz (eligiendo algún nodo como elemento raíz en el caso de un grafo) y se exploran todos los vecinos de este nodo. A continuación para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el árbol.
Formalmente, es un algoritmo de búsqueda sin información, que expande y examina todos los nodos de un árbol sistemáticamente para buscar una solución. El algoritmo no usa ninguna estrategia heurística.
domingo, 19 de abril de 2015
BÚSQUEDA CIEGA
¿Qué son las técnicas de
búsqueda?
Las técnicas de búsqueda son una serie de esquemas de
representación del conocimiento, que mediante diversos algoritmos nos permite
resolver ciertos problemas desde el punto de vista de la I.A.
BÚSQUEDA CIEGA
Sólo utiliza información acerca de si un estado es o no
objetivo para guiar su proceso de búsqueda.
Tipos de búsqueda ciega:
Búsqueda en amplitud:
- Procedimientos de búsqueda nivel a nivel.
- Para cada uno de los nodos de un nivel se aplican todos
los posibles operadores.
- No se expande ningún nodo de un nivel antes de haber
expandido todos los del nivel anterior.
Búsqueda en profundidad:
- La búsqueda se realiza por una sola rama del árbol hasta
encontrar una solución o hasta que se tome la decisión de terminar la búsqueda
por esa dirección.
Búsqueda en profundidad progresiva:
- Se define una profundidad predefinida.
- Se desarrolla el árbol realizando una búsqueda en profundidad hasta el límite definido en el punto anterior.
- Se desarrolla el árbol realizando una búsqueda en profundidad hasta el límite definido en el punto anterior.
- Si se encuentra la solución à FIN
- En caso contrario, se establece un nuevo límite y
volvemos al segundo paso.
Búsqueda bidireccional:
- Se llevan a la vez dos búsquedas: una descendente desde
el nodo inicial y otra ascendente desde el nodo meta.
lunes, 23 de marzo de 2015
¿QUE ES UN DIAGRAMA PAMA?
DIAGRAMA PAMA:Se refiere contar con una idea bastante precisa del ambiente, las percepciones y acciones, y por último de las metas. A este conjunto de datos se le conoce como PAMA (Percepción, Acción, Meta y Ambiente).
EJEMPLOS
Ejemplo 1: un conductor
de taxi implementando un diagrama PAMA
Tipo de agente: Conductor de taxi.
Percepciones: Cámaras, velocímetro, sistema GPS, sonar, micrófono.
Acciones: Manejo del volante, acelerar, frenar, hablar con el pasajero.
Metas: Un viaje seguro,
rápido, sin infracciones, cómodo, obtención de máxima ganancia.
Ambiente: Carretera, tráfico,
peatones, clientes.
Ejemplo
2: Un sistema de diagnóstico medico
Percepciones: Sintomas, evidencia y respuesta del paciente.
Acciones: Preguntas, pruebas, tratamiento.
Metas: Paciente
salufable, reducción al minimo de costos.
Ambiente: Paciente,
hospital.
Bibliografia
viernes, 20 de marzo de 2015
domingo, 8 de marzo de 2015
AMIENTES
Clasificación de los ambientes que puede enfrentar un
agente
Observable: Un ambiente es observable si los sensores del
agente detectan todos los aspectos relevantes para decidir qué acción debe
llevarse a cabo.
Parcialmente Observable: Un ambiente es parcialmente
observable debido a la imprecisión y el ruido en los sensores.
Determinista: Si el próximo estado del ambiente está
determinado por la acción que ejecuta el agente.
Estocástico: Cuando otros factores influyen en el próximo
estado del ambiente.
Episódico: La experiencia de un agente puede evaluarse en
rondas. Las acciones se evalúan en cada episodio o ronda.
Secuencial: Un ejemplo de ambiente secuencial en un agente
es un programa que juega ajedrez. Ya que
actúa conforme a una secuencia de movimientos determinada.
Estático: Si el ambiente puede cambiar mientras el agente se
encuentra deliberando se dice que es estático.
Dinámico: Si el ambiente no puede cambiar mientras el agente
se encuentra deliberando se dice que es dinámico.
Discreto: Es cuando hay un número limitado de posibles
estados del ambiente, distintos y claramente definidos.
Continuo: Es cuando hay un número ilimitado de posibles
estados del ambiente, distintos y claramente definidos.
Bibliografías:
AGENTES
AGENTES
Definición de agente:
Es una entidad capaz de percibir su entorno, procesar tales
percepciones y responder o actuar en su entorno de manera racional, es decir,
de manera correcta y tendiendo a maximizar un resultado esperado. Es capaz de
percibir su medio ambiente con la ayuda de sensores y actuar en ese medio
utilizando actuadores que son elementos que reaccionan a un estímulo realizando
una acción.
fuente:
viernes, 27 de febrero de 2015
DESARROLLO HISTÓRICO DE LA I.A
DESARROLLO HISTORICO DE LA INTELIGENCIA ARTIFICIAL
- Cerca de 300 a. C., Aristóteles fue el primero en describir de manera estructurada un conjunto de reglas, silogismos, que describen una parte del funcionamiento de la mente humana y que, al seguirlas paso a paso, producen conclusiones racionales a partir de premisas dadas.
- En 1315, Ramon Llull tuvo la idea de que el razonamiento podía ser efectuado de manera artificial.
- En 1847 George Boole estableció la lógica proposicional (booleana), mucho más completa que los silogismos de Aristóteles, pero aún algo poco potente.
- En 1879 Gottlob Frege extiende la lógica booleana y obtiene la Lógica de Primer Orden la cual cuenta con un mayor poder de expresión y es utilizada universalmente en la actualidad.
- En 1903 Lee De Forest inventa el triodo, también llamado bulbo o válvula de vacío.
- En 1937 Alan Turing publicó un artículo de bastante repercusión sobre los "Números Calculables", un artículo que estableció las bases teóricas para todas las ciencias de computación, y que puede considerarse el origen oficial de la informática teórica. En este artículo introdujo el concepto de Máquina de Turing, una entidad matemática abstracta que formalizó el concepto de algoritmo y resultó ser la precursora de las computadoras digitales.
- En 1940 Alan Turing y su equipo construyeron el primer computador electromecánico y en 1941 Konrad Zuse creó la primera computadora programable y el primer lenguaje de programación de alto nivel Plankalkül. Las siguientes máquinas más potentes, aunque con igual concepto, fueron la ABC y ENIAC.
- En 1943 Warren McCulloch y Walter Pitts presentaron su modelo de neuronas artificiales, el cual se considera el primer trabajo del campo de inteligencia artificial, aun cuando todavía no existía el término.
- En 1950 Turing consolidó el campo de la inteligencia artificial con su artículo Computing , en el que propuso una prueba concreta para determinar si una máquina era inteligente o no, su famosa Prueba de Turing por lo que se le considera el padre de la Inteligencia Artificial. Años después Turing se convirtió en el adalid que quienes defendían la posibilidad de emular el pensamiento humano a través de la computación y fue coautor del primer programa para jugar ajedrez.
- En 1951 William Shockley inventa el transistor de unión. El invento hizo posible una nueva generación de computadoras mucho más rápidas y pequeñas.
- En 1956 se dio el término "inteligencia artificial" en Dartmouth durante una conferencia convocada por McCarthy, a la cual asistieron, entre otros, Minsky, Newell y Simon. En esta conferencia se hicieron previsiones triunfalistas a diez años que jamás se cumplieron, lo que provocó el abandono casi total de las investigaciones durante quince años.
- En 1980 la historia se repitió con el desafío japonés de la quinta generación, que dio lugar al auge de los sistemas expertos pero que no alcanzó muchos de sus objetivos, por lo que este campo sufrió una nueva interrupción en los años noventa.
- En 1987 Martin Fischles y Oscar Firschein describieron los atributos de un agente inteligente. Al intentar describir con un mayor ámbito (no sólo la comunicación) los atributos de un agente inteligente, la IA se ha expandido a muchas áreas que han creado ramas de investigación enormes y diferenciadas.
- En los 90´s surgen los agentes inteligentes
- 2010 - En la actualidad se está tan lejos de cumplir la famosa prueba de Turing como cuando se formuló: Existirá Inteligencia Artificial cuando no seamos capaces de distinguir entre un ser humano y un programa de computadora en una conversación a ciegas. Como anécdota, muchos de los investigadores sobre IA sostienen que «la inteligencia es un programa capaz de ser ejecutado independientemente de la máquina que lo ejecute, computador o cerebro
- En 2010 el programa Suzette ganó el premio Loebner.
viernes, 20 de febrero de 2015
PRUEBA DE TURING
Test
de Turing o prueba de Turing
El test de Turing o prueba de Turing es una prueba
propuesta por Alan Turing para demostrar la existencia de inteligencia en una
máquina. Fue expuesto en 1950 en un artículo.
La prueba consiste en un desafío. Se supone un juez situado
en una habitación, una máquina y un ser humano en otra. El juez debe descubrir
cuál es el ser humano y cuál es la máquina, estándoles a los dos permitido
mentir o equivocarse al contestar por escrito las preguntas que el juez les
hiciera. La tesis de Turing supone que si ambos jugadores son suficientemente
hábiles, el juez no podrá distinguir quién es el ser humano y quién la máquina.
Su nombre es Eugene Goostman, y ha logrado convencer a un
tercio del jurado que le examinaba de que es un joven adolescente ucraniano de
13 años de edad.
Goostman no es humano, sino un programa informático. Uno
que ha conseguido engañar al 33 por ciento de los jueces que le sometieron a
prueba durante un test organizado por la Royal Society de Londres.
fuentes:
Suscribirse a:
Entradas (Atom)